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

تعریف گراف‌های جهت دار

گراف جهت دار 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 می‌نامیم.

گراف‌های جهت دار هم، مانند گراف‌ها، دارای یک نمایش تصویری ساده هستند. یک گراف جهت دار با نموداری از گراف زمینه آن، به علاوه پیکان‌هایی که سر کمان متناظر با هریال آن را مشخص می‌کنند، نمایش داده می‌شود:

هر مفهومی که برای گراف‌ها برقرار باشد به‌طور خودکار برای گراف‌های جهت دار نیز معتبر خواهد بود بنابراین گراف جهت دار شکل (۱) الف همبند است و هیچ دوری به طول ۳ ندارد، زیرا گراف زمینه آن شکل (۱) ب، دارای این ویژگی هاست اما مفاهیم بسیاری وجود دارند که شامل مفهوم جهت می‌باشند تنها برای گراف‌های جهت دار معتبرند.

یک گشت جهت دار در D عبارتست از یک دنباله متناهی ناتهی ak,uk....... ,u1 ,a1 u0)=W)، که جمله‌های آن یک در میان راس و کمان هستند و به ازای i=۱٬۲,….. ,k کمان ai دارای سر ui و دم ui - ۱ است.

همانند گشت‌ها در گراف‌ها، غالباً گشت جهت دار (u0,a1,u1,….. , ak , uk) را به‌طور ساده با دنباله راس‌های (u0,u1, …. , uk) نمایش می‌دهیم. گذرگاه جهت دار، گشت جهت داری است که گذرگاه باشد. مسیرهای جهت دار، دورهای جهت دار و تورهای جهت دار نیز به‌طور مشابه تعریف می‌شوند.

گراف جهت داری که دارای هیچ طوقه‌ای نیست و بین هر دو راس آن، هیچ دو کمان هم جهتی قرار ندارد یک گراف جهت دار قوی نامیده می‌شود.

big>مسیرهای جهت داردورهای جهت دارکاربردهای گراف جهت دار</big

۱-طراحی یک استوانه کامپیوتری کارآمد

۲-یک طرفه کردن جاده‌ها: یک طرفه کردن سیستم جاده‌ای به طوری که آرایش ترافیک تا حد ممکن حفظ شود.

۳-رتبه بندی شرکت کنندگان در یک تورنمنت

در یک تورنمنت تنیس، تعدادی بازیکن شرکت دارند که هر بازیکن با تمام بازیکنان دیگر مسابقه می‌دهد. اگر نتایج بازی‌ها را داشته باشیم، چگونه می‌توانیم بازیکنان را رتبه بندی کنیم؟ به‌طور مثال، تورنمنت شکل (۶) را در نظر بگیرید. این تورنمنت نتایج بازی‌های بین شش بازیکن را نشان می‌دهد بازیکن ۱، بازیکنان ۲، ۴، ۵، ۶ را شکست داده و مغلوب بازیکن ۳ شده‌است و الی آخر.

یک راه ممکن برای رتبه بندی بازیکنان این است که یک مسیر همیلتنی جهت دار در تورنمنت پیدا کنیم. (با توجه به نتیجه قضیه (۱) چنین مسیری حتماً وجود دارد.) سپس با توجه به موقعیت بازیکنان در این مسیر، آن‌ها را رتبه بندی می‌کنیم. به عنوان مثال، مسیر همیلتنی جهت دار (۶، ۵، ۴، ۲، ۱، ۳) مشخص می‌کند که بازیکن ۳، قهرمان و بازیکن ۱ نایب قهرمان است و به همین ترتیب. البته این روش رتبه بندی، در عمل دچار مشکل می‌شود، زیرا یک تورنمنت در حالت کلی تعداد زیادی مسیر همیلتنی جهت دار دارد. درمثال فوق، مسیرهای (۳، ۶، ۵، ۴، ۲، ۱)، (۵، ۲، ۳، ۶، ۴، ۱) و غیره نیز در تورنمنت وجود دارند.

روش دیگر آن است که امتیازها (تعداد بازیکن‌های برده توسط هر بازیکن) را محاسبه کرده، آن‌ها را با هم مقایسه کنیم. اگر این کار را برای مثال بالا انجام دهیم به بردار امتیاز زیر می‌رسیم. (۱، ۲، ۲، ۳، ۳، ۴)= S1

مشکلی که در اینجا پدیدار می‌شود آنست که این بردار امتیاز، بین بازیکن‌های ۲و ۳ تمایزی قائل نیست در حالی که بازیکن ۳ بازیکنانی با امتیازات بیشتر را شکست داده است. با توجه به این مطلب از بردار امتیاز مرتبه دوم زیر استفاده می‌کنیم. (۸،۵،۹،۳،۴،۳)= S2

که در این بردار، امتیاز مرتبه دوم هر بازیکن عبارت است از مجموع امتیازات بازیکنانی که از این بازیکن شکست خورده‌اند. در این حالت بازیکن ۳ رتبه اول را کسب می‌کند. با ادامه دادن این فرا یند، بردارهای دیگر به صورت زیر به دست می‌آیند.

(۱۵،۱۰،۱۶،۷،۱۲،۹)= S۳=(۳۸،۲۸،۳۲،۲۱،۲۵،۱۶) S4

منابع

• . نظریه گراف و کاربردهای آن (نویسنده جی. ای. باندی و یو. اس. مورتی) مترجم:حمیدضرابی زاده