О максимальном потоке

Для заданной транспортной сети определить величину максимального потока грузов, которые можно доставить в течение заданного времени из города S в город t. Пропускные способности всех участков дорог считаются известными.

Этап 1

Начнём с процедуры расстановки пометок. Пометка источника S Далее рассмотрим те вершины, которые соединены с источником дугой. Это V, V, V. Пропустим по всей сети первоначальный нулевой поток Припишем около каждой дуги после значения пропускной способности значение первоначального потока.

Просмотрим вершину S, для этого пометим вершиныV, V, V .

Просмотрим вершину V, ставим метки. Просмотрим, ставим метки .

Изменение потока:

Поэтому заменим величину первоначального потока:

на.

на ,.

Этап 2

Просмотрим вершину V1, вершины V4 и V2 получают метки. И просмотрим V3, V2 уже просмотрена,. Просмотрим V2, V4 уже помечена, Изменение потока:

Вносим изменения потока. Дуга (V2, t) стала насыщенной.

Этап 3

Просмотрим вершину V1.

Просмотрим V3, V2 уже помечена, просмотрим V2, V4 уже помечена, просмотрим V4.

Изменение потока:

Вносим изменения потока. Дуга (V3,V2) стала насыщенной.

Этап 4

Просмотрим вершину V3 и V3.

Вносим изменения потока. Дуга (V3, V2) стала насыщенной.

Этап 5

Просмотрим вершину V3.

Просмотрим V6.

Изменение потока:

Вносим изменения потока. Дуга (S, V3) стала насыщенной.

Поток f=21 является максимальным, а множество дуг составляют минимальный разрез сети. Минимальный разрез на рисунке обозначен волнистой линией.