uzluga.ru
добавить свой файл
1



Пусть пропускные способности всех дуг равны между собой и равны 1.

  • Пусть пропускные способности всех дуг равны между собой и равны 1.

  • Тогда целочисленный s-t-поток можно рассматривать как набор непересекающихся по дугам (ребрам) s-t-путей.



Theorem 7.1 (Menger [1927] )

  • Theorem 7.1 (Menger [1927] )

  • Пусть G ― граф (ориентированный или неориентированный), пусть s и t две вершины и k N. Тогда существует k реберно-непересекающихся s-t-путей, тогда и только тогда, когда после удаления любых k – 1 ребер t остается достижима из s.



Пусть (G, u, s, t) ― сеть с u ≡1, такая что t достижима после удаления любых k – 1 дуг.

  • Пусть (G, u, s, t) ― сеть с u ≡1, такая что t достижима после удаления любых k – 1 дуг.

  • Тогда минимальным s-t-разрез имеет пропускную способность по крайней мере k.

  • По теореме 6.5 существует целочисленный поток величины по крайней мере k.

  • По теореме 6.7 этот поток можно разложить в целочисленные потоки на s-t-путях.

  • Так как u ≡1 получаем по крайней мере k s-t-путей.





Будем говорить, что два пути вершинно-непересекающиеся если они не имеют общих ребер и общих внутренних вершин (они могут иметь одну или две общих граничных точки).

  • Будем говорить, что два пути вершинно-непересекающиеся если они не имеют общих ребер и общих внутренних вершин (они могут иметь одну или две общих граничных точки).



Theorem 7.2 (Menger [1927] )

  • Theorem 7.2 (Menger [1927] )

  • Пусть G ― граф (ориентированный или неориентированный), пусть s и t две несмежные вершины и k N. Тогда существует k вершинно-непересекающихся s-t-путей, тогда и только тогда, когда после удаления любых k – 1 вершин (отличных от s и t) t остается достижима из s.





Граф с более чем k вершинами и свойством, что он остается связным после удаления любого множества из k−1 вершины называется k-связным.

  • Граф с более чем k вершинами и свойством, что он остается связным после удаления любого множества из k−1 вершины называется k-связным.

  • Граф с не менее чем двумя вершинами называется k-реберно-связным, если он остается связным после удаления любого множества из k−1 ребра.



Следствие 7.3 ( Уитни [1932] )

  • Следствие 7.3 ( Уитни [1932] )

  • Граф G с не менее чем двумя вершинами является k-реберно-связным тогда и только тогда, когда для каждой пары s, t V(G) с s ≠ t существует k реберно-непересекающихся s-t-путей.

  • Граф G с не менее чем k вершинами является k- связным тогда и только тогда, когда для каждой пары s, t V(G) с s ≠ t существует k вершинно-непересекающихся s-t-путей.



Первое утверждение прямо следует из теоремы 7.1.

  • Первое утверждение прямо следует из теоремы 7.1.

  • Если граф не является k-связным, то существуют вершины s и t и множество X из k −1 вершины, такие, что в графе нет s-t-пути после удаления множества X.

  •  в графе нет k вершинно-непересекающихся s-t-путей.

  • Пусть в G есть две вершины s и t для которых нет k вершинно-непересекающихся s-t-путей.

  • Если s и t не смежны, то теорема 7.2  существует множество X из k −1 вершины, такое, что после его удаления в G нет s-t-пути.

  • G не является k-связным.



Пусть s и t соединено множеством F параллельных ребер.

  • Пусть s и t соединено множеством F параллельных ребер.

  • Тогда в G – F нет k – |F| вершинно-непересекающихся s-t-путей. (|F| ≥ 1)

  • Теорема 7.2  существует множество X из k − |F| – 1 вершины, такое, что после его удаления в G нет s-t-пути.

  • Существует вершина v, которая не достижима в G – F – X, либо из s, либо из t.

  • Пусть из t. Добавляя s к X, получаем разделяющее множество вершин мощности не более k – 1.

  • G не является k-связным.



Дано: Два орграфа (G, H) на одном множестве вершин.

  • Дано: Два орграфа (G, H) на одном множестве вершин.

  • Найти семейство (Pf)fE(H) реберно-непересекающихся путей в G таких, что для каждого ребра(дуги) f = (t, s) в H, Pf s-t-путь.

  • Такое семейство называется решением (G, H).



