Решение. Этап 1.

Шаг 1.

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

путь : , значит, по этому пути пропускаем поток в 2 единицы;

путь : , значит, по этому пути пропускаем поток в 3 единицы;

путь : , значит, по этому пути пропускаем поток в 1 единицу.

Шаг 2. Путь содержит насыщенную дугу . Больше нельзя добавить потока по этому пути. Пути , и содержат насыщенные дуги.

Но путь имеет две дуги, которые еще ненасыщенные.

Шаг 3. Увеличиваем поток по найденному пути: . Значит, на этом пути поток увеличиваем на 1 единицу, и тем самым дуга стала насыщенной.

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

Этап 2.

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

Шаг 5, 6. Вершину пометить . На шаге 6 предусматривается пометка вершин, смежных с вершиной I, соединенных ненасыщенными дугами. Но на построенной сети таких вершин нет.

В результате вершина S оказалась непомеченной.

Этап 3. Шаг 8. Так как вершина S непомеченная, то поток, сформированный на сети, получился максимальным.

Строим разрез на сети. Разбиваем множество вершин на два подмножества: A и B. Так как только одна вершина оказалась помеченной, то множество A состоит из одной вершины I, а остальные образуют множество B:

.

Проводим разрез , который состоит из дуг и :

.

Определяем величину максимального потока :

(ед.),

Задача 2. На заданной сети в скобках указаны пропускные способности дуг. Требуется сформировать на сети максимальный поток, направленный из истока в сток , и выписать ребра, образующие на сети разрез минимальной пропускной способности.

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