رسم مکمل

نهایی: در ۲ امتحان از ۲۶، روی‌هم ۱/۲۵ نمره

ایده

مکمل $\overline{G}$ همان رأس‌های $G$ را دارد و دو رأس در آن یال دارند اگر و فقط اگر در $G$ یال نداشته باشند. پس همهٔ جفت‌های رأس را یکی‌یکی نگاه کن و فقط جفت‌هایی را وصل کن که در $G$ یال نیستند. برای اطمینان، شمار یال‌های دو گراف باید روی هم این شود:

q (G) + q (\overline{G}) = \frac{p ( p - ۱ )}{۲}

نمونهٔ نهایی

نهایی دی ۱۴۰۲، سؤال ۸۰/۷۵ نمره

مکمل گراف $G$ که در شکل زیر آمده است را رسم کنید.

گراف با رأس‌های a، b، c، d و e و یال‌های ab، ac، ad، ae، bd، de و ce

جفت‌های رأس را نگاه کن و فقط آنهایی را وصل کن که در $G$ یال نیستند؛ رأس $a$ با همهٔ رأس‌ها یال دارد، پس در مکمل تنها می‌ماند.۰/۷۵ نمره
$E (G) E (\overline{G}) = {ab, a c, a d, a e, b d, d e, ce} = {b c, b e, c d}$

رسم مکمل

ایده

نمونهٔ نهایی

همهٔ سؤال‌های این تیپ

امتحان نهایی ۲