گراف مکمل

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 30 شهریور 1400
دسته‌بندی: گراف
امتیاز:
بازدید: 34 مرتبه

اگر G=(V,E) یک گراف ساده باشد، مکمل گراف G را به‌صورت زیر نشان می‌دهند:

G°=G¯=(V,E¯)

گراف مکمل G¯ از روی گراف ساده G به‌صورت زیر ساخته می‌شود: 

مجموعه راس‌های G¯ همان مجموعه راس‌های G است ولی دو راس متمایز v1 و v2 از G¯ به‌وسیله یک یال به‌هم وصل می‌شود اگر و فقط اگر v1 و v2 به‌وسیله یالی در G به‌هم وصل نشده باشد.

به‌عنوان نمونه گراف ساده G و گراف مکمل آن یعنی G¯ به‌موازات هم رسم شده‌اند:

گراف مکمل - پیمان گردلو        

تمرین

نمودار گراف G در شكل زیر رسم شده است:

گراف مکمل - پیمان گردلو

نمودار مكمل G را رسم كنيد. 

برای رسم G¯ به تعداد راس های گراف G راس درنظر می‌گيريم، سپس بين هر دو راسی كه در گراف G به‌هم متصل نشده‌اند، يک يال رسم می‌كنيم، بدين ترتيب نمودار گراف G¯ به‌صورت زير است:


گراف مکمل - پیمان گردلو   

تمرین

فرض كنيد G=(V,E) يک گراف ساده است، كدام عبارت صحيح است؟  

G¯=(V¯,E¯)    1G¯=(V¯,E)    2G¯=(V,E¯)    3G¯=(V,E)    4

گزينه 3 صحيح است.


چون از گراف مكمل G¯ چنين بر می‌آيد كه مجموعه راس آن همان مجموعه راس گراف G است ولی مجموعه يالی آن مكمل مجموعه يالی گراف G می‌باشد، لذا G¯=(V,E¯) به‌طوری‌كه:


v1,v2V,  E¯=v1v2v1v2E

تمرین

فرض كنيد گراف ساده G پنجاه وشش يال و G¯ هشتاد يال دارد، در اين‌صورت مرتبه G را به‌دست آورید.   

qG+qG¯=p256+80=p(p1)2p2p272=0p=17p=16


جواب p=17  قابل قبول است.

برای ارسال نظر وارد سایت شوید