Предложение 7.4

  • Предложение 7.4

  • Пусть (G, H) пример задачи «Ориентированные реберно-непересекающиеся пути» такой, что H является множеством параллельных ребер и G + H ― эйлеров граф. Тогда (G, H) имеет решение.



Input: Сеть (G, u, s, t).

  • Input: Сеть (G, u, s, t).

  • Output: s-t-поток f максимального значения.

  • Set f(e) = 0 для всех e E(G).

  • Найти кратчайший по числу ребер f-увеличивающий путь P. If такого пути нет then stop.

  • Вычислить Увеличить f вдоль P на γ и go to 2.



Лемма 7.5

  • Лемма 7.5

  • Пусть f1, f2, ... последовательность потоков, таких что fi+1 получается из fi увеличением потока вдоль Pi, где Pi ― кратчайший fi-увеличивающий путь. Тогда

  • a) |E(Pk)| ≤ | E(Pk+1)| для всех k.

  • b) |E(Pk)| + 2 ≤ |E(Pl)| для всех k < l таких, что PkPl содержит пару обратных дуг.



Рассмотрим граф G1, который получается из PkPk+1 удалением обратных дуг. (Дуги, появляющиеся в обоих путях, берутся дважды).





Рассмотрим граф G1, который получается из PkPk+1 удалением обратных дуг. (Дуги, появляющиеся в обоих путях, берутся дважды).

  • Рассмотрим граф G1, который получается из PkPk+1 удалением обратных дуг. (Дуги, появляющиеся в обоих путях, берутся дважды).

  • Так как для любой дуги в E(Gfk)\E(Gfk+1) путь Pk должен содержать обратную ей дугу, то E(G1)  E(Gfk).





Рассмотрим граф G1, который получается из PkPk+1 удалением обратных дуг. (Дуги, появляющиеся в обоих путях, берутся дважды).

  • Рассмотрим граф G1, который получается из PkPk+1 удалением обратных дуг. (Дуги, появляющиеся в обоих путях, берутся дважды).

  • Так как для любой дуги в E(Gfk)\E(Gfk+1) путь Pk должен содержать обратную ей дугу, то E(G1)  E(Gfk).

  • Пусть H1 состоит из двух копий (t,s). Тогда G1+ H1 Эйлеров.





Рассмотрим граф G1, который получается из PkPk+1 удалением обратных дуг. (Дуги, появляющиеся в обоих путях, берутся дважды).

  • Рассмотрим граф G1, который получается из PkPk+1 удалением обратных дуг. (Дуги, появляющиеся в обоих путях, берутся дважды).

  • Так как для любой дуги в E(Gfk)\E(Gfk+1) путь Pk должен содержать обратную ей дугу, то E(G1)  E(Gfk).

  • Пусть H1 состоит из двух копий (t,s). Тогда G1+ H1 Эйлеров.

  • Предложение 7.4   два реберно-непересекающихся пути Q1 и Q2.

  • E(G1)  E(Gfk)  Q1 и Q2 увеличивающие пути в Gfk.



Pk был выбран кратчайшим путем.

  • Pk был выбран кратчайшим путем.

  • |E(Pk)| ≤ |E(Q1)| и |E(Pk)| ≤ |E(Q2)|.

  • 2|E(Pk)| ≤ |E(Q1)| + |E(Q2)| ≤ |E(G1)| ≤

  • |E(Pk)| + |E(Pk+1)|.

  • |E(Pk)| ≤ |E(Pk+1)|.



Пусть k < l такие, что для любого i, k < i < l Pi Pl не содержит обратных дуг.

  • Пусть k < l такие, что для любого i, k < i < l Pi Pl не содержит обратных дуг.

  • Рассмотрим граф G1, который получается из PkPl удалением обратных дуг.

  • E(G1)  E(Gfk)

    • E(Pk)  E(Gfk), E(Pl)  E(Gfl)
    • Любая дуга в E(Gfl)\E(Gfk) должна быть обратной дуге в одном из путей Pk, Pk+1,…, Pl–1.
    • По выбору k и l только Pk содержит обратные дуги.
  • 2|E(Pk)| ≤ |E(Q1)| + |E(Q2)| ≤ |E(G1)| ≤

  • |E(Pk)| + |E(Pk+1)| – 2.



