گراف ناهمبند: گرافی که بین برخی رأسهای آن مسیر وجود ندارد
آشنایی با ساختارهای جدا از هم در نظریه گراف و کاربردهای ساده روزمره
در این مقاله با مفهوم «گراف ناهمبند» آشنا میشوید. میفهمیم چرا در برخی گرافها بین بعضی از رأسها هیچ مسیری وجود ندارد. همچنین «مؤلفههای همبندی»1، تفاوت گراف همبند و ناهمبند، و مثالهای ساده و کاربردی از این نوع گرافها را بررسی خواهیم کرد. هدف، درک بصری و ریاضی این مفهوم در سطح دبیرستان است.
تعریف ساده و تقسیمبندی اولیه گرافها
گراف در ریاضیات، مجموعهای از نقطهها (رأسها) است که برخی از آنها با خطهایی (یالها) به هم وصل شدهاند. اگر بتوان از هر رأس به هر رأس دیگر از طریق دنبالهای از یالها رسید، آن گراف را همبند مینامیم. در غیر این صورت، گراف ناهمبند خواهد بود. به عبارت دیگر، در یک گراف ناهمبند، دستکم دو رأس وجود دارند که هیچ مسیری بین آنها نیست.
مثال ساده: فرض کنید پنج نفر در یک مهمانی هستیم. اگر بین هر دو نفر دستدادنی برقرار شده باشد (یا به صورت زنجیرهای)، گروه همبند است. اما اگر دو نفر اصلاً با سایرین ارتباطی نداشته باشند و فقط با هم دست بدهند، گراف به دو بخش جدا تبدیل میشود. این یک گراف ناهمبند است.
مؤلفههای همبندی؛ تکههای جدای گراف
در یک گراف ناهمبند، هر بخش بیشینهای که درون خود همبند است اما به بخش دیگر وصل نیست، یک مؤلفه همبند نامیده میشود. تعداد مؤلفهها را با k نشان میدهند. اگر گراف همبند باشد، k = 1 و اگر ناهمبند باشد، k \ge 2.
فرمول پایه: برای گرافی با n رأس و m یال، اگر m \lt n - 1 باشد، گراف حتماً ناهمبند خواهد بود. اما عکس این گزاره همیشه درست نیست.
| ویژگی | گراف همبند | گراف ناهمبند |
|---|---|---|
| تعداد مؤلفهها | 1 | 2 یا بیشتر |
| وجود مسیر بین هر دو رأس | بله | خیر (حداقل یک جفت رأس) |
| حداقل تعداد یال | n-1 (درخت) | 0 (گراف تهی) |
مثالهای عینی از گراف ناهمبند در دنیای واقعی
در شبکههای کامپیوتری، اگر یک روتر مرکزی از کار بیفتد و دو بخش شبکه نتوانند با هم ارتباط برقرار کنند، آن شبکه به دو مؤلفه ناهمبند تبدیل میشود. همچنین در شبکههای اجتماعی، اگر دو گروه از کاربران هیچ دنبالکننده مشترکی نداشته باشند و پیامی بین آنها ردوبدل نشود، گراف ارتباطی آنها ناهمبند است. مثال آموزشی: فرض کنید شش شهر داریم: آ، ب، پ، ت، ث، ج. جادهها فقط بین شهرهای (آ، ب)، (ب، پ) و (ث، ج) وجود دارد. در این صورت دو مؤلفه داریم: مؤلفه اول شامل آ، ب، پ و مؤلفه دوم شامل ث، ج. شهر ت هم به تنهایی یک مؤلفه (رأس تنها) است. پس هیچ مسیری بین مثلاً شهر پ و شهر ث وجود ندارد.تشخیص ناهمبندی؛ روش گامبهگام
برای تشخیص همبند یا ناهمبند بودن یک گراف میتوان از روش پیمایش سطحبهسطح یا پیمایش عمقاول استفاده کرد. مراحل ساده:- یک رأس دلخواه را انتخاب کن.
- با استفاده از الگوریتم ساده، تمام رأسهایی را که از این رأس قابل دسترس هستند، علامت بزن.
- اگر بعد از پایان کار، تمام رأسها علامت خورده باشند، گراف همبند است. در غیر این صورت، ناهمبند است و هر دسته از رأسهای علامتنخورده، مؤلفه جدیدی را میسازند.
نکته عملی فرض کنید در حال طراحی یک مسیر مترو هستید. اگر دو ایستگاه به هیچ وجه از طریق خطوط مترو به هم متصل نشوند، شبکه حملونقل شما ناهمبند است و نیاز به خط جدید دارید.
چالشهای مفهومی
۱) آیا گرافی با یک رأس و بدون یال، همبند است یا ناهمبند؟
پاسخ: گراف با یک رأس را «همبند» در نظر میگیریم. چون شرط «وجود مسیر بین هر دو رأس» به صورت تهی برقرار است. این گراف یک مؤلفه دارد.
پاسخ: گراف با یک رأس را «همبند» در نظر میگیریم. چون شرط «وجود مسیر بین هر دو رأس» به صورت تهی برقرار است. این گراف یک مؤلفه دارد.
۲) اگر گرافی دارای n رأس و n-1 یال باشد، آیا حتماً همبند است؟
پاسخ: نه لزوماً. مثلاً با n=4 میتوان یک مثلث (سه رأس با سه یال) و یک رأس تنها داشت. مجموع یالها 3 = n-1 اما گراف ناهمبند است. شرط m \ge n-1 برای همبندی لازم است ولی کافی نیست.
پاسخ: نه لزوماً. مثلاً با n=4 میتوان یک مثلث (سه رأس با سه یال) و یک رأس تنها داشت. مجموع یالها 3 = n-1 اما گراف ناهمبند است. شرط m \ge n-1 برای همبندی لازم است ولی کافی نیست.
۳) آیا گراف تهی (بدون یال) با بیش از یک رأس، ناهمبند است؟
پاسخ: بله. اگر هیچ یالی وجود نداشته باشد، هر رأس به تنهایی یک مؤلفه همبند است. پس تعداد مؤلفهها برابر با تعداد رأسها خواهد بود و گراف ناهمبند محسوب میشود.
پاسخ: بله. اگر هیچ یالی وجود نداشته باشد، هر رأس به تنهایی یک مؤلفه همبند است. پس تعداد مؤلفهها برابر با تعداد رأسها خواهد بود و گراف ناهمبند محسوب میشود.
جمعبندی: گراف ناهمبند، گرافی است که دستکم دو رأس آن توسط هیچ مسیری به هم وصل نیستند. این گرافها از چند «مؤلفه همبند» تشکیل میشوند. درک این مفهوم برای تحلیل شبکههای ارتباطی، شبکههای اجتماعی و طراحی مسیرها اهمیت دارد. تشخیص ناهمبندی با استفاده از الگوریتمهای ساده پیمایش امکانپذیر است.
