Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Алгоритм Форда-Фалкерсона

Читайте также:
  1. Алгоритм выполнения.
  2. Алгоритм действий.
  3. Алгоритм действий.
  4. Алгоритм действий.
  5. Алгоритм действий.
  6. Алгоритм действий.
  7. Алгоритм действий.

Доказательство теоремы 1 даёт алгоритм для построения минимального разреза (Vs, Vt), который отделяет vs от vt, и максимальный поток φ от vs до vt. Этот алгоритм был предложен Л. Фордом и Д. Фалкерсоном. Алгоритм начинает работу с известного допустимого потока φ (например, с нулевого). Потом расчеты развиваются в виде последовательности “расстановки пометок” (операция А), каждая из которых приводит к потоку с большей величиной (операция Б), или же завершается выводом, что рассмотренный поток максимален.

Будем предполагать, что пропускные способности cj дуг сети целые числа.

Операция А (расстановка пометок). Каждая вершина может находиться в одном из трёх состояний: вершине приписана пометка и вершина просмотрена (то есть она имеет пометку и все смежные с ней вершины “обработаны”), вершина помечена, но не просмотрена, вершина не помечена. Пометка вершины vi имеет один из двух видов: (+ vj, l) или (- vj, l). Часть + vj пометки первого типа показывает, что поток допускает увеличение вдоль дуги (vj, vi) на величину l. Часть - vj пометки второго типа показывает, что поток допускает уменьшения вдоль дуги (vi, vj) на величину l. Сначала все вершины не имеют пометок.

Шаг 1. Источнику vs присваивается пометка (+, ). Вершина vs помечена, но не “просмотрена”.

Шаг 2. Возьмём произвольную помеченную, но не просмотренную вершину. Пусть оно имеет пометку ( vr, l (vj)). “Просмотрим” её, то есть просмотрим все вершины, смежные с ней, и пометем те из них, которые не помечены.

Всем непомеченным вершинам vj, в которые входят дуги er из vi и для которых φ (е r) < cr, приписываем пометку (+ vi, l (vj)), где l (vj) = min (l (vi)), cr - φ (еr)).

Всем непомеченным вершинам vj, из которых выходят дуги er в xi и для которых φ (er) > 0, приписываем пометку (- vi, l (vj)), где l (vj) = min (l (vi)), φ (еr)).

Теперь вершина vi и помечена, и просмотрена, а вершина vj, помечена, но не просмотрена.

Шаг 3. Повторять шаг 2 до тех пор, пока или сток – вершина vt – будет помечена, или вершина vt будет не помечена и никаких других пометок нельзя будет расставить. В первом случае переходим к операции Б, а во втором случае алгоритм заканчивает работу с максимальным потоком φ. Во втором случае множество помеченных и множество непомеченных вершин образовывают две стороны минимального сечения (Vs, Vt).

Операция Б (увеличения потока)

Шаг 4. Принять v = vt и перейти к шагу 5.

Шаг 5. Если пометка в вершине v имеет вид (+ z, l (v)), то изменить поток вдоль дуги (z, v) с φ (z, v) на φ (z, v) + l (v).

Если пометка в вершине v имеет вид (- z, l (v)), то изменить поток вдоль дуги (v, z) с φ (v, z) на φ (v, z) - l (v).

Шаг 6. Если z = vs, то стереть все пометки и вернуться к шагу 1, чтобы снова начать расставлять пометки, но, используя уже улучшенный поток, который найден на шаге 5.

Если z ≠ vs, то взять v = z и вернуться к шагу 5.

Рассмотрим на примере работу алгоритма Форда-Фалкерсона.

1. Возьмём поток, изображённый на рисунке 2.1 как начальный допустимый поток. Он имеет величину 3.

2. Присвоим источнику, вершине v1, пометку (+, ). Вершина v1 помечена, но не просмотрена.

3. Просмотрим вершины, смежные с вершиной v1. Вершине v2 присвоим пометку (+ v1, 1), а вершине v3 – пометку (- v1, 2) (φ (v1, v2) = 5 < 6 = c1, φ (v3, v1) = 2 > 0). Вершина v1 помечена и просмотрена, а вершины v2 и v3 помечены, но не пересмотрены.

4. Пересмотрим вершины, смежные с вершиной v3. Из вершин, смежных с вершиной v3, не помечены вершины v4 и v5. Вершине v4 присвоим пометку (-v3, 2), поскольку φ (v4, v3) = 4 > 0 и min (2, 4) = 2. Вершину v5 не помечаем, поскольку φ (v5, v3) = 0.

5. Просмотрим вершины, смежные с вершиной v2. Вершине v5 присвоим пометку (+ v2, 1), поскольку φ (v2, v5) = 7 < 8 = c5. Сток помечен. Переходим к операции В – увеличения потока.

6. Сток имеет пометку (+ v2, 1). Поэтому увеличиваем поток вдоль дуги (v2, v5) на 1.

7. Вершина v2 имеет пометку (+v1, 1). Поэтому увеличиваем поток вдоль дуги (v1, v2) на 1. Мы получили новый поток величины 4 (рис. 2.4.1).

Рис. 2.4.1 Поток величины 4

 

8. Стираем все пометки.

9. Присваиваем вершине v1 пометку (+, ).

10. Пересматриваем вершины, смежные с вершиной v1. Вершине v3 присваиваем пометку (-v1, 2). Вершину v2 не помечаем, так как φ (v1, v2) = 6 = c (y1).

11. Пересмотрим вершины, смежные с вершиной v3. Вершине v4 присвоим пометку (-v3, 2), поскольку φ (v4, v3) = 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.4.2). По теореме 1 этот максимальный. Проверим это.

Рис. 2.4.2 Максимальный поток

 

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.

 


Дата добавления: 2015-08-09; просмотров: 170 | Нарушение авторских прав


Читайте в этой же книге: Введение | Виды графов | Представление графов с помощью матриц | Потоки в сетях | Задача о максимальном потоке | Решение. Этап 1. | Решение. Этап 1. | Этап 3. |
<== предыдущая страница | следующая страница ==>
О максимальном потоке| Графы со многими источниками и стоками

mybiblioteka.su - 2015-2024 год. (0.01 сек.)