Решение. Этап 1. Сформируем на сети какой-либо начальный поток

Сформируем на сети какой-либо начальный поток. Рассмотрим путь . Поскольку , по этому пути пропускаем поток в 2 единицы. На сети значение потока обозначим числами без скобок. По пути пропускаем поток в 4 единицы, так как . По пути пропускаем поток в 3 единицы, так как . Таким образом, начальный поток имеет вид:

,

,

.

Начальный поток изображен на рисунке.

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

Теперь каждый из этих путей содержит насыщенную дугу, следовательно, полученный поток – насыщенный.

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

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

Этап 2.

На построенной сети помечаем вершины. Вершину пометим . Смежную ей вершину помечаем , так как эти вершины соединяет ненасыщенная дуга . Вершину помечаем , так как вершины и соединяет ненасыщенная дуга . Вершину помечаем , так как вершины и соединяет непустая дуга . Вершины и помечаем , так как они соединены с вершиной ненасыщенными дугами и . Вершина смежная вершине , и эти вершины соединены ненасыщенной дугой , поэтому вершину помечаем . Вершина смежная вершине , и эти вершины соединены ненасыщенной дугой , поэтому вершину помечаем .

Вершина оказалась помеченной. Значит, существует последовательность помеченных вершин от к : . В этой последовательности каждая последующая вершина помечена буквой предыдущей вершины. Перераспределим поток на этом пути. Определим число : . Увеличиваем на 1 единицу поток на дугах, имеющих направление от к : , , , . Уменьшаем на 1 единицу поток на дугах, имеющих обратное направление: . Получаем следующую сеть с новым сформированным потоком, который изображен на рисунке.

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

Вновь помечаем вершины. Вершину пометим . Смежную ей вершину помечаем , так как эти вершины соединяет ненасыщенная дуга . Все остальные вершины, в том числе и вершина , остаются непомеченными. Значит, поток на сети максимальный.

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