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



درخت زیر را در نظر بگیرید. یک یال را
**زرد**
می‌نامیم، اگر به یک رأس درجه‌ی ۱ وصل باشد. یک رأس را 
**شل**
می‌نامیم، اگر دست کم دو یال زرد به رئوس مسیر آن به ریشه (رأس بالا) وصل باشند (به جز یال خود رأس و یال متصل به ریشه). برای مثال $A$ در ابتدا شل است، زیرا  ۴ یال زرد به رئوس مسیر آن تا ریشه وصل هستند؛ امّا رأس $B$ در ابتدا شل نیست.
{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۷:p22-1.png?300 |}}
در هر مرحله می‌توان یک رأس شل در نظر گرفته و از درخت حذف کرد. توجه کنید ممکن است رأسی در ابتدا شل نباشد، امّا پس از تعدادی مرحله شل شود. حداکثر چند رأس می‌توان از درخت حذف کرد؟
  - ۹
  - ۱۶
  - ۱۰
  - ۷
  - ۱۳
<پاسخ>
 گزینه‌ی ۵ درست است.


اگر به ترتیب شماره‌های زیر، رئوس را حذف کنیم، ۱۳ رأس حذف می‌شوند:
{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۷:22-2.png?300 |}}
حال ثابت می‌کنیم هیچ‌گاه نمی‌توان  بیش از ۱۳ رأس حذف کرد. شکل زیر را در نظر بگیرید:
{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۷:22-3.png?300 |}}
رئوس قرمز و سبز و هم‌چنین دست کم یکی از دو فرزند هر کدام از رئوس سبز هیچ‌گاه حذف نمی‌شوند. این یک ناورداست (اگر در یک مرحله این حکم برقرار باشد، در مرحله‌ی بعد نیز برقرار است).
پس حداکثر ۱۳ رأس برای حذف شدن باقی می‌ماند.
</پاسخ>

  * [[سوال ۲۱|سوال قبل]]
  * [[سوال ۲۳|سوال بعد]]