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

گراف جهت دار 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) نمایش می‌دهیم. گذرگاه جهت دار، گشت جهت داری است که گذرگاه باشد. مسیرهای جهت دار، دورهای جهت دار و تورهای جهت دار نیز به‌طور مشابه تعریف می‌شوند.

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

طول مسیرها و مسیرهای جهت دار در گراف‌های جهت دار، ارتباط مستقیمی با یکدیگر ندارند. این مطلب از گراف جهت دار شکل (۲) که مسیر جهت داری به طول بیشتر از یک ندارد، کاملاً مشهود است.

پرونده:Picture2.JPG

شگفت آور آن که، با نگاه به عدد رنگی یک گراف جهت دار می‌توان اطلاعاتی راجع به طول مسیرهای جهت دار آن به دست آورد. قضیه زیر که متعلق به روی (۱۹۶۷) و گالای (۱۹۶۸) می‌باشد به توضیح این مطلب می‌پردازد.

قضیه (۱) گراف جهت دار D شامل مسیر جهت داری به طول۱- x است.

اثبات فرض کنید َA یک مجموعه مینیمال از کمان‌های D است به طوری که D-A = َD شامل هیچ دور جهت داری نیست و فرض کنید که طول بلندترین مسیر جهت دار در َD برابر K باشد، رنگ‌های ۱، ۲،........ و۱+ k را به این ترتیب به راس‌های َD اختصاص می‌دهیم که راس v دارای رنگ i است، اگر طول بلندترین مسیر جهت دار در َD با ابتدای v، برابر۱- i باشد. مجموعه راس‌های به رنگ i را با Vi نمایش می‌دهیم، در ادامه نشان خواهیم داد که (V1,V2,….. , Vk+۱)، یک (k+۱) – رنگ آمیزی راسی مجاز از D است.

در ابتدا توجه به این مطلب ضروری است که ابتدا و انتهای هر مسیر جهت داردر َD، رنگ‌های متفاوتی دارند. زیرا فرض کنید که p یک (u,v) مسیر جهت دار با طول مثبت در َD و v€Vi می‌باشد. در این صورت یک مسیر جهت دار (v1,….. , v2 , vi)= Q در َD وجود دارد که در آنv = v1. چون َD شامل هیچ دور جهت داری نیست، PQ یک مسیر با ابتدای u و طول حداقل i می‌باشد. پس داریم: u€Vi.

