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

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

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

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

Дефиниција 

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

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

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

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

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

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

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

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

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

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

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

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

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

Употреба 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Види још 
Проблеми минималне цене протока

Референце 

Графовски алгоритми
У теорији оптимизације Проблем максималног протока укључује налажење подесног протока кроз једно-изворну једно-завршну транспортну мрежу која је максимална . Проблем максималног протока се може посматрати као специјални случај комплекснијих проблема транспортних мрежа као што је проблем кружења . Максимална вредност с-т тока( односно тока од извора ка завршном току је једнак минималном капацитету с-т пресека( однсно пресека од с до т ) у мрежи , као што је наведено у максимални-проток минимални-пресек теореми . _TOC_ Историја Проблем Максималног тока је први пут формулисанод стране Т . Е Харрис као поједностављен модел тока совјетске железнице . У години Лестер Р. Форд . Јр и Делберт Р . Фулкерсон направили су први познати алгоритам Форд-Фулкерсон алгоритам . Током времена откривена су разна побољшана решењаПроблема максималног протока , посебно алгоритам најраће промене пута од Едмондса и Карпа и независно Динитз-а . Алгоритам блокиарања тока од Динитз-а . Алгоритам гуранја-ознаке од Голдберг-а и Тарјан-а . Бинарно блокирање тока Голдберг-а и Рао-а . Алгоритам електричног тока Кристиано , Келнер , Мадри и Спиелман-а налази отприлике оптималан максимални ток , али ради само са неусмереним графовима . Дефиниција Нека је Н=( В , Е ) мрежа са с , т∈В чворовима који су извор и понор од Н респективно Капацитет чвора је сликанје ц:Е→Р+ где је Цув или Ц( у , в ) . Представља макцималан проток кроз чвор . Проток је сликање ф:Е' →Р+ где је фу , в или ф( у , в ) под утиском ограничења : 1.фув≤цув за свако ( у , в ) ∈В( Ограничење капацитета:проток кроз чвор не може да надмаши његов капацитет ) 2.Σу:( у , в ) ∈Еф( у , в ) =Σу:( у , в ) ∈Ефсв за свако в∈Б\{ с , т }( Конзервација протока:сума протока која улази у чвор мора да буде једнака суми протока која излази из чвора , осим извора и понора ) . Вредност протока је деФинисана једнакошћу |ф|=Σв:( с , в ) ∈Ефсв где с је извор од Н . Представља количину протока која пролази од извора до понора . у Проблему максималног протока треба максимизовати |ф| , тако да постоји што више протока од с до т . Решења Моземо да дефинишемо резидуални граф која даје систематични начин за тражење унапред-уназад операције. да би могао да се нађе максимални проток . Са задатом транспортном мрежом Г , и протоком ф у г , можемо да деФинишемо резидуални граф Гф од Г са респектом по ф као што следи : 1. Скуп чворова од Гф је исти као и Г. 2. Сваки чвор е=( у , в ) од Гф је са капацитетом од Це-Ф( е ). 3. Сваки чвор е' =( в , у ) Гф је са капацитетом од ф( е ) . Следећа табела приказује алгоритме за решавање проблема максималног протока . Теорема интегралног тока По теореми интегралног тока : Ако сваки чвор у трансортној мрежи има интегрални капацитет , онда постоји интегрални максимум протока . Употреба Више-изворни више-понорни проблем максималног протока са задатом мрежом Н=( В , Е ) са скупом извора С={ с1 , \ . . . , сн } и скуп понора Т = { т1 , \ . . . , тн } уместо само једног извора и понора Треба да нађемо максимални проток преко н . Можемо да трансформишемо више-изворни , више-понорни проблем у проблем максималног протока додавањем интегрисаног извора који се повезује за сваки чвор у С и интегрисани понор за који су сви чворови из Т повезани( Такође познати као супер-извор и супер-понор ) Са бесконачним капацитетом на свакој грани( видети фигуру1.1 ) . Покривач минималне путање у директном ацикличном графу Са задатим графом Г=( В , Е ) треба да нађемо минимални број путања да покријемо сваки чвор у В . Можемо да конструишемо бипартитивни граф Г=( Визлазно∪Вулазно , Е ) од Г где : 1. Визлазно={ в∈В : в има позитиван излазни степен }. 2. Вулазно={ в∈В : в има позитиван улазни степен }. 3. Е = { ( у , в ) ∈( Визлазно , Вулазно ) : ( у , в ) ∈Е } . Онда може бити приказано преко Конигове теореме Г има усаглашену величину од м само ако постоји н-м путања који покривају сваки чвор у графу Г где је н број чворова у Г . Дакле проблем се може решити налажењем максималног броја упаривања у Г . Максимална бројност бипартитивног упаривања Са задатим бипартитивном графом Г=( З∪Џ , Е ) Треба да нађемо максимални број повезивања у Г , то је повезивање које садржа максимални могући број грана . Овај проблем се може трасформисати у проблем максималног протока конструисањем мреже N = ( З∪Џ∪{ с , т } , Е ' } где : 1. Е садржи гране у Г усмерене од Џ до З 2.( с , џ ) ∈Е ' за свако џ∈Џ и ( з , т ) ∈Е ' за свако з∈З 3.ц( е ) =1 за свако е∈Е ' Онда Максимална вредност Протока у Н је једнака величини максималног упаривања у Г . Проблем Максималног протока са капацитетом чворова У задатој мрежи Н=( В , Е ) где посотји капацитет за сваки чвор , као и за сваку грану постоји пресликавање ц:В→Р+ обележено са ц( в ) тако да проток ф мора да испуњава услове ограничења капацитета као и конзервације протока и такође ограничење капацитета чворова . Σи∈В фив≤ц( в ) за свако в∈В\{ с , т } другим речима количина протока која пролази кроз чвор не може да надмашује његов капацитет . Да би се нашао максимални проток кроз Н Мо+емо да трнсформишемо проблем у првобитни проблем максималног протока тако што ћемо да проширимо Н . Прво сваки в∈В заменимо са вулазно и визлазно , где је вулазно повезано гранама које улазе у в , а визлазно је повезано гранама које излазе из в , онда придодати капацитет ц( в ) грани која повезује вулазно и визлазно( видети фигуру4.1 али опазити да су вулазно и визлазно погрешно замењени ) . У овој проширеној мрежи ограничење капацитета чворава је уклоњено па се проблем може третирати као првобитни проблем максималног протока . Максимална независна путања Са задатим усмереним графом Г=( В , Е ) и два чвора с и т , треба да нађемо максимални број независних путања од с до т . Две путање су независне ако немају заједнички чвор осим с и т . Можемо да конструишемо мрежу Н=( В , Е ) од графа г са капацитетима чворова где : 1.с и т су извор и понор од Н у том редоследу. 2.ц( в ) =1 за свако в∈В 3.ц( е ) =1 за свако е∈Е Онда је вредност максималног протока једнака Максималном броју путања од с до т . Максимална путања дисјунктних грана Са задатим усмереним графом Г=( В , Е ) и два чвора с и т треба да нађемо максимални број путања са дисјунктним гранама од с до т . Овај проблем можемо да трансформишемо у проблем максималног протока конструисањем мреже Н=( В , Е ) из Г где су с и т извор и понор ( у том редоследу ) и свакој грани придружимо јединични капацитет . Види још Проблеми минималне цене протока Референце Графовски алгоритми