گراف جهتدار
از ویکیپدیا، دانشنامهٔ آزاد
گراف جهتدار (به انگلیسی: 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 به b وجود داشته باشد، گراف را قویاً همبند مینامیم. [۲]
[ویرایش] جستارهای وابسته
[ویرایش] پانویس
[ویرایش] منبع
- گریمالدی، رالف پی.. ریاضیات گسسته و ترکیباتی. تهران: موسسه نشر علوم نوین، بهار ۱۳۸۱. ISBN 964-6133-41-X.