اکنون می‌توانیم نشان دهیم که دو سر هر کمانی از D رنگ‌های متفاوتی دارند. فرض کنید (u,v)€A (َD). اگر (u,v)€A (َD)، در این صورت (u,v) یک مسیر جهت دار در َD است و در نتیجه v,u رنگ‌های متفاوتی دارند. در غیر این صورت داریم: u,v)€ Aَ). با توجه به مینیمال بودن َA u,v)+ َD)شامل یک دور جهت دار در C است. در این صورت (C-(u,v یک (u,v)- مسیر جهت دار در َD بوده و بنابراین در این حالت هم، v,u رنگ‌های متفاوتی دارند.

بنابراین (V1,V2,....... ,Vk+۱) یک رنگ آمیزی راسی مجاز از D می‌باشد. در نتیجه داریم: k+۱ ≥ x و بنابراین D دارای مسیر جهت داری به طول x-۱ ≤ k است.

نتیجه بهتری که می‌توان از قضیه (۱) حاصل نمود، این است که هر گراف G، دارای یک جهت دهی است که طول بزرگترین مسیر جهت دار آن x-۱ است. اگر یکx-رنگ آمیزی راسی مجاز ,….(V1, V2, Vx) از G داده شده باشد، Gرا بدین صورت جهت دهی می‌کنیم: u€Vi و v€Vj با شرط i ≤j، یال uv را به کمان (u,v) تبدیل می‌کنیم. واضح است که در این جهت دهی از G، هیچ مسیر جهت داری نمی‌تواند بیش از x راس داشته باشد زیرا هیچ دوراس از مسیر نمی‌توانند همرنگ باشند.

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

پرونده:Picture3.JPG

یک مسیر همیلتنی جهت دار از D، مسیر جهت داری است که تمام راس‌های D را شامل می‌گردد. بلافاصله از قضیه(۱) نتیجه می‌شود که هر تورنمنت دارای چنین مسیری است. این مطلب نخستین بار توسط ریدی (۱۹۳۴) اثبات شد.

قضیه (۲) گراف جهت دار بدون طوقه D، دارای مجموعه مستقلی مانند S است. به طوری که هر راس D که در S نیست، توسط مسیر جهت داری به طول حداکثر ۲، از یک را س S قابل دستیابی است.

اثبات از استقراء روی v استفاده می‌کنیم. درستی قضیه به ازای v=۱ بدیهی است. فرض کنید که قضیه به ازای تمام گراف‌های جهت دار با کمتر از vراس برقرار باشد و v را یک راس دلخواه D در نظر بگیرید. طبق فرض استقراء مجموعه مستقلی مانند َS در((D-({v} UN(v که در این رابطه Nمثبت است، وجود دارد به طوری که هر راس َD که در َS نیست، توسط مسیر جهت داری به طول حداکثر ۲، از یک راس َS قابل دستیابی است. اگر v یک همسایه خروجی از راسی مانند uدرَS باشد، آنگاه هر راس از(N(v با مسیر جهت داری به طول ۲ از u قابل دستیابی است. بنابراین در این حالت، َS = Sویژگی مورد نظر را داراست. از طرف دیگر، اگر v همسایه خروجی هیچ راسی از َS نباشد، در این صورت v به هیچ راسی از َS متصل نیست و مجموعه مستقل { S = َS U { v دارای ویژگی مورد نظر خواهد بود.

نتیجه: هر تورنمنت شامل راسی است که تمام راس‌های دیگر با مسیر جهت داری به طول حداکثر ۲ از آن قابل دستیابی می‌باشند. اثبات اگر D یک تورنمنت باشد، آنگاه α=۱.

با استفاده از نتیجه قضیه (۱) اگر فرض کنیم که تورنمنت قویا همبند است (توضیح: قویاً همبند یعنی دو راس از یک گراف طوری باشند که هریک از دیگری قابل دستیابی باشد.) می‌توانیم نتایج قویتری را بدست آوریم.

قضیه زیر متعلق به مون (۱۹۹۶) است. اگر S و T، زیر مجموعه‌هایی از V باشند، مجموعه کمان‌هایی که از D که دم آن‌ها درS و سر آن‌ها در T باشد، با (S,T) نمایش می‌دهیم.

قضیه (۳) هر راس از یک تورنمنت قویاٌ همبند D با ۳ ≤ v، درون یک –k دور جهت دار با شرطk ≤v و k ≤۳قرار دارد. اثبات: فرض کنید D یک تورنمنت قویاٌ همبند با شرط ۳ ≤ v و u یک راس دلخواه D باشد. قرار می‌دهیم(S=N(u که در آن Nدرجهت مثبت است و(T=N(uکه در آن Nدرجهت منفی است ابتدا نشان می‌دهیم که u درون یک ۳- دور جهت دار قرار دارد چون D قویاٌ همبند است، S,T هیچ‌کدام نمی‌توانند تهی باشند و به همین علت، (S,T) باید ناتهی باشد (شکل۴) بنابراین کمانی مانند (v,w) با شرطv€S وw€T وجود دارد و u در ۳- دور جهت دار (u,v,w,u) قرار می‌گیرد. پرونده:Picture4.JPG

اینک قضیه را با استقرار روی k اثبات می‌کنیم. فرض کنید uدرون دورهای جهت دار به هریک از طول‌های ۳ تا n قرار داشته باشد (n ≤v). در ادامه نشان خواهیم داد که u در یک (n+۱) – دور جهت دار نیز قرار دارد. فرض کنید(C=(v, v1............. ,vn یک n -دور جهت دار باشد که در آن v۰=vn=u اگر راسی مانند v در V(D)\V(C) وجود داشته باشد که سر یک کمان که دم آن روی C است و دم دیگری که سر آن روی C است باشد در این صورت راس‌های مجاور vi و vi+۱ روی C وجود دارند به طوری که (vi,v) و (v,vi+۱) کمان‌هایی از D هستند. در این حالت، u درون (n+۱)- دور جهت دار (v0,v1,……, vi, v, vi+۱,….vn) قرار دارد.

در غیر این صورت، مجموعه راس‌هایی از (V(D)\V(Cکه سر کمان‌های متصل به C هستند را با S و مجموعه راس‌هایی از(V(D)\V(C که دم کمان‌های متصل به Cهستند را با T نمایش می‌دهیم. شکل (۵)

پرونده:Picture5.JPG

همانند حالت قبل، با توجه به اینکه D قویا همبند است، S,T و (S,T) همگی ناتهی هستندو کمانی مانند (v,w) در D با شرط S v وT w وجود دارد. بنابراین u درون (n+۱)- دور جهت دار (v0,v,w,v2,……,vn) قرار دارد. یک دور همیلتنی جهت دار از D، دور جهت داری است که تمام راس‌های D را شامل می‌شود با توجه به قضیه (۳) هر تورنمنت قویا همبند، شامل چنین دوری است. این مطلب را نخستین بار، کمیون ۱ اثبات کرد.

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

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

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

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

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

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

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

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

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

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