سوال 4
حل تشریحی سوال شماره 4 ساختمان داده
کنکور دکتری مهندسی کامپیوتر 1398
4.
اگر ظرفیت همۀ یالها در یک شبکه برابر C باشد، زمان اجرای الگوریتم فورد - فالكرسون برای محاسبه شار بیشینه از مبدا s و به مقصد t در بدترین حالت کدام مورد خواهد بود؟
(فرض کنید تعداد رئوس و یالهای گراف به ترتیب n و m هستند و درجه خروجی s برابر k باشد. همچنین فرض کنید در هر مرحله الگوریتم بیشترین شار ممکن را از مسیر انتخاب شده عبور میدهد.
1)
O(kC+m+n)
2)
O(kC(m+n))
3)
O(C(m+n))
4)
O(k(m+n))
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،