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

درختی داریم که ‎$n$‎  راس دارد. در هر مرحله می‌توانیم به ازای هر مولفه از این درخت  دقیقا یکی از ‎۲‎ کار زیر را انجام دهیم.
  * ‎ یک یال دلخواه را از مولفه حذف کنیم.
  * ‎ همه‌ی برگ‌‌ها را در مولفه حذف کنیم.

دقت کنید که در یک مرحله می‌توان روی دو مولفه کار متفاوتی انجام داد. ثابت کنید:

  - به ازای هر درخت می توان مراحل را طوری انجام داد که در ‎$O(\sqrt{n})$‎ مرحله همه ی یال‌ها حذف بشوند.
  - به ازای هر ‎$n$‎  مثالی بزنید که  به ‎$\Omega(\sqrt{n})$‎  مرحله نیاز باشد تا همه‌ی یال‌ها حذف شوند. 


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