طوقه در گراف: یالی که یک رأس را به خودش وصل میکند
تعریف طوقه و جایگاه آن در نظریهٔ گراف
در نظریهٔ گراف1، یک گراف از مجموعهٔ رأسها2 و مجموعهٔ یالها3 تشکیل میشود. یال معمولاً دو رأس متمایز را به هم وصل میکند. اما طوقه4 (Loop) حالت خاصی از یال است که در آن مبدأ و مقصد یال یکی است؛ یعنی یک رأس به خودش متصل میشود.
برای نمونه در گراف زیر، رأس A دارای یک طوقه است که از آن خارج و به خودش بازمیگردد. طوقه در گرافهای بدون جهت معمولاً به صورت یک کمان دایرهای دور رأس رسم میشود. در گرافهای جهتدار، طوقه میتواند جهت داشته باشد، ولی از آنجا که شروع و پایان آن یکی است، جهت تأثیری در محاسبات درجه ندارد.
تأثیر طوقه بر درجهٔ رأس و فرمولهای مربوط
یکی از مهمترین مفاهیم در گراف، درجهٔ رأس (Degree) است که تعداد یالهای متصل به آن رأس را نشان میدهد. اما طوقه در این محاسبه رفتاری متفاوت دارد:
- در گراف بدون جهت، هر طوقه به اندازهٔ 2 واحد به درجهٔ رأس اضافه میکند. دلیل: طوقه از رأس خارج و دوباره وارد آن میشود، بنابراین دو بار «برخورد» با رأس دارد.
- در گراف جهتدار، طوقه معمولاً 1 واحد به درجهٔ خروجی و 1 واحد به درجهٔ ورودی اضافه میکند و در نتیجه درجهٔ کل 2 واحد افزایش مییابد.
فرمول عمومی جمع درجهٔ رأسها در گراف بدون جهت با وجود طوقه به صورت زیر است (توجه کنید هر طوقه دو بار شمارش میشود):
در این فرمول، |E| تعداد یالهای غیرطوقهای است. طوقهها در سمت راست ضریب 2 دارند چون همانطور که اشاره شد هر طوقه درجهٔ رأس را 2 واحد افزایش میدهد.
مقایسهٔ گراف ساده، گراف با طوقه و گراف با یال موازی
| ویژگی | گراف ساده | گراف دارای طوقه | گراف دارای یال موازی |
|---|---|---|---|
| امکان طوقه | خیر | بله | ممکن است (اما طوقه نوعی یال موازی به حساب میآید) |
| تأثیر در درجهٔ رأس | هر یال +1 به دو رأس | هر طوقه +2 به یک رأس | مشابه یال ساده، اما چندباره |
| نمایش در ماتریس مجاورت5 | قطر اصلی صفر | درایهٔ قطر 1 (در گراف بدون جهت) یا 2 (در گراف جهتدار با احتساب خروج و ورود) | درایهٔ خارج از قطر میتواند بیش از 1 باشد |
کاربرد عملی: مدلسازی خودارجاعی در شبکههای اجتماعی
فرض کنید در یک شبکهٔ اجتماعی، هر کاربر یک رأس است و «لایک کردن پست خود شخص» یک کنش است که از کاربر به خودش اشاره دارد. اگر بخواهیم این وضعیت را با یک گراف جهتدار مدل کنیم، هر «لایک شخص به پست خودش» معادل یک طوقه بر روی رأس آن کاربر خواهد بود. طوقه در اینجا نشاندهندهٔ خودارجاعی (Self-reference) است.
مثال دیگر: در یک گراف که نمایانگر روابط «همکار بودن» در یک شرکت است، اگر قانونی وجود داشته باشد که «هر شخص با خودش همکار محسوب میشود»، آنگاه هر رأس یک طوقه خواهد داشت. در الگوریتمهای جستجو مانند جستجوی عمقی6، طوقهها به عنوان یالهایی که رأس را به خودش وصل میکنند، میتوانند باعث ایجاد حلقههای بینهایت نشوند اگر الگوریتم به درستی طراحی شده باشد (معمولاً با علامتگذاری رأسهای دیده شده از ورود مجدد جلوگیری میشود).
چالشهای مفهومی
چالش ۱ : آیا طوقه در گراف بدون جهت مجاز است؟
بله، طوقه در گراف بدون جهت مجاز است، اما در این صورت گراف دیگر «ساده» محسوب نمیشود. در بسیاری از کتابهای درسی دبیرستان، گرافهای بدون جهت معمولاً بدون طوقه تعریف میشوند، اما در نظریهٔ عمومی گراف، طوقه مجاز بوده و قواعد خاص خود را دارد.
چالش ۲ : چگونه یک طوقه را در ماتریس مجاورت نمایش دهیم؟
در گراف بدون جهت، ماتریس مجاورت متقارن است و یک طوقه در رأس i باعث میشود درایهٔ (i,i) مقدار 1 بگیرد. در گراف جهتدار اگر طوقه جهتدار در نظر گرفته شود، همان درایه باز هم 1 خواهد بود. توجه کنید که برای محاسبهٔ درجه از روی ماتریس، در گراف بدون جهت طوقه به عنوان 2 واحد در جمع سطر یا ستون محاسبه میشود.
چالش ۳ : آیا طوقه بر قضیهٔ دست دادن (Handshaking Lemma) تأثیر میگذارد؟
بله. قضیهٔ دست دادن میگوید مجموع درجات همهٔ رأسها برابر دو برابر تعداد یالهاست. در حضور طوقه، هر طوقه دو بار در مجموع درجات شمرده میشود، بنابراین در فرمول باید ضریب 2 برای طوقهها در نظر گرفت. این تغییر مهم در محاسبات گراف با طوقه ضروری است.
طوقه یالی است که یک رأس را به خودش متصل میکند و نقش اساسی در گسترش نظریهٔ گراف به سوی گرافهای غیرساده دارد. در این مقاله دیدیم که طوقه چگونه درجهٔ رأس را به صورت ویژه تحت تأثیر قرار میدهد (افزایش 2 واحدی)، چگونه در ماتریس مجاورت نمایش داده میشود، و چه کاربردهایی در مدلسازی سیستمهای خودارجاعی مانند شبکههای اجتماعی دارد. همچنین با چالشهای مفهومی مانند تأثیر طوقه بر قضیهٔ دست دادن آشنا شدیم. درک طوقه برای مطالعهٔ گرافهای وزندار، الگوریتمهای گراف و مسائل بهینهسازی گام اساسی محسوب میشود.
پاورقی
1 نظریهٔ گراف (Graph Theory): شاخهای از ریاضیات که به مطالعهٔ گرافها به عنوان ساختارهایی شامل رأس و یال میپردازد.
2 رأس (Vertex): نقطه یا گره در یک گراف که نشاندهندهٔ یک موجودیت یا شیء است.
3 یال (Edge): ارتباط بین دو رأس در گراف که میتواند جهتدار یا بدون جهت باشد.
4 طوقه (Loop): یالی که یک رأس را به خودش متصل میکند و مبدأ و مقصد آن یکی است.
5 ماتریس مجاورت (Adjacency Matrix): ماتریسی مربعی که درایهٔ سطر i و ستون j نشاندهندهٔ وجود یال از رأس i به j است.
6 جستجوی عمقی (Depth-First Search - DFS): الگوریتمی برای پیمایش گراف که تا حد امکان در عمق پیش میرود و سپس بازمیگردد.
