گراف جهت‌دار و بدون دور $G$ مفروض است. گرافی مثل $H$ با حداقل تعداد یال‌ها را که زیر گراف $G$ باشد و بستار متعدی‌اش با بستار متعدی $G$ برابر باشد، زیر گراف کاهش یافته‌ی $G$ می‌نامیم. (بستار متعدی گراف $G$، گرافی است که مجموعه‌ی راس‌هایش همان مجموعه‌ی راس‌های $G$ است و در آن از راسی مثل $u$ به راسی مثل $v$ یال وجود دارد، اگر و فقط اگر در گراف $G$ از $u$ به $v$ مسیری وجود داشته باشد.)

الف) ثابت کنید هر گراف جهت‌دار بی‌دور، فقط یک زیرگراف کاهش یافته دارد.

ب) الگوریتم سریعی از مرتبه‌ی $O(n^3)$ ارائه دهید که زیر گراف کاهش‌یافته‌ی یک گراف جهت‌دار بی‌دور را بیابد. (نیازی به برنامه نیست.)

• سوال بعد
• سوال قبل