Пропускателна способност на мрежа

т.н. Дадени са два върха s и t. Търсим макс.поток,който мд мине от s до t.

Всяко ребро мд поеме поток равен на капа-цитета си. Означенията в макс поток в граф са, както следва: връх а има входен поток 3 ед-ци, които се разпределят към c и d. Връх d също има входен капацитет 3 единици, които получава от a и b и ги предава на t.
За построим макс. поток в граф, работим поетапно. На основа на графа G, строим граф на потоците(flow graph) Gf, съдържащ потоците определени до момента. В нач. всички ребра имат нулев поток.При прик-лючване на алг. Gf ще съдържа макс.поток. При това строим и граф с остатъч. потоци Gr (residual graph), съдържащ неизполз. капацитети по всяко ребро (разликата от капацитета и използ.количество).Търсим път от s към t в Gr.
Мин.капацитет на реб-ро по този път е възможния за добавяне в поток. Добавяме го в Gf. Продължаваме по този начин, докато не се изчерпят всички пътища в Gr. Алг.е недетерминиран, защо-то няма стратегия за последователността на избор на възможните пътища.

Даден е ориентиран граф с указан капаци-тет на всяко ребро c_v,w. Този капацитет мд показва пропускателна способност на тръ-ба,на улица и Избираме един от възможните пътища: s-b-d-t. Мин.поток тук е 2 единици.Когато реб-ровият капацитет се запълни, премахваме ребро от графа Gr.
=>избор на нов път.Той е s-a-c-t с мин. поток 2 единици
=>пътя s-a-d-t с мин.поток 1. Тази единица се добавя към теглата в Gf. Алг.приключва, защото няма повече пътища в Gr.
Накрая сумираме входните капацитети в Gf за върха t и получаваме макс.поток. В случая той е 5 единици. Сега ще покажем недетерминираността на алг. Ако в нач. тръгнем по пътя s-a-d-t, ще допуснем поток от 3 единици. Това е добър резултат, но в Gr не остава път от s към t (фиг. 25). Това е пример как greedy алг.не винаги работят
Разсъждавайки по този начин, налице е нов път s-b-d-a-c-t, който има поток 2 единици. Това означава, че щом връщаме от d към a поток, то по тази тръба могат да минат същите единици и в обратна посока, от d към a, стига да има наличен път
Отново макс. поток е 5 единици, но сме елиминирали възможността грешен нач. избор на път да повлияе върху решението. Доказано е, че така модифицирам алг., винаги открива максималния поток. Нещо повече, алг.работи и при цикличен граф.
Накрая ще направим оценка на алг. Ако капацитетите са цели числа, всяка итера-ция увеличава потока поне с една единица. Ако макс.поток е f,то f етапа са достатъчни за намирането му и времето е O(f*│E│). Това е така, защото път мдб намерен за O(│E│) време, при използване на алг. за намиране на най-къс път

в безтегловен граф (unweighted shortest path). За да нама-лим времето, ще избираме винаги пътя с макс поток, при което ще приложим алг.на Дейкстра. Ако cap_max е макс.капацитет на дадено ребро, то O(│E│log cap_max) итера-ции са необх.за получаване на макс.поток. Знаем, че времето за една итерация е O(│E│log│V│) и
=> общото време ще е O(│E│²log│V│log cap_max). Ако работим с много малки капацитети, едно добро прибл.се дава с времето O(│E│²log│V│).
Друг начин за избор на текущ път е пътя с мин.брой ребра. В този случай етапите са O(│E│*│V│) и след като всеки етап изисква O(│E│)време(отново използ.алг.за най-къс път),получаваме O(│E│²│V│) за общото време.За по-нататъшно подобрение на времето, трд се смени структурата данни. Възможно е подобрение на времето и при налагане на някои ограничения,напр. за граф, в който всеки връх има само едно входящо или едно изходящо ребро (без s и t, разбира се) с капацитет 1. В този случай времето е O(│E││V│^1/2).