avangard-pressa.ru

Задача о многополюсном максимальном потоке - Математика

Рассмотрим задачу нахождения максимального потока для всех пар узлов в неориентированной сети. Эту задачу можно рассматривать как обобщение задачи с одним источником и одним стоком, которую можно решить, применяя алгоритм Форда-Фалкерсона для каждой пары вершин. Однако более эффективным является алгоритм, предложенный Р. Гомори и Т. Ху.

Алгоритм Гомори-Ху

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. Сеть с пропускными возможностями

Числа, приписанные дугам, отвечают их пропускным способностям, отвечают их пропускным способностям. Нужно для каждой пары узлов сети определить величину максимального потока между ними. Эта задача решается при n – 1= 6 – 1 = 5 итераций алгоритма Гомори-Ху. Если алгоритм Форда-Фалкерсона расстановки пометок применялся бы к каждой паре узлов, то нужно было бы решить пятнадцать задач о максимальном потоке.

Реализуем алгоритм Гомори-Ху на данной сети.

1. Выберем вершины s = v1 и t = v2. Минимальную пропускную способность относительно источника s = v1 и стока t = v2имеет разрез со сторонами Vs = {v1, v3, v4, v5, v6} и Vt = {v2}. По теореме 1 величина максимального потока между вершинами v1 и v2 равна пропускной способности разреза (Vs, Vt): w12 = w21 = c(Vs, Vt) = 2 + 3 = 5. Объединим вершины с Vs в одну вершину и соединим её с вершиной v2 веткой с пропускной способностью 5 (рис. 2.7).

Рис. 2.7. Первый шаг алгоритма

2. Выберем вершины s = v1 и t = v3. Минимальную пропускную способность относительно источника s = v1 и стока t = v3имеет разрез со сторонами Vs = {v1} и Vt = {v2, v3, v4, v5, v6}. По теореме 1 величина максимального потока между вершинами v1 и v3 равна пропускной способности разреза (Vs, Vt): w13 = w31 = c(Vs, Vt) = 2 + 4 + 2 = 8. Объединим вершины v3, v4, v5, v6 в одну вершину и соединим её с вершиной v1 веткой с пропускной способностью 8 (рис. 2.8).

Рис 2.8. Второй шаг

3. Выберем вершины s = v4 и t = v3. Минимальную пропускную способность относительно источника s = v4 и стока t = v3имеет разрез со сторонами Vs = {v4} и Vt = {v1, v2, v3, v5, v6}. По теореме 1 величина максимального потока между вершинами v4 и v3 равна пропускной способности разреза (Vs, Vt): w43 = w34 = c(Vs, Vt) = 2 + 5 + 4 = 11. Объединим вершины v3, v5, v6 в одну вершину и соединим её с вершиной v4 веткой с пропускной способностью 11 (рис. 2.9).

Рис. 2.9. Третий шаг

4. Выберем вершины s = v5 и t = v3. Минимальную пропускную способность относительно источника s = v5 и стока t = v3имеет разрез со сторонами Vs = {v5} и Vt = {v1, v2, v3, v4, v6}. Величина максимального потока между вершинами v5 иv3 равна пропускной способности разреза (Vs, Vt): w53 = w35 = c(Vs, Vt) = 5 + 4 = 9. Объединим вершины v3, v6 в одну вершину и соединим её с вершиной v5 веткой с пропускной способностью 9 (рис. 2.10).

Рис. 2.10. Четвёртый шаг

5. Выберем вершины s = v6 и t = v3. Минимальную пропускную способность относительно источника s = v6 и стока t = v3имеет разрез со сторонами Vs = {v6} и Vt = {v1, v2, v3, v4, v5}.

Рис. 2.11. Остаточное дерево разрезов

Величина максимального потока между вершинами v6 и v3 равна пропускной способности разреза (Vs, Vt): w63 = w36 =c(Vs, Vt) = 5 + 6 + 4 = 15. Объединим вершину v3 с вершиной v6 веткой с пропускной способностью 15 (рис. 2.11).

По дереву перерезов, изображённого на рис. 2.11, легко найти остальные величины максимальных потоков. Например,v16 = v61 = 8, поскольку в цепи дерева разрезов, которая соединяет вершины v1 и v2, минимальная пропускная способность веток равна 8. Запишем величины максимальных потоков в виде матрицы:

.

Здесь на пересечение i-строки и j-столбца стоит величина максимального потока между вершинами vi и vj.