Потоки в сетях

g,i,j, источником S и стоком t.S,t X.Множество чисел ,определенных на

дугах ( , называется потоками в

дугах, если выполняется условие

максимальной.

0-й поток), затем стремится увеличить величину потока с помощью систематического

поиска всех возможных аугментальных целей потока от s к t. Поиск аугментальной цели осуществляется с помощью расставленных пометок в вершинах графа. Поэтому указывают, вдоль каких дуг может быть увеличен поток и на сколько.
Как только найдена одна из таких цепей, поток вдоль нее увеличивают до max значения, а пометки в вершинах стираются и вновь полученный поток используется в качестве исходного при новой расстановке пометок. Алгоритм работу заканчивает и дает max поток, если нельзя найти ни 1 аугментальную цель.

t) потоке.
А. Расстановка пометок.

циклов, нумерация вершины от меньшего номера к большему).

может быть получена.
Новые потоки;

для
Пометка для
Пометка для
Пометка для
Пометка для
и

не отмечены.

Итерация 6.
Пометка для
Пометка для
Пометка для
не может быть

помечена.

29,а min разрез имеет вид;
Величина min разреза =10+4+8+7=29= величине max

потока. Вершина 9 не помечена и никаких других пометок нельзя расставить.

Min разрез отделяет множество помеченных вершин

от непомеченных

Пример.

от
к
Начальный поток – с нулевыми значениями на всех

дугах.

Шаг 1. Припишем

пометку

Шаг 2. (1) множество вершин

есть

2.Множество вершин

не помечена.

Итак,

помечена и просмотрена,

и

помечены и не просмотрены,

а все остальные вершины не помечены.

помечены и просмотрены, а
и
помечены, но не просмотрены.
Взяв

для просмотра

и повторяя шаг 2, прейдем к следующим пометкам;

пометкой будет

для

пометкой будет

Беря для просмотра

найдем, что никаких пометок расставить нельзя

Продолжим просмотр с

получим следующие потоки:

до их стирания на шаге 6:
- насыщенная дуга.
Стираем пометки

и возвращаемся к шагу 1 для второго прохода ,получим:

пометки вершин до стирания имеют вид: