المپدیا

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

ابزار کاربر

ابزار سایت


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

دوستی‌های ماندگار

تعاریف زیر در گراف‌های جهت‌دار و بدون‎‌دور ارائه شده است:

  • رأس ‎$v$‎، رأس ‎$u$‎ را ‎«دوست دارد‎» اگر و فقط اگر یک مسیر جهت‌دار از ‎$v$‎ به ‎$u$‎ موجود باشد.
  • دو رأس ‎$v_1$‎ و ‎$v_2$‎ با هم ‎«قهر»‎ هستند، اگر و فقط اگر نه ‎$v_1$‎، ‎$v_2$‎ را دوست داشته باشد، نه ‎$v_2$‎، ‎$v_1$‎ را.
  • «عرضِ»‎ گراف سایز بزرگ‌ترین زیرمجموعه از رئوس است که اعضای آن زیرمجموعه دوبه‌دو با هم قهر باشند.

گراف جهت‌دار و بدون‌دور ‎$G$‎ با ‎$n$‎ رأس و ‎$e$‎ یال داده شده است. می‌دانیم عرض ‎$G$‎ برابر ‎$w$‎ است. الگوریتمی از زمان اجرای ‎$O(n^3)$‎ ارائه کنید که با گرفتن گراف ‎$G$،‎، گراف ‎$G'$‎ را به ما برگرداند که شرایط زیر را داشته باشد.

  • ‎ تعداد رئوس ‎$G'$‎ حداکثر ‎$n$‎ باشد.
  • ‎ تعداد یال‌های ‎$G'$‎ کم‌تر از ‎$nw$‎ باشد.
  • به‌ازای هر دو رأس ‎$u$‎ و ‎$v$‎ که بگیریم، راس $v$، راس $u$‎ را در ‎$G'$‎ دوست داشته باشد اگر و فقط اگر در ‎$G$‎ آن را دوست دارد.

الگوریتم خود را تحلیل و اثبات کنید.


ابزار صفحه