Теорема 7.6 (Edmonds, Karp [1972] )

  • Теорема 7.6 (Edmonds, Karp [1972] )

  • Алгоритм Эдмондса-Карпа остановится, сделав не более чем mn/2 увеличений, где m ― число ребер и n ― число вершин.



Пусть P1, P2,… увеличивающие пути, выбранные в алгоритме Эдмонса-Карпа.

  • Пусть P1, P2,… увеличивающие пути, выбранные в алгоритме Эдмонса-Карпа.

  • По выбору γ на шаге 3 алгоритма, каждый увеличивающий путь содержит по крайней мере одну узкую дугу e: uf (e) = γ.

  • Пусть Pi1, Pi2 ,… последовательность увеличивающих путей, в которых дуга e узкая.

  • Тогда между Pij, Pij+1 должен быть увеличивающий путь с обратной дугой к e.



Лемма 7.5 b) 

  • Лемма 7.5 b) 

  • |E(Pij)| + 4 ≤ |E(Pk)| + 2 ≤ |E(Pij+1)| для всех j.

  • 1 ≤ |E(Pij)| ≤ n – 1 

  •  не более n/4 увеличивающих путей, в которых дуга e узкая.

  • Так как любой увеличивающий путь содержит по крайней мере одну дугу из Ğ, как узкую, то  не более (n|E(Ğ)|)/4 =(mn)/2 увеличивающих путей.



Следствие 7.7

  • Следствие 7.7

  • Алгоритм Эдмондса-Карпа решает Задачу «Максимальный Поток» за O(m2n) элементарных операций.



Функция f : E(G) → R+ является максимальным s-t-потоком тогда и только тогда, когда выполнены следующие три условия:

  • Функция f : E(G) → R+ является максимальным s-t-потоком тогда и только тогда, когда выполнены следующие три условия:

  • в Gf не существует f-увеличивающего пути.



Определение 7.8

  • Определение 7.8

  • Дана сеть (G, u, s, t), функция f : E(G) → R+ , удовлетворяющая f(e) ≤ u(e) для всех e E(G) и

  • Назовем вершину v V(G)\{s,t} активной, если exf (v) > 0.

  • s-t-Предпоток является s-t-потоком тогда и только тогда, когда нет активных вершин.



Определение 7.9

  • Определение 7.9

  • Даны сеть (G, u, s, t) и s-t-предпоток f . Функцией расстояния называется функция: V(G) → Z+ такая, что (t) = 0, (s) = n и(v) ≤ (w) + 1 для всех (v, w)  E(Gf).

  • Дуга e = (v, w)  E(Ğ) называется допустимой если

  • e E(Gf) и (v) = (w) + 1.



В процессе работы алгоритм строит последовательность предпотоков и задает функцию расстояния на них.

  • В процессе работы алгоритм строит последовательность предпотоков и задает функцию расстояния на них.

  • Алгоритм стартует с предпотока, который вдоль дуг, выходящих из s, равен их пропускным способностям и 0 вдоль остальных дуг и с функции расстояния (s) = n и (v) = 0 для всех v V(G) \{s}.

  • Алгоритм останавливается, когда в сети нет активных вершин.



Input: Сеть (G, u, s, t).

  • Input: Сеть (G, u, s, t).

  • Output: максимальный s-t-поток f.

  • Set (s) = n и (v) = 0 для всех v V(G) \{s}.

  • Set f(e) := u(e) для каждого e  δ+(s). Set f(e) := 0 для каждого e E(G) \δ+(s).

  • While существуют активные вершины do:

  • Пусть v ― активная вершина

  • If нет допустимой дуги e  δ+(v)

  • then Relabel(v)

  • else Push(e) ( e  δ+(v) произвольная допустимая дуга )

  • Push(e): 1) Set γ:= min{exf (v), uf (e)}, где v ― вершина с e  δ+(v).

  • 2) Увеличим f вдоль e на γ.

  • Relabel(v): Set (v):= min{(w)+1: e = (v, w)  E(Gf)}. ((v) ↑)





Предложение 7.10

  • Предложение 7.10

  • В процессе работы Алгоритма Проталкивания Предпотока f всегда является s-t-предпотоком ивсегда является функцией расстояния относительно f.



