KonkurStudy

سوال ۸۳ کنکور ارشد علوم کامپیوتر ۱۴۰۰

اهمیت
۰/۵

کدام گزاره (گزاره‌ها) درست است؟

الف) اگر در الگوریتم فورد ـ فالکرسون مسیرهای افزایشی را به دلخواه انتخاب کنیم و نیز ظرفیت همه یال‌های شبکه عدد طبیعی باشد، حتماً الگوریتم پس از متناهی گام متوقف می‌شود. (به پایان می‌رسد.)

ب) مسئله کوله‌پشتی ۰ و ۱ دارای الگوریتم حریصانه با زمان چندجمله‌ای است.

#ford-fulkerson#max-flow#augmenting-path#integer-capacities#0-1-knapsack#greedy