یال‌های مکمل و کامل کردن گراف

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

ایده

$G$ و $\overline{G}$ روی هم همهٔ یال‌های گراف کامل $K_{p}$ را می‌سازند:

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

یال‌هایی که باید به $G$ اضافه کنی تا کامل شود، دقیقاً یال‌های $\overline{G}$ هستند. اگر منتظم بودن یا جمع درجه‌های $G$ را داده‌اند، اول $q (G)$ را از جمع درجه‌ها بیاب.

نمونهٔ نهایی

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

اگردر گراف $G$ از مرتبهٔ $۸$ ، مجموع درجات $۴۰$ باشد، تعداد یال‌های گراف مکمل $G$ را به‌دست آورید.

از جمع درجه‌ها شمار یال‌های $G$ را بیاب.۰/۲۵ نمره
$۲ q = ۴۰ \Rightarrow q (G) = ۲۰$
$G$ و مکملش روی هم همهٔ یال‌های گراف کامل از مرتبهٔ $۸$ هستند.۰/۲۵ نمره
$q (G) + q (\overline{G}) = \frac{۸ \times ۷}{۲} = ۲۸ \Rightarrow ۲۰ + q (\overline{G}) = ۲۸$
$q (\overline{G})$ را بگیر.۰/۲۵ نمره
$q (\overline{G}) = ۲۸ - ۲۰ = ۸$

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

امتحان نهایی ۱۳

۷ سؤال دیگر