مسئله بیشینه جریان

در تئوری بهینه‌سازی، مسائل بیشینه جریان شامل پیدا کردن یک جریان عملی بیشینه از داخل یک شبکهٔ جریان تک-مبدأ و تک-مقصد است.

می‌توان به مسئلهٔ بیشینه جریان، به صورت حالت خاصی از مسائل پیچیده‌تر شبکهٔ جریان، مانند مسئلهٔ گردش، نگاه کرد. مقدار ماکسیمم یک جریان s-t (جریان از مبدأ به مقصد) برابر حداقل ظرفیت یک برش s-t (برشی که مبدأ را از مقصد جدا می‌کند) در شبکه است، همان‌طور که در قضیهٔ جریان بیشینه-برش کمینه ذکر شده است.

تاریخچه

مسئلهٔ بیشینهٔ جریان ابتدا توسط T. E. Harris و F. S. Ross در سال ۱۹۵۴ به عنوان مدل ساده شده‌ای از جریان رفت و آمد خط آهن شوروی مطرح شد. در ۱۹۵۵، .Lester R. Ford, Jr و Delbert R. Fulkerson اولین الگوریتم شناخته شده، الگوریتم فورد–فالکرسون را ایجاد کردند.

در طول زمان، تعداد زیادی راه حل بهبود یافته برای مسئلهٔ بیشینهٔ جریان پیدا شده است، به ویژه الگوریتم کوتاه‌ترین راه افزوده از Edmonds و Karp و به صورت مستقل از Dinitz، الگوریتم سد کردن جریان Dinitz، الگوریتم ارسال-برچسب Goldberg و Tarjan، و الگوریتم سد کردن دودویی جریان از Goldberg و Rao. الگوریتم جریان الکتریکی Madry، Kelner، Christano و Spielman یک جریان بیشینهٔ تقریباً بهینه می‌یابد اما فقط در گراف‌های بدون جهت کار می‌کند.

مسئلهٔ بیشینه جریان چند-مبدأ و چند-مقصد

می‌خواهیم جریان بیشینه را روی شبکهٔ  که دارای مجموعهٔ مبدأهای  و مجموعهٔ مقصدهای  (به جای تنها یک مبدأ و یک مقصد) است، پیدا کنیم. می‌توانیم مسئله چند-مبدأ و چند-مقصد را با افزودن یک مبدأ تثبیت شده که به تمام راس‌های  متصل است و یک مقصد تثبیت شده که به تمام راس‌های  متصل است (ابرمبدأ و ابرمقصد) و یال‌های آن‌ها ظرفیت بی‌نهایت دارند، به یک مسئلهٔ بیشینه جریان تبدیل کنیم.

مسئلهٔ بیشینه جریان با ظرفیت رأس

اگر شبکهٔ  را داشته باشیم که در آن علاوه بر یال‌ها، هر رأس هم ظرفیت دارد، یعنی نگاشت  که با  نمایش داده می‌شود به طوری که جریان f علاوه بر شرط ظرفیت و بقای جریان‌ها، شرط ظرفیت رأس را هم داشته باشد:
به بیان دیگر مقدار جریانی که از یک رأس می‌گذرد نمی‌تواند از ظرفیت آن بیشتر باشد. برای یافتن ماکسیمم جریان در  می‌توان با گسترش ، مسئله را به یک مسئلهٔ بیشینه جریان تبدیل کرد. ابتدا هر  با  و  جایگزین می‌شود که  متصل به یال‌هایی است که به  وارد می‌شود و  متصل به یال‌هایی است که از آن خارج می‌شوند، سپس ظرفیت  را به یالی نسبت می‌دهیم که  و  را شامل می‌شود (شکل ۴٫۴٫۱ را ببینید، ولی در نظر داشته باشید که جای  و  به اشتباه در آن جابه‌جا شده‌است). در این شبکهٔ گسترش یافته، شرط ظرفیت رأس برداشته شده است؛ بنابراین می‌توان با این مسئله مانند یک مسئلهٔ بیشینه جریان برخورد کرد.

بیشینه مسیر یال‌مجزا

برای پیدا کردن بیشینه تعداد مسیرهای یال‌مجزا از رأس  به رأس  در گراف جهت دار ، می‌توان مسئله را با ساختن شبکهٔ  از  با مبدأ  و مقصد  و نسبت دادن جریان واحد به هر یال، به یک مسئلهٔ بیشینه جریان تبدیل کرد.

بازی‌های حذفی بیسبال

در این مسئله،  تیم در یک لیگ به طور حذفی با یک‌دیگر مسابقه می‌دهند. در یک مرحلهٔ خاص،  تعداد بردها،  تعداد بازی‌های باقی‌مانده برای تیم ام، و  تعداد بازی‌های باقی‌مانده در مقابل تیم ام است. اگر تیمی شانس اول شدن از دست بدهد، از لیگ حذف خواهد شد. هدف این مسئله تعیین کردن تیم‌های حذف شده در هر زمان از فصل است. Schwartz برای این مسئله روشی پیشنهاد داد که این مسئله را به مسئلهٔ بیشینهٔ جریان تبدیل می‌کند. در این روش شبکه‌ای ساخته می‌شود که تعیین می‌کند آیا تیم  حذف می‌شود یا نه.

فرض کنید گراف  شبکه‌ای با  باشد که  و  به ترتیب مبدأ و مقصد را تعیین می‌کنند. یک رأس  را به طوری که  به گراف اضافه می‌کنیم و آن را با یالی با ظرفیت  به  وصل می‌کنیم که تعداد بازی‌های بین دو تیم  و  را نشان می‌دهد. هم چنین برای هر تیم  یک رأس ایجاد می‌کنیم و هر رأس  را به رأس‌های  و  وصل می‌کنیم تا تضمین کنیم یکی از آن‌ها برنده می‌شود. برای این یال‌ها ظرفیتی تعیین نمی‌کنیم. در انتها، وزن یال بین تیم  و مقصد  را wₖ+rₖ–wᵢ قرار می‌دهیم تا تعداد بردهای تیم i از wₖ+rₖ تجاوز نکند. مجموعهٔ تیم‌های شرکت‌کننده در لیگ را  می‌نامیم و . ادعا می‌کنیم تیم  حذف نمی‌شود اگر و تنها اگر اندازهٔ جریانی با مقدار  در شبکهٔ  وجود داشته باشد. در مقالهٔ مذکور نشان داده شده که این مقدار همان مقدار بیشینهٔ جریان از  به  است.

عدالت در اشتراک اتومبیل

مسئله این است که  نفر از یک ماشین در  روز به صورت اشتراکی استفاده می‌کنند. هر شرکت کننده می‌تواند در هر روز انتخاب کند که شرکت می‌کند یا خیر. هدف ما این است که عادلانه تصمیم بگیریم که در یک روز مشخص، چه کسی رانندگی می‌کند. راه حل به این صورت است:

می‌توانیم بر اساس تعداد افرادی که از ماشین استفاده می‌کنند تصمیم بگیریم، یعنی اگر  نفر از ماشین در یک روز استفاده می‌کنند، هر نفر به مقدار  مسئولیت دارد؛ بنابراین برای هر شخص ، اجبار رانندگی () به صورتِ ذکر شده است؛ بنابراین، شخص  فقط باید  بار در  روز رانندگی کند.

هدف این است که پی ببریم آیا چنین وضعیتی امکان‌پذیر است یا خیر. برای این منظور همان‌طور که در شکل نشان داده شده است، سعی می‌کنیم مسئله را به یک شبکه تبدیل کنیم.

حال می‌توان ثابت کرد که اگر جریان  وجود داشته باشد، آنگاه چنین وضعیت عادلانه‌ای و چنین جریانی با مقدار  همواره وجود دارد.