طول دور در گراف: تعداد یالهای دور
تعریف گراف و مفهوم دور
گراف1 مجموعهای از رأسها (نقاط) و یالها (خطهایی که رأسها را به هم وصل میکنند) است. یک دور در گراف، مسیری بسته است که در آن هیچ رأس یا یالی بیش از یک بار تکرار نشود، به جز رأس شروع که همان رأس پایان است. به عبارت دقیقتر، دور یک مسیر بسته2 با حداقل 3 رأس است (در گرافهای ساده).
مثال ساده: یک مثلث با سه رأس A، B و C و سه یال AB، BC و CA یک دور به طول 3 (سه یال) دارد. اگر یک یال دیگر مانند AD اضافه کنیم، باز هم دور اصلی مثلث باقی میماند.
روش محاسبه طول دور در گرافهای مختلف
برای محاسبه طول یک دور، کافی است یالهای آن را بشماریم. اما گاهی دورها در هم پیچیدهاند. مثلاً در گراف زیر: رأسهای 1,2,3,4 به صورت چهارضلعی با یالهای (1-2)، (2-3)، (3-4)، (4-1) متصل شدهاند. طول دور مشخص برابر 4 است. حال اگر یک یال قطری (2-4) اضافه کنیم، دو دور کوچکتر نیز ایجاد میشود: دور (2،3،4) به طول 3 و دور (1،2،4) به طول 3.
در مسائل بهینهسازی، معمولاً کوتاهترین دور یا طولانیترین دور گراف مورد نظر است. کوتاهترین دور را دور محیطی3 مینامند.
مثال عملی: فرض کنید نقشه یک پارک تفریحی با چهار ایستگاه (A، B، C، D) به صورت مربع طراحی شده است. هر یال یک مسیر پیادهروی با طول مشخص دارد (مثلاً AB=100 متر، BC=120 متر، CD=100 متر، DA=120 متر). دور ABCD یک دور به طول 4 یال است، اما مجموع طول فیزیکی برابر 100+120+100+120=440 متر میشود. در نظریه گراف فقط تعداد یالها اهمیت دارد، مگر اینکه گراف وزنی باشد.
انواع دورها و تفاوت با مسیر بسته
همه مسیرهای بسته دور محسوب نمیشوند. یک مسیر بسته میتواند یک رأس را دوبار تکرار کند (مثل مسیر A-B-C-B-A) که این یک دور نیست، چون رأس B تکرار شده است. در مقابل، دور باید ساده باشد: هیچ رأس (به جز شروع/پایان) بیش از یک بار دیده نشود.
| نوع دور | شرط | مثال طول |
|---|---|---|
| دور ساده | هیچ رأس (به جز اول و آخر) تکرار نشود | 3,4,5,… |
| دور هامیلتونی4 | از همه رأسهای گراف دقیقاً یک بار عبور کند | تعداد رأسهای گراف |
| دور اویلری5 | از همه یالهای گراف دقیقاً یک بار عبور کند (نه الزاماً ساده) | تعداد یالهای گراف |
کاربرد عملی: کوتاهترین دور در شبکه حملونقل
فرض کنید شهر شما دارای 5 میدان است که با خیابانهای یکطرفه به هم متصل شدهاند. شهرداری میخواهد یک مسیر گشتزنی شبانه طراحی کند که از هر میدان حداکثر یک بار عبور کند و در نهایت به نقطه شروع بازگردد (دور هامیلتونی). اگر گراف دارای چند دور هامیلتونی با طولهای متفاوت باشد، کوتاهترین دور (از نظر تعداد خیابانها) به صرفهترین مسیر است.
مثال عددی: گرافی با رأسهای {A,B,C,D} و یالهای AB، BC، CD، DA، AC. در اینجا دو دور هامیلتونی وجود دارد: A-B-C-D-A با طول 4 و A-C-B-D-A (با استفاده از یال AC و سپس C-B، B-D؟ توجه: باید بررسی کنیم که B-D وجود ندارد. پس در این گراف شاید فقط یک دور هامیلتونی باشد. این مثال نشان میدهد که تشخیص دور هامیلتونی نیاز به بررسی همه یالها دارد.)
برای محاسبه سیستماتیک طول دورها، از ماتریس مجاورت6 استفاده میشود. در توان دوم ماتریس مجاورت، درایههای قطر اصلی نشاندهنده تعداد مسیرهای بسته به طول 2 هستند (که معمولاً دور محسوب نمیشوند). برای یافتن دورهای واقعی باید توانهای بالاتر ماتریس را بررسی کرد.
چالشهای مفهومی
خیر. در نظریه گراف استاندارد، یک دور باید حداقل سه رأس متمایز داشته باشد (در گراف ساده). مسیر A-B-A فقط دو رأس دارد و دو بار از یال AB عبور میکند که تکرار یال را به دنبال دارد. به چنین مسیری اصطلاحاً «مسیر بسته با طول 2» میگویند و آن را دور نمینامند.
برای گرافهای بزرگ، الگوریتمهایی مانند جستجوی عمق اول (DFS)7 با تکنیک رنگگذاری رأسها به کار میروند. هر زمان که به رأسی برسیم که قبلاً در مسیر فعلی دیده شده و فاصله آن با رأس جاری بیش از یک باشد، یک دور کشف میشود. طول آن دور برابر اختلاف زمانهای ورود به آن رأسها است.
در گرافهای بدون حلقه (loop)، دور به طول صفر (همان رأس بدون حرکت) مجاز نیست. دور به طول یک فقط در صورت وجود حلقه (یالی که یک رأس را به خودش وصل کند) ممکن است، اما در گرافهای ساده حلقه نداریم. بنابراین طول دور معمولاً از 3 شروع میشود.
فرمولهای مرتبط با طول دور
در یک گراف همبند با n رأس و m یال، تعداد دورهای بنیادی برابر m-n+1 است (که به آن عدد پیوندی8 میگویند). اما طول هر دور به ساختار گراف بستگی دارد.
مثال: گراف با n=4 و m=4 که به شکل مربع کامل (چهارضلعی) باشد: $m-n+c=4-4+1=1$. یعنی دقیقاً یک دور بنیادی به طول 4 دارد.
پاورقی
1 گراف (Graph): ساختاری متشکل از مجموعه رأسها و مجموعه یالها که رابطه دودویی بین رأسها را نمایش میدهد.
2 مسیر بسته (Closed Walk): توالی از رأسها که رأس اول و آخر یکسان است و یالها مجاز به تکرار هستند.
3 دور محیطی (Girth): کوتاهترین طول دور در یک گراف. اگر گراف بدون دور باشد، محیط آن بینهایت تعریف میشود.
4 دور هامیلتونی (Hamiltonian Cycle): دوری که از هر رأس گراف دقیقاً یک بار عبور کند.
5 دور اویلری (Eulerian Circuit): مسیر بستهای که از هر یال گراف دقیقاً یک بار عبور کند.
6 ماتریس مجاورت (Adjacency Matrix): ماتریس مربعی که سطرها و ستونها متناظر با رأسها هستند و درایه (i,j) برابر یک اگر یال بین i و j وجود داشته باشد، در غیر این صورت صفر است.
7 جستجوی عمق اول (DFS): الگوریتم پیمایش گراف که تا جایی که ممکن است در عمق پیش میرود و سپس عقب برمیگردد.
8 عدد پیوندی (Cyclomatic Number): تعداد مستقلترین دورهای بنیادی در گراف که برابر $m - n + c$ است.
