دور در گراف: مسیر بسته با رأس‌های متمایز

بروزرسانی شده در: 12:42 1405/02/17 مشاهده: 103 دسته بندی: کپسول آموزشی

دور در گراف: مسیر بسته با رأس‌های متمایز

بررسی ساختار چرخه‌ها، انواع دورها و کاربرد آن‌ها در مسائل گسسته و شبکه

در نظریه گراف، «دور» به مسیر بسته‌ای گفته می‌شود که یال‌ها و رأس‌های آن به جز نقطه آغاز و پایان هم‌گی متمایز باشند. این ساختار پایه‌ای در حل مسائل مسیریابی، تشخیص شبکه‌های بدون دور (درخت)، مرتب‌سازی توپولوژیک و تحلیل شبکه‌های حمل‌ونقل کاربرد دارد. در این مقاله با زبانی ساده و مثال‌های ملموس، تعریف دقیق دور، انواع آن، روش تشخیص، فرمول‌های مرتبط و چالش‌های مفهومی را بررسی می‌کنیم.

۱. تعریف دور و تفاوت آن با مسیر ساده

در نظریه گراف¹، یک مسیر دنباله‌ای از رأس‌ها است که هر رأس مجاور با رأس بعدی توسط یک یال به هم وصل شده باشد. اگر اولین و آخرین رأس مسیر یکی باشد، آن مسیر را بسته می‌نامیم. اما برای اینکه این مسیر بسته به دور (Cycle) تبدیل شود، باید شرط زیر برقرار باشد:

$ C = v_1, v_2, ..., v_k, v_1 $ که در آن $ k \ge 3 $ و همه رأس‌ها به جز $ v_1 $ (که با خودش تکرار می‌شود) متمایز هستند.

به عبارت دیگر: دور یک مسیر بسته با حداقل 3 یال است که هیچ رأس یا یالی (به جز شروع/پایان) تکرار نمی‌شود. به همین دلیل به آن «مسیر بسته با رأس‌های متمایز» نیز می‌گویند.

مثال عملی: نقشه یک پارک را تصور کنید که در آن چهار نقطه A, B, C, D وجود دارد. اگر بتوانید از A به B، سپس به C، بعد به D و دوباره به A برگردید، یک دور به طول 4 تشکیل داده‌اید. اما اگر مسیر A-B-C-B-A را طی کنید، به دلیل تکرار رأس B، این یک دور محسوب نمی‌شود.

۲. ویژگی‌های اساسی دورها در گراف ساده

در یک گراف ساده² (بدون یال موازی و بدون حلقه)، ساده‌ترین نوع دور، مثلثی با سه رأس است. ویژگی‌های مهم دورها عبارتند از:

طول دور (Length): تعداد یال‌های تشکیل‌دهنده دور. کوچکترین طول دور ممکن در گراف ساده، 3 است.
دور همیلتونی³: دوری که از تمام رأس‌های گراف دقیقاً یک بار عبور کند.
دور اویلری⁴: دوری که از تمام یال‌های گراف دقیقاً یک بار عبور کند.
گراف بدون دور (آسیکلیک): گرافی که هیچ دوری نداشته باشد. درخت‌ها⁵ مهم‌ترین نمونه گراف‌های بدون دور هستند.

یک فرمول ساده: در یک گراف با n رأس و m یال، اگر m \ge n باشد، آن‌گاه گراف حداقل یک دور دارد. این شرط لازم است اما کافی نیست.

۳. انواع دورها از دیدگاه ساختار گراف

دورها را بر اساس نوع گراف و محدودیت‌های مسیری می‌توان به دسته‌های زیر تقسیم کرد:

نوع دور	توضیح کوتاه	مثال (تعداد رأس)
دور ساده	هیچ رأس یا یالی تکرار نمی‌شود	3,4,5,...
دور جهت‌دار	در گراف جهت‌دار، جهت یال‌ها یکسان و بسته باشد	v1→v2→v3→v1
دور القایی	زیرگرافی که خود یک دور است و یال دیگری بین رأس‌های آن وجود ندارد	چهارضلعی بدون قطر
دور مبنا (پایه)	دورهایی که از یک درخت پوشا با اضافه کردن یک یال ساخته می‌شوند	هر یال غیر درختی یک دور می‌سازد

۴. کاربرد عملی: تشخیص دور در شبکه انتقال داده

فرض کنید یک شبکه کامپیوتری متشکل از 6 گره (روتر) و 7 پیوند (لینک) داریم. اگر در این شبکه یک دور وجود داشته باشد، ممکن است بسته‌های داده به طور نامحدود در حلقه گردش کنند و شبکه را قفل کنند. برای جلوگیری از این پدیده، پروتکل‌های مسیریابی مانند درخت پوشای کمینه از گراف اصلی دورها را حذف می‌کنند. عملاً کافی است یکی از یال‌های دور را غیرفعال کنیم تا دیگر چرخه‌ای وجود نداشته باشد.

