1. Сеть. Потоки в сети. Теорема Форда — Фалкерсона

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

Таким образом, можно считать, что пропускные способности рёбер заданы для любой пары вершин. В дискретной математике пропускные способности рёбер, как и все возникающие константы, считаются целыми (или рациональными) числами.

Заметим, что сети имеют огромные приложения, в частности, «сети планирования» (имеется в виду планирование производства некоторых новых, достаточно сложных изделий), где «пропускные способности» рёбер — это время, за которое нужно из нескольких узлов изделия (вершин графа) получить другой (более сложный) узел. Сетевое планирование здесь не исследуется, так как гораздо больший интерес представляет сеть связи, где пропускные способности рёбер — это обычно «количество одновременных разговоров», которые могут происходить между телефонными узлами (вершинами графа).

Поток в сети между (источником) и (стоком) — набор чисел (то есть количество условного «груза», перевозимого из вершины с номером в вершину с номером ), удовлетворяющих четырём условиям:

• Числа (провозимый по ребру груз не должен превосходить пропускной способности этого ребра). Если , то ребро — насыщенно.

• Числа , причем если , то (нет встречных перевозок). Это условие превращает поток в орграф: мы считаем, что в паре вершин, определяющей ребро, первой является та, из которой груз отправляется, а второй — та, куда он отправлен.

• Если вершина — промежуточная (не совпадает с источником и стоком), то

То есть количество груза, вывозимого из вершины , равно количеству груза, ввозимого в эту вершину.

• Количество груза, вывозимого из источника , должно быть равно количеству груза, ввозимого в сток :

Число — величина данного потока (или просто поток между и ).

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

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

Теорема Форда — Фалкерсона (1955). Максимальный поток между вершинами и равен величине минимального сечения между этими вершинами.

Доказательство этой теоремы является конструктивным (то есть показывает, как найти нужный максимальный поток).

1. Докажем сначала, что любой поток между вершинами и меньше или равен величине любого сечения. Пусть дан некоторый поток и некоторое сечение. Величина данного потока складывается из величин «грузов», перевозимых по всем возможным путям из вершины в . Каждый такой путь обязан иметь общее ребро с данным сечением. Так как по каждому ребру сечения суммарно нельзя перевести «груза» больше, чем его пропускная способность, поэтому сумма всех грузов меньше или равна сумме всех пропускных способностей рёбер данного сечения. Утверждение доказано.

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

2. Докажем теперь обратное неравенство. Пусть имеется некоторый поток (какой-то поток всегда существует, например, нулевой, когда все ). Будем помечать вершины графа, причём считаем, что все помеченные вершины образуют множество . Пометки вершин производятся от источника. Далее можно помечать только те непомеченные вершины, для которых найдётся ненасыщенное ребро из помеченной вершины или даже насыщенное ребро, если оно направлено из непомеченной в помеченную (то есть обратно направлено). Каждая пометка вершины (если эта вершина может быть помечена) состоит из двух чисел: первое число — это «» или «» номер вершины (из ), с которой смежна новая помечаемая вершина, и второе — (обязательно должно быть положительным) — это фактически та добавка к потоку, которая может быть «довезена» в эту вершину из источника по сравнению с исходным потоком , допускаемая пропускной способностью ребра.

Более точно, множество помеченных вершин образуется следующим образом:

• Источник принадлежит и его пометка всегда имеет вид ; второе число, условно говоря, равно бесконечности — что для дискретной математики означает, что это больше любого реального числа, которое нам встретится.

Если вершина принадлежит и (дуга — прямая и ненасыщенная), то вершина также принадлежит и пометка вершины равна , где *. Заметим, что здесь число — это число уже помеченной вершины , а знак «» перед номером означает, что дуга, связывающая вершины является прямой и ненасыщенной (идёт от к ).

Если вершина принадлежит и (дуга — обратная), то вершина с номером также должна принадлежать и её пометка , где «» означает, что уже помеченная вершина смежна с непомеченной обратной дугой, ** (груз, направляемый в вершину , считаем отрицательным).

* — вместо можно написать , так как минимум от всех будет рассматриваться далее.

** — вместо можно написать , так как минимум от всех будет рассматриваться далее.

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

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

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

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

Рисунок 11

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

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

Схематичный пример маршрута представлен на следующем рисунке.

Рисунок 12

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

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

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

Рассуждение теоремы Форда — Фалкерсона фактически является алгоритмом нахождения максимального потока между двумя вершинами (или доказательством того, что этот поток является максимальным).

Примечание. Если в данной сети имеется несколько источников и несколько стоков, то описанный выше алгоритм можно применить следующим образом. Вводим новый источник и новый сток, причём новый источник соединяем рёбрами со всеми источниками, а новый сток — со всеми стоками, при этом пропускные способности новых рёбер считаем сколь угодно большими числами, так что эти дуги в любом возможном потоке были бы ненасыщенными (напомним, что ребра, идущие из источника и ребра, идущие в сток, всегда являются прямыми дугами). После этого для нового графа решаем задачу о максимальном потоке (из одного нового источника в один новый сток). Решив её, стираем все введённые ребра и вершины.

Пример.

Таблица 1