Поиск максимальных потоков в сетях
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
4 > 0, l(v3) = 2 и min(2, 4) = 2.
12. Пересмотрим вершины, смежные с вершиной v4. Вершине v5 присвоим пометку (-v4, 2), так как ?(v5, v4) = 4 > 0, l(v4) = 2 и min(2, 4) = 2. Сток помечен. Переходим к операции Б увеличения потока.
13. Сток имеет пометку (-v4, 2). Поэтому уменьшаем поток вдоль дуги (v5, v4) на 2.
14. Вершина v4 имеет пометку (-v3, 2). Поэтому уменьшаем поток вдоль дуги (v4, v3) на 2.
15. Вершина v3 имеет пометку (-v1, 2). Поэтому уменьшаем поток вдоль дуги (v3, v1) на 2. Мы получили новый поток величины 6 (рис. 2.3). По теореме 1 этот максимальный. Проверим это.
Рис. 2.3. Максимальный поток
16. Стираем все пометки.
17. Присваиваем вершине v1 пометку (+, ).
18. Вершины, смежные вершине v1, нельзя помечать, поскольку дуга (v4, v3) насыщенна ?(v1, v2) = ?(е1) = с(е1) = 6, а через дугу (v3, v1) поток не передаётся. Сток остался не помеченным. Значит, полученный поток максимальный. Дуги (v1, v2) и (v3, v1) образуют минимальный разрез. Множество помеченных вершин образует ту его сторону, которая содержит источник: Vs = {v1}. Непомеченные вершины образуют другую сторону разреза, который содержит сток: Vt = { v2, v3, v4, v5}. Построенный поток имеет вид ?(е1) = 6, ?(е5) = 8, ?(е6) = 2, ?(е4) = 2, ?(е3) = 2, ?(е2) = ?(е7) = 0.
2.5. Графы со многими источниками и стоками
Алгоритм Форда-Фалкерсона примененный и для определения величины максимального потока между множеством вершин источников и множеством вершин стоков. Разобьем множество вершин на множество источников V+ = {v V: Q(v) > 0}, которые образуют поток, множество стоков V- = {v V: Q(v) < 0}, которые используют поток и множество промежуточных вершин V0 = {v V: Q(v) = 0}, которые сохраняют поток . Преобразуем поток ? в поток, который имеет только один источник и только один сток, увеличив количество вершин в сети. Для этого добавим две новые вершины “фиктивный” источник vs и “фиктивный” сток vt. Соединим вершину vs со всеми действительными источниками. Этим дугам припишем поток, который образован соответствующим источником. А из каждого действительного стока направим дугу в “фиктивный” сток vt. Этим дугам припишем поток, который используется соответствующим стоком. При этом пропускные способности добавленных дуг считаем бесконечными. В результате получаем сеть с одним источником и одним стоком. Применяя к ней алгоритм Форда-Фалкерсона, находим максимальный поток, который максимальный и для исходной сети.
Проиллюстирируем на примере преобразования сети с несколькими источниками и несколькими стоками до сети с одним источником и одним стоком.
Рис. 2.4. Сеть с двумя стоками
На рис. 2.4 изображена сеть с двумя источниками v1 и v3 и тремя стоками v7, v8, v9 Q (v1) = 5, Q (v3) = 3, Q (v7) = 3, Q (v8) = 4, Q (v9) = 1, Q (v2) = Q (v4) = Q (v5) = Q (v6) = 0
Преобразуем эту сеть в сеть с одним источником и одним стоком.
На рис. 2.5 изображена сеть уже с одним источником vs и одним стоком vt.
Рис. 2.5. Преобразованная сеть
2.6. Задача о многополюсном максимальном потоке
Рассмотрим задачу нахождения максимального потока для всех пар узлов в неориентированной сети. Эту задачу можно рассматривать как обобщение задачи с одним источником и одним стоком, которую можно решить, применяя алгоритм Форда-Фалкерсона для каждой пары вершин. Однако более эффективным является алгоритм, предложенный Р. Гомори и Т. Ху.
Алгоритм Гомори-Ху
1. Выберем некоторые две вершины графа. Обозначим одну из них через vs, а другую через vt.
2. Применим алгоритм Форда-Фалкерсона и найдём максимальный поток из источника vs в сток vt. При этом множество помеченных вершин и множество непомеченных вершин образуют две стороны минимального разреза Vs и Vt.
3. Выберем две вершины графа vi и vj Vs.
4. Заменим дуги из минимального разреза (Vs, Vt) одной дугой, а вершины бока разреза, в котором не лежат вершины vi , vj, (например, Vt), одной вершиной. Пропускную способность в таким образом определённой дуге примем равной пропускной способности разреза (Vs, Vt).
5. Положим: vi = vs, vj = vt и вернемся ко второму шагу. После того, как будет выбрана n - 1 пара вершин, мы определим все величин максимального потока для исходной сети. Основная идея алгоритма лежит в итеративном построении максимального остовного дерева, ветви которого соответствуют разрезам, а пропускные возможности ветвей равны пропускным способностям этих разрезов. Если бы мы применили алгоритм Форда-Фалкерсона к каждой паре вершин, то нам бы пришлось его применить раз. В алгоритме же Гомори-Ху максимальный поток между парой вершин определяется с помощью алгоритма расстановки пометок только n - 1 раз. Проиллюстрируем на примере алгоритм Гомори-Ху.
Рассмотрим сеть, изображённую на рис. 2.6.
Рис. 2.6. Сеть с пропускными возможностями
Числ