§ 2. Максимальный поток через сеть. Алгоритм

ФОРДА – ФАЛКЕРСОНА

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

Наиболее часто в сети решается задача о максимальном потоке и минимальном разрезе.

Разрезом графа G называют некоторое множество дуг (ребер) этого графа, удаление которых делает этот граф несвязным.

Пусть задана сеть . Каждой дуге поставлено в соответствие неотрицательное число , называемое пропускной способностью дуги.

Пусть v – произвольная вершина сети. Обозначим через множество дуг, заходящих в v , а через множество дуг, выходящих из v.

Потоком сети называют функцию , удовлетворяющую условиям:

где вершина s – исток сети, а вершина t – сток сети.

Функцию можно рассматривать как количество вещества, протекающего (в единицу времени) по дуге от вершины v_i к вершине v_j .

Второе условие в определении потока называют условием сохранения потока: в промежуточных вершинах потоки не создаются и не исчезают. А это означает, что поток, выходящий из вершины истока s, в точности равен потоку, входящему в вершину стока t.

Величина называется остаточной пропускной способностью дуги .

Если , то дуга называется насыщенной.

Теорема. Максимальный поток через сеть G равен минимальной пропускной способности ее разреза.