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

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

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

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

Историја[уреди]

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

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

Дефиниција[уреди]

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

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

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

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

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

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

Решења[уреди]

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

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

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

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

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

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

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

Теорема интегралног тока[уреди]

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

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

Употреба[уреди]

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Такође видети[уреди]

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

Референце[уреди]

  1. ^ Александер Сцхријвер,"О Историји транспортације и проблема максималног протока"
  2. ^ форд Л. Р., ЈР;Фулкерсон Д. Р. "Максимални проток кроз мрежу"
  3. ^ форд Л. Р., ЈР;фулкерсон Д. Р. "Проток у мрежи"