О максимальном потоке

Алгоритм размещения пометок основан на следующей теореме.

Теорема 1.Теорема про максимальный поток и минимальный разрез. Для произвольной сети максимальная величина потока из v_s в v_t равняется минимальной пропускной способности разреза, который отделяет v_s от v_t.

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

Покажем, что величина w произвольного потока φ не превышает пропускной способности разреза (V_s,V_t), который отделяет v_s от v_t. Поскольку функция φ поток, то она удовлетворяет уравнению (1) сохранении потока:

- = w,

- = 0, v v_s, v _t, (2)

- = - w.

Сложим те уравнения из (2), которые соответствуют вершинам из V_s. Учитывая, что v_s V_s, v_t V_t, получаем:

w = - .

Всё множество вершин распадается на две стороны: V = V_s V_t. Получаем

w = - =

= + - - =

= - ≤ ≤ = c(V_s, V_t).

Теперь нужно показать, что существуют некоторые поток φ и разрез (V_s, V_t), для которых величина потока равняется пропускной способности разреза. Как видно, все потоки от V_s до V_t ограничены и среди них можно выбрать максимальный поток φ. С её помощью определим разрез (V_s, V_t), для которого

= c(V_s, V_t), = 0.

Определим множество V_s рекуррентно:

1) v_s V_s.

2) Если, v_s V_s дуга e идёт из вершины v_i в какую-либо вершину v_j и φ (e) < c (e), то v_j V_s.

3) Если v_i V_s, дуга e идёт из вершины v_r в вершину v_i и φ (e), то v_j V_s.

Шаг 1) построения множества V_s означает, что источник v_s принадлежит построенной стороне разреза. Покажем, что сток тогда лежит на другой стороне разреза – v_t V_t = V/V_s. Допустим противоположное: пусть v_t V_s. Тогда существует “неориентированная” цепь, которая идёт из источника v_s в сток v_t, такая, что для каждой дуги e_i цепи с направлением, совпадающим с ориентацией “от источника к стоку” > 0.

Обозначим через l₁ = min { c (e_j) - c (e_i)} все дуги e_i цепи с направлением, совпадающим с ориентацией “от источника к стоку”, l₂ = min { φ (e_i)} все дуги e_i цепи с направлением, не совпадающим с ориентацией “от источника к стоку”, l = min (l₁, l₂). Поток φ можно увеличить на l, увеличив на l поток на дугах цепи, ведущих “от стока к источнику”. Это противоречит тому, что величина потока φ максимальная величина допустимого потока из вершины v_s в вершину v_t.

Дата добавления: 2015-08-09