Постановка задачи о максимальном потоке на сети.
На сети, что задается графом (I,U), где I — множество вершин, U — множество дуг, с определенной на ней функцией пропускных способностей rij ((і,j) — дуга с U), зафиксированные две вершины — i1 и in. Вершина i1 (источник) имеет интенсивность d, вершина in (стек) — интенсивность –d, все другие вершины нейтральные. Нужно найти максимальную интенсивность источника d, при которой сеть допускает поток. Поток, что отвечает такому максимальному значению интенсивности d*, называется максимальным потоком, а именно значение d* — величиной этого потока.
Алгоритм Форда-Фалкерсона применяется для построения максимального потока на сети из заданной начальной вершины-источника в заданную конечную вершину-сток.
Будем считать, что вершиной-источником является 1-я вершина, вершиной-стоком — вершина с номером n.
Входные данные.
Для работы алгоритма необходимо задать следующую информацию:
1. Число вершин сети.
2. Матрицу смежности С, элементы которой сіj определяются соотношениями:
сij=1, если существует дуга (і,j);
сij=0, если дуга (і,j) отсутствует.
3. Величины rij пропускных способностей дуг (і,j).
4. Начальный поток на сети, то есть величины xij, которые удовлетворяют условия:
a) 0£xij£rij;
b) Для произвольной вершины (кроме первой и последней) поток, что входит в вершину, равняется потоку, что выходит из нее.
Изложение алгоритма Форда-Фалкерсона.
Алгоритм состоит из последовательных итераций, которые проводятся до тех пор, пока не будет выполняться признак оптимума.
В каждой итерации можно выделить два этапа.
Этап 1 (этап выставления отметок).
1. В каждый момент времени каждая вершина может находиться в одном из трех положений:
а) не обозначенная;
б) обозначенная, но не рассмотрена;
в) обозначена и рассмотрена.
Общий вид отметки j-ї вершины: [i+qj], или [и–,qj], где и — номер некоторой обозначенной вершины, при просмотре которой была обозначена вершина j. Вершина 1 всегда обозначена и имеет отметку [1+q1], где q1 равное + ¥ (бесконечности).
2. Просмотр произвольной обозначенной вершины j заключается в следующем:
a) произвольная необозначенная вершина k, для которой существует дуга (j,k) и имеет место неравенство xjk<rjk, получает отметку вида [j+qk], где
qk=min{qj, rjk – xjk};
б) произвольная необозначенная вершина k, для которой существует дуга (k,j) и имеет место условие xkj>0, получает отметку вида [j–,qk], где
qk=min{qj, xkj}.
3. Процесс выставления отметок заканчивается в одном из двух случаев:
а) вершина с номером n обозначена;
б) условие а) не выполняется, но ни одну вершину больше пометить нельзя.
В первом случае переходим к этапу изменения потока на сети. Во втором — до определения минимального разреза сети и максимального потока.
Этап 2 (этап изменения потока).
Поток в сети изменяется на величину qn согласно правила.
Если вершина n имеет отметку [k+qn], где k — номер некоторой вершины, то xkn=xkn+qn. Если отметка имеет вид [k–,qn], то xnk=xnk–qn. Переходим к вершине с номером k. Если отметка вершины k имеет вид [j+qk], то xjk=xjk+qn; если она равняется [j–,qk], то xkj=xkj–qn. Подобные действия продолжаем до тех пор, пока не будет достигнута начальная вершина. В этом случае все старые отметки вытираем и возвращаемся к первому этапу.
В результате работы согласно алгоритма определяются минимальный разрез сети и, как следствие, максимальный поток.
Минимальный разрез определяется совокупностью дуг, которые выходят из множества обозначенных вершин и заходят в множество необозначенных.
Величина максимального потока ровная суммарной пропускной способности минимального разреза.
Программное обеспечение.
Обучающий модуль, с помощью которого задача о максимальном потоке на сети Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО.
Задание.
Решить методом Форда-Фалкерсона задачи о максимальном потоке на сети, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи, в каждой из которых сеть задается матрицами смежности C и пропускных способностей R. Во всех задачах источником считается вершина 1, а стоком — вершина 6.
1) | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 10 | 18 | 0 | 0 | 0 | ||||
0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 14 | 1 | |||||
C = | 0 | 1 | 0 | 1 | 0 | 0 | , | R = | 0 | 10 | 0 | 17 | 0 | 0 | ; | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 9 | 0 | 0 | 22 | 12 | |||||
0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 18 | |||||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2) | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 11 | 33 | 0 | 0 | 0 | ||||
0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 14 | 4 | 0 | |||||
C = | 0 | 1 | 0 | 1 | 1 | 0 | , | R = | 0 | 5 | 0 | 15 | 23 | 0 | ; | |
0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 23 | |||||
0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 11 | 0 | 22 | |||||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3) | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 20 | 21 | 22 | 0 | 0 | ||||
0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 5 | 13 | 14 | 0 | |||||
C = | 0 | 0 | 0 | 0 | 1 | 1 | , | R = | 0 | 0 | 0 | 0 | 12 | 28 | ; | |
0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 12 | 0 | 11 | 10 | |||||
0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 17 | |||||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4) | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 5 | 19 | 27 | 0 | 0 | ||||
0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 17 | 15 | |||||
C = | 0 | 1 | 0 | 0 | 1 | 1 | , | R = | 0 | 23 | 0 | 0 | 7 | 8 | ; | |
0 | 1 | 1 | 0 | 1 | 0 | 0 | 5 | 12 | 0 | 11 | 0 | |||||
0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 28 | |||||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5) | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 24 | 33 | 6 | 12 | 0 | ||||
0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 10 | 15 | 7 | 0 | |||||
C = | 0 | 0 | 0 | 1 | 1 | 1 | , | R = | 0 | 0 | 0 | 11 | 15 | 17 | ; | |
0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 12 | 26 | |||||
0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 25 | |||||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
6) | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 19 | 16 | 8 | 18 | 0 | ||||
0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 20 | 1 | 0 | 0 | |||||
C = | 0 | 0 | 0 | 0 | 1 | 1 | , | R = | 0 | 0 | 0 | 0 | 32 | 42 | . | |
0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 45 | 0 | 0 | 2 | |||||
0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 31 | 0 | 20 | |||||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Ответы:
1) d* = 28. 2) d* = 44. 3) d* = 55. 4) d* = 51. 5) d* = 68. 6) d* = 61.
Лабораторная работа 9.