Потоки на сетях

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

Сеть – это взвешенный конечный граф без циклов и петель, ориентированный в одном общем направлении от вершины I, являющейся входом (истоком) графа к вершине S, являющейся выходом (стоком) графа.

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

Пусть общее количество вершин сети равно n.

Дугу, выходящую из вершины и заканчивающуюся в вершине , будем обозначать .

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

Если вершины и не соединены, то .

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

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

Если , то дуга называется ненасыщенной, если , то насыщенной.

Совокупность потоков по всем дугам называется потоком по сети или просто потоком.

Задача о максимальном потоке

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

	Общее количество вещества, вытекающего из истока, равно общему количеству вещества, поступающему в сток, (является мощностью потока)
	Поток по дуге не превосходит пропускной способности дуги
	Для любой вершины кроме истока и стока количество поступающего вещества равно количеству исходящего – условие сохранения потока в узлах

Алгоритм решения

1)Построить некоторый начальный поток.

2) Выделить путь из истока в сток по ненасыщенным дугам. Увеличить поток по каждой дуге этого пути на для этого пути. Увеличить поток по каждой дуге этого пути на . Затем процедуру повторить для пункта 2.

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

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

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

2 2 5 5 4 8 1 6 1 7 3 8 2 4 4 4
2 22 5 5 2+1 4 2 8 11 6 1 71 3 8 22 4 42 4
1 – 2 – 5 – 6 2 ед. 1 – 3 – 5 – 6 1 ед. 1 – 4 – 6 2 ед	Насыщенные дуги выделены. На использованных ребрах введена ориентация.
2 22 5 52+1+2 4 2+2 28 11 6 1 71+2 3 82 2+2 22 4 42+2 4
1 – 3 – 4 – 6 2 ед. 1 – 2 – 3 – 4 – 5 – 6 2 ед.	Мощность потока 9 единиц. Пропускная способность каждого из разрезов 4+5=2+1+4+2=9 ед.

Пример 2

2 45

317

4

5

8

1 8367

5

7 1 3 4

45 7

2 445

3174

4

54

8

1 8 3675

5 55

7 1 3 44

4

454 7

1–2–5–7 4 ед.

1–3–6–8 5 ед.

1–4–7–8 4 ед.

2 445

317 4+3

143

54+1

8

1 8 3675+1+1

5 +155

7 11 3 1 4 4

4+3

454+1 7

1–4–5–8 3 ед.

1–2–6–8 1 ед.

1–3–4–7–6–8 1 ед.

Разрез 7+7+4=18

20