Задача о максимальном потоке в сети Алгоритм Фалкерсона-Форда. - презентация

1 Задача о максимальном потоке в сети Алгоритм Фалкерсона-Форда

2 Постановка задачи Пункт 0 (вход, источник) и пункт n (выход, сток) и каждой дуге (отрезку), связывающей пункты i и j, сопоставлено число d ij >0 Количество вещества, проходящего по дуге от i до j, будем называть потоком по дуге (i, j) и обозначать через X ij. Очевидно, что 0X ijd ij для всех i, j Величину Z называем величиной потока в сети и ставим задачу максимизации Z.

3 Алгоритм Фалкерсона-Форда 1. Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью. 2. В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся. 3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток: 1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью cmin. 2. Для каждого ребра на найденном пути увеличиваем поток на cmin, а в противоположном ему - уменьшаем на cmin. 3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.

4 4. Возвращаемся на шаг 2.

5 1. Подбирается поток с ненулевой частотой. В нашем случае в скобках указан поток. z ij d ij 2. Исходя из заданной сети N строим новую сеть N' следующим образом: любая дуга, из которой z l =0 (старый поток) остается в новой сети с той же пропускной способностью, если же z l 0, эта дуга заменяется двумя дугами – одна в том же направлении с пропускной способностью U l -x l и обратная к x l.

6 3. Если в новой сети можно найти ненулевой поток, то добавляем его к исходному, и получаем поток больше исходного до тех пор, пока на шаге три для очередной сети мы не сможем найти ненулевой поток. F=4+1=5

7 Алгоритмы Алгоритм Краскалла Алгоритм Дейкстры

8 Остов минимального веса Задача нахождения остова минимального веса во взвешенном связном графе, возникает при проектировании линий электропередачи, трубопроводов, дорог и т.п., когда требуется заданные центры соединить некоторой системой каналов, связных либо непосредственно соединяющим их каналом, либо через другие центры и каналы, так, чтобы общая длина (или, например, стоимость) каналов связи была минимальной. Решение этой задачи «слепым» перебором вариантов потребовало бы чрезвычайно больших вычислений даже при относительно малых n (можно доказать, что полный граф Kn содержит nn–2 различных остовных дерева). Однако для ее решения имеются эффективные алгоритмы. Опишем два из них - алгоритмы Дж. Краскала (1956) и Р. Прима (1957), применяемые к произвольному связному графу (G, w) порядка n.

9 Алгоритм Краскалла Шаг 1. Строим граф T 1 =O n +e 1, присоединяя к пустому графу на множестве вершин V G ребро e 1 V G минимального веса. Шаг 2. Если граф T i уже построен и i

10 Задание Построить связный 9-вершинный граф, без петель и кратных ребер. Случайным образом распределить веса ребер. С помощью алгоритма Краскалла найти остов минимального веса.

11 Задание Дан граф, найти остов минимального веса

12 Задача о минимальной связке Найти остовное дерево графа с наименьшим весом, используя алгоритм Краскалла

13 Задача о кратчайшей цепи Задача о кратчайшем пути. Пусть задана сеть из n + 1 вершины, то есть ориентированный граф, в котором выделены две вершины – вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг. Длиной пути (контура) называется сумма длин входящих в него дуг (если длины дуг не заданы, то длина пути (контура) определяется как число входящих в него дуг). Задача заключается в поиске кратчайшего пути (пути минимальной длины) от входа до выхода сети. Известно, что для существования кратчайшего пути необходимо и достаточно отсутствия в сети контуров отрицательной длины.

14 Алгоритм Дейкстры Алгоритм основан на приписывании узлам временных или постоянных меток. Первоначально только источнику приписывается постоянная метка, равная нулю. Всем другим узлам приписываются временные метки, соответствующие весу дуги из источника в рассматриваемый узел. Если такой дуги нет, то узлу приписывается временная метка, равная бесконечности.

15 Алгоритм Дейкстры Для определения ближайшего к источнику узла выберем временную метку с минимальным значением и объявим ее постоянной. Затем, до тех пор, пока стоку не будет приписана постоянная метка, необходимо выполнить следующее:

16 Алгоритм Дейкстры 1. Рассмотреть оставшиеся узлы с временными метками. Сравнить величину каждой временной метки с суммой величин последней из постоянных меток и веса дуги, ведущей из соответствующего постоянно помеченного узла в рассматриваемый. Минимальная из двух сравниваемых величин определяется как новая временная метка рассматриваемого узла. 2. Среди временных меток выбрать минимальную и объявить ее постоянной. После постоянного помечивания стока алгоритм прекращает работу, при этом минимальная сумма весов дуг, соединяющий источник и сток, равна постоянной метке стока. Искомая цепь состоит из дуг, для каждой из которых разность между постоянными метками ее концевых узлов равна весу этой дуги.

17 Задание 1 Дана сеть. Определить ориентированную цепь из узла S в узел t, сумма весов дуг которой минимальна. S V1V1 V2V2 t V5V5 V3V3 V4V

18 Задание 2 Дана сеть. Определить ориентированную цепь из узла S в узел t, сумма весов дуг которой минимальна S t

19 Задание 3 Дана сеть. Определить ориентированную цепь из узла S в узел t, сумма весов дуг которой минимальна. t S V1V1 V2V2 V3V3 V8V8 V7V7 V6V6 V4V4 V5V5