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

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

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

1. Выберем некоторые две вершины графа. Обозначим одну из них через v_s, а другую через v_t.

2. Применим алгоритм Форда-Фалкерсона и найдём максимальный поток из источника v_s в сток v_t. При этом множество помеченных вершин и множество непомеченных вершин образуют две стороны минимального разреза V_s и V_t.

3. Выберем две вершины графа v_i и v_j V_s.

4. Заменим дуги из минимального разреза (V_s, V_t) одной дугой, а вершины бока разреза, в котором не лежат вершины v_i ,v_j, (например, V_t), – одной вершиной. Пропускную способность в таким образом определённой дуге примем равной пропускной способности разреза (V_s, V_t).

5. Положим: v_i = v_s, v_j = v_t и вернемся ко второму шагу. После того, как будет выбрана n - 1 пара вершин, мы определим все величин максимального потока для исходной сети. Основная идея алгоритма лежит в итеративном построении максимального остовного дерева, ветви которого соответствуют разрезам, а пропускные возможности ветвей равны пропускным способностям этих разрезов. Если бы мы применили алгоритм Форда-Фалкерсона к каждой паре вершин, то нам бы пришлось его применить раз. В алгоритме же Гомори-Ху максимальный поток между парой вершин определяется с помощью алгоритма расстановки пометок только n - 1 раз. Проиллюстрируем на примере алгоритм Гомори-Ху.

Рассмотрим сеть, изображённую на рис. 2.6.

Рис. 2.6. Сеть с пропускными возможностями

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

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

1. Выберем вершины s = v₁ и t = v₂. Минимальную пропускную способность относительно источника s = v₁ и стока t = v₂имеет разрез со сторонами V_s = {v₁, v₃, v₄, v₅, v₆} и V_t = {v₂}. По теореме 1 величина максимального потока между вершинами v₁ и v₂ равна пропускной способности разреза (V_s, V_t): w₁₂ = w₂₁ = c(V_s, V_t) = 2 + 3 = 5. Объединим вершины с V_s в одну вершину и соединим её с вершиной v₂ веткой с пропускной способностью 5 (рис. 2.7).

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

2. Выберем вершины s = v₁ и t = v₃. Минимальную пропускную способность относительно источника s = v₁ и стока t = v₃имеет разрез со сторонами V_s = {v₁} и V_t = {v₂, v₃, v₄, v₅, v₆}. По теореме 1 величина максимального потока между вершинами v₁ и v₃ равна пропускной способности разреза (V_s, V_t): w₁₃ = w₃₁ = c(V_s, V_t) = 2 + 4 + 2 = 8. Объединим вершины v₃, v₄, v₅, v₆ в одну вершину и соединим её с вершиной v₁ веткой с пропускной способностью 8 (рис. 2.8).

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

3. Выберем вершины s = v₄ и t = v₃. Минимальную пропускную способность относительно источника s = v₄ и стока t = v₃имеет разрез со сторонами V_s = {v₄} и V_t = {v₁, v₂, v₃, v₅, v₆}. По теореме 1 величина максимального потока между вершинами v₄ и v₃ равна пропускной способности разреза (V_s, V_t): w₄₃ = w₃₄ = c(V_s, V_t) = 2 + 5 + 4 = 11. Объединим вершины v₃, v₅, v₆ в одну вершину и соединим её с вершиной v₄ веткой с пропускной способностью 11 (рис. 2.9).

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

4. Выберем вершины s = v₅ и t = v₃. Минимальную пропускную способность относительно источника s = v₅ и стока t = v₃имеет разрез со сторонами V_s = {v₅} и V_t = {v₁, v₂, v₃, v₄, v₆}. Величина максимального потока между вершинами v₅ иv₃ равна пропускной способности разреза (V_s, V_t): w₅₃ = w₃₅ = c(V_s, V_t) = 5 + 4 = 9. Объединим вершины v₃, v₆ в одну вершину и соединим её с вершиной v₅ веткой с пропускной способностью 9 (рис. 2.10).

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

5. Выберем вершины s = v₆ и t = v₃. Минимальную пропускную способность относительно источника s = v₆ и стока t = v₃имеет разрез со сторонами V_s = {v₆} и V_t = {v₁, v₂, v₃, v₄, v₅}.

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

Величина максимального потока между вершинами v₆ и v₃ равна пропускной способности разреза (V_s, V_t): w₆₃ = w₃₆ =c(V_s, V_t) = 5 + 6 + 4 = 15. Объединим вершину v₃ с вершиной v₆ веткой с пропускной способностью 15 (рис. 2.11).

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

.

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