گراف جهت‌دار

گراف جهتدار (به انگلیسی: Directed Graph)‏ نوع خاصی از انواع گراف‌ها است.

$V$ را یک مجموعه ناتهی متناهی از رأس‌های یک گراف و $E$ را مجموعه یال‌های آن تعریف می‌کنیم. هم‌چنین می‌دانیم E⊆V×V. جفت (V٫E) را یک گراف جهتدار گوییم، اگر جهت یال‌های آن مهم باشد. به عنوان مثال در یک لیگ ورزشی، اگر هر تیم را با یک رأس نشان دهیم و یال‌های آن را از تیم برنده به تیم بازنده وصل کنیم، گراف ما یک گراف جهت‌دار خواهد بود که نشان‌دهنده نتایج بازی‌هاست.

شکل ۱

طریقه نشان دادن جهت یال

شکل ۲

در نمودار یک گراف، جهت یک یال با گذاشتن سهم جهت دار بر روی آن مشخص می‌شود (شکل ۱).

اگر بخواهیم جهت یال‌های گراف را از روی مجموعه یال‌های آن بیابیم، کافیست به ترتیب نوشته شدن عضوها دقت کنیم. مثلاً در مجموعه نشان داده شده در شکل ۲ داریم:

‎$E=\{(1,2),(2,5),(2,3),(3,1),(5,5),(4,5)\}$‎

برای هر یال مانند $(1,2)$ می‌گوییم این یال با رأس‌های ۲ و ۱ تلاقی دارد. ۱ را مجاور به ۲ و ۲ را مجاور از ۱ می‌نامیم. علاوه بر این رأس ۱ را مبدأ یا منبع یال $(1,2)$ و رأس ۲ را پایان یا رأس پایانی می‌خوانیم.
در صورتی که ذکر نشود گرافی جهتدار است یا بدون جهت، آن را بدون جهت در نظر می‌گیریم.

در یک گراف جهت دار، اگر به ازای هر دو رأس $a$ و $b$ ($a\ne \;b$) یک مسیر جهتدار از $a$ به $b$ وجود داشته باشد، گراف را قویاً همبند می‌نامیم.

جستارهای وابسته

• گراف
• نظریه گراف
• ریاضیات گسسته

منبع

• گریمالدی، رالف پی.. ریاضیات گسسته و ترکیباتی. تهران: موسسه نشر علوم نوین، بهار ۱۳۸۱. ISBN 964-6133-41-X.