گراف جهتدار: تفاوت میان نسخهها
جز r2.7.2) (ربات: افزودن et:Suunatud graaf |
جز r2.7.3) (ربات: افزودن ko:유향 그래프 |
||
خط ۴۴: | خط ۴۴: | ||
[[it:Digrafo (matematica)]] |
[[it:Digrafo (matematica)]] |
||
[[kk:Бағдарланған граф]] |
[[kk:Бағдарланған граф]] |
||
[[ko:유향 그래프]] |
|||
[[pl:Graf skierowany]] |
[[pl:Graf skierowany]] |
||
[[pt:Grafo orientado]] |
[[pt:Grafo orientado]] |
نسخهٔ ۲۹ ژانویهٔ ۲۰۱۳، ساعت ۰۰:۴۵
گراف جهتدار (به انگلیسی: Directed Graph) نوع خاصی از انواع گرافها است.
را یک مجموعه ناتهی متناهی از رأسهای یک گراف و را مجموعه یالهای آن تعریف میکنیم. همچنین میدانیم E⊆V×V. جفت (V٫E) را یک گراف جهتدار گوییم، اگر جهت یالهای آن مهم باشد.[۱] به عنوان مثال در یک لیگ ورزشی، اگر هر تیم را با یک رأس نشان دهیم و یالهای آن را از تیم برنده به تیم بازنده وصل کنیم، گراف ما یک گراف جهتدار خواهد بود که نشاندهنده نتایج بازیهاست.
طریقه نشان دادن جهت یال
در نمودار یک گراف، جهت یک یال با گذاشتن سهم جهت دار بر روی آن مشخص میشود (شکل ۱).
اگر بخواهیم جهت یالهای گراف را از روی مجموعه یالهای آن بیابیم، کافیست به ترتیب نوشته شدن عضوها دقت کنیم. مثلاً در مجموعه نشان داده شده در شکل ۲ داریم:
برای هر یال مانند میگوییم این یال با رأسهای ۲ و ۱ تلاقی دارد. ۱ را مجاور به ۲ و ۲ را مجاور از ۱ مینامیم. علاوه بر این رأس ۱ را مبدأ یا منبع یال و رأس ۲ را پایان یا رأس پایانی میخوانیم.
در صورتی که ذکر نشود گرافی جهتدار است یا بدون جهت، آن را بدون جهت در نظر میگیریم.
در یک گراف جهت دار، اگر به ازای هر دو رأس و () یک مسیر جهتدار از به وجود داشته باشد، گراف را قویاً همبند مینامیم.[۲]
جستارهای وابسته
پانویس
منبع
- گریمالدی، رالف پی.. ریاضیات گسسته و ترکیباتی. تهران: موسسه نشر علوم نوین، بهار ۱۳۸۱. ISBN 964-6133-41-X.