گراف Cₙ: گرافی که فقط از یک دور n رأسی تشکیل شده است.

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

گراف Cₙ: گرافی که فقط از یک دور n رأسی تشکیل شده است

بررسی ساختار، ویژگی‌های ریاضی، مثال‌های عینی و چالش‌های گراف‌های دوری برای دانش‌آموزان دبیرستان

در این مقاله با گراف $C_n$ آشنا می‌شوید؛ گرافی ساده و متشکل از یک دور با $n$ رأس و $n$ یال. ویژگی‌هایی مانند منتظم بودن، تعداد یال‌ها، حالت‌های خاص برای $n$های کوچک، کاربرد در مسائل بهینه‌سازی و چالش‌های درک تفاوت آن با مسیر و گراف کامل بررسی می‌شود. مثال‌های علمی و جداول مقایسه، درک این گراف بنیادین را برای دانش‌آموزان دبیرستانی آسان می‌کند.

تعریف دقیق و ساختار اولیه گراف $C_n$

گراف $C_n$ (که گاهی «گراف دور» یا «چرخهٔ ساده»¹ نامیده می‌شود) یک گراف بدون جهت، ساده و همبند است که از $n$ رأس و $n$ یال تشکیل شده و دقیقاً یک دور (حلقهٔ بسته) با طول $n$ دارد. به زبان ساده: اگر $n$ نقطه را روی یک دایره بگذارید و هر نقطه را فقط به دو نقطهٔ مجاورش (یکی در جهت عقربه‌های ساعت و یکی خلاف آن) وصل کنید، یک گراف $C_n$ خواهید داشت. هیچ یال اضافه‌ای بین رأس‌های غیرمجاور وجود ندارد.

مثال عددی: برای $n = 5$، گراف $C_5$ یک پنج‌ضلعی منتظم است. رأس‌ها را به ترتیب $v_1, v_2, v_3, v_4, v_5$ نامگذاری می‌کنیم. یال‌ها عبارتند از: $(v_1,v_2), (v_2,v_3), (v_3,v_4), (v_4,v_5), (v_5,v_1)$. همان‌طور که می‌بینید، هر رأس دقیقاً به دو رأس دیگر متصل است.

فرمول شمارش یال‌ها: در گراف $C_n$ تعداد یال‌ها برابر است با $|E| = n$. همچنین هر رأس دارای درجه²$2$ است (به جز وقتی $n \le 2$ که گراف تعریف خاصی دارد). بنابراین $C_n$ یک گراف $2$-منتظم است.

ویژگی‌های مهم و حالت‌های خاص برای $n$های کوچک

گراف $C_n$ بسته به مقدار $n$ رفتار متفاوتی از خود نشان می‌دهد. برخی از مهم‌ترین ویژگی‌های آن عبارتند از:

همبندی: $C_n$ برای $n \ge 3$ یک گراف همبند است (از هر رأس به هر رأس دیگر مسیر وجود دارد).
دور بودن: طول کوچک‌ترین دور (کمتر) برابر $n$ است.
رنگ‌آمیزی: عدد رنگی³ گراف $C_n$ برای $n$ زوج برابر $2$ و برای $n$ فرد برابر $3$ است.
گراف مکمل⁴: مکمل $C_n$ برای $n \ge 5$ معمولاً گرافی متراکم با یال‌های بسیار است.

مقدار $n$	نام گراف	تعداد یال‌ها	عدد رنگی	ویژگی خاص
$n=1$	حلقهٔ خودی (حلقه⁵)	$1$	$1$	نیاز به یال جایز (حلقه)
$n=2$	یال دوگانه	$2$	$2$	دور حقیقی ندارد (ساده نیست)
$n=3$	مثلث (گراف کامل $K_3$)	$3$	$3$	تنها گراف دوری که کامل است
$n=4$	چهارضلعی (چرخهٔ زوج)	$4$	$2$	دو رنگ قابل رنگ‌آمیزی
$n=5$	پنج‌ضلعی (چرخهٔ فرد)	$5$	$3$	نیاز به سه رنگ

مثال عینی: مسیریابی در یک شبکهٔ دوری

فرض کنید $6$ روستا در یک مسیر دایره‌ای (حلقوی) قرار گرفته‌اند و هر روستا فقط با دو روستای مجاور خود جاده دارد. این شبکه دقیقاً یک گراف $C_6$ است. اگر یک نامه‌رسان بخواهد از روستای شماره $1$ به روستای شماره $4$ نامه بفرستد، دو مسیر مجزا وجود دارد: مسیر کوتاه از طریق $1 \to 2 \to 3 \to 4$ با طول $3$ و مسیر طولانی‌تر از طرف دیگر $1 \to 6 \to 5 \to 4$ با طول $3$ (در $C_6$ هر دو مسیر به یک اندازه هستند). اگر یک یال (جاده) قطع شود، شبکه هنوز همبند می‌ماند (به یک مسیر ساده تبدیل می‌شود) اما اگر دو یال قطع شود ممکن است شبکه از هم بپاشد. این مثال نشان می‌دهد که گراف‌های دوری در شبکه‌های مقاوم به خطا (Fault-Tolerant) کاربرد دارند.