مثال عددی: فرض کنید گرافی با رأس‌های {A,B,C,D} و یال‌های AB, BC, CD, DA, AC داریم. این گراف شامل دو دور است: یکی A-B-C-D-A (طول 4) و دیگری A-B-C-A (طول 3). با حذف یال AC، فقط یک دور باقی می‌ماند. با حذف یک یال دیگر از آن دور، گراف به یک درخت (بدون دور) تبدیل می‌شود.

۵. الگوریتم تشخیص دور در گراف با جستجوی عمق اول

یکی از روش‌های پایه‌ای برای یافتن دور در گراف، استفاده از جستجوی عمق اول (DFS)⁶ است. ایده اصلی: حین پیمایش گراف، اگر به راسی برسیم که قبلاً ملاقات شده و پدر (والد) فعلی رأس نباشد، یک دور کشف کرده‌ایم. مراحل تشخیص دور در گراف بدون جهت به صورت زیر است:

گام 1 – همه رأس‌ها را با رنگ سفید (ملاقات نشده) علامت بزن.
گام 2 – از یک رأس شروع کن و به همسایه‌ها برو.
گام 3 – اگر همسایه‌ای را دیدی که قبلاً ملاقات شده و پدر رأس فعلی نیست، پس یک دور وجود دارد.
گام 4 – الگوریتم را تا ملاقات همه رأس‌ها ادامه بده.

$ \text{DFS}(v, parent) $ : اگر $ u $ همسایه $ v $ و قبلاً ملاقات شده و $ u \ne parent $، آن‌گاه یک دور پیدا شده است.

۶. چالش‌های مفهومی

پرسش ۱: آیا یک مسیر بسته با دو رأس می‌تواند دور باشد؟
خیر. در یک گراف ساده (بدون یال موازی و حلقه)، برای ایجاد یک مسیر بسته با دو رأس به حداقل دو یال موازی نیاز داریم که در گراف ساده مجاز نیست. در گراف‌های چندگانه (با یال موازی)، دو رأس با دو یال جداگانه می‌توانند یک دور به طول 2 بسازند، اما در گراف ساده، کوچکترین دور طول 3 دارد.

پرسش ۲: آیا یک گراف می‌تواند بدون دور باشد ولی همچنان بیش از یک مؤلفه همبندی داشته باشد؟
بله. برای مثال، دو درخت جداگانه که هیچ یالی بین آنها نیست، هر کدام بدون دور هستند. مجموع آنها یک گراف بدون دور (جنگل) تشکیل می‌دهد که چند مؤلفه دارد. شرط «بدون دور بودن» به معنای همبند بودن نیست.

پرسش ۳: چگونه می‌توان از روی تعداد یال‌ها و رأس‌ها وجود دور را حدس زد؟
در یک گراف همبند، اگر m \ge n باشد، گراف حداقل یک دور دارد. درخت‌ها دقیقاً m = n - 1 یال دارند و بدون دورند. بنابراین، هر یال اضافی به تعداد m - n + 1 دور مبنا ایجاد می‌کند.

۷. فرمول‌های کلیدی در محاسبه دور مبنا

برای یک گراف همبند با n رأس و m یال، تعداد دورهای مبنا (که فضای دور گراف را می‌سازند) برابر است با:

$ \text{عدد دوری (Cyclomatic Number)} = m - n + 1 $

این عدد نشان می‌دهد که چند یال باید از گراف حذف شود تا به یک درخت (گراف بدون دور) برسیم. در یک گراف با c مؤلفه همبندی، فرمول به صورت زیر اصلاح می‌شود:

$ \mu = m - n + c $

جمع‌بندی: دور در گراف، مسیری بسته با رأس‌های متمایز است که پایه بسیاری از تحلیل‌های ساختاری در نظریه گراف محسوب می‌شود. شناخت انواع دور (ساده، جهت‌دار، القایی) و روش‌های تشخیص آن (شمارش یال‌ها، الگوریتم DFS، عدد دوری) برای درک مفاهیمی مانند درخت، شبکه‌های بدون حلقه و مسائل بهینه‌سازی ضروری است. با تسلط بر این مفهوم، دانش آموزان دبیرستانی می‌توانند مسائل مسیریابی، مرتب‌سازی و طراحی شبکه را با دیدی عمیق‌تر تحلیل کنند.

پاورقی

¹ گراف (Graph): ساختاری متشکل از رأس‌ها (نقاط) و یال‌ها (اتصالات بین رأس‌ها).

² گراف ساده (Simple Graph): گرافی که در آن بین هر دو رأس حداکثر یک یال وجود دارد و هیچ حلقه‌ای (یالی که از یک رأس به خودش وصل شود) ندارد.

³ دور همیلتونی (Hamiltonian Cycle): دوری که از هر رأس گراف دقیقاً یک بار عبور می‌کند.

⁴ دور اویلری (Eulerian Circuit): دوری که از هر یال گراف دقیقاً یک بار عبور می‌کند.

⁵ درخت (Tree): گراف همبند بدون هیچ دوری.

⁶ جستجوی عمق اول (Depth-First Search - DFS): الگوریتم پیمایش گراف که تا جایی که ممکن است در عمق پیش می‌رود سپس به عقب برمی‌گردد.

جستجوهای پرتکرار

دور در گراف: مسیر بسته با رأس‌های متمایز