موضوع مقاله: گراف جهت‌دار و کاربردهای آن | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # گراف جهت‌دار و کاربردهای آن | مقدمه: تعریف گراف‌های جهت دار گراف جهت دار D، یک سه تایی مرتب Ψ(D و (A(D و (V(D)است که تشکیل شده از یک مجموعه ناتهی V(D) از راسها و یک مجموعه (A (D مجزای از (V(Dاز کمانها و یک تابع وقوع(Ψ(D که به هر کمان D یک زوج مرتب از راسهای D- که الزاماً متمایز نیستند- را نسبت می‌دهد. | ## بخش 1: گراف جهت‌دار و کاربردهای آن | می‌توانیم به هر گراف جهتدار D، یک گراف G با همان مجموعه راس‌ها متناظر کنیم، به طوری که به ازای هر کمان از D، یک یال درG با همان دو سر وجود داشته باشد. بالعکس، می‌توانیم از هر گراف دلخواه G، یک گراف جهت دار بدست آوریم بدین صورت که برای هر یال، یک ترتیب روی راسهای دو سر آن مشخص نماییم. مسیرهای جهت دار، دورهای جهت دار و تورهای جهت دار نیز به‌طور مشابه تعریف می‌شوند. گراف جهت داری که دارای هیچ طوقه‌ای نیست و بین هر دو راس آن، هیچ دو کمان هم جهتی قرار ندارد یک گراف جهت دار قوی نامیده می‌شود. big>مسیرهای جهت دار</big طول مسیرها و مسیرهای جهت دار در گراف‌های جهت دار، ارتباط مستقیمی با یکدیگر ندارند. این مطلب از گراف جهت دار شکل (۲) که مسیر جهت داری به طول بیشتر از یک ندارد، کاملاً مشهود است. قضیه زیر که متعلق به روی (۱۹۶۷) و گالای (۱۹۶۸) می‌باشد به توضیح این مطلب می‌پردازد. اثبات فرض کنید َA یک مجموعه مینیمال از کمان‌های D است به طوری که D-A = َD شامل هیچ دور جهت داری نیست و فرض کنید که طول بلندترین مسیر جهت دار در َD برابر K باشد، رنگ‌های ۱، ۲،... و۱+ k را به این ترتیب به راس‌های َD اختصاص می‌دهیم که راس v دارای رنگ i است، اگر طول بلندترین مسیر جهت دار در َD با ابتدای v، برابر۱- i باشد. مجموعه راس‌های به رنگ i را با Vi نمایش می‌دهیم، در ادامه نشان خواهیم داد که (V1,V2,….. در ابتدا توجه به این مطلب ضروری است که ابتدا و انتهای هر مسیر جهت داردر َD، رنگ‌های متفاوتی دارند. چون َD شامل هیچ دور جهت داری نیست، PQ یک مسیر با ابتدای u و طول حداقل i می‌باشد. در این صورت (C-(u,v یک (u,v)- مسیر جهت دار در َD بوده و بنابراین در این حالت هم، v,u رنگ‌های متفاوتی دارند. | ## بخش 2: گراف جهت‌دار و کاربردهای آن | نتیجه بهتری که می‌توان از قضیه (۱) حاصل نمود، این است که هر گراف G، دارای یک جهت دهی است که طول بزرگترین مسیر جهت دار آن x-۱ است. واضح است که در این جهت دهی از G، هیچ مسیر جهت داری نمی‌تواند بیش از x راس داشته باشد زیرا هیچ دوراس از مسیر نمی‌توانند همرنگ باشند. هریک از این تورنمنت‌ها را می‌توان به عنوان نتایج بازی‌های یک مسابقه دوره‌ای بین چهار بازیکن در نظر گرفت. به‌طور مثال تورنمنت اول در شکل (۳) نشان می‌دهد که یک بازیکن، هر سه بازی خود را برنده شده‌است و دیگر بازیکنان، هر کدام، فقط یک برد دارند. به طوری که هر راس D که در S نیست، توسط مسیر جهت داری به طول حداکثر ۲، از یک را س S قابل دستیابی است. فرض کنید که قضیه به ازای تمام گراف‌های جهت دار با کمتر از vراس برقرار باشد و v را یک راس دلخواه D در نظر بگیرید. طبق فرض استقراء مجموعه مستقلی مانند َS در D- v} UN(v که در این رابطه Nمثبت است، وجود دارد به طوری که هر راس َD که در َS نیست، توسط مسیر جهت داری به طول حداکثر ۲، از یک راس َS قابل دستیابی است. اگر v یک همسایه خروجی از راسی مانند uدرَS باشد، آنگاه هر راس از(N(v با مسیر جهت داری به طول ۲ از u قابل دستیابی است. از طرف دیگر، اگر v همسایه خروجی هیچ راسی از َS نباشد، در این صورت v به هیچ راسی از َS متصل نیست و مجموعه مستقل { S = َS U { v دارای ویژگی مورد نظر خواهد بود. نتیجه: هر تورنمنت شامل راسی است که تمام راس‌های دیگر با مسیر جهت داری به طول حداکثر ۲ از آن قابل دستیابی می‌باشند. big>دورهای جهت دار</big با استفاده از نتیجه قضیه (۱) اگر فرض کنیم که تورنمنت قویا همبند است (توضیح: قویاً همبند یعنی دو راس از یک گراف طوری باشند که هریک از دیگری قابل دستیابی باشد.) می‌توانیم نتایج قویتری را بدست آوریم. اگر S و T، زیر مجموعه‌هایی از V باشند، مجموعه کمان‌هایی که از D که دم آن‌ها درS و سر آن‌ها در T باشد، با (S,T) نمایش می‌دهیم. قضیه (۳) هر راس از یک تورنمنت قویاٌ همبند D با ۳ ≤ v، درون یک –k دور جهت دار با شرطk ≤v و k ≤۳قرار دارد. | ## بخش 3: گراف جهت‌دار و کاربردهای آن | قرار می‌دهیم(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) قرار می‌گیرد. در غیر این صورت، مجموعه راس‌هایی از (V(D)\V(Cکه سر کمان‌های متصل به C هستند را با S و مجموعه راس‌هایی از(V(D)\V(C که دم کمان‌های متصل به Cهستند را با T نمایش می‌دهیم. یک دور همیلتنی جهت دار از D، دور جهت داری است که تمام راس‌های D را شامل می‌شود با توجه به قضیه (۳) هر تورنمنت قویا همبند، شامل چنین دوری است. big>کاربردهای گراف جهت دار</big ۱-طراحی یک استوانه کامپیوتری کارآمد ۲-یک طرفه کردن جاده‌ها: یک طرفه کردن سیستم جاده‌ای به طوری که آرایش ترافیک تا حد ممکن حفظ شود. ۳-رتبه بندی شرکت کنندگان در یک تورنمنت در یک تورنمنت تنیس، تعدادی بازیکن شرکت دارند که هر بازیکن با تمام بازیکنان دیگر مسابقه می‌دهد. این تورنمنت نتایج بازی‌های بین شش بازیکن را نشان می‌دهد بازیکن ۱، بازیکنان ۲، ۴، ۵، ۶ را شکست داده و مغلوب بازیکن ۳ شده‌است و الی آخر. (با توجه به نتیجه قضیه (۱) چنین مسیری حتماً وجود دارد.) سپس با توجه به موقعیت بازیکنان در این مسیر، آن‌ها را رتبه بندی می‌کنیم. به عنوان مثال، مسیر همیلتنی جهت دار (۶، ۵، ۴، ۲، ۱، ۳) مشخص می‌کند که بازیکن ۳، قهرمان و بازیکن ۱ نایب قهرمان است و به همین ترتیب. البته این روش رتبه بندی، در عمل دچار مشکل می‌شود، زیرا یک تورنمنت در حالت کلی تعداد زیادی مسیر همیلتنی جهت دار دارد. درمثال فوق، مسیرهای (۳، ۶، ۵، ۴، ۲، ۱)، (۵، ۲، ۳، ۶، ۴، ۱) و غیره نیز در تورنمنت وجود دارند. روش دیگر آن است که امتیازها (تعداد بازیکن‌های برده توسط هر بازیکن) را محاسبه کرده، آن‌ها را با هم مقایسه کنیم. (۱، ۲، ۲، ۳، ۳، ۴)= S1 مشکلی که در اینجا پدیدار می‌شود آنست که این بردار امتیاز، بین بازیکن‌های ۲و ۳ تمایزی قائل نیست در حالی که بازیکن ۳ بازیکنانی با امتیازات بیشتر را شکست داده است. | ## جمع‌بندی | (۸،۵،۹،۳،۴،۳)= S2 که در این بردار، امتیاز مرتبه دوم هر بازیکن عبارت است از مجموع امتیازات بازیکنانی که از این بازیکن شکست خورده‌اند.