عدد احاطه‌گری با دلیل

نهایی: در ۲۲ امتحان از ۲۶، روی‌هم ۲۶ نمرهکنکور: ۱ سؤال

ایده

عدد احاطه‌گری را با دو نابرابری می‌گیریم. رأسی با درجهٔ $d$ دقیقاً $d + ۱$ رأس را احاطه می‌کند، پس با $n$ رأس و بیشترین درجهٔ $Δ$ کمتر از $⌈ n / (Δ + ۱)⌉$ رأس کافی نیست ( $⌈ x ⌉$ یعنی گرد کردن به بالا). اگر مجموعهٔ احاطه‌گری به همین اندازه یافتی، همان $γ (G)$ است؛ اگر نشد، با رأس‌هایی که هر کدام رأس جداگانه‌ای لازم دارند نشان بده کمتر ممکن نیست.

⌈ \frac{n}{Δ + ۱} ⌉ \leq γ (G) \leq ∣ D ∣

نمونهٔ نهایی

نهایی شهریور ۱۴۰۵، عصر، سؤال ۱۰۱/۲۵ نمره

عدد احاطه‌گری گراف زیر را به‌دست آورید و ادعای خود را ثابت کنید.

گراف با رأس‌های a تا i (مسیر c تا g با دو برگ در هر سر)

کران پایین را از $n$ و $Δ$ بگیر؛ گراف نُه رأس دارد و بیشترین درجه‌اش $۳$ است.۰/۵ نمره
$γ (G) \geq ⌈ \frac{۹}{۳ + ۱} ⌉ = ⌈ ۲/۲۵ ⌉ = ۳$
یک مجموعهٔ احاطه‌گر سه‌عضوی نشان بده.۰/۲۵ نمره
$N [c] \cup N [e] \cup N [g] = {a, b, c, d} \cup {d, e, f} \cup {f, g, h, i} = V$
کران بالا و کران پایین را کنار هم بگذار.۰/۵ نمره
$۳ \leq γ (G) \leq ۳ \Rightarrow γ (G) = ۳$

عدد احاطه‌گری با دلیل

ایده

نمونهٔ نهایی

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

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

کنکور ۱