سوالات المپیاد:دوره ی تابستان:دوره ی ۱۸:تئوری:سوال ۱۰
دوستی‌های ماندگار
تعاریف زیر در گراف‌های جهت‌دار و بدون‌دور ارائه شده است:
- رأس $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$ آن را دوست دارد.
الگوریتم خود را تحلیل و اثبات کنید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
