سوال ۱۲۰ کنکور ارشد علوم کامپیوتر ۱۴۰۱
اهمیت
۰/۵
دو عبارت زیر را در نظر بگیرید (گراف‌ها ساده هستند):
(الف) فرض کنیم G یک گراف از مرتبه n ≥ ۱۱ باشد. در این‌صورت حداقل یکی از G یا G̅ غیرمسطح است.
(ب) فرض کنیم G یک گراف همبند مسطح از مرتبه n < ۱۲ باشد. در این‌صورت ۴ ≥ δ(G).
کدام‌یک از این دو عبارت صحیح است؟ (دلتای کوچک به معنی کمترین درجه رأس‌های گراف است.)
پاسخ صحیح: گزینهٔ C — هر دو
پاسخ تشریحی
Both statements follow from the planar edge bound: a simple planar graph on vertices has at most edges (a consequence of Euler's formula …
ادامهٔ پاسخ تشریحی ویژهٔ مشترکان است.
مشاهدهٔ پاسخ کامل#graph-theory#planar-graph#euler-formula#graph-complement#minimum-degree#edge-bound