====== سوال ۲ ======

در گراف زیر حداقل چند یال باید حذف کنیم تا طول هیچ دوری بیش از چهار نباشد؟
{{ :سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۲۷:2-1.png?200 |}}

  - $4$
  - $5$
  - $9$
  - $6$
  - $8$







<پاسخ>
گزینه (۱) درست است.


شکل را به صورت یک جدول فرض کرده و یک خانه‌ی گوشه به همراه یکی از خانه‌های مجاور آن در شکل را در نظر بگیرید. محیط این دو خانه، دوری به طول شش در گراف خواهد ساخت (مانند شکل زیر).
{{ :سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۲۷:2-2.png?200 |}}
در گراف، هشت دور به شکل گفته شده داریم. حذف هر کدام از یال‌های گراف،  حداکثر دو تا از این دورها را از بین خواهد برد. پس دست کم به چهار یال نیاز داریم. حال با حذف چهار یال  زیر، طول هیچ دوری بیش از چهار نخواهد بود:
{{ :سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۲۷:2-3.png?200 |}}
</پاسخ>
  * [[سوال ۱|سوال قبل]]
  * [[سوال ۳|سوال بعد]]