: مکمل یک گراف و گراف خود مکمل

||V{maketoc}||

^@#16:

!مکمل یک گراف و گراف خود مکمل

!مکمل یک گراف ساده

فرض کنید {TEX()} {G} {TEX} یک گراف ساده، با مجموعه رئوس {TEX()} {V(G)} {TEX} است مکمل {TEX()} {G} {TEX} که با{TEX()} {\overline{G}} {TEX} نمایش می دهند یک گراف ساده دیگر است که همان مجموعه رئوس {TEX()} {V(G)} {TEX} را دارد و در آن هر دو راسی که در{TEX()} {G} {TEX} مجاور نبوده اند مجاور می باشند.

• توجه کنید تعداد یالهای گراف{TEX()} {G} {TEX} به علاوه یالهای مکمل آن برابر یالهای ((گراف)) کامل {TEX()} {|V(G)|} {TEX} راس خواهد شد.

• مکمل گراف کامل تهی است و بالعکس.

• مکمل یک گراف دو بخشی کامل عبارتست از اجتماع دو گراف کامل ( اثبات به عهده شما!)

به عبارت ساده تر مکمل گراف ساده{TEX()} {G} {TEX} همان گراف{TEX()} {G} {TEX} است فقط هر جا یال داریم آن را حذف و هر جا نداریم آن را اضافه می کنیم

---

!قضیه

اگر گراف{TEX()} {G} {TEX} ناهمبند باشد{TEX()} {\overline{G}} {TEX} همبند است

این قضیه را بعداً‌ در فصل همبندی به روش دیگری نیز اثبات خواهیم کرد. اثبات ( برهان خلف ) فرض می کنیم{TEX()} {\overline{G}} {TEX} ناهمبند است یعنی{TEX()} {\overline{G}} {TEX} از حداقل دو مولفه تشکیل شده است دو راس دلخواه {TEX()} {v,u} {TEX}را از {TEX()} {G} {TEX} ( که {TEX()} {\overline{G}} {TEX} نیز تعلق دارند ) در نظر می گیریم.

{TEX()} {v,u} {TEX} هر دو یا به دو مولفه متمایز {TEX()} {\overline{G}} {TEX} تعلق دارند یا هر دو در یک مولفه {TEX()} {\overline{G}} {TEX} واقعند.

اگر{TEX()} {v,u} {TEX} در دو مولفه متمایز{TEX()} {\overline{G}} {TEX} باشند آنگاه {TEX()} {v,u} {TEX} در {TEX()} {\overline{G}} {TEX}غیر همجوراند بنابراین در {TEX()} {G} {TEX}همجوارند با مسیری به طول یک و این با فرض ناهمبند بودن{TEX()} {G} {TEX} در تناقض است.

اگر {TEX()} {v,u} {TEX}در یک مولفه{TEX()} {\overline{G}} {TEX} باشند راسی مانند {TEX()} {w} {TEX} در مولفه دیگر{TEX()} {\overline{G}} {TEX} در نظر می گیریم {TEX()} {w} {TEX} در{TEX()} {\overline{G}} {TEX} نه با{TEX()} {u} {TEX} و نه با{TEX()} {v} {TEX} همجوار است. بنابراین {TEX()} {w} {TEX} در{TEX()} {G} {TEX} هم با {TEX()} {u} {TEX} و هم با {TEX()} {v} {TEX} همجوار خواهد بود. یعنی در{TEX()} {G} {TEX} مسیری به طول 2، دو راس{TEX()} {v,u} {TEX} را به هم متصل می کند.

بنابراین نشان دادیم مسیری بین دو راس دلخواه وجود دارد.

::{picture=img/daneshnameh_up/7/7a/mco0061a.jpg}::

---

!گراف خود مکمل

گراف{TEX()} {G} {TEX} را خود ((مکمل)) گویند اگر{TEX()} {G} {TEX}و{TEX()} {\overline{G}} {TEX} یکریخت باشند.

---

!!مثال

گراف چهارراسی زیر خود مکمل است.

::{picture=img/daneshnameh_up/6/67/mco0061b.jpg}::

گراف 5 راسی زیر نیز خود مکمل است.

::{picture=img/daneshnameh_up/c/cf/mco0061c.jpg}::

{TEX()} {G} {TEX}و{TEX()} {\overline{G}} {TEX} در بالا یکریختند زیرا کافی است برای هر{TEX()} {i} {TEX}،{TEX()} {u_i} {TEX}‌را با{TEX()} {v_i} {TEX} متناظر بگیرند.

---

!تمرین مهم

شرط لازم و کافی برای وجود یک گراف خود مکمل {TEX()} {n} {TEX} راسی را بیابید.

حل به عهده کاربر محترم.

__راهنمایی__

شرط لازم و کافی این است که{TEX()} {n=4k} {TEX}یا{TEX()} {(k\in Z)n=4k+1} {TEX} باشد. و برای اثبات آن از مجموع درجات می توانید کمک بگیرید.

---

!قضیه

هرگراف خود مکمل همبند است.

فرض می کنیم گراف ساده{TEX()} {G} {TEX} خود مکمل است یعنی {TEX()} {G} {TEX} با {TEX()} {\overline{G}} {TEX} یکریخت است. باید نشان دهیم {TEX()} {G} {TEX} همبند است. ((برهان خلف)) را به کار می بریم یعنی فرض می کنیم {TEX()} {G} {TEX} ناهمبند است. در این صورت طبق قضیه قبل {TEX()} {\overline{G}} {TEX}همبند است. از طرفی می دانیم{TEX()} {G} {TEX}و{TEX()} {\overline{G}} {TEX} یکریختند. ضمناً‌ یکریختی حافظ همبندی است. بنابراین {TEX()} {G} {TEX} نیز باید همبند باشد که با فرض برهان خلف ( ناهمبندی {TEX()} {G} {TEX} ) تناقض دارد. بنابراین{TEX()} {G} {TEX} نمی تواند نا همبند باشد یعنی{TEX()} {G} {TEX} همبند است.

---

! پیوند های خارجی

[http://Olympiad.roshd.ir/computer/content/pdf/0083.pdf]

---

!همچنین ببینید

*((گراف خط یک گراف ))

*((گراف چرخ ))

#@^