Транспортные сети ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекция 15 Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная дискретная математика

Основные определения Сеть – это связный ориентированный граф без петель, в котором: 1. Имеется только одна вершина (узел), в которую не заходит ни одна дуга, называемая входом (истоком) x 0 2. Имеется только одна, вершина (узел), из которой не выходит ни одна дуга, называемая выходом (стоком) z 3. Каждой дуге u присвоена числовая характеристика C(u) 0, которая называется пропускной способностью дуги u 2

Пример транспортной сети x 0 – вход сети z – выход сети x i (i 0) – промежуточные вершины. 3 x0x0 x1x1 x2x2 x4x4 x3x3 z

Поток сети Потоком на транспортной сети называется функция (u), заданная на множестве дуг сети, которое удовлетворяет свойствам: 1) 2). 4 множество дуг, входящих в вершину х множество дуг, выходящих из вершины х поток в транспортной сети

Основные определения Дуга u называется насыщенной, если поток (u)=C(u) Дуга u называется свободной если (u)=0 Дуга u называется занятой, если (u)>0 Поток в сети называется полным, если любой путь, идущий от входа к выходу сети содержит хотя бы одну насыщенную дугу. 5

Какая дуга? 6 x0x0 x1x1 x2x2 x4x4 x3x3 z 2/2 5/2 7/0 3/09/1 14/1 6/1 4/3 12/0 1/1 11/1

Разрез транспортной сети Разрезом называется множество дуг, соединяющих вершины множества и. 7 совокупность вершин сети такая, что а. множества дуг, входящих в вершины множества А множества дуг, выходящих из вершин множества А

Пример 8 x0x0 x1x1 x2x2 x4x4 x3x3 z {(x 0,x 3 ), (x 1,x 3 ), (x 1,z), (x 2,z)} {(x 3,x 4 )}

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

Теорема Форда-Фалкерсона Если в транспортной сети для некоторого разреза V и величины потока z имеет место C(A)= z, то V обладает минимальной пропускной способностью в сети, а z является максимальным для данной сети. 10

Пример 11 x0x0 x1x1 x2x2 x4x4 x3x3 z 1/1 6/3 2/1 1/1 3/0 2/2 5/2 3/3 1/1

Алгоритм Форда-Фалкерсона Алгоритм в основном включает 2 этапа: 1.Нахождение полного потока. 2.Нахождение максимального потока, с помощью передачи меток. 12

1.Нахождение полного потока Поочередно рассмотрим все пути между х 0 и z и для каждой дуги выбранного пути найдем разность между пропускной способностью дуги и потоком, проходящим по дуге. Увеличим поток таким образом, чтобы путь, ведущий из х 0 в z содержал хотя бы одну насыщенную дугу. Для каждой дуги выбранного пути прибавляем к числителю минимальную полученную разность. Выбираем следующий путь. Повторяем эти действия до тех пор, пока не получим полный поток в сети. 13

2.Нахождение максимального потока, с помощью передачи меток Увеличение потока z сети состоит в разметке вершин индексами, указывающими путь, по которому возможно изменение потока. Если разметка достигает вершины z, то поток можно увеличить по пути, соответствующему полученной разметке. Увеличение потока возможно до тех пор, пока в результате разметки вершина z получает метки. 14

2.Нахождение максимального потока, с помощью передачи меток Шаг 1. Помечаем вершину х 0 индексом Шаг 2. Если x i уже имеет пометку, то: Метка приписывается всем непомеченным вершинам, которые связаны с x i ненасыщенной дугой, ведущей из x i к данной вершине. Метку получают все вершины y, удовлетворяющие условиям: y – непомеченная Метку получают все непомеченные вершины, связанные занятой дугой, идущей из данной вершины в вершину x i. Метку получают все вершины y, удовлетворяющие условиям: i+i -i у – непомеченная

2.Нахождение максимального потока, с помощью передачи меток (продолжение) Шаг 3. Если в результате такой разметки окажется помеченная вершина z, то переходим к пункту 4. В противном случае, поток, полученный на предыдущем цикле, был максимальным. Шаг 4. Строим путь от х 0 к z, все вершины которого соответствуют номерам меток предыдущих вершин с точностью до знака. Построение пути начинается от вершины z. Поток во всех дугах пути изменяется по следующим правилам: 16 если если направление дуги u и направление потока в сети совпадают если дуга u и направление потока противоположны

Пример нахождения максимального потока и минимального разреза сети 17 x0x0 x2x2 x4x4 x1x1 z 7/6 3/0 10/7 7/6 1/0 2/1 11/9 3/2 5/2 x3x3 16/11 Для заданной транспортной сети найдем максимальный поток и минимальный разрез при помощи алгоритма Форда-Фалкерсона x0x0 x2x2 x4x4 x1x1 z 7/6 3/0 10/7 7/6 1/0 2/1 11/9 3/2 5/2 x3x3 16/11 Находим путь, по которому возможно увеличение потока Величина начального потока в сети: 10/8 7/7 1/1 Вычисляем =1 Увеличиваем поток Величина потока в сети:

Продолжение примера 18 x0x0 x2x2 x4x4 x1x1 z 7/6 3/0 2/1 11/9 3/2 5/2 x3x3 16/11 10/8 7/7 1/1 Величина потока в сети: x0x0 x2x2 x4x4 x1x1 z 7/6 3/0 10/8 7/7 1/1 2/1 11/9 3/2 5/2 x3x3 16/11 Находим путь, по которому возможно увеличение потока 10/9 11/10 16/12 Вычисляем =1 Увеличиваем поток Величина потока в сети: 2/2

Продолжение примера 19 x0x0 x2x2 x4x4 x1x1 z 7/6 3/0 10/9 7/7 1/1 2/2 11/10 3/2 5/2 x3x3 16/12 Находим путь, по которому возможно увеличение потока Вычисляем =1 Увеличиваем поток Величина потока в сети: x0x0 x2x2 x4x4 x1x1 z 7/6 3/0 10/9 7/7 1/1 2/2 11/10 3/2 5/2 x3x3 16/12 Величина потока в сети: 11/11 5/3 16/13

Продолжение примера 20 x0x0 x2x2 x4x4 x1x1 z 7/6 3/0 10/9 7/7 1/1 2/2 11/11 3/2 5/3 x3x3 16/13 Находим путь, по которому возможно увеличение потока Вычисляем =1 Увеличиваем поток Величина потока в сети: x0x0 x2x2 x4x4 x1x1 z 7/6 3/0 10/9 7/7 1/1 2/2 11/11 3/2 5/3 x3x3 16/13 Величина потока в сети: 3/3 16/14

Продолжение примера Расставляем метки 21 x0x0 x2x2 x4x4 x1x1 z /6 3/0 10/9 7/7 1/1 2/2 5/3 11/11 16/14 3/3 Строим путь от х 0 к z Полученный путь: Изменяем поток во всех дугах пути 7/5 3/1 5/4 16/15 x3x3 Вычисляем =1

Продолжение примера Расставляем метки 22 x0x0 x2x2 x4x4 x1x1 z /5 3/1 10/9 7/7 1/1 2/2 5/4 11/11 16/15 3/3 Строим путь от х 0 к z Полученный путь: Изменяем поток во всех дугах пути 7/4 3/2 5/5 16/16 x3x3 Вычисляем =1

Продолжение примера 23 x0x0 x2x2 x4x4 x1x1 z /6 3/2 10/9 7/7 1/1 2/2 11/11 16/16 3/3 5/5 x3x3 x0x0 x2x2 x4x4 x1x1 z /6 3/2 10/9 7/7 1/1 2/2 11/11 16/16 3/3 5/5 x3x3 Повторяем процесс расстановки меток до тех пор, пока вершина z получает метку. Если она не получила метку, то поток, который получили на предыдущем шаге, максимальный. Множество вершин разреза: Множество : Разрез образуют дуги: (x 1,x 4 ),(x 1,x 2 ),(x 0,x 2 ),(x 0,x 3 ) Пропускная способность разреза Величина максимального потока сети равна величине минимального разреза