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