Сети: опр., пути в сетях, алгоритм Форда - Фалкерсона.

Опр1: Пусть задан ориен-ный граф G=(x,A) с вершинами . Каждой дуге поставлено в соответствие число , называемое пропускной способностью дуги. Такой граф будем называть сетью. Функцию , определённую на множестве дуг сети назовём потоком сети, если , , выполняется . множество дуг выходящих из вершины – множество дуг входящих в , .

Опр2: Назовём дугу насыщенной, если поток этой дуги равен её пропускной способности, т.е. .

Пути:Теорема 1. Пусть - путь . Если все дуги этого пути не насыщенные, то можно увеличить поток сети.

Опр3: Цель для которой называется насыщенной.

Опр4: Поток в сети назовём полным, если любой путь, соединяющий исток со стоком (s с t) содержит по крайне мере 1 насыщенную дугу.

Теорема 3. В сети цепи от с , то поток нельзя больше увеличить, т.е. он максимальный.

Теорема 4.(Форда Фалкерсона) Для заданной сети макси максимальное значение потока равно минимальной пропускной способности разреза.

Алгоритм Форда Фалкерсона поиска максимального потока в сети.

1)Строим произвольный поток (нулевой)

2)Ищем полный поток. Если поток не полный, то в сети путь, все дуги которого не насыщены. Увеличиваем поток через эти дуги до тех пор, пока не насытится, по крайней мере, 1 из дуг. Т.о., получаем новый поток . Если он не полный, то операцию повторяем.

3)Отыскание максимального потока.

а) Помечаем вершину S символом +.

б) Если вершина помечена, то символом + помечаем все вершины х, для которых пути не насыщены.

в) Если таким образом удалось пометить сток t, то цепь, идущая через помеченные вершины к t. Вычисляем и увеличиваем поток на . Процедура повторяется пока удаётся пометить сток t. Иначе идти к 4).

4) Конец алгоритма.