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