نکته محاسباتی: فاصلهٔ بین دو رأس در $C_n$ با فرمول $d(v_i, v_j) = \min(|i-j|, n - |i-j|)$ محاسبه می‌شود. این فرمول برای مسائل مسیریابی بسیار مفید است.

کاربردهای عملی گراف $C_n$ در مسائل بهینه‌سازی

اگرچه گراف دور ساده به نظر می‌رسد، اما در مسائل بهینه‌سازی ترکیبیاتی و طراحی الگوریتم‌ها نقش اساسی دارد. سه کاربرد مهم عبارتند از:

مسئله فروشنده دوره‌گرد (TSP)⁶: حالت پایهٔ TSP روی یک گراف دوری ساده‌ترین حالت ممکن است؛ جواب بهینه همان دور اصلی است.
شبکه‌های حلقوی (Ring Networks): در مخابرات و فیبر نوری، توپولوژی حلقوی (که همان $C_n$ است) به دلیل سادگی و افزونگی استفاده می‌شود. پروتکل حلقهٔ نشانه نمونهٔ کلاسیک این کاربرد است.
طراحی جداول مسابقات دورهای: در مسابقات ورزشی که هر تیم فقط با تیم بعدی و قبلی خود مسابقه می‌دهد (مانند مسابقات لیگ به صورت رفت و برگشت ساده در یک گروه کوچک)، ساختار دوری به کار می‌رود.

چالش‌های مفهومی درک گراف $C_n$

چالش ۱: آیا $C_3$ با $K_3$ تفاوت دارد؟
پاسخ: خیر، برای $n=3$ گراف دور با گراف کامل سه‌رأسی یکسان است، زیرا در یک مثلث هر رأس به دو رأس دیگر (که هر دو مجاورند) وصل می‌شود و یال هیچ نقصی ندارد.

چالش ۲: چرا گراف $C_n$ برای $n \ge 3$ دووجهی است؟
پاسخ: گراف $C_n$ را می‌توان روی صفحه بدون تقاطع یال‌ها رسم کرد (به صورت یک چندضلعی منتظم). بنابراین یک گراف صفحه‌ای⁷ است و قضیه اویلر⁸ برای آن صدق می‌کند: $V - E + F = 2$ که در آن $F = 2$ (دو وجه: داخل و خارج دور).

چالش ۳: تفاوت بین گراف $C_n$ و مسیر $P_n$ چیست؟
پاسخ: مسیر $P_n$ دارای $n$ رأس و $n-1$ یال است و دو رأس انتهایی درجه $1$ دارند. اما $C_n$ با اضافه کردن یک یال بین دو رأس انتهایی $P_n$ ساخته می‌شود و همهٔ رأس‌ها درجه $2$ پیدا می‌کنند.

جمع‌بندی
گراف $C_n$ یکی از ساده‌ترین و در عین حال بنیادین‌ترین ساختارها در نظریه گراف است. با درک درستی از ویژگی‌هایی مانند منتظمی، عدد رنگی، صفحه‌ای بودن و کاربردهای عملی آن در شبکه‌های حلقوی و مسائل بهینه‌سازی، دانش‌آموزان می‌توانند پایه‌ای محکم برای مطالعه گراف‌های پیچیده‌تر مانند گراف‌های چرخ‌دنده‌ای $W_n$ و گراف‌های کامل $K_n$ به دست آورند. به خاطر داشته باشید که مقدار $n$ (تعداد رأس‌ها) تعیین‌کنندهٔ بسیاری از خصوصیات این گراف است، به ویژه زوج یا فرد بودن آن در رنگ‌آمیزی و قابلیت اویلری⁹ بودن.

پاورقی

¹ چرخه ساده (Cycle Graph): گرافی همبند که هر رأس آن درجه $2$ داشته باشد.

² درجه (Degree): تعداد یال‌های وارد شده به یک رأس.

³ عدد رنگی (Chromatic Number): کوچک‌ترین تعداد رنگ لازم برای رنگ‌آمیزی رأس‌ها به طوری که هیچ دو رأس مجاور همرنگ نباشند.

⁴ گراف مکمل (Complement Graph): گرافی که روی همان رأس‌ها تعریف می‌شود و در آن دو رأس مجاورند اگر و فقط اگر در گراف اصلی مجاور نباشند.

⁵ حلقه (Loop): یالی که یک رأس را به خودش متصل می‌کند. در گراف‌های ساده مجاز نیست.

⁶ مسئله فروشنده دوره‌گرد (Traveling Salesman Problem - TSP): یافتن کوتاه‌ترین مسیر دوری که از همهٔ رأس‌ها دقیقاً یک بار عبور کند.

⁷ گراف صفحه‌ای (Planar Graph): گرافی که بتوان آن را روی صفحه بدون تقاطع یال‌ها رسم کرد.

⁸ قضیه اویلر (Euler's Formula): برای گراف‌های صفحه‌ای همبند: $V - E + F = 2$ که $F$ تعداد وجوه است.

⁹ گراف اویلری (Eulerian Graph): گرافی که دارای دور اویلری (مسیری که از هر یال دقیقاً یک بار عبور کند و به نقطه شروع برگردد) باشد. $C_n$ برای $n \ge 3$ اویلری است.