گراف‌ها: مجموعه‌های احاطه‌گر
ایستگاه‌ها را طوری بگذارید که هر نقطهٔ نقشه پوشیده شود و کمترین تعداد ممکن را پیدا کنید: عدد احاطه‌گری گراف.
📖 از اینجا شروع کنید: گام‌های «درس» را به ترتیب بخوانید (۱، ۲، ۳ …) و به هر پرسش جواب بدهید. بعد با «تمرین» ادامه دهید.
- ایران: پایهٔ ۱۲
- روسیه: صنف ۷
- فرانسه: صنف ۱۲
رهنما
این کارگاه یک بخش اضافی است و در کتاب‌های درسی افغانستان نیست. فرض کنید در بعضی چهارراه‌های یک شهر دستگاه خودپرداز می‌گذاریم. هر چهارراه یا باید خودپرداز داشته باشد یا یک سرک از آن دور باشد. این را با یک گراف نشان می‌دهیم: چهارراه‌ها رأس اند و سرک‌ها یال. رأسی که در مجموعه است، خودش و رأس‌های مجاورش را احاطه می‌کند.
مجموعه‌ای از رأس‌ها احاطه‌گر است اگر هر رأس گراف یا در مجموعه باشد یا مجاور یکی از رأس‌های مجموعه. کمترین تعداد رأس یک مجموعهٔ احاطه‌گر، عدد احاطه‌گری است و γ(G) نوشته می‌شود؛ مجموعهٔ احاطه‌گری با همین تعداد، احاطه‌گر مینیمم است.
مینیمال و مینیمم فرق دارند. مجموعهٔ مینیمال با برداشتن هر رأس دیگر احاطه‌گر نمی‌ماند؛ مجموعهٔ مینیمم کمترین تعداد رأس ممکن را دارد. هر رأس حداکثر Δ + ۱ رأس را احاطه می‌کند (Δ بزرگ‌ترین درجه است)، پس n رأس دست‌کم به سقفِ n تقسیم بر Δ + ۱ رأس نیاز دارد. سقف یعنی گرد کردن به بالا.