Предпоток изменяется только в процедуре Push.

  • Предпоток изменяется только в процедуре Push.

  • Так как γ:= min{exf (v), uf (e)}, то после процедуры Push f остается предпотоком.

  • Так как (v):= min{(w) + 1: e = (v, w)  E(Gf)}, то остается функцией расстояния после процедуры Relable.

  • Покажем, что после процедуры Push(e) также остается функцией расстояния относительно нового предпотока.



Необходимо показать, что (a) ≤ (b) + 1 для всех новых дуг (a, b) в Gf .

  • Необходимо показать, что (a) ≤ (b) + 1 для всех новых дуг (a, b) в Gf .

  • Поскольку в процедуре Push(e) поток изменяется только вдоль дуги e = (v, w), то новой в Gf может быть только одна дуга (w, v), обратная к e.

  • Так как e была допустимой дугой, то (w) = (v) – 1 ≤ (v) + 1.



Лемма 7.11

  • Лемма 7.11

  • Если f ― s-t-предпоток ифункция расстояния относительно f, то

  • s достижима из любой активной вершины в Gf .

  • t не достижима из s в Gf .



Пусть v активная вершина, и пусть R множество вершин достижимых из v в Gf .

  • Пусть v активная вершина, и пусть R множество вершин достижимых из v в Gf .

  • Тогда f(e) = 0 для всех e δ −(R) в G.

  • v – активная  exf (v) > 0

  •  w R, такая что exf (w) < 0

  • f – предпоток, то такая вершина может быть только s.



Пусть существует s-t-путь в Gf , например s = v0, v1, …, vk = t.

  • Пусть существует s-t-путь в Gf , например s = v0, v1, …, vk = t.

  • (vi) ≤ (vi+1) + 1, i = 0,…k – 1.

  • (s) ≤ (t) + k.

  • Но (s) = n, (t) = 0 и k n – 1.



Теорема 7.12

  • Теорема 7.12

  • Когда Алгоритм Проталкивания Предпотока останавливается, f является максимальным s-t-потоком.



Лемма 7.13

  • Лемма 7.13

  • a) Для каждого v V(G), (v) строго возрастает при каждом выполнении процедуры Relabel(v), и никогда не убывает.

  • На любом шаге алгоритма,  (v) ≤ 2n – 1 для всех v V(G).

  • Общее число вызовов процедуры Relabel не превышает 2n2.



Процедура Push(e) называется проталкиванием, примененным к вершине v. Проталкивание называется насыщающим, если в результате ребро e становится насыщенным, то есть если uf (e) обращается в нуль (ребро исчезает из остаточного графа); в противном случае проталкивание считают ненасыщающим.

  • Процедура Push(e) называется проталкиванием, примененным к вершине v. Проталкивание называется насыщающим, если в результате ребро e становится насыщенным, то есть если uf (e) обращается в нуль (ребро исчезает из остаточного графа); в противном случае проталкивание считают ненасыщающим.



Лемма 7.14

  • Лемма 7.14

  • Число насыщающих проталкиваний не превышает mn.



Доказательство



Для получения оценки O(n3) на число ненасыщающих проталкиваний мы должны выбрать порядок в котором применяются процедуры Push и Relabel.

  • Для получения оценки O(n3) на число ненасыщающих проталкиваний мы должны выбрать порядок в котором применяются процедуры Push и Relabel.

  • Как обычно, предположим, что орграф G задан листом смежности, то есть для каждой вершины v указан список list(v) дуг выходящих из v. При этом указатель curr(v) указывает на один элемент в списке list(v) (вначале на первый элемент в списке).



Input: Сеть (G, u, s, t).

  • Input: Сеть (G, u, s, t).

  • Output: Максимальный s-t-поток f.

  • Set (s) = n и (v) = 0 для всех v V(G) \{s}.

  • Set f(e) := u(e) для каждого e  δ+(s). Set f(e) := 0 для каждого e E(G) \δ+(s).

  • For всех v V(G) do: curr(v):= первый элемент list(v)

  • Set Q:={v V(G): v ― активная }. If Q = ø then stop.

  • For всех v Q do: Discharge(v).

  • Go to 4.

  • Discharge(v)

  • Set e:= curr(v).

  • If e допустимо then Push(e) else do:

  • If e последнее ребро в list(v) then Relabel(v),

  • curr(v):= первый элемент list(v), return,

  • else curr(v):= следующий элемент list(v).

  • 3. If exf (v) > 0 then go to 1.



