المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۳۰:سوال چهار

بخش‌بندی گراف (۲۰ نمره)

زاریچ که زندگی خود را وقف شکست ویروس کرونا کرده است، از روی نقشه‌ی شهرهای آلوده یک گراف ساده‌ی ۳۰ رأسی ساخته است. او می‌خواهد رأس‌های این گراف را به تعدادی بخش افراز کند، طوری که بین رأس‌های درون هر بخش هیچ یالی وجود نداشته باشد (هر بخش یک مجموعه‌ی مستقل باشد). او پس از بررسی‌های فراوان فهمیده است که می‌تواند رأس‌های گراف را به ۱۰ بخش با شرایط بالا تقسیم کند،‌ اما امکان انجام این کار برای ۹ بخش وجود ندارد.

الف) ثابت کنید گراف زاریچ دوری با حداکثر ۸ رأس دارد. (۱۰ نمره)

ب) ثابت کنید گراف زاریچ دوری با حداکثر ۵ رأس دارد. (۱۰ نمره؛ با حل این بخش، نمره‌ی بخش الف را نیز دریافت می‌کنید.)

پاسخ


ابزار صفحه