1.1 Способы задания графа

Для задания графа существуют следующие способы:

1. Геометрический (рисунок 1);

Рисунок 1 – Геометрический способ задания графа

2. Матрица смежности (таблица 1)

Таблица 1 – Матрица смежности

	A	b	c	d
a	0	1	1	0
b	1	0	1	0
c	1	1	0	1
d	0	0	1	0

Матрица смежности – квадратная матрица, размерности, равной количеству вершин. При этом а[i, j] - целое число, равное количеству рёбер, связывающих i-ю, j-ю вершину. Если в графе нет петель, то диагональные элементы равны 0. Если рёбра не повторяются, то все элементы 0 или 1. Если граф неориентированный, то матрица симметрична.

1.2 Алгоритм Диница

Алгоритм представляет собой несколько фаз. На каждой фазе сначала строится остаточная сеть, затем по отношению к ней строится слоистая сеть (обходом в ширину), а в ней ищется произвольный блокирующий поток. Найденный блокирующий поток прибавляется к текущему потоку, и на этом очередная итерация заканчивается.

Покажем, что если алгоритм завершается, то на выходе у него получается поток именно максимальной величины.

В самом деле, предположим, что в какой-то момент в слоистой сети, построенной для остаточной сети, не удалось найти блокирующий поток. Это означает, что сток вообще не достижим в слоистой сети из истока. Но поскольку слоистая сеть содержит в себе все кратчайшие пути из истока в остаточной сети, это в свою очередь означает, что в остаточной сети нет пути из истока в сток. Следовательно, применяя теорему Форда-Фалкерсона, получаем, что текущий поток в самом деле максимален.

1.3 Поиск блокирующего потока

Чтобы завершить построение алгоритма Диница, надо описать алгоритм нахождения блокирующего потока в слоистой сети — ключевое место алгоритма.

Мы рассмотрим три возможных варианта реализации поиска блокирующего потока:

Искать s-t пути по одному, пока такие пути находятся. Путь можно найти за O(m) обходом в глубину, а всего таких путей будет O(m) (поскольку каждый путь насыщает как минимум одно ребро). Итоговая асимптотика поиска одного блокирующего потока составит O(m²).

Аналогично предыдущей идее, однако удалять в процессе обхода в глубину из графа все «лишние» рёбра, т.е. рёбра, вдоль которых не получится дойти до стока.

Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое не удалённое ребро, и увеличивать этот указать в цикле внутри обхода в глубину.

1.4 Асимптотика

Оценим асимптотику этого решения. Каждый обход в глубину завершается либо насыщением как минимум одного ребра (если этот обход достиг стока), либо продвижением вперёд как минимум одного указателя (в противном случае). Можно понять, что один запуск обхода в глубину из основной программы работает за O (k + n), где k — число продвижений указателей. Учитывая, что всего запусков обхода в глубину в рамках поиска одного блокирующего потока будет O(p), где p — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за O(pk + pn). Учитывая, что все указатели в сумме прошли расстояние O (m), даёт асимптотику O (m + pn). В худшем случае, когда блокирующий поток насыщает все рёбра, асимптотика получается O (n m); эта асимптотика и будет использоваться далее.

Можно сказать, что этот способ нахождения блокирующего потока чрезвычайно эффективен в том смысле, что на поиск одного увеличивающего пути он тратит O (n) операций в среднем. Именно в этом и кроется разность на целый порядок эффективностей алгоритма Диница и Эдмондса-Карпа (который ищет один увеличивающий путь за O (m)).

Этот способ решения является по-прежнему простым для реализации, но достаточно эффективным, и потому наиболее часто применяется на практике.

Таким образом, весь алгоритм Диница выполняется за O (n² m), если блокирующий поток искать описанным выше способом за O (n m).