Лемма 7.15

  • Лемма 7.15

  • Процедура Discharge вызывает процедуру Relabel только, если v активна и нет допустимых ребер в +(v).



  • Discharge(v)

  • Set e:= curr(v).

  • If e допустимо then Push(e) else do:

  • If e последнее ребро в list(v) then Relabel(v),

  • curr(v):= первый элемент list(v), return,

  • else curr(v):= следующий элемент list(v).

  • 3. If exf (v) > 0 then go to 1.



Вершина v всегда активна перед выполнением шага 2 процедуры Discharge(v).

  • Вершина v всегда активна перед выполнением шага 2 процедуры Discharge(v).

  •  Процедура Discharge вызывает процедуру Relabel только, если v активна.

  • Осталось показать, что в момент вызова Relabel (v) ≤ (w) .

  • Рассмотрим произвольную дугу e =(v,w) E(Gf).

  • С момента предыдущего вызова Relabel для вершины v весь список ее дуг был просмотрен. В частности, указатель curr (v) указывал и на дугу e. Поскольку, он ее покинул, то

    • либо (v) < (w) + 1
    • либо e E(Gf) и появилась в Gf позднее, когда проталкивался поток по дуге =(w,v) и (w) = (v) + 1 > (v).


Лемма 7.16

  • Лемма 7.16

  • Число ненасыщающих проталкиваний не превышает 4n3.



Так как γ:= min{exf (v), uf (e)}, то на каждой итерации шага 5 может быть не более одного ненасыщающего проталкивания для каждой вершины.

  • Так как γ:= min{exf (v), uf (e)}, то на каждой итерации шага 5 может быть не более одного ненасыщающего проталкивания для каждой вершины.

  • Покажем, что число итераций шага 5 ≤ 4n2.

  • Разделим все итерации на итерации с запуском Relabel и без запуска.

  • Лемма 7.13 с)  не более 2n2 итераций с Relabel



Пусть Ψ = max{(v) : v - активная}

  • Пусть Ψ = max{(v) : v - активная}

  • Ψ = 0, если нет активных вершин.

  • На каждой итерации без Relabel Ψ уменьшается минимум на 1.

    • Пусть w – активная вершина после шага 5 без Relabel. Так как шаг 5 выполнялся для всех активных на тот момент вершин, то w стала активной в процессе этой итерации шага 5 по причине проталкивания потока по дуге (v,w).
    • v была активной и (v) = (w) + 1
  • В начале и в конце алгоритма Ψ = 0  число итераций без Relabel не больше суммарной величины Δ на которое Ψ увеличивается в течение работы алгоритма.

  • Так как увеличение Ψ соответствует увеличению (v) в результате Relabel, то Δ ≤ 2n2 (по Лемме 7.13 ).



Теорема 7.17 (Goldberg, Tarjan [1988])

  • Теорема 7.17 (Goldberg, Tarjan [1988])

  • Алгоритм Голдберга-Тарьяна определяет максимальный s-t-поток за время O(n3).



Дано: Сеть (G, u, s, t).

  • Дано: Сеть (G, u, s, t).

  • Найти s-t-разрез в G с минимальной пропускной способностью.



Предложение 7.18

  • Предложение 7.18

  • Задача «Разрез с минимальной пропускной способностью» может быть решена за то же самое время как и задача «Максимальный Поток», в частности за время O(n3).



Построить линейный алгоритм для задачи «Максимальный Поток», для случая когда G – t является ордеревом с корнем в s.

  • Построить линейный алгоритм для задачи «Максимальный Поток», для случая когда G – t является ордеревом с корнем в s.



Задан ациклический орграф с весами с : E(G) → R+ , найти максимальный взвешенный ориентированный разрез в G.

  • Задан ациклический орграф с весами с : E(G) → R+ , найти максимальный взвешенный ориентированный разрез в G.

  • Показать как эта проблема может быть сведена к задаче «Разрез с минимальной пропускной способностью» и решена за время O(n3).