گراف جهت دار و کاربردهای ان

گراف جهت دار و کاربردهای آن. گراف جهت دار D، یک سه تایی مرتب((Ψ(D و (A(D و (V(D)است که تشکیل شده از یک مجموعه ناتهی V(D) از راسها و یک مجموعه (A (D مجزای از (V(Dاز کمانها و یک تابع وقوع(Ψ(D که به هر کمان D یک زوج مرتب از راسهای D- که الزاماً متمایز نیستند- را نسبت می دهد. اگر a یک کمان وu,v دو راس باشند به طوری که(u,v) = Ψ(D)(a)، آنگاه میگوئیم که u,a را به v وصل کرده است؛ u، دم v,a سرa نامیده می شود.
. نظریه گراف و کاربردهای آن (نویسنده جی. ای. باندی و یو. اس. مورتی) مترجم:حمیدضرابی زاده
می توانیم به هر گراف جهتدار D، یک گراف G با همان مجموعه راس ها متناظر کنیم، به طوری که به ازای هر کمان از D، یک یال درG با همان دو سر وجود داشته باشد. این گراف، گراف زمینه D نامیده می شود. بالعکس، می توانیم از هر گراف دلخواه G، یک گراف جهت دار بدست آوریم بدین صورت که برای هر یال، یک ترتیب روی راسهای دو سر آن مشخص نماییم. گراف جهت دار حاصل را یک جهت دهی از G می نامیم.
گراف های جهت دار هم، مانند گراف ها، دارای یک نمایش تصویری ساده هستند. یک گراف جهت دار با نموداری از گراف زمینه آن، به علاوه پیکان هایی که سر کمان متناظر با هریال آن را مشخص می کنند، نمایش داده می شود:
هر مفهومی که برای گراف ها برقرار باشد به طور خودکار برای گراف های جهت دار نیز معتبر خواهد بود بنابراین گراف جهت دار شکل (۱) الف همبند است و هیچ دوری به طول ۳ ندارد، زیرا گراف زمینه آن شکل (۱) ب، دارای این ویژگی هاست اما مفاهیم بسیاری وجود دارند که شامل مفهوم جهت می باشند تنها برای گراف های جهت دار معتبرند.