Участник:Anastasy/Алгоритм Диница

1 Постановка задачи

1.1 Общее описание алгоритма

Алгоритм Диница -- полиномиальный алгоритм, предназначенный для поиска максимального потока в транспортной сети. Он был предложен советским учёным Ефимом Диницем в 1970 году. Временная сложность алгоритма [math]O(nm^2)[/math].

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

1.2 Математическое описание алгоритма

Математическая постановка задачи приведена в статье ..., мы будем использовать введённые в ней обозначения.

Введём необходимые определения.

Остаточной сетью [math]G^R[/math] по отношению к сети [math]G[/math] и некоторому потоку [math]f[/math] в ней называется сеть, в которой каждому ребру [math](u,v) \in G[/math] с пропускной способностью [math]c_{uv}[/math] и потоком [math]f_{uv}[/math] соответствуют два ребра:

• [math](u,v)[/math] с пропускной способностью [math]c_{uv}^R = c_{uv} - f_{uv}[/math]
• [math](v,u)[/math] с пропускной способностью [math]c_{vu}^R = f_{uv}[/math]

Стоит отметить, что при таком определении в остаточной сети могут появляться кратные рёбра: если в исходной сети было как ребро [math](u,v)[/math], так и [math](v,u)[/math].