محسن دستگاهی دارد که به عنوان ورودی یک گراف می‌گیرد و در خروجی گرافی دیگر به او می‌دهد!

کارهایی که دستگاه او می‌تواند انجام دهد به شرح زیر است:

• ببین دو رأس مجاور انتخاب شده یک رأس اضافه کند.
• رأس جدیدی را به دو رأس مجاور انتخاب شده متصل نماید.

محسن یک بازی خطرناک با دستگاه خود شروع می‌کند. به این ترتیب که با یک گراف مثلث $(C_3)$ شروع می‌کند و هر بار گراف خود را به دست‌گاه می‌دهد و گراف خروجی را برای دور بعد در نظر می‌گیرد و هر موقعی که از بازی خسته شود، گراف‌ش را به عنوان نتیجه‌ی بازی اعلام می‌کند.

کدام یک از شکل‌های زیر می‌تواند نتیجه‌ی بازی محسن با دستگاه خود باشد؟

شکل الف)

شکل ب)

شکل ج)

1. الف
2. ج
3. الف و ج
4. ب و ج
5. هیچ‌کدام

عدد هم‌بندی یک گراف را حداقل تعداد رأس‌هایی در نظر می‌گیریم که باید از آن گراف حذف شود تا آن گراف ناهم‌بند شود. (توجه کنید به طور قراردادی عدد هم‌بندی را برای یک گراف کامل $n$ رأسی برابر $n-1$ در نظر می‌گیریم).

در بین همه‌ی گراف‌هایی که می‌توانند نتیجه‌ی بازی خطرناک محسن باشند، بیش‌ترین عدد همبندی چند است؟

1. $2$
2. $3$
3. $4$
4. $5$
5. تا هر عددی می‌تواند زیاد شود

گراف مسطح به گرافی می‌گوییم که بتوان آن را در صفحه کشید، بدون آن که یال‌هایش یک‌دیگر را قطع کنند. در این وضعیت، صفحه به ناحیه‌هایی تقسیم می‌شود. به غیر از ناحیه‌ی نامحدودی که اطراف گراف را در بر می‌گیرد، بقیه‌ی ناحیه‌ها را محدود می‌نامند. مثلاً گراف شکل الف در سؤال قبل، دارای ۴ ناحیه‌ی محدود است. دو ناحیه با هم مجاورند اگر حداقل در یک یال با هم مرز مشترک داشته باشند.

عدد رنگی سطحی را برای گراف‌های مسطح، حداقل تعداد رنگ‌های لازم برای رنگ کردن ناحیه‌های محدود گراف تعریف می‌کنیم؛ به طوری که هیچ دو ناحیه‌ی محدود مجاوری هم‌رنگ نباشند.

در بین همه‌ی گراف‌هایی که می‌توانند نتیجه‌ی بازی خطرناک محسن باشند، بیش‌ترین عدد رنگی سطحی چند است؟

1. $2$
2. $3$
3. $4$
4. $5$
5. ممکن است گرافی نامسطح نتیجه‌ی این بازی خطرناک باشد

• سوال بعد
• سوال قبل