Проблем максималног тока

У теорији оптимизације Проблем максималног протока укључује налажење подесног протока кроз једно-изворну једно-завршну транспортну мрежу која је максимална.

Проблем максималног протока се може посматрати као специјални случај комплекснијих проблема транспортних мрежа као што је проблем кружења. Максимална вредност с-т тока(односно тока од извора ка завршном току је једнак минималном капацитету с-т пресека(однсно пресека од с до т) у мрежи, као што је наведено у максимални-проток минимални-пресек теореми. _TOC_

Проблем Максималног тока је први пут формулисан 1954 од стране Т. Е Харрис као поједностављен модел тока совјетске железнице^[1]. У 1955. години Лестер Р. Форд. Јр и Делберт Р. Фулкерсон направили су први познати алгоритам Форд-Фулкерсон алгоритам.^[2][3]

Током времена откривена су разна побољшана решењаПроблема максималног протока, посебно алгоритам најраће промене пута од Едмондса и Карпа и независно Динитз-а. Алгоритам блокиарања тока од Динитз-а. Алгоритам гуранја-ознаке од Голдберг-а и Тарјан-а. Бинарно блокирање тока Голдберг-а и Рао-а. Алгоритам електричног тока Кристиано, Келнер, Мадри и Спиелман-а налази отприлике оптималан максимални ток , али ради само са неусмереним графовима.

Нека је Н=(В, Е) мрежа са с, т∈В чворовима који су извор и понор од Н респективно Капацитет чвора је сликанје ц:Е→Р⁺ где је Ц_ув или Ц(у, в). Представља макцималан проток кроз чвор. Проток је сликање ф:Е'→Р⁺ где је ф_{у, в} или ф(у, в) под утиском ограничења:

1.ф_ув≤ц_ув за свако (у, в)∈В(Ограничење капацитета:проток кроз чвор не може да надмаши његов капацитет)

2.Σ_{у:(у, в)∈Е}ф(у, в)=Σ_{у:(у, в)∈Е}ф_св за свако в∈Б\{с, т}(Конзервација протока:сума протока која улази у чвор мора да буде једнака суми протока која излази из чвора , осим извора и понора).

Вредност протока је деФинисана једнакошћу |ф|=Σ_{в:(с, в)∈Е}ф_св где с је извор од Н. Представља количину протока која пролази од извора до понора.

у Проблему максималног протока треба максимизовати |ф| , тако да постоји што више протока од с до т.

Моземо да дефинишемо резидуални граф која даје систематични начин за тражење унапред-уназад операције. да би могао да се нађе максимални проток.

Са задатом транспортном мрежом Г , и протоком ф у г , можемо да деФинишемо резидуални граф Г_ф од Г са респектом по ф као што следи:

1. Скуп чворова од Г_ф је исти као и Г.

2. Сваки чвор е=(у, в) од Г_ф је са капацитетом од Ц_е-Ф(е).

3. Сваки чвор е'=(в, у) Г_ф је са капацитетом од ф(е).

Следећа табела приказује алгоритме за решавање проблема максималног протока.

По теореми интегралног тока:

Ако сваки чвор у трансортној мрежи има интегрални капацитет , онда постоји интегрални максимум протока.

Више-изворни више-понорни проблем максималног протока

са задатом мрежом Н=(В, Е) са скупом извора С={с₁, ..., с_н} и скуп понора Т = {т₁, ..., т_н} уместо само једног извора и понора Треба да нађемо максимални проток преко н. Можемо да трансформишемо више-изворни, више-понорни проблем у проблем максималног протока додавањем интегрисаног извора који се повезује за сваки чвор у С и интегрисани понор за који су сви чворови из Т повезани(Такође познати као супер-извор и супер-понор)Са бесконачним капацитетом на свакој грани(видети фигуру 4.1.1).

Покривач минималне путање у директном ацикличном графу

Са задатим графом Г=(В, Е) треба да нађемо минимални број путања да покријемо сваки чвор у В. Можемо да конструишемо бипартитивни граф Г=(В_{излазно}∪В_улазно, Е) од Г где:

1. В_{излазно}={в∈В: в има позитиван излазни степен}.

2. В_улазно={в∈В: в има позитиван улазни степен}.

3. Е = {(у, в)∈(В_{излазно}, В_улазно): (у, в)∈Е}.

Онда може бити приказано преко Конигове теореме Г има усаглашену величину од м само ако постоји н-м путања који покривају сваки чвор у графу Г где је н број чворова у Г. Дакле проблем се може решити налажењем максималног броја упаривања у Г.

Максимална бројност бипартитивног упаривања

Са задатим бипартитивном графом Г=(З∪Џ, Е) Треба да нађемо максимални број повезивања у Г , то је повезивање које садржа максимални могући број грана. Овај проблем се може трасформисати у проблем максималног протока конструисањем мреже N = (З∪Џ∪{с, т}, Е' } где:

1. Е садржи гране у Г усмерене од Џ до З

2.(с, џ)∈Е' за свако џ∈Џ и (з, т)∈Е' за свако з∈З

3.ц(е)=1 за свако е∈Е'

Онда Максимална вредност Протока у Н је једнака величини максималног упаривања у Г.

Проблем Максималног протока са капацитетом чворова

У задатој мрежи Н=(В, Е) где посотји капацитет за сваки чвор , као и за сваку грану постоји пресликавање ц:В→Р⁺ обележено са ц(в) тако да проток ф мора да испуњава услове ограничења капацитета као и конзервације протока и такође ограничење капацитета чворова.

Σ_и∈В ф_ив≤ц(в) за свако в∈В\{с, т}

другим речима количина протока која пролази кроз чвор не може да надмашује његов капацитет.

Да би се нашао максимални проток кроз Н Мо+емо да трнсформишемо проблем у првобитни проблем максималног протока тако што ћемо да проширимо Н. Прво сваки в∈В заменимо са в_улазно и в_{излазно} , где је в_улазно повезано гранама које улазе у в , а в_{излазно} је повезано гранама које излазе из в, онда придодати капацитет ц(в) грани која повезује в_улазно и в_{излазно}(видети фигуру 4.4.1 али опазити да су в_улазно и в_{излазно} погрешно замењени). У овој проширеној мрежи ограничење капацитета чворава је уклоњено па се проблем може третирати као првобитни проблем максималног протока.

Максимална независна путања

Са задатим усмереним графом Г=(В, Е) и два чвора с и т , треба да нађемо максимални број независних путања од с до т. Две путање су независне ако немају заједнички чвор осим с и т. Можемо да конструишемо мрежу Н=(В, Е) од графа г са капацитетима чворова где:

1.с и т су извор и понор од Н у том редоследу.

2.ц(в)=1 за свако в∈В

3.ц(е)=1 за свако е∈Е

Онда је вредност максималног протока једнака Максималном броју путања од с до т.

Максимална путања дисјунктних грана

Са задатим усмереним графом Г=(В, Е) и два чвора с и т треба да нађемо максимални број путања са дисјунктним гранама од с до т. Овај проблем можемо да трансформишемо у проблем максималног протока конструисањем мреже Н=(В, Е) из Г где су с и т извор и понор (у том редоследу) и свакој грани придружимо јединични капацитет.

Проблеми минималне цене протока