Теорема о декомпозиции

Теорема

Теорема (о декомпозиции потока):

Любой поток [math]f[/math] транспортной сети [math]G = (V, E)[/math] можно представить в виде совокупности [math]O(E)[/math] путей из истока в сток и циклов. При этом все пути и циклы имеет положительный поток.

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

[math]\triangleright[/math]

Пусть [math]s[/math] - исток, [math]t[/math] - сток потока [math]f[/math]. Пусть из [math]s[/math] выходит хотя бы одно ребро с положительным потоком. Пойдем по этому ребру, попадем в вершину [math]v_1[/math]. Если [math]v_1[/math] совпадает с [math]t[/math], то найденный путь является путем из [math]s[/math] в [math]t[/math], иначе по закону сохранения потока для вершины [math]v_1[/math] из нее должно выходить хотя бы одно ребро с положительным потоком в некоторую вершину [math]v_2[/math]. Будем продолжать этот процесс до тех пор, пока [math]v_i[/math] не совпадет с [math]t[/math] (найден путь из [math]s[/math] в [math]t[/math]) либо с [math]v_j, j \lt i[/math] или [math]s[/math] (найден цикл). Данный путь (цикл) будет иметь положительный поток [math]f'[/math], равный минимальному среди потоков по всем ребрам пути (цикла). Уменьшая поток каждого ребра этого пути (цикла) на величину [math]f'[/math], получаем новый поток. Будем продолжать описанный алгоритм до тех пор, пока поток из [math]s[/math] не станет нулевым. Потребуем теперь, чтобы потоки из других вершин стали нулевыми. Для этого повторим поиск циклов вышеописанным способом для других вершин. Итак, поскольку потоки по всем ребрам равны нулю, то мы получили искомую декомпозицию потока. Заметим, что после поиска одного пути (цикла) поток хотя бы по одному из ребер обнулится, следовательно, для полного представления потока потребуется не более [math]E[/math] таких операций.

[math]\triangleleft[/math]

Алгоритм

Рассмотрим алгоритм, описанный в доказательстве теоремы. Построение декомпозиции потока можно записать с помощью псевдокода (на вход подается транспортная сеть [math]G = (V, E)[/math]):

Псевдокод

simpleDecomposition(s)
[math] Q \leftarrow \varnothing [/math]
[math] P \leftarrow \varnothing [/math]
[math]v \leftarrow s[/math]
while [math] v \notin P [/math]  
  находим [math] (vu): f(vu)\gt 0 [/math]
  if [math]\neg \exists (vu): f(vu)\gt 0 [/math]
    if [math] v = t [/math]
      break
    else
      return NULL
  [math] Q \leftarrow Q \cup (vu) [/math]
  [math] P \leftarrow P \cup v [/math]
  [math] v \leftarrow u [/math]
if [math]v \in P [/math]
  удаляем из [math]Q[/math] все ребра, найденные до того, как [math]v[/math] была включена в [math]P[/math]
[math]f(Q) \leftarrow f(Q) - \min\limits_{uv \in Q}f(uv) [/math]
return [math](f, Q)[/math]

fullDecomposition()
[math] d \leftarrow \emptyset [/math]
while [math] p = [/math] simpleDecomposition(s) [math] \neq [/math] NULL
  [math] d \leftarrow d \cup p [/math]
for [math] u \in V [/math]
  while [math] p = [/math] simpleDecomposition(u) [math] \neq [/math] NULL
    [math] d \leftarrow d \cup p [/math]
return d

Анализ работы алгоритма

Утверждение:

Время работы алгоритма поиска декомпозиции потока, описанного выше, равно [math]O(VE)[/math].

[math]\triangleright[/math]

Действительно, каждый путь (цикл) содержит не более [math]V[/math] вершин, следовательно поиск пути (цикла) работает за [math]O(V)[/math]. Т. к. декомпозиция потока содержит [math]O(E)[/math] путей, то суммарное время работы составит [math]O(VE)[/math].

[math]\triangleleft[/math]

Источники

Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2005.