جریان بیشینه و تطابق¶
با مساله جریان بیشینه در فصل قبل آشنا شدیم. در این جا با یکی از کاربرد های دیگر این مساله که حل مساله تطابق و تعمیم های آن است آشنا می شویم.
حل مساله تطابق بیشینه در گراف دو بخشی¶
این مساله را می توان به کمک مساله جریان بیشینه حل کرد. به این صورت که به گراف دوبخشی دو راس مبدا و مقصد اضافه کنید و راس مبدا را به همه رئوس بخش بالا با ظرفیت یک و رئوس بخش پایین را به راس مقصد با وزن ۱ یال بدهید. به ازای هر یال گراف نیز یک یال با وزن یک از راس بالا به پایین بکشید. ( مانند شکل )
در این گراف بزرگترین تطابق همان جریان بیشینه است.
تطابق بیشینه وزن دار¶
در این مساله هر یال ارزشی دارد و ارزش یک تطابق برابر جمع ارزش یال های آن است. مسائل مختلفی را می توان برای تطابق وزن دار مطرح کرد. مانند تطابق با بیشترین ارزش، تطابق بیشینه با بیشترین ارزش یا تطابق با اندازه خاص و بیشترین ارزش. این مسائل را می توان به کمک تعمیمی از مساله جریان بیشینه که در زیر بررسی می کنیم حل کرد. خوب است که حین خواندن سعی کنید که خودتان به این مساله فکر کنید و قبل از رسیدن به بخش راه حل این سوال آن را حل کرده باشید.
جریان با کمترین هزینه¶
در این مساله هدف پیدا کردن جریانی است که کمترین هزینه را داشته باشد. هزینه هر جریان برابر جمع جریان گذرنده از هر یال * هزینه آن یال به ازای تمام یال هاست. می خواهیم به ازای تمام مقادیر صحیح جریان ( از ۰ تا جریان بیشینه ) کمینه هزینه را به دست بیاوریم.
راه حل¶
از روشی مشابه روش فورد فلکرسون که در فصل قبل آموختیم استفاده می‌کنیم. با این تفاوت که به جای انتخاب یک مسیر دلخواه، مسیری که کمترین هزینه را دارد را انتخاب می‌کنیم و سپس یک واحد جریان را از آن می گذرانیم. این کار را تا زمانی که دیگر نتوان جریانی گذراند ادامه می‌دهیم. در هر مرحله هزینه به دست آمده کمینه هزینه ممکن برای آن مقدار جریان است. طبق درستی الگوریتم فورد، این الگوریتم جواب را تا جریان بیشینه به دست می‌آورد.
اثبات بهینگی¶
مانند اثبات درستی الگوریتم فورد، می‌توان ثابت کرد که در هر مرحله، اگر f مقدار جریان هدف و c هزینه آن باشد و کوتاه ترین مسیر از مبدا به مقصد x باشد، در گراف ساخته شده هم f-1 مقدار جریان هدف باشد، مینیمم هزینه ای که می توان با آن این مقدار جریان را عبور داد، c-x است.
تحلیل پیچیدگی¶
برای به دست آوردن کوتاه ترین مسیر، می توان از الگوریتم spfa استفاده کرد ( چون یال منفی داریم نمی توان از الگوریتم دایسترا استفاده کرد. ) که پیچیدگی زمانی \(O(E)\) دارد. پس پیچیدگی زمانی کل از \(O(fE)\) است.
راه حل تطابق بیشینه وزن دار¶
یک گراف مانند بالا می سازیم با این تفاوت که یال های مبدا و مقصد را با ظرفیت بینهایت قرار می‌دهیم و یال های وسط را با ظرفیت یک و هزینه اش را برابر وزن یال قرار می دهیم. سپس با الگوریتم جریان با کمترین هزینه می‌توان تمام مسائل بالا را پاسخ گفت.
این کتاب توسط مشارکت کنندگان شاززز به وجود آمده است.
این کتاب عمومی است و تحت پروانه cc-by-sa در دسترس است.
آخرین به روز رسانی در ژوئن 09, 2022.
