المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۱:تئوری مقدماتی سوم:سوال ۲

سوال ۲

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

  • ‎ یک یال دلخواه را از مولفه حذف کنیم.
  • ‎ همه‌ی برگ‌‌ها را در مولفه حذف کنیم.

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

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

ابزار صفحه