====== یال‌های دو طرفه ======


فرض کنید الگوریتمی چند جمله‌ای داده شده است که گراف جهت‌دار و مسطح $G$ را به عنوان ورودی می‌گیرد و مینیمم تعداد یال از آن را تعیین می‌کند که با حذف آن‌ها هیچ دوری در گراف باقی نماند.

گراف جهت‌دار و مسطح $H$ داده شده است با استفاده از الگوریتم بالا یک الگوریتم چندجمله‌ای طراحی کنید که کم‌ترین تعداد یال از $H$ را دو طرفه کند به طوری که گراف به یک گراف قوی همبند تبدیل شود. یک گراف قوی همبند است که از هر راس به هر راس دیگر یک مسیر وجود داشته باشد.


<پاسخ>



</پاسخ>


  * [[سوال ۵|سوال بعد]]
  * [[سوال ۳|سوال قبل]]