حل تشریحی سوال شماره 58 طراحی الگوریتم
کنکور ارشد مهندسی کامپیوتر 1398
58.
فرض کنید در یک شبکه شار برای محاسبه شار از راس s به راس t از الگوریتم زیر استفاده کنیم.
شار عبوری از همه یال‌ها را صفر قرار میدهیم. در هر مرحله یک مسیر از s به t انتخاب میکنیم که یال‌های مسیر همچنان ظرفیت خالی داشته باشند. شار همه یال‌های این مسیر را به اندازه یکسان افزایش میدهیم طوری که حداقل یک یال مسیر ظرفیتش تکمیل شود. این کار را انقدر ادامه میدهیم تا چنین مسیری یافت نشود.
درمورد اندازه شار حاصل از این الگوریتم کدام مورد درست است؟
1)
با شار بیشینه برابر است
2)
حداقل به اندازه نصف شار بیشینه است
3)
حداقل به اندازه یک چهارم شار بیشینه است
4)
میتوان شبکه‌ای مثال زد که برای ان خروجی الگوریتم فوق کمتر از 0/0001 شار بیشینه باشد
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،