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

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

Пример Транспортне мреже са максималним протоком извор је с, а забршни чвор је т, бројеви означавају проток и капацитет

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

Историја

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

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

Дефиниција

Транспортна мрежа ца извором с , и понором т. Бројеви поред чворова су капацитети

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

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

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

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

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

Решења

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

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

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

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

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

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

Метода	Комплексност	Опис
Линеарно програмирање		Ограничења су задата са дефиницијом легалног протока.
форд-фулкерсон алгоритам	О(макс ф)	Све док постоји путања кроз Резидуални граф, послати минимум преосталих капацитета кроз путању. Алгоритам ради цамо ако су све тежине цели бројеви. Иначе је могуће да форд-фулкерсонов алгоритам неће конвергирати ка максималној вредности.
Едмондс-Карп алгоритам	О(ВЕ2)	Специјализација форд-фулкерсон алгоритма , налажење увеличавајуће путање са претрагом графа у ширину.
Динитцово блокирање протока алгоритма	О(В2Е)	У свакој Фази алгоритма гради се слојевит граф са претрагом у ширину у резидуалном графу. Максимални проток у слојевитом графу може бити израчунат у О(ВЕ) времену, а максимални број Фаза је н-1. У мрежама са јединичхим капацитетима , Динитцов алгоритам се завршава у О(Екорен(В))
Генерални пуш-релабел алгоритам максималног протока	О(В2Е)	Пуш-релабел алгоритам одржава предток такође ток функције са могућношћу вишка у чворовима. Алгоритам се извршава док постоји чвор са вишком такође активним чвором у графу. Пуш операција повећава проток на резидуалним гранама , а висина на контролама графа чије се резидуалне гране могу "гурнути“. Висина функције је промењена са релабел операцијом. Коректна дефиниција ових операција гарантује да је резултујући проток функције је максимални проток
Пуш-релабел алгоритам са фИфО правилом селекције чвора	О(В3)	пуш-релабел алгоритам варијанта која увек бира најскорије коришћен активни чвор и изводи пуш операције док остатак није позитиван или док не постоји прихватљив остатак грана од овог чвора
Динитцово блокирање протока алгоритма са динамичким дрветом	О(ВЕлог(В))	Струстура података динамичког дрвећа убрзава израчунавање максималног протока у слојевитом графу до О(Е лог(Б))
Пуш-релабел алгоритам са динамичким дрветом	О(БЕлог(Б2/Е))	Алгоритам гради дрвећа ограничехе величине на резидуалном графу с обзиром на висину функције. Ова дрвећа дају више-нивоа пуш операције
Бинарно блокирање протока са динамичким дрветом	О(Емин(В2/3/sup>, корен(Е))лог(В2/Е)лог У)	Вредност У одговара максимуму капацитета мреже.
МПМ(Малхотра, Прамодх-Кумар и Махесхвари) Алгоритам	О(Б3)
Џим Орлинов + КРТ(Кинг, Рао, Тарјан) Алгоритам	О(ВЕ)	Орлинов алгоритам решава проблем максималног протока у О(ВЕ) времену за м≤О(х(16/15)-е) док га КРТ решава у О(ВЕ) за м>н1+е

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

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

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

Употреба

Трансформација више-изворног , више-понорног проблема максималног протока у једно-изворни , једно-понорни проблем максималног протока (фигура4.1.1)

Трансформација проблема максималног бипартитивног упаривања у проблем максималног протока (фигура4.3.1)

Трасформација проблема максималног протока са ограничењима капацитетима чворова у оригинални проблем максималног протока раздвајањем чворова (фигура4.4.1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Види још

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