سوالات المپیاد:دوره ی تابستان:دوره ی ۱۸:تئوری:سوال ۱۰
دوستی‌های ماندگار
تعاریف زیر در گراف‌های جهت‌دار و بدون‌دور ارائه شده است:
- رأس v، رأس u را «دوست دارد» اگر و فقط اگر یک مسیر جهت‌دار از v به u موجود باشد.
- دو رأس v1 و v2 با هم «قهر» هستند، اگر و فقط اگر نه v1، v2 را دوست داشته باشد، نه v2، v1 را.
- «عرضِ» گراف سایز بزرگ‌ترین زیرمجموعه از رئوس است که اعضای آن زیرمجموعه دوبه‌دو با هم قهر باشند.
گراف جهت‌دار و بدون‌دور G با n رأس و e یال داده شده است. می‌دانیم عرض G برابر w است. الگوریتمی از زمان اجرای O(n3) ارائه کنید که با گرفتن گراف G،، گراف G′ را به ما برگرداند که شرایط زیر را داشته باشد.
- تعداد رئوس G′ حداکثر n باشد.
- تعداد یال‌های G′ کم‌تر از nw باشد.
- به‌ازای هر دو رأس u و v که بگیریم، راس v، راس u را در G′ دوست داشته باشد اگر و فقط اگر در G آن را دوست دارد.
الگوریتم خود را تحلیل و اثبات کنید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
