مکمل یک گراف: سفری به جهان یالهای مکمل
تعریف پایه: مکمل گراف چیست؟
فرض کنید یک گراف ساده1 مانند $G$ داریم. این گراف از مجموعهای از رأسها2 و یالها3 تشکیل شده است. مکمل این گراف که آن را با نماد $\overline{G}$ نشان میدهند، گرافی است که:
- مجموعه رأسهای آن دقیقاً همان مجموعه رأسهای $G$ است.
- دو رأس در $\overline{G}$ با یک یال به هم متصل میشوند اگر و تنها اگر در گراف اصلی $G$ آن دو رأس به هم متصل نباشند.
به عبارت دیگر، یالهای مکمل همان یالهای «غیرموجود» در گراف اصلی هستند. یک نکته مهم: حلقه (یالی که یک رأس را به خودش وصل کند) در این تعریف وجود ندارد، چون گرافهای ساده بدون حلقه در نظر گرفته میشوند.
یک مثال ساده: گرافی با $3$ رأس به نامهای $A$، $B$ و $C$ را در نظر بگیرید. فرض کنید در گراف اصلی $G$ فقط یک یال بین $A$ و $B$ داریم. آنگاه در مکمل $\overline{G}$، یالهای غیرموجود در $G$ یعنی جفتهای $(A,C)$ و $(B,C)$ تبدیل به یال میشوند. همچنین یال $(A,B)$ در مکمل وجود ندارد. بنابراین مکمل یک گراف کاملاً به ما میگوید که «چه ارتباطاتی در گراف اصلی کمبود دارد».
رابطه بین گراف و مکمل: جدول مقایسه
| ویژگی | گراف اصلی $G$ | مکمل $\overline{G}$ |
|---|---|---|
| مجموعه رأسها | $V$ | $V$ (دقیقاً یکسان) |
| یالها | مجموعه $E$ | مجموعه مکمل $\overline{E}$ (همه جفتهای ممکن به جز یالهای $E$) |
| تعداد یالها (با $n$ رأس) | $m$ | $\frac{n(n-1)}{2} - m$ |
| مکمل دوباره | $\overline{\overline{G}} = G$ (مکملگیری دو بار، گراف اولیه را بازمیگرداند) | |
توجه کنید که تعداد کل یالهای ممکن در یک گراف با $n$ رأس برابر است با $\binom{n}{2} = \frac{n(n-1)}{2}$. این عدد جمع یالهای $G$ و $\overline{G}$ است.
گام به گام: ساخت مکمل برای یک گراف مشخص
فرض کنید گراف زیر را داریم (با $4$ رأس):
- رأسها: $ \{1,2,3,4\} $
- یالها: $(1,2), (2,3), (3,4)$
گام 1: همه جفتهای ممکن رأسها را بنویسید. برای $n=4$، جفتها عبارتند از: $(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$.
گام 2: یالهای موجود در $G$ را حذف کنید: $(1,2), (2,3), (3,4)$ حذف میشوند.
گام 3: یالهای باقیمانده، یالهای مکمل هستند: $(1,3), (1,4), (2,4)$. پس مکمل این گراف، گرافی با همان رأسهای $1,2,3,4$ و سه یال بالا خواهد بود.
چک کردن: اگر دوباره مکمل این گراف جدید را بگیریم، باید به گراف اولیه برسیم. یالهای ممکن کل $6$ تاست. در مکمل جدید، یالهای موجود $(1,2)$ و $(2,3)$ و $(3,4)$ میشود که همان $G$ است. درست کار میکند.
کاربرد عملی: شبکه اجتماعی و دوستان مشترک
فرض کنید در یک شبکه اجتماعی کوچک، رأسها نماینده افراد هستند و یال بین دو نفر نشان میدهد که آن دو با هم دوست هستند. گراف روابط دوستی را در نظر بگیرید. حالا مکمل این گراف چه چیزی را نشان میدهد؟ مکمل، روابط «ندوستی» یا همان افرادی را نشان میدهد که هنوز با هم ارتباط برقرار نکردهاند. این مفهوم در الگوریتمهای پیشنهاد دوست کاربرد دارد: اگر دو نفر دوست نباشند اما دوستان مشترک زیادی داشته باشند، سیستم ممکن است آنها را به یکدیگر پیشنهاد دهد. در حقیقت، تحلیل گراف مکمل به شناسایی فرصتهای جدید برای ایجاد یال کمک میکند.
مثال عینی: در یک گروه $5$ نفره، گراف دوستی شامل یالهای $(1,2), (2,3), (3,4), (4,5), (5,1)$ (یک چرخه $5$ تایی) است. مکمل این گراف شامل یالهایی میشود که افراد غیرهمسایه در این چرخه را به هم وصل میکند (قطرها). با بررسی مکمل میتوان فهمید کدام جفت افراد هنوز با هم دوست نشدهاند تا شاید ارتباط جدیدی شکل گیرد.
چالشهای مفهومی
پاسخ: بله، به گراف خودمکمل4 میگویند. در این حالت $G \cong \overline{G}$ (همریخت هستند). شرط لازم برای وجود چنین گرافی این است که تعداد یالها برابر باشد: $m = \frac{n(n-1)}{4}$. بنابراین $\frac{n(n-1)}{2}$ باید زوج باشد. سادهترین مثال، گراف مسیری با $4$ رأس (مسیر $P_4$) است که با مکمل خود همریخت میباشد.
پاسخ: گراف کامل $K_n$ شامل همه یالهای ممکن بین $n$ رأس است. بنابراین در مکمل آن هیچ یالی وجود ندارد. به چنین گرافی، گراف تهی6 میگویند که با نماد $\overline{K_n}$ نشان داده میشود و فقط شامل $n$ رأس ایزوله (بدون یال) است. برعکس، اگر گراف تهی داشته باشیم، مکمل آن یک گراف کامل است.
پاسخ: بله. اگر در گراف اصلی $G$ درجه رأس $v$ برابر $\deg_G(v)$ باشد، در مکمل $\overline{G}$ درجه همان رأس برابر است با $(n-1) - \deg_G(v)$. چرا؟ چون هر رأس میتواند به $n-1$ رأس دیگر متصل شود و در مکمل، آن دسته از همسایههایی که در $G$ نبودهاند، به آن وصل میشوند. بنابراین مجموع درجه یک رأس در گراف اصلی و مکمل همیشه $n-1$ است.
ویژگیهای مهم و قضیهای ساده
مکمل گراف ابزار قدرتمندی در اثبات قضایای نظریه گراف است. یکی از قضایای شناخته شده میگوید: «در هر گراف با حداقل $6$ رأس، یا خود گراف شامل یک مثلث (سه رأس که هر دو به هم وصلند) است یا مکمل آن شامل یک مثلث است». این یک حالت خاص از قضیه رمزی7 است. همچنین:
- اگر $G$ ناهمبند باشد، آنگاه $\overline{G}$ همبند است (مگر موارد خاص).
- مکمل یک گراف دوبخشی8 لزوماً دوبخشی نیست.
- خودمکمل بودن به معنای تقارن خاصی در ساختار گراف است.
مثال جالب: گراف چرخدندهای $W_5$ (یک چرخه $4$ تایی با یک رأس مرکزی متصل به همه) مکملی دارد که آن هم یک گراف چرخدندهای دیگر است. این نشان میدهد که گاهی مکمل، ساختار مشابه با گراف اصلی دارد.
پاورقی
1 گراف ساده (Simple Graph): گرافی بدون یال چندگانه و بدون حلقه (یالی که رأس را به خودش وصل کند).
2 رأس (Vertex): هر نقطه یا گره در گراف که نشاندهنده یک شیء یا شخص است.
3 یال (Edge): ارتباط بین دو رأس که به صورت یک خط یا کمان رسم میشود.
4 گراف خودمکمل (Self-Complementary Graph): گرافی که با مکمل خود همریخت (از نظر ساختار یکسان) باشد.
5 گراف کامل (Complete Graph): گرافی که هر دو رأس متمایز آن با یک یال به هم متصل باشند. با نماد $K_n$ نشان داده میشود.
6 گراف تهی (Empty Graph یا Null Graph): گرافی که هیچ یالی بین رأسهای آن وجود ندارد.
7 قضیه رمزی (Ramsey's Theorem): قضیهای در ترکیبیات که میگوید برای هر عدد صحیح، در هر گرافی با تعداد کافی رأس، زیرگراف کامل یا زیرگراف تهی با اندازه معین وجود دارد.
8 گراف دوبخشی (Bipartite Graph): گرافی که رأسهای آن را میتوان به دو دسته تقسیم کرد به طوری که هر یال فقط بین دو دسته قرار گیرد.