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

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

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

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

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

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

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