مرتبه و اندازهٔ گراف

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

ایده

مرتبهٔ گراف تعداد رأس‌هاست و اندازهٔ آن تعداد یال‌ها. همهٔ رأس‌ها را بشمار، رأس تنها را هم، و هر یال را فقط یک بار.

p (G) = ∣ V (G) ∣, q (G) = ∣ E (G) ∣

یالی که رأسی را به خودش وصل کند «طوقه» است. گرافی با طوقه یا با دو یال بین یک جفت رأس «ساده» نیست، مثل گراف پل‌های کونیگسبرگ.

با توجه به گراف $G$ مقابل به سوالات زیر پاسخ دهید.

الف)

مرتبه و اندازه گراف را بنویسید.

همهٔ رأس‌های شکل را بشمار.۰/۲۵ نمره
$V (G) = {a, b, c, d, e, f, g} \Rightarrow p = ۷$
یال‌ها را رأس‌به‌رأس و بدون تکرار بشمار.۰/۲۵ نمره
$ab, a g, a e, b g, b e, ec, e d, e f, e g, g f \Rightarrow q = ۱۰$

۵ سؤال دیگر