مسئله بیشینه جریان کیست؟ توضیح بده.
در تئوری بهینه‌سازی، مسائل بیشینه جریان شامل پیدا کردن یک جریان عملی بیشینه از داخل یک شبکهٔ جریان تک-مبدأ و تک-مقصد است.می‌توان به مسئلهٔ بیشینه جریان، به صورت حالت خاصی از مسائل پیچیده‌تر شبکهٔ جریان، مانند ، نگاه کرد. مقدار ماکسیمم یک جریان "s-t" (جریان از به ) برابر حداقل ظرفیت یک (برشی که مبدأ را از مقصد جدا می‌کند) در شبکه است، همان‌طور که در قضیهٔ جریان بیشینه-برش کمینه ذکر شده است.تاریخچه.مسئلهٔ بیشینهٔ جریان ابتدا توسط و F. S. Ross در سال ۱۹۵۴ به عنوان مدل ساده شده‌ای از جریانرفت و آمد خط آهن شوروی مطرح شد. در ۱۹۵۵، و اولین الگوریتم شناخته شده، الگوریتم فورد–فالکرسون را ایجاد کردند.در طول زمان، تعداد زیادی راه حل بهبود یافته برای مسئلهٔ بیشینهٔ جریان پیدا شده است، به ویژه الگوریتم کوتاه‌ترین راه افزوده از Edmonds و Karp و به صورت مستقل از Dinitz، الگوریتم سد کردن جریان Dinitz، الگوریتم ارسال-برچسب و ، و الگوریتم سد کردن دودویی جریان از Goldberg و Rao. الگوریتم جریان الکتریکی Madry، Kelner، Christano و Spielman یک جریان بیشینهٔ تقریباً بهینه می‌یابد اما فقط در گراف‌های بدون جهت کار می‌کند.تعریف.فرض کنید formula_1 یک شبکه است با formula_2 که به ترتیب مبدأ و مقصد هستند.مسئلهٔ بیشینه جریان، بیشینه کردن formula_16 است، یعنی هدایت بیش‌ترین جریان ممکن از formula_14 به formula_18.راه‌حل‌ها.می‌توان گراف باقیمانده را تعریف کرد تا راهی اصولی برای جستجو کردن عملیات‌های جلو-عقب برای یافتن بیشینه جریان فراهم کند.اگر شبکهٔ جریان formula_19 و جریان formula_20 روی formula_19 را داشته باشیم، formula_22، گراف باقیماندهٔ formula_19 را با توجه به formula_20 اینگونه تعریف می‌کنیم:الگوریتم‌های حل مسئلهٔ بیشینه جریان در جدول زیر نشان داده شده‌است.قضیهٔ جریان انتگرال.قضیهٔ جریان انتگرال می‌گوید:کاربرد.مسئلهٔ بیشینه جریان چند-مبدأ و چند-مقصد.می‌خواهیم جریان بیشینه را روی شبکهٔ formula_33 که دارای مجموعهٔ مبدأهای formula_34 و مجموعهٔ مقصدهای formula_35 (به جای تنها یک مبدأ و یک مقصد) است، پیدا کنیم. می‌توانیم مسئله چند-مبدأ و چند-مقصد را با افزودن یک مبدأ تثبیت شده که به تمام راس‌های formula_36 متصل است و یک مقصد تثبیت شده که به تمام راس‌های formula_37 متصل است (ابرمبدأ و ابرمقصد) و یال‌های آن‌ها ظرفیت بی‌نهایت دارند، به یک مسئلهٔ بیشینه جریان تبدیل کنیم.کمینه پوشش مسیر در گراف جهت‌دار بدون دور.برای پیدا کردن کمینه تعداد مسیر‌ها برای پوشش دادن تمام رأس‌های formula_38 در یک گراف جهت‌دار بدون دور formula_39، می‌توانیم یک گراف دوبخشی formula_40 از formula_19 بسازیم که:آنگاه می‌توان با استفاده از نظریه کونیگ نشان داد که formula_47 یک تطابق با اندازهٔ formula_48 دارد اگر و تنها اگر formula_49 راه وجود داشته باشد که هر رأس در formula_19 را پوشش می‌دهد و formula_51 تعداد رأس‌های formula_19 است؛ بنابراین مسئله را می‌توان با پیدا کردن تطابق ماکسیمم در formula_47 حل کرد.تطابق بیشینهٔ دوبخشی.برای پیدا کردن تطابق بیشینه (تطابقی که بیش‌ترین تعداد رأس‌های ممکن را دارد) در یک گراف دو بخشی formula_54، می‌توانیم مسئله را با ساختن شبکهٔ formula_55 به یک مسئلهٔ بیشینه جریان تبدیل کنیم، که:آنگاه مقدار بیشینه جریان در formula_15 برابر اندازهٔ تطابق ماکسیمم در formula_19 است.مسئلهٔ بیشینه جریان با ظرفیت رأس.اگر شبکهٔ formula_68 را داشته باشیم که در آن علاوه بر یال‌ها، هر رأس هم ظرفیت دارد، یعنی نگاشت formula_69 که با formula_70 نمایش داده می‌شود به طوری که جریان f علاوه بر شرط ظرفیت و بقای جریان‌ها، شرط ظرفیت رأس را هم داشته باشد:formula_71به بیان دیگر مقدار جریانی که از یک رأس می‌گذرد نمی‌تواند از ظرفیت آن بیشتر باشد. برای یافتن ماکسیمم جریان در formula_15 می‌توان با گسترش formula_15، مسئله را به یک مسئلهٔ بیشینه جریان تبدیل کرد. ابتدا هر formula_74 با formula_75 و formula_76 جایگزین می‌شود که formula_75 متصل به یال‌هایی است که به formula_38 وارد می‌شود و formula_76 متصل به یال‌هایی است که از آن خارج می‌شوند، سپس ظرفیت formula_70 را به یالی نسبت می‌دهیم که formula_75 و formula_76 را شامل می‌شود (شکل ۴٫۴٫۱ را ببینید، ولی در نظر داشته باشید که جای formula_75 و formula_76 به اشتباه در آن جابه‌جا شده‌است). در این شبکهٔ گسترش یافته، شرط ظرفیت رأس برداشته شده است؛ بنابراین می‌توان با این مسئله مانند یک مسئلهٔ بیشینه جریان برخورد کرد.بیشینه مسیر مستقل.دو مسیر از هم مستقل اند اگر به جز formula_14 و formula_18 رأس مشترکی نداشته باشند. برای پیدا کردن بیشینه تعداد راه‌های مستقل از دو رأس formula_14 به formula_18 در گراف جهت‌دار formula_39، می‌توان از formula_19 دارای ظرفیت رأس، شبکهٔ formula_33 را ساخت به طوری که:آنگاه مقدار بیشینه جریان برابر تعداد مسیرهای مستقل از formula_14 به formula_18 است.بیشینه مسیر یال‌مجزا.برای پیدا کردن بیشینه تعداد مسیرهای یال‌مجزا از رأس formula_14 به رأس formula_18 در گراف جهت دار formula_39، می‌توان مسئله را با ساختن شبکهٔ formula_33 از formula_19 با مبدأ formula_14 و مقصد formula_18 و نسبت دادن جریان واحد به هر یال، به یک مسئلهٔ بیشینه جریان تبدیل کرد.بیشینه مسیر رأس‌مجزا.برای پیدا کردن بیشینه تعداد مسیرهای رأس‌مجزا از رأس formula_14 به رأس formula_18 در گراف جهت‌دار formula_39، می‌توان مسئله را با ساختن شبکهٔ formula_33 به صورت زیر، به یک مسئلهٔ بیشینه جریان تبدیل کرد:کاربردهای مسئله در دنیای واقعی.بازی‌های حذفی بیسبال.در این مسئله، formula_51 تیم در یک لیگ به طور حذفی با یک‌دیگر مسابقه می‌دهند. در یک مرحلهٔ خاص، formula_127 تعداد بردها، formula_128 تعداد بازی‌های باقی‌مانده برای تیم formula_129ام، و formula_130 تعداد بازی‌های باقی‌مانده در مقابل تیم formula_131ام است. اگر تیمی شانس اول شدن از دست بدهد، از لیگ حذف خواهد شد. هدف این مسئله تعیین کردن تیم‌های حذف شده در هر زمان از فصل است. Schwartz برای این مسئله روشی پیشنهاد داد که این مسئله را به مسئلهٔ بیشینهٔ جریان تبدیل می‌کند. در این روش شبکه‌ای ساخته می‌شود که تعیین می‌کند آیا تیم formula_132 حذف می‌شود یا نه.فرض کنید گراف formula_39 شبکه‌ای با formula_134 باشد که formula_14 و formula_18 به ترتیب مبدأ و مقصد را تعیین می‌کنند. یک رأس formula_137 را به طوری که formula_138 به گراف اضافه می‌کنیم و آن را با یالی با ظرفیت formula_130 به formula_14 وصل می‌کنیم که تعداد بازی‌های بین دو تیم formula_129 و formula_131 را نشان می‌دهد. هم چنین برای هر تیم formula_129 یک رأس ایجاد می‌کنیم و هر رأس formula_137 را به رأس‌های formula_129 و formula_131 وصل می‌کنیم تا تضمین کنیم یکی از آن‌ها برنده می‌شود. برای این یال‌ها ظرفیتی تعیین نمی‌کنیم. در انتها، وزن یال بین تیم formula_129 و مقصد formula_18 را "w"k+"r"k–"w"i قرار می‌دهیم تا تعداد بردهای تیم i از "w"k+"r"k تجاوز نکند. مجموعهٔ تیم‌های شرکت‌کننده در لیگ را formula_36 می‌نامیم و formula_150. ادعا می‌کنیم تیم formula_132 حذف نمی‌شود اگر و تنها اگر اندازهٔ جریانی با مقدار formula_152 در شبکهٔ formula_19 وجود داشته باشد. در مقالهٔ مذکور نشان داده شده که این مقدار همان مقدار بیشینهٔ جریان از formula_14 به formula_18 است.برنامه‌ریزی خطوط هوایی.یکی از مسائل مهم در صنایع خطوط هوایی، برنامه‌ریزی برای خدمهٔ پرواز است. مسائل برنامه‌ریزی در خطوط هوایی می‌تواند به عنوان کاربردی از تعمیم مسئلهٔ بیشینهٔ جریان مطرح شود. ورودی مسئله، مجموعه‌ای از پروازها (formula_156) است که شامل مکان و زمان پروازهای ورودی و خروجی است. در یک مدل از برنامه‌ریزی، هدف این است که یک برنامه‌ریزی عملی صورت گیرد به طوری که حداکثر formula_132 خدمه فعالیت کنند.برای حل این مسئله، از مدل متفاوتی از به نام گردش کراندار استفاده می‌کنیم، که مدل کلی‌ای از مسئلهٔ جریان است که در آن برای حداقل جریان منحصر با یال‌ها محدودیت قائل می‌شویم.formula_39 را یک شبکه با مبدأ و مقصد formula_134 در نظر می‌گیریم. برای هر پرواز formula_129، یک رأس formula_161 برای مبدأ و یک رأس formula_162 برای مقصد آن به formula_38 اضافه می‌کنیم. هم چنین یال‌های زیر را به formula_164 اضافه می‌کنیم:در روش ذکر شده، ادعا و اثبات می‌شود که پیدا کردن یک جریان با مقدار formula_132 بین formula_14 و formula_18 در formula_19، همان پیدا کردن برنامه‌ای عملی برای مجموعهٔ پروازهای formula_156 با حداکثر formula_132 خدمه است.نوع دیگری از برنامه‌ریزی خطوط هوایی، پیدا کردن حداقل خدمه برای انجام شدن تمامی پروازهاست. برای پیدا کردن جواب این مسئله، یک گراف دو قسمتی formula_183 می‌سازیم که هر پرواز یک کپی در مجموعهٔ formula_184 و مجموعهٔ formula_185 دارد. اگر یک هواپیما بتواند پرواز formula_131 را بعد از پرواز formula_129 انجام دهد، formula_188 به formula_189 وصل می‌شود. یک تطابق در formula_47 شامل یک برنامه برای formula_156 است و بدیهی است که حداکثر تطابق دوقسمتی در این گراف، یک برنامهٔ هوایی با حداقل تعداد خدمه را نشان می‌دهد. همان‌طور که در قسمت کاربردهای این مقاله ذکر شد، پیدا کردن تطابق بیشینه دوبخشی یکی از کاربردهای مسئلهٔ بیشینهٔ جریان است.مسئلهٔ تقاضای گردش.تعدادی کارخانه هستند که کالا تولید می‌کنند و تعدادی دهکده هستند که باید به آن‌ها کالا برسد. آن‌ها با شبکه‌ای از جاده‌ها به هم متصل اند که هر جاده ظرفیت formula_192 برای بیشینه کالایی که می‌تواند از آن بگذرد دارد. مسئله یافتن این است که آیا گردشی وجود دارد که تقاضا را برآورده کند یا خیر. این مسئله می‌تواند به یک مسئلهٔ بیشینه جریان تبدیل شود:formula_39 این شبکهٔ جدید است. گردشی وجود دارد که تقاضا را برآورده کند اگر و تنها اگر:formula_203اگر یک گردش وجود داشته باشد، مسئلهٔ بیشینه جریان جواب این که چه مقدار کالا برای برآورده شدن تقاضا باید از طریق یک جادهٔ خاص فرستاده شود را به ما می‌دهد.عدالت در اشتراک اتومبیل.مسئله این است که formula_15 نفر از یک ماشین در formula_132 روز به صورت اشتراکی استفاده می‌کنند. هر شرکت کننده می‌تواند در هر روز انتخاب کند که شرکت می‌کند یا خیر. هدف ما این است که عادلانه تصمیم بگیریم که در یک روز مشخص، چه کسی رانندگی می‌کند.راه حل به این صورت است:می‌توانیم بر اساس تعداد افرادی که از ماشین استفاده می‌کنند تصمیم بگیریم، یعنی اگر formula_48 نفر از ماشین در یک روز استفاده می‌کنند، هر نفر به مقدار formula_207 مسئولیت دارد؛ بنابراین برای هر شخص formula_129، اجبار رانندگی (formula_209) به صورتِ ذکر شده است؛ بنابراین، شخص formula_129 فقط باید formula_211 بار در formula_132 روز رانندگی کند.هدف این است که پی ببریم آیا چنین وضعیتی امکان‌پذیر است یا خیر. برای این منظور همان‌طور که در شکل نشان داده شده است، سعی می‌کنیم مسئله را به یک شبکه تبدیل کنیم.حال می‌توان ثابت کرد که اگر جریان formula_132 وجود داشته باشد، آنگاه چنین وضعیت عادلانه‌ای و چنین جریانی با مقدار formula_132 همواره وجود دارد.