چرا مساله min cut با max flow یکسان هست؟ - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۲۰ نفر آنلاین
۲ عضو و ۱۱۸ مهمان در سایت حاضرند

چرا مساله min cut با max flow یکسان هست؟

0 امتیاز
45 بازدید
مساله max cut این هست که در یک network یال هایی را حذف کنید به شکلی که منبع s و راس مقصد t از هم جدا شوند ( ودر مجموع وزن این یال ها باید مینیمم شود )

و max flow این هست که در یک network می خواهیم بیشترین جریان بین دو راس منبع s و راس مقصد t را پیدا کنیم .

حالا من متوجه نمیشم چرا این 2 با هم یکسان هستند (توضیحات CLRS هم زیاد قابل فهم نبود ) کسی میتونه به شکل ساده تر توضیح بده :(
سوال شده دی 18, 1393  بوسیله ی PSPCoder (امتیاز 1,411)   2 12 47

لطفا وارد شوید یا ثبت نام کنید برای جواب دادن به این سوال.

...