المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

یک گراف ساده‌ی ‎$n$ رأسی داریم. در هر مرحله می‌توانیم یال‌های یک مسیر از گراف را حذف کنیم.

  1. ثابت کنید در حداکثر ‎$O(n\sqrt{n})$‎ مرحله می‌توانیم تمام یال‌های گراف را حذف کنیم.
  2. ثابت کنید در حداکثر ‎$O(n\log n)$‎ مرحله می‌توانیم تمام یال‌های گراف را حذف کنیم.

ابزار صفحه