سوال ۸۳ کنکور ارشد علوم کامپیوتر ۱۴۰۰
اهمیت
۰/۵
کدام گزاره (گزارهها) درست است؟
الف) اگر در الگوریتم فورد ـ فالکرسون مسیرهای افزایشی را به دلخواه انتخاب کنیم و نیز ظرفیت همه یالهای شبکه عدد طبیعی باشد، حتماً الگوریتم پس از متناهی گام متوقف میشود. (به پایان میرسد.)
ب) مسئله کولهپشتی ۰ و ۱ دارای الگوریتم حریصانه با زمان چندجملهای است.
پاسخ صحیح: گزینهٔ A — ۱) فقط (الف)
پاسخ تشریحی
We evaluate each claim independently.
ادامهٔ پاسخ تشریحی ویژهٔ مشترکان است.
مشاهدهٔ پاسخ کامل#ford-fulkerson#max-flow#augmenting-path#integer-capacities#0-1-knapsack#greedy