🗊Презентация Потоковые Алгоритмы. Лекция 7

Потоковые Алгоритмы Лекция 7

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

Первая Теорема Менгера 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 дуг. Тогда минимальным s-t-разрез имеет пропускную способность по крайней мере k. По теореме 6.5 существует целочисленный поток величины по крайней мере k. По теореме 6.7 этот поток можно разложить в целочисленные потоки на s-t-путях. Так как u ≡1 получаем по крайней мере k s-t-путей.

Доказательство (для графа)

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

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

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

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

Характеризация k-связных графов Следствие 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. Если граф не является 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 смежны) Пусть 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) на одном множестве вершин. Найти семейство (Pf)fE(H) реберно-непересекающихся путей в G таких, что для каждого ребра(дуги) f = (t, s) в H, Pf ― s-t-путь. Такое семейство называется решением (G, H).

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

Алгоритм Эдмонса-Карпа 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 Пусть f1, f2, ... последовательность потоков, таких что fi+1 получается из fi увеличением потока вдоль Pi, где Pi ― кратчайший fi-увеличивающий путь. Тогда a) |E(Pk)| ≤ | E(Pk+1)| для всех k. b) |E(Pk)| + 2 ≤ |E(Pl)| для всех k < l таких, что Pk⋃Pl содержит пару обратных дуг.

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

Граф G1

Доказательство a) Рассмотрим граф G1, который получается из Pk Pk+1 удалением обратных дуг. (Дуги, появляющиеся в обоих путях, берутся дважды). Так как для любой дуги в E(Gfk)\E(Gfk+1) путь Pk должен содержать обратную ей дугу, то E(G1)  E(Gfk).

Остаточные графы

|E(Pk)| ≤ | E(Pk+1)| для всех k Рассмотрим граф G1, который получается из Pk Pk+1 удалением обратных дуг. (Дуги, появляющиеся в обоих путях, берутся дважды). Так как для любой дуги в E(Gfk)\E(Gfk+1) путь Pk должен содержать обратную ей дугу, то E(G1)  E(Gfk). Пусть H1 состоит из двух копий (t,s). Тогда G1+ H1 Эйлеров.

G1+ H1

|E(Pk)| ≤ | E(Pk+1)| для всех k Рассмотрим граф G1, который получается из Pk Pk+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.

|E(Pk)| ≤ | E(Pk+1)| для всех k 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)|.

|E(Pk)| + 2 ≤ |E(Pl)| для всех k < l таких, что Pk⋃Pl содержит пару обратных дуг Пусть k < l такие, что для любого i, k < i < l Pi  Pl не содержит обратных дуг. Рассмотрим граф G1, который получается из Pk Pl удалением обратных дуг. 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] ) Алгоритм Эдмондса-Карпа остановится, сделав не более чем mn/2 увеличений, где m ― число ребер и n ― число вершин.

Доказательство Пусть P1, P2,… увеличивающие пути, выбранные в алгоритме Эдмонса-Карпа. По выбору γ на шаге 3 алгоритма, каждый увеличивающий путь содержит по крайней мере одну узкую дугу e: uf (e) = γ. Пусть Pi1, Pi2 ,… последовательность увеличивающих путей, в которых дуга e узкая. Тогда между Pij, Pij+1 должен быть увеличивающий путь Pк с обратной дугой к e.

Доказательство Лемма 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 Алгоритм Эдмондса-Карпа решает Задачу «Максимальный Поток» за O(m2n) элементарных операций.

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

s-t-Предпоток Определение 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 Даны сеть (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). 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) ↑)

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

Доказательство Предпоток изменяется только в процедуре 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 . Поскольку в процедуре Push(e) поток изменяется только вдоль дуги e = (v, w), то новой в Gf может быть только одна дуга (w, v), обратная к e. Так как e была допустимой дугой, то  (w) =  (v) – 1 ≤  (v) + 1.

Алгоритм проталкивания предпотока (3) Лемма 7.11 Если f ― s-t-предпоток и  функция расстояния относительно f, то s достижима из любой активной вершины в Gf . t не достижима из s в Gf .

Доказательство a) Пусть v активная вершина, и пусть R множество вершин достижимых из v в Gf . Тогда f(e) = 0 для всех e  δ −(R) в G. v – активная  exf (v) > 0  w  R, такая что exf (w) < 0 f – предпоток, то такая вершина может быть только s.

Доказательство b) Пусть существует 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.

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

Число вызовов процедуры Relabel Лемма 7.13 a) Для каждого v  V(G),  (v) строго возрастает при каждом выполнении процедуры Relabel(v), и никогда не убывает. На любом шаге алгоритма,  (v) ≤ 2n – 1 для всех v  V(G). Общее число вызовов процедуры Relabel не превышает 2n2.

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

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

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

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

Алгоритм Голдберга-Тарьяна 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 Процедура 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).  Процедура 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 Число ненасыщающих проталкиваний не превышает 4n3.

Доказательство Так как γ:= min{exf (v), uf (e)}, то на каждой итерации шага 5 может быть не более одного ненасыщающего проталкивания для каждой вершины. Покажем, что число итераций шага 5 ≤ 4n2. Разделим все итерации на итерации с запуском Relabel и без запуска. Лемма 7.13 с)  не более 2n2 итераций с Relabel

Число итераций шага 5 без Relabel Пусть Ψ = 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]) Алгоритм Голдберга-Тарьяна определяет максимальный s-t-поток за время O(n3).

Задача «Разрез с минимальной пропускной способностью» Дано: Сеть (G, u, s, t). Найти s-t-разрез в G с минимальной пропускной способностью.

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

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

Упражнение 7.2 Задан ациклический орграф с весами с : E(G) → R+ , найти максимальный взвешенный ориентированный разрез в G. Показать как эта проблема может быть сведена к задаче «Разрез с минимальной пропускной способностью» и решена за время O(n3).