سوال ۲

در گراف زیر حداقل چند یال باید حذف کنیم تا طول هیچ دوری بیش از چهار نباشد؟

  1. $4$
  2. $5$
  3. $9$
  4. $6$
  5. $8$

پاسخ

گزینه (۱) درست است.

شکل را به صورت یک جدول فرض کرده و یک خانه‌ی گوشه به همراه یکی از خانه‌های مجاور آن در شکل را در نظر بگیرید. محیط این دو خانه، دوری به طول شش در گراف خواهد ساخت (مانند شکل زیر). در گراف، هشت دور به شکل گفته شده داریم. حذف هر کدام از یال‌های گراف، حداکثر دو تا از این دورها را از بین خواهد برد. پس دست کم به چهار یال نیاز داریم. حال با حذف چهار یال زیر، طول هیچ دوری بیش از چهار نخواهد بود: