Алгоритмы на графах. Задача о максимальном потоке в сетях Требуется от источника к стоку передать максимальное количество энергии. В условиях задачи о. - презентация

1 Алгоритмы на графах

2 Задача о максимальном потоке в сетях Требуется от источника к стоку передать максимальное количество энергии. В условиях задачи о максимальном потоке вес дуги называется ее пропускной способностью C(e). Определим поток через рассматриваемую сеть N как функцию J, сопоставляющую каждой дуге e неотрицательное действительное число J(e), называемое потоком через ребро е, причем J(e)C(e). Другими словами, поток через любую дугу не должен превосходить ее пропускной способности, и величина потока, входящего в любую вершину (сумма потоков входящих дуг), отличную от S и t, равно величине потока, исходящего из этой вершины. Дуга, для которой справедливо равенство J(e)=C(e), называется насыщенной, в противном случае, ненасыщенной.

3 Пропускная способность разреза Разрезом W в сети называется любое множество вершин, обязательно содержащее выход и не содержащее вход. Пропускной способностью C(W) разреза W называется сумма пропускных способностей дуг, заходящих в разрез. Полным называется такой поток, для которого любой ориентированный путь содержит насыщенную дугу. Если поток не полный, то существует путь из источника в сток, все дуги которого не насыщены. Теорема. Во всякой сети величина любого максимального потока равна пропускной способности любого минимального разреза.

4 Алгоритм Форда-Фалкерсона 1. Перенумеровать все вершины сети произвольным образом, кроме истока и стока. 2. Задать некоторый начальный поток в сети (например, нулевой). 3. Вершинам сети присвоить целочисленные метки, а дугам - знаки + и - по следующим правилам:

5 Алгоритм Форда-Фалкерсона a) вершине-истоку присвоить метку 0; b) находим непомеченную вершину W, смежную помеченной вершине V. Если поток по соединяющей вершины V-W дуге меньше пропускной способности этой дуги, то происходит помечивание, иначе переходим к рассмотрению следующей вершины. Если вершина W является образом помеченной вершины V, то происходит прямое помечивание: вершина W получает метку, равную номеру вершины V, соединяющая вершины V-W дуга получает метку + и мы переходим к рассмотрению следующей вершины. Если вершина W не имеет ни одного помеченного прообраза, то происходит обратное помечивание: вершина W получает метку, равную номеру вершины V (являющейся в данном случае её образом), соединяющая вершины W-V дуга получает метку - и мы переходим к рассмотрению следующей вершины. Процесс помешивания продолжается до тех пор, пока все удовлетворяющие этим условиям вершины не получат метку.

6 Алгоритм Форда-Фалкерсона 4. Если в результате процедуры помешивания вершина-сток метки не получила, то текущий поток - максимальный, задача решена. В противном случае, перейти к пункту Рассмотреть последовательность вершин L = ( U 0,..., v 0 ), метка каждой из которых равна номеру следующей за ней вершины, и множество дуг М, соединяющих соседние вершины из L. Построить новый поток по схеме: a) Если дуга принадлежит множеству М и имеет знак +, то новый поток по этой дуге = старый поток по этой дуге + К b) Если дуга принадлежит множеству М и имеет знак -, то новый поток по этой дуге = старый поток по этой дуге - К c) Если дуга не принадлежит множеству М, то новый поток по дуге = старый поток по этой дуге. 6. Перейти к п.3

7 Алгоритм Форда-Фалкерсона Схема нахождения К: К = min{ К 1 ; К 2 }, где Для нахождения К 1 рассматриваются все дуги, принадлежащие множеству М и имеющие знак + и для каждой такой дуги вычисляется разность между пропускной способностью дуги и потоком по этой дуге. Затем из этих значений разностей выбирается минимальное значение и присваивается К 1. Для нахождения К 2 рассматриваются все дуги, принадлежащие множеству М и имеющие знак -. Затем из этих дуг выбирается дуга с минимальным потоком и значение потока по этой дуге присваивается К 2.

8 Пример

9 Этап 1

10 Этап 2

11 Этап 3.1

12 Этап 3.2

13

14 Этап 4

15 Этап 5

16

17 Этап 3.1. Вторая итерация

18 Этап 3.2. Вторая итерация

19

20 Этап 4. Вторая итерация

21 Этап 5. Вторая итерация

22 Этап 3.1. Третья итерация

23 Этап 3.2. Третья итерация

24 Этап 4. Третья итерация

25 Этап 5. Третья итерация

26 Этап 3.1. Четвертая итерация

27 Этап 3.2. Четвертая итерация

28

29 Этап 4. Четвертая итерация

30 Задание Найти максимальный поток в сети

31 Задание Найти максимальный поток в сети

32 Задание Найти максимальный поток в сети