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

مثالی از یک شبکه جریان با بیشینه جریان. مبدا و مقصد است. اعداد نمایانگر جریان و ظرفیت اند.
در تئوری بهینه‌سازی، مسائل بیشینه جریان شامل پیدا کردن یک جریان عملی بیشینه از داخل یک شبکه جریان تک-مبدا و تک-مقصد است.
می‌توان به مسئله بیشینه جریان، به صورت حالت خاصی از مسائل پیچیده‌تر شبکه جریان، مانند مسئله گردش، نگاه کرد. مقدار ماکسیمم یک جریان 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 یک جریان بیشینه تقریبا بهینه می‌یابد اما فقط در گراف‌های بدون جهت کار می‌کند.
تعریف
یک شبکه جریان با مبدا و مقصد . اعداد کنار یال‌ها ظرفیت هستند.
فرض کنید یک شبکه است با که به ترتیب مبدا و مقصد هستند.
ظرفیت یک یال، نگاشت است که با یا نمایش داده می‌شود، و نشان دهنده بیشینه مقدار جریانی است که می‌تواند از یال بگذرد.
یک جریان ، نگاشت است که با یا نمایش داده می‌شود و دارای دو شرط زیر است:
به ازای هر (شرط ظرفیت: جریان یک یال نمی‌تواند از ظرفیتش بیشتر باشد)
به ازای هر (بقای جریان‌ها: جمع جریان‌های ورودی یک راس باید با جمع جریان‌های خروجی از آن برابر باشد، به جز در راس‌های مبدا و مقصد)
مقدار جریان به صورت تعریف می‌شود که ، مبدا است. مقدار جریان، نشان‌دهنده میزان جریان گذرنده از مبدا به مقصد است.
مسئله بیشینه جریان ، بیشینه کردن است، یعنی هدایت بیش‌ترین جریان ممکن از به .
راه‌حل‌ها
می‌توان گراف باقیمانده را تعریف کرد تا راهی اصولی برای جستجو کردن عملیات‌های جلو-عقب برای یافتن بیشینه جریان فراهم کند.
اگر شبکه جریان و جریان روی را داشته باشیم، ، گراف باقیمانده را با توجه به اینگونه تعریف می‌کنیم:
مجموعه راس‌های همانند است.
هر راس از ، دارای ظرفیت است.
هر راس از ، دارای ظرفیت است.
الگوریتم‌های حل مسئله بیشینه جریان در جدول زیر نشان داده شده‌است.
روش
پیچیدگی
توضیح
برنامه‌نویسی خطی
شرط‌ها توسط تعریف جریان مجاز داده شده‌اند. برنامه خطی را اینجا ببینید.
الگوریتم فورد-فالکرسون
تا جایی که مسیری باز در گراف باقی مانده وجود دارد، کمینه ظرفیت‌های گراف باقی مانده را به مسیر می‌فرستد.
این الگوریتم فقط زمانی کار می‌کند که همه وزن‌ها عدد صحیح باشند، در غیر این صورت ممکن است مقدار بیشینه برگردانده نشود.
الگوریتم Edmonds Karp
مدل خاصی از الگوریتم فورد-فالکرسون، که با جستجوی سطح اول مسیرهای اضافه شده را پیدا می‌کند.
الگوریتم سد جریان Dinitz
این الگوریتم در هر مرحله یک گراف لایه‌ای را به وسیله جستجوی سطح اول روی گراف باقیمانده می‌سازد. بیشینه جریان در یک گراف لایه‌ای در (O(VE محاسبه می‌شود، و بیشترین تعداد مرحل n-1 است. الگوریتم دینیک در شبکه‌های دارای ظرفیت‌های واحد، در به پایان می‌رسد.
الگوریتم ارسال-برچسب عمومی
الگوریتم ارسال-برچسب از یک پیش‌جریان (یک تابع جریان با امکان افزایش در راس‌ها) پشتیبانی می‌کند. الگوریتم اجرا تا وقتی که راسی با افزایش مثبت (یک راس فعال در گراف) وجود دارد اجرا می‌شود. عمل push جریان را روی یک یال باقیمانده افزایش می‌دهد، و یک تابع ارتفاع روی راس‌ها کنترل می‌کند که کدام یال باقیمانده می‌تواند push شود. استفاده درست از این توابع تضمین می‌کنند که جریان به دست آمده یک جریان بیشینه است.
الگوریتم ارسال-برچسب عمومی همراه با قانون انتخاب راس FIFO
این الگوریتم همواره آخرین راس فعال را انتخاب می‌کند و عمل push را تا زمانی که افزایش مثبت است یا یک یال باقیمانده مجاز از این راس وجود دارد، انجام می‌دهد.
الگوریتم سد جریان Dinitz به همراه درخت پویا
داده ساختار درخت پویا سرعت محاسبه بیشینه جریان را در گراف لایه‌ای تا افزایش می‌دهد.
الگوریتم ارسال-برچسب عمومی همراه با درخت پویا
این الگوریتم با توجه به تابع ارتفاع، درختی با اندازه محدود روی گراف باقی‌مانده می‌سازد. این درخت‌ها امکان اعمال push چندسطحی را فراهم می‌کنند.
الگوریتم سد جریان دودویی
مقدار U به بیشینه ظرفیت شبکه وابسته است.
الگوریتم MPM (مخفف Pramodh-Kumar, Malhotra و Maneshwari)
به مراجعه کنید.
الگوریتم KRT + Jim Orlins (مخفف Rao, King و Tarjan)
مسئله بیشینه جریان را در زمان برای حل می‌کند در حالی که KRT آن را در زمان برای حل می‌کند.
قضیه جریان انتگرال
قضیه جریان انتگرال می‌گوید:
اگر هر یال در شبکه جریان ظرفیت انتگرالی داشته باشد، آنگاه یک جریان ماکسیمال انتگرالی وجود دارد.
کاربرد
مسئله بیشینه جریان چند-مبدا و چند-مقصد
شکل ۴٫۱٫۱. تبدیل یک مسئله بیشینه جریان چند-مبدا چند-مقصد به یک مسئله بیشینه جریان تک-مبدا تک-مقصد.
می‌خواهیم جریان بیشینه را روی شبکه که دارای مجموعه مبداهای و مجموعه مقصدهای (به جای تنها یک مبدا و یک مقصد) است، پیدا کنیم. می‌توانیم مسئله چند-مبدا و چند-مقصد را با افزودن یک مبدا تثبیت شده که به تمام راس‌های متصل است و یک مقصد تثبیت شده که به تمام راس‌های متصل است (ابرمبدا و ابرمقصد) و یال‌های آن‌ها ظرفیت بی‌نهایت دارند، به یک مسئله بیشینه جریان تبدیل کنیم.
کمینه پوشش مسیر در گراف جهت‌دار بدون دور
برای پیدا کردن کمینه تعداد مسیرها برای پوشش دادن تمام راس‌های در یک گراف جهت‌دار بدون دور ، می‌توانیم یک گراف دوبخشی از بسازیم که:
که درجه خروجی هر مثبت است.
که درجه ورودی هر مثبت است.
آنگاه می‌توان با استفاده از نظریه کونیگ نشان داد که یک تطابق با اندازه دارد اگر و تنها اگر راه وجود داشته باشد که هر راس در را پوشش می‌دهد و تعداد راس‌های است؛ بنابراین مسئله را می‌توان با پیدا کردن تطابق ماکسیمم در حل کرد.
تطابق بیشینه دوبخشی
شکل ۴٫۳٫۱. تبدیل یک مسئله تطابق بیشینه دوبخشی به مسئله بیشینه جریان.
برای پیدا کردن تطابق بیشینه (تطابقی که بیش‌ترین تعداد راس‌های ممکن را دارد) در یک گراف دو بخشی ، می‌توانیم مسئله را با ساختن شبکه به یک مسئله بیشینه جریان تبدیل کنیم، که:
شامل یال‌هایی از است که جهتشان از به است.
برای هر و برای هر .
برای هر (شکل ۴٫۳٫۱ را ببینید).
آنگاه مقدار بیشینه جریان در برابر اندازه تطابق ماکسیمم در است.
مسئله بیشینه جریان با ظرفیت راس
شکل ۴٫۴٫۱. تبدیل یک مسئله تطابق بیشینه جریان با شرط ظرفیت راس‌ها به مسئله بیشینه جریان اصلی با بخش کردن راس‌ها.
اگر شبکه را داشته باشیم که در آن علاوه بر یال‌ها، هر راس هم ظرفیت دارد، یعنی نگاشت که با نمایش داده می‌شود به طوری که جریان f علاوه بر شرط ظرفیت و بقای جریان‌ها، شرط ظرفیت راس را هم داشته باشد:
به بیان دیگر مقدار جریانی که از یک راس می‌گذرد نمی‌تواند از ظرفیت آن بیشتر باشد. برای یافتن ماکسیمم جریان در می‌توان با گسترش ، مسئله را به یک مسئله بیشینه جریان تبدیل کرد. ابتدا هر با و جایگزین می‌شود که متصل به یال‌هایی است که به وارد می‌شود و متصل به یال‌هایی است که از آن خارج می‌شوند، سپس ظرفیت را به یالی نسبت می‌دهیم که و را شامل می‌شود (شکل ۴٫۴٫۱ را ببینید، ولی در نظر داشته باشید که جای و به اشتباه در آن جابه‌جا شده‌است). در این شبکه گسترش یافته، شرط ظرفیت راس برداشته شده است؛ بنابراین می‌توان با این مسئله مانند یک مسئله بیشینه جریان برخورد کرد.
بیشینه مسیر مستقل
دو مسیر از هم مستقل اند اگر به جز و راس مشترکی نداشته باشند. برای پیدا کردن بیشینه تعداد راه‌های مستقل از دو راس به در گراف جهت‌دار ، می‌توان از دارای ظرفیت راس، شبکه را ساخت به طوری که:
و به ترتیب مبدا و مقصد اند.
برای هر .
برای هر .
آنگاه مقدار بیشینه جریان برابر تعداد مسیرهای مستقل از به است.
بیشینه مسیر یال‌مجزا
برای پیدا کردن بیشینه تعداد مسیرهای یال‌مجزا از راس به راس در گراف جهت دار ، می‌توان مسئله را با ساختن شبکه از با مبدا و مقصد و نسبت دادن جریان واحد به هر یال، به یک مسئله بیشینه جریان تبدیل کرد.
بیشینه مسیر راس‌مجزا
برای پیدا کردن بیشینه تعداد مسیرهای راس‌مجزا از راس به راس در گراف جهت‌دار ، می‌توان مسئله را با ساختن شبکه به صورت زیر، به یک مسئله بیشینه جریان تبدیل کرد:
هر راس در گراف را به دو راس و تقسیم کنید.
برای هر راس یالی با ظرفیت یک از به اضافه کنید.
هر یال در گراف را با یالی از به با ظرفیت یک تعویض کنید.
یک راس مقصد اختصاصی جدید به نام اضافه کنید.
برای هر راس ، یالی از به با ظرفیت یک اضافه کنید.
یک بیشینه جریان از به t پیدا کنید. مقدار جریان برابر تعداد مسیرهای راس‌مجزا است.
کاربردهای مسئله در دنیای واقعی
بازی‌های حذفی بیسبال
تشکیل شبکه جریان برای مسئله بازی‌های حذفی بیسبال.
در این مسئله، تیم در یک لیگ به طور حذفی با یک‌دیگر مسابقه می‌دهند. در یک مرحله خاص، تعداد بردها، تعداد بازی‌های باقی‌مانده برای تیم ام، و تعداد بازی‌های باقی‌مانده در مقابل تیم ام است. اگر تیمی شانس اول شدن از دست بدهد، از لیگ حذف خواهد شد. هدف این مسئله تعیین کردن تیم‌های حذف شده در هر زمان از فصل است. Schwartz برای این مسئله روشی پیشنهاد داد که این مسئله را به مسئله بیشینه جریان تبدیل می‌کند. در این روش شبکه‌ای ساخته می‌شود که تعیین می‌کند آیا تیم حذف می‌شود یا نه.
فرض کنید گراف شبکه‌ای با باشد که و به ترتیب مبدا و مقصد را تعیین می‌کنند. یک راس را به طوری که به گراف اضافه می‌کنیم و آن را با یالی با ظرفیت به وصل می‌کنیم که تعداد بازی‌های بین دو تیم و را نشان می‌دهد. هم چنین برای هر تیم یک راس ایجاد می‌کنیم و هر راس را به راس‌های و وصل می‌کنیم تا تضمین کنیم یکی از آن‌ها برنده می‌شود. برای این یال‌ها ظرفیتی تعیین نمی‌کنیم. در انتها، وزن یال بین تیم و مقصد را w k +r k –w i قرار می‌دهیم تا تعداد بردهای تیم i از w k +r k تجاوز نکند. مجموعه تیم‌های شرکت‌کننده در لیگ را می‌نامیم و . ادعا می‌کنیم تیم حذف نمی‌شود اگر و تنها اگر اندازه جریانی با مقدار در شبکه وجود داشته باشد. در مقاله مذکور نشان داده شده که این مقدار همان مقدار بیشینه جریان از به است.
برنامه‌ریزی خطوط هوایی
یکی از مسائل مهم در صنایع خطوط هوایی، برنامه‌ریزی برای خدمه پرواز است. مسائل برنامه‌ریزی در خطوط هوایی می‌تواند به عنوان کاربردی از تعمیم مسئله بیشینه جریان مطرح شود. ورودی مسئله، مجموعه‌ای از پروازها ( ) است که شامل مکان و زمان پروازهای ورودی و خروجی است. در یک مدل از برنامه‌ریزی، هدف این است که یک برنامه‌ریزی عملی صورت گیرد به طوری که حداکثر خدمه فعالیت کنند.
برای حل این مسئله، از مدل متفاوتی از مسئله گردش به نام گردش کراندار استفاده می‌کنیم، که مدل کلی‌ای از مسئله جریان است که در آن برای حداقل جریان منحصر با یال‌ها محدودیت قائل می‌شویم.
را یک شبکه با مبدا و مقصد در نظر می‌گیریم. برای هر پرواز ، یک راس برای مبدا و یک راس برای مقصد آن به اضافه می‌کنیم. هم چنین یال‌های زیر را به اضافه می‌کنیم:
یال‌هایی با ظرفیت ۰،۱ بین و هر
یال‌هایی با ظرفیت ۰،۱ بین هر و
یال‌هایی با ظرفیت ۰،۱ بین هر جفت و
یال‌هایی با ظرفیت ۰،۱ بین هر و ، اگر بتوانیم با صرف هزینه و زمان معقول از به برسیم.
یالی با ظرفیت ∞,۰ بین و
در روش ذکر شده، ادعا و اثبات می‌شود که پیدا کردن یک جریان با مقدار بین و در ، همان پیدا کردن برنامه‌ای عملی برای مجموعه پروازهای با حداکثر خدمه است.
نوع دیگری از برنامه‌ریزی خطوط هوایی، پیدا کردن حداقل خدمه برای انجام شدن تمامی پروازهاست. برای پیدا کردن جواب این مسئله، یک گراف دو قسمتی می‌سازیم که هر پرواز یک کپی در مجموعه و مجموعه دارد. اگر یک هواپیما بتواند پرواز را بعد از پرواز انجام دهد، به وصل می‌شود. یک تطابق در شامل یک برنامه برای است و بدیهی است که حداکثر تطابق دوقسمتی در این گراف، یک برنامه هوایی با حداقل تعداد خدمه را نشان می‌دهد. همان‌طور که در قسمت کاربردهای این مقاله ذکر شد، پیدا کردن تطابق بیشینه دوبخشی یکی از کاربردهای مسئله بیشینه جریان است.
مسئله تقاضای گردش
تعدادی کارخانه هستند که کالا تولید می‌کنند و تعدادی دهکده هستند که باید به آن‌ها کالا برسد. آن‌ها با شبکه‌ای از جاده‌ها به هم متصل اند که هر جاده ظرفیت برای بیشینه کالایی که می‌تواند از آن بگذرد دارد. مسئله یافتن این است که آیا گردشی وجود دارد که تقاضا را برآورده کند یا خیر. این مسئله می‌تواند به یک مسئله بیشینه جریان تبدیل شود:
یک راس مبدا ( ) اضافه کنید و یال‌هایی از آن به هر راس کارخانه ( ) با ظرفیت تولید اضافه کنید، که آهنگ تولید کارخانه است.
یک راس مقصد ( ) اضافه کنید و یال‌هایی از هر راس دهکده ( ) با ظرفیت به آن اضافه کنید، که میزان تقاضای دهکده است.
این شبکه جدید است. گردشی وجود دارد که تقاضا را برآورده کند اگر و تنها اگر:
اگر یک گردش وجود داشته باشد، مسئله بیشینه جریان جواب این که چه مقدار کالا برای برآورده شدن تقاضا باید از طریق یک جاده خاص فرستاده شود را به ما می‌دهد.
عدالت در اشتراک اتومبیل
مسئله این است که نفر از یک ماشین در روز به صورت اشتراکی استفاده می‌کنند. هر شرکت کننده می‌تواند در هر روز انتخاب کند که شرکت می‌کند یا خیر. هدف ما این است که عادلانه تصمیم بگیریم که در یک روز مشخص، چه کسی رانندگی می‌کند.
راه حل به این صورت است:
می‌توانیم بر اساس تعداد افرادی که از ماشین استفاده می‌کنند تصمیم بگیریم، یعنی اگر نفر از ماشین در یک روز استفاده می‌کنند، هر نفر به مقدار مسئولیت دارد؛ بنابراین برای هر شخص ، اجبار رانندگی ( ) به صورت ذکر شده است؛ بنابراین، شخص فقط باید بار در روز رانندگی کند.
هدف این است که پی ببریم آیا چنین وضعیتی امکان‌پذیر است یا خیر. برای این منظور همان‌طور که در شکل نشان داده شده است، سعی می‌کنیم مسئله را به یک شبکه تبدیل کنیم.
حال می‌توان ثابت کرد که اگر جریان وجود داشته باشد، آنگاه چنین وضعیت عادلانه‌ای و چنین جریانی با مقدار همواره وجود دارد.