Поиск максимальных потоков в сетях
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
?(ei)} все дуги ei цепи с направлением, не совпадающим с ориентацией “от источника к стоку”, l = min(l1, l2). Поток ? можно увеличить на l, увеличив на l поток на дугах цепи, ведущих “от стока к источнику”. Это противоречит тому, что величина потока ? максимальная величина допустимого потока из вершины vs в вершину vt.
2.4. Алгоритм Форда-Фалкерсона
Доказательство теоремы 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 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.2).
Рис. 2.2. Поток величины 4
8. Стираем все пометки.
9. Присваиваем вершине v1 пометку (+, ).
10. Пересматриваем вершины, смежные с вершиной v1. Вершине v3 присваиваем пометку (-v1, 2). Вершину v2 не помечаем, так как ?(v1, v2) = 6 = c(y1).
11. Пересмотрим вершины, смежные с вершиной v3. Вершине v4 присвоим пометку (-v3, 2), поскольку ?(v4, v3) =