84. Алгоритм Форда-Фалкерсона построения максимального потока.

Теорема (Форда-Фалкерсона). Если - допустимый поток максимальной мощности в сети , то существует такой разрез , что .

Алгоритм Форда-Фалкерсона для построения максимального потока.

1) Пропускаем по сети любой допустимый поток.

2) Следуем следующему алгоритму:

2.1) Помечаем источник , но не окрашиваем. Все остальные вершины делаем непомеченными.

2.2) Если помечена, то строим увеличивающий поток и переходим к шагу 2.1.

2.3) Если существуют помеченные неокрашенные вершины, то рассматриваем все вершины смежные с помеченной : если , то помечаем , если , то помечаем , иначе вообще не помечаем вершину . Окрашиваем и переходим к шагу 2.2.

2.4) , . Алгоритм завершает работу.

85. Необходимые и достаточные условия существования эйлерова цикла в графе.

Опр. Неориентированным графом наз. G=E(V,E), где E<= V⁽²⁾ причём |V|<∞, v_iV – вершины G, e_iE – рёбра графа G.

Опр. Маршрутом, соед. v₁ и v_e+1 или {v₁, v_e+1} наз. посл-сть v₁,e₁,v₂,e₂,…,e_e,v_e+1, где e_i={v_i,v_i+1}.

Маршрут, все рёбра которого различны наз. цепью. Если v₁=v_e+1, то цепь, соед. v₁ и v₁ наз простым циклом.

Опр. Граф наз эйлеровым, если в нём существует цикл, содержащий все его рёбра (эйлеров цикл).

Теор. Связный граф является эйлеровым тогда и только тогда, когда степень каждой его вершины чётна.

Док. (=>)

Эйлеров цикл – цепь => каждое ребро войдёт в него ровно 1 раз. Т.к. цикл проходит через все вершины графа, то в каждую вершину он входит по одному ребру, а выходит по другому, причём больше эти рёбра в цикле не встречаются => степень вершины чётна.

(<=)

По индукции.

n = 3 – очевидно верно.

Пусть верно для n`<n.

Док-м для n.

По усл. граф связен и имеет чётные степени всех вершин => степень каждой вершины >= 2, а значит в графе существует простой цикл C. Рассм. Граф G\C. Он состоит из конечного числа, непересекающихся связных компонент C₁,…, C_n. Для Сi число рёбер <n, а степень каждой вершины чётна. Значит по предположению эйлеров цикл для G строится след. образом: выбираем  вершину C и идём по этому циклу до вершины общей с какой-либо С_i, затем проходим эйлеров цикл C_i и т.д.

86. Теорема о разложении положительного потока.

Опр. Пусть G=(V,E) – сеть. f:E→R наз. потоком, если  v-внутренних вершин div f(v)=0. где ; M(f) = div f(s) = - div f(t)

Опр. Элементарными путями в сети с источником s и стоком t наз.  ориент. циклы без самопересечений, и  ориентированные циклы (s, t)- и (t, s)-пути без самопересечений.

Теор.(о разложении положительного потока)

 положительный поток f в сети G можно представить в виде суммы не более чем m+1 (m=|E|) элементарных потоков:

с – эл. циклы, p – пути. При этом если

M(f) > 0, то (s, t)P – путь

M(f) < 0, то (t, s)P – путь

87. Потоки мин. Стоимости. Алгоритм Басакера-Гоуэна.

Пусть G=(V,E)-сеть. c(e)>0 – пропускная способность G, d(e) – удельная стоимость, eE. f- доп. поток на G, тогда его стоимостью наз .Задача – для G с заданными c и d найти доп. поток f мощности m и минимальной стоимости S(f). G_f – граф модифицированных стоимостей для f на G(V, E) строится по таким правилам:

V_f = V; если с(e) – f(e) > 0, то eE_f и d_f (e)=d(e)

f(e) > 0, то -eE_f и d_f (-e)= -d(e)

Алгоритм Басакера-Гоуэна:

1. Пропускаем f – нулевой поток

2. Строим G_f. Находим в G_f путь min стоимости из s в t P_f. Если (s,t) пути в G_f нет, то алгоритм закончен.

3) На соотв. пути P в графе G считаем

ε = min{ eP, c(e)-f(e), если e в G и G_f совпадает

m, f(e), если e в G и G_f против. }

4) Увеличиваем f на ε на пути p. Переходим к п.1.