گراف همبند و بدون دور را درخت گویند. درخت $T$ را از راس $r$ به این صورت ریشه دار می‌کنیم که درخت را از راس $r$ آویزان می‌کنیم و تمام یال ها را از بالا به پایین جهت دار می‌کنیم. به بیانی دیگر یال‌های درخت را به این صورت جهت دار می‌کنیم که تمام یال‌های متصل به $r$ را از $r$ به سمت بیرون جهت می‌دهیم، و بقیه‌ی یال ها را طوری جهت دهی می‌کنیم که تعداد یال‌های وارد شده به هر راس به غیر از $r$ برابر ۱ شود.دقت کنید که در این صورت تعداد یال‌های وارد شده به $r$ برابر صفر است. فاصله ریشه تا راس دلخواه $i$، برابر تعداد یال هایی است که برای رسیدن از ریشه به راس $i$ طی میکنیم. برای مثال درخت شکل زیر را از راس سیاه رنگ ریشه دار کرده ایم. هم چنین فاصله بعضی از راس ها تا ریشه در شکل نشان داده شده است.

هدف پاک کردن یال‌های یک درخت ریشه دار در کمترین تعداد مرحله است. در هر مرحله مجاز به انجام یکی از دو عملیات زیر برای هر درخت ریشه دار باقی مانده هستیم:

• عملیات اول: تمام یال‌های متصل به ریشه را پاک کن.
• عملیات دوم: یکی از راس هایی که بیشترین فاصله را تا ریشه دارند مانند $i$ انتخاب کن. از ریشه و از روی یال ها و در جهت یال ها به سمت $i$ حرکت کن و یال هایی که از آن‌ها عبور کرده ای را پاک کن.

در حقیقت در هر مرحله می‌توان بر روی هر درخت ریشه دار باقی مانده، هر یک از عملیات اول یا دوم را انجام داد. دقت کنید که با پاک شدن یال ها، هر درخت ریشه دار به‌یک یا چند درخت ریشه دار تبدیل می‌شود. برای مثال در شکل تمام یال‌های درخت اولیه در ۳ مرحله پاک شده اند. در این شکل ریشه‌ی درخت ها با رنگ سیاه نشان داده شده اند. دقت کنید که بعد از مرحله‌ی اول درخت ریشه دار اولیه با ۱۲ راس، به ۴ درخت ریشه دار با ۳، ۱، ۱ و ۷ راس تبدیل شده است.

الف) یک درخت ریشه دار با ۱۰۰ راس داده شده است. روشی ارائه دهید که در ۱۴ مرحله تمام یال‌های آن را پاک کند.

ب) یک درخت ریشه دار با ۱۰۰ راس مثال بزنید که در کمتر از ۱۰ مرحله نتوان تمام یال‌های آن را پاک کرد.