یالهای مجاور در گراف: دو یال با یک رأس مشترک
آشنایی با مفهوم مجاورت یالها، نحوه تشخیص، شمارش و کاربرد آن در مسئلههای گراف
در این مقاله با مفهوم یالهای مجاور در نظریه گراف آشنا میشوید. دو یال را مجاور گوییم اگر حداقل یک رأس مشترک داشته باشند. این مفهوم پایهای در مسائلی مانند مسیریابی، تحلیل شبکههای اجتماعی و الگوریتمهای گراف کاربرد گسترده دارد. همچنین روشهای شمارش یالهای مجاور، تفاوت آن با رأسهای مجاور و چند چالش مفهومی را گام به گام بررسی خواهیم کرد.
۱. تعریف پایهای و تفاوت با مجاورت رأسها
در نظریه گراف1، یک گراف G از دو مجموعه رأسها (نقاط) و یالها (پارهخطهای متصلکننده) تشکیل میشود. اگر دو یال مانند e_1 و e_2 حداقل یک رأس مشترک داشته باشند، به آنها یالهای مجاور میگویند. برای درک بهتر، ابتدا مفهوم رأسهای مجاور را مرور میکنیم: دو رأس مجاورند اگر با یک یال به هم وصل شده باشند. اما در مجاورت یالها، تمرکز روی خود یالهاست، نه رأسها. در حقیقت، یالها از طریق اشتراک در یک رأس، به یکدیگر نزدیک میشوند.
مثال ساده: یک مثلث با رأسهای A, B, C و یالهای AB, BC, CA را در نظر بگیرید. یال AB با یال BC مجاور است (زیرا رأس B مشترک است). همچنین AB با CA نیز مجاور است (رأس A مشترک). در یک مثلث، هر جفت یالی مجاورند.
۲. انواع گراف و تأثیر بر مجاورت یالها
نوع گراف در تشخیص یالهای مجاور تأثیر مستقیم دارد. مهمترین انواع عبارتند از:| نوع گراف | ویژگی مجاورت یالها | مثال |
|---|---|---|
| گراف ساده2 | بدون یال چندگانه و بدون حلقه، هر دو یال حداکثر یک رأس مشترک دارند. | گراف مسیر با 4 رأس |
| گراف با یالهای چندگانه3 | دو یال چندگانه بین یک جفت رأس، هر دو رأس را مشترک دارند و مجاور محسوب میشوند. | دو یال موازی بین X و Y |
| گراف با حلقه4 | یک حلقه (یالی که یک رأس را به خودش وصل میکند) با یالهای متصل به آن رأس مجاور است. | حلقه در رأس v مجاور یال vw |
۳. درجه یک یال و رابطه با رأسها
برای هر یال e = uv، تعداد یالهای مجاور با آن را درجه یال مینامیم. اگر درجه یک یال را با deg(e) نمایش دهیم، فرمول زیر برقرار است: $ \deg(e) = \deg(u) + \deg(v) - 2 $ که در آن \deg(u) و \deg(v) به ترتیب درجه (تعداد یالهای متصل به) رأس u و v هستند. دلیل آن این است که مجموع درجه دو رأس، هر دو سر یال e را حساب میکند، اما خود یال e را دو بار شمرده و سپس با کسر 2، آن را حذف میکنیم.
مثال عددی: در یک گراف، رأس A درجه 3 و رأس B درجه 4 دارد و یال AB موجود است. تعداد یالهای مجاور با AB برابر است با:
$ 3 + 4 - 2 = 5 $
یعنی این یال با 5 یال دیگر مجاور است (به جز خودش).
۴. کاربرد عملی: شمارش یالهای مجاور در شبکه حملونقل
فرض کنید یک نقشه از ایستگاههای مترو داریم که در آن ایستگاهها رأس و مسیرهای بین دو ایستگاه مجاور یال هستند. دو مسیر (یال) را مجاور میگوییم اگر حداقل یک ایستگاه مشترک داشته باشند. این مفهوم در طراحی شبکه برای یافتن مسیرهای جایگزین یا بررسی تراکم ترافیک میان ایستگاههای شلوغ کاربرد دارد. به عنوان یک مثال عینی، گراف زیر را در نظر بگیرید: رأسها: {1,2,3,4} یالها: e1=12, e2=23, e3=34, e4=14 یالهای مجاور با e1 (یال بین 1 و 2) کدامند؟ با رأس 1 یال e4 مشترک است. با رأس 2 یال e2 مشترک است. بنابراین یالهای مجاور با e1 عبارتند از e2 و e4.۵. چالشهای مفهومی
پرسش ۱: آیا دو یال که فقط یک رأس مشترک دارند، همیشه مجاور محسوب میشوند؟
پاسخ: بله، دقیقاً تعریف مجاورت یالها همین است. حتی اگر یک رأس مشترک داشته باشند، مجاور نامیده میشوند. نیازی به اشتراک هر دو رأس نیست.
پاسخ: بله، دقیقاً تعریف مجاورت یالها همین است. حتی اگر یک رأس مشترک داشته باشند، مجاور نامیده میشوند. نیازی به اشتراک هر دو رأس نیست.
پرسش ۲: در یک گراف کامل5 با n رأس، چند جفت یال مجاور وجود دارد؟
پاسخ: تعداد کل یالها $ \frac{n(n-1)}{2} $ است. هر یال با $ 2(n-2) $ یال دیگر مجاور است (چون دو سر آن هرکدام به n-2 رأس دیگر متصلاند). اما در شمارش جفتها باید احتیاط کرد و از تقارن استفاده نمود. رابطه نهایی تعداد جفتهای مجاور برابر است با $ \frac{n(n-1)(n-2)}{2} $.
پاسخ: تعداد کل یالها $ \frac{n(n-1)}{2} $ است. هر یال با $ 2(n-2) $ یال دیگر مجاور است (چون دو سر آن هرکدام به n-2 رأس دیگر متصلاند). اما در شمارش جفتها باید احتیاط کرد و از تقارن استفاده نمود. رابطه نهایی تعداد جفتهای مجاور برابر است با $ \frac{n(n-1)(n-2)}{2} $.
پرسش ۳: آیا یک یال میتواند با خودش مجاور باشد؟
پاسخ: در تعریف استاندارد، مجاورت برای دو یال متمایز تعریف میشود. بنابراین یک یال با خودش مجاور نیست، مگر در برخی متون خاص که آن را مجاز بدانند (که معمولاً به آن حلقه یا شرایط ویژه میگویند). در این مقاله، منظور از یالهای مجاور، دو یال متفاوت است.
پاسخ: در تعریف استاندارد، مجاورت برای دو یال متمایز تعریف میشود. بنابراین یک یال با خودش مجاور نیست، مگر در برخی متون خاص که آن را مجاز بدانند (که معمولاً به آن حلقه یا شرایط ویژه میگویند). در این مقاله، منظور از یالهای مجاور، دو یال متفاوت است.
۶. جمعبندی
در این مقاله با مفهوم یالهای مجاور در گراف آشنا شدیم. یاد گرفتیم که دو یال مجاور هستند اگر حداقل یک رأس مشترک داشته باشند. تفاوت این مفهوم با مجاورت رأسها را مرور کردیم و دیدیم که چگونه نوع گراف (ساده، چندگانه، دارای حلقه) در تشخیص مجاورت تأثیر میگذارد. همچنین فرمول محاسبه درجه یک یال و کاربرد آن در شبکه حملونقل را بررسی کردیم. در نهایت با پاسخ به سه چالش مفهومی، درک عمیقتری از این موضوع پایهای نظریه گراف به دست آوردیم.
پاورقی
1 نظریه گراف (Graph Theory): شاخهای از ریاضیات که ساختارهای متشکل از رأس و یال را مطالعه میکند.2 گراف ساده (Simple Graph): گرافی بدون یال چندگانه و بدون حلقه.
3 یالهای چندگانه (Multiple Edges): دو یا چند یال که دقیقاً دو رأس یکسان را به هم متصل میکنند.
4 حلقه (Loop): یالی که یک رأس را به خودش وصل میکند.
5 گراف کامل (Complete Graph): گرافی که هر دو رأس متمایز آن با یک یال به هم وصل شده باشند.