Как найти минимальный разрез в сети

Как найти минимальный разрез в сети

Решить задачу нахождения максимального потока в транспортной сети с помощью алгоритма Форда—Фалкерсона, и построить разрез сети S.
Исходные данные:
Дана сеть S(X,U)
— исток сети; — сток сети, где ∈X; ∈X.
Значения пропускных способностей дуг заданы по направлению ориентации дуг: от индекса i к индексу j.

r[0,1] = 39; r[4,7] = 44; r[6,3] = 33; r[5,7] = 53; r[0,2] = 10;
r[4,2] = 18; r[6,7] = 95; r[5,4] = 16; r[0,3] = 23; r[2,5] = 61;
r[2,1] = 81; r[6,5] = 71; r[1,4] = 25; r[2,6] = 15; r[3,2] = 20

1. Зададим на сети нулевой поток (на всех дугах величина потока равна 0). Нулевой поток — это начальный допустимый поток на сети. Значение потока на каждой дуге будем указывать за скобками пропускной способности дуги.). Значение потока, равное «0», не указываем.
2. Выбираем на сети (произвольно) путь, ведущий из вершины x0 в вершину x7:
X0-X1-X4-X6-X7
3. Находим и увеличиваем поток на эту величину. Ребро Х1-Х4 помечаем как рассмотренное.

4. Выбираем еще один путь, например: Х0-Х2-Х5-Х7, находим и увеличиваем поток на эту величину. Ребро Х0-Х2 помечаем как рассмотренное.

5. Выбираем еще один путь, например: Х0-Х3-Х2-Х5-Х7, находим и увеличиваем поток на эту величину. Ребро Х3-Х2 помечаем как рассмотренное.

6. Более путей от Х0 до Х7 нет, суммируем увеличения потока: 25+10+20=55.
Вывод: максимальный поток равен 55.

2) Построить разрез сети S.
Процедура «пометок вершин».
Начальное состояние: все вершины не имеют пометок.
Вершине Х0 приписывается пометка. Всем вершинам , для которых дуга не насыщена присваиваются пометки ( красные круги)

Определяем дуги минимального разреза: это дуги, начала которых находятся в помеченных вершинах, а концы — в непомеченных вершинах.
Это дуги:
Таким образом, минимальный разрез данной сети
Вычисление величины максимального потока

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

Привет, Хабр!
В свободное от учебы время пишу статьи, которых мне не хватало несколько лет назад.

При решении задачи о максимальном потоке я столкнулся с тем, что во всех мне известных источниках было дано формальное описание самих алгоритмов, что очень сильно затрудняло понимание изложенного материала. И в этой статье я попробую на базовом уровне разобрать Алгоритм Форда-Фалкерсона на конкретном примере, чтобы после прочтения данной статьи, вы хотя бы понимали основную суть самого алгоритма.

Постановка задачи

Имеется следующий ориентированный граф, в котором вес ребра обозначает пропускную способность между вершинами. Нужно найти максимальный поток, который можно пропустить из истокав сток.

Исходный граф

Исходный граф

Как работает сам алгоритм?

Следует понимать остаточную сеть как тот же граф, который имеется на входе, но в этом случае мы будем производить над ним некоторые операции:

Отправлять определенное количество потока из текущей вершины в соседние.

Возвращать определенное количество потока из соседних вершин в текущую.

В начальный момент времени поток, который мы хотим провести через нашу сеть, должен быть равен нулю. Остаточная сеть совпадает с исходной сетью.

Находим любой путь из истока в сток в остаточной сети. Если путь не находим, утверждается, что поток является максимальным.

Пускаем через найденный путь поток равный минимальному весу ребра, которое входит в множество рёбер найденного пути.

Из веса рёбер на этом пути высчитываем размер потока, который мы пустили.

А к весу обратных рёбер (будем считать, что они существуют в остаточной сети и равны 0) прибавляем размер потока. Другими словами, на предыдущем шаге мы отправили некоторое количество потока из текущей вершины в следующую, а теперь при желании можем вернуть это же количество потока обратно в текущую.

Возвращаемся обратно к нахождению пути в остаточной сети после модификации.

Разбор конкретного примера

Разобьем одну итерацию проведения потока по выбранному пути на маленькие шаги, чтобы визуально стало понятно, как меняется остаточная сеть после проталкивания очередного потока.

Допустим наш алгоритм нашел следующий путь из вершинывнашей остаточной сети, которая на момент начала, совпадает с исходным графом.

Сколько потока можем провести по этому пути.
— Больше 2 ед. мы никак не сможем пустить, пропускаем наш поток по этим рёбрам из истока в сток.
Получаем следующее:

Рёбра с нулевым весом можно удалять. Таким образом, на первой итерации мы смогли увеличить максимальный поток на 2 ед.

Теперь дело за малым, остается всего лишь итерироваться до тех пор, пока существует путь из в .

Допустим, на 2-ой итерации мы нашли такой путь в нашей остаточной сети:

Пропускаем 3 ед . потока по этому пути, и перестраиваем остаточную сеть.
Получаем следующее:

На 3-ей итерации нашли такой путь в нашей модифицированной остаточной сети:

Пускаем 1 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:

На 4-ой итерации находим следующий путь в остаточной сети:

Пускаем 4 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:

Итоговая остаточная сеть

Итоговая остаточная сеть

На этом этапе наш алгоритм прекратит выполнение из-за того, что пути из истока в сток не существует. И ответом к поставленной задаче будет служить сумма потоков всех найденных увеличивающихся путей.
Ответ: 10 ед.

Спасибо большое за внимание, надеюсь, был полезен!
Буду рад любым отзывам или поправкам для повышения доступности изложения материала!

7. Транспортная сеть. Основные понятия и определения. Поток в транспортной сети. Теорема Форда – Фалкерсона. Алгоритм Форда – Фалкерсона. Разрез транспортной сети и его свойства. Поиск максимального паросочетания

Транспортная сеть — ориентированный граф G = (V, E) , в котором каждое ребро (u,v) \in E имеет неотрицательную пропускную способность c(u,v)>=0 и поток f(u,v).

Выделим теперь специальные типы вершин в сети.

Вершина y, из которой дуги только исходят, т.е. если , называется источником или входом сети S.

Вершина z, в которую дуги только входят, т.е. если , называется стоком или выходом сети S.

Потоком в транспортной сети Т называется неотрицательная вещественная функция, определенная на множестве дуг, удовлетворяющая условиям:

  • ограниченности: поток по любой дуге сети не превосходит пропускной способности этой дуги;
  • сохранения: суммарный поток , заходящий в любую вершину сети ( кроме истока и стока ) равен суммарному потоку , выходящему из этой вершины.

Дуга сети называется насыщенной, если поток по этой дуге равен пропускной способности этой дуги.

Поток по пути называется полным, если хотя бы одна дуга пути насыщена.

Как упоминалось выше, поток в сети — это функция, определенная на множестве дуг. Величиной потока называется сумма значений этой функции по всем выходным дугам сети ( выходные дуги сети — это дуги, инцидентные стоку).Понятия потока и величины потока в сети часто путают, однако между ними существует различие: поток — это функция, а величина потока — число.

Разрезом сети называется множество, которому принадлежит исток, и не принадлежит сток. Т.е. разрез — это минимальное (в смысле отношения включения) множество дуг, удаление которых “ разрывает” все пути, соединяющие исток и сток.

Пропускной способностью разреза называется число, равное сумме пропускных способностей дуг этого разреза. Разрез называется минимальным, если имеет наименьшую пропускную способность.

Теорема Форда – Фалкерсона.

В любой транспортной сети величина любого максимального потока равна пропускной способности любого минимального разреза.

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

Алгоритм начинает свою работу с нулевого потока и на каждой своей итерации увеличивает поток в сети. На каждом шаге находится увеличивающая величину потока цепь. Поток увеличивается вдоль дуг этой цепи, пока она не станет насыщенной.

  1. Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
  2. В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.
  3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:
    1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью Cmin.
    2. Для каждого ребра на найденном пути увеличиваем поток на Cmin, а в противоположном ему — уменьшаем на Cmin.
    3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.

    Для определения потока в сети используют алгоритм Форда-Фалкерсона:

    а) ищем любую цепь из истока графа в сток;

    б) каждой дуге приписываем возможный больший поток из истока в сток (записываем его через дробь с весом дуги; при этом поток не может превысить вес дуги, но может быть ему равен);

    в) если поток становится равен весу дуги, то эта дуга является насыщенной, то есть через нее нельзя пройти при рассмотрении цепей в графе;

    г) так перебираем все возможные цепи, пока станет невозможно попасть из истока в сток;

    д) поток в сети будет равен сумме потоков всех дуг, инцидентных стоку графа (следует заметить, что сумма потоков всех дуг, инцидентных стоку графа равна сумме потоков всех дуг, инцидентных истоку графа).

    Сети с заданными пропускными способностями узлов и связей.

    Пусть в сети N= (К, R) заданы пропускные способности связей санузлов g;,j= 1,2. | к |. Необходимо найти максимальный поток между источником 5 и стоком /, при этом полный поток, входящий в узел Хр не должен превышать^ для всех j. Такая задача возникает, например, при отправке туристов в места отдыха при ограничениях мест в гостиницах на промежуточных пунктах.

    Сеть с заданной пропускной способностью узлов

    Рис. 3.12. Сеть с заданной пропускной способностью узлов

    Рассмотрим соответствующий граф (рис. 3.12).

    Для вычисления максимального потока с заданными ограничениями на пропускную способность узлов преобразуем сеть, изображенную на рис. 3.12, следующим образом [19]: каждому узлу Xj сети ./V поставим в соответствие два узла xj и xj сети N’ и соединим их связью (Xj , xj)c пропускной способностью^. Все связи, входящие в вершину Xj, сделаем входящими в вершину xj , а исходящие — исходящими из вершины xj (рис. 3.13).

    Модифицированная сеть с заданной пропускной способностью связей вместо узлов

    Рис. 3.13. Модифицированная сеть с заданной пропускной способностью связей вместо узлов

    Отметим также, что если минимальный разрез сети N’ не содержит связи (ху + , x

    j), то пропускные способности узлов в N излишни. Если минимальный разрез в N’ содержит такие связи, то соответствующие им узлы в А^насыщены полученным максимальным потоком и ограничивают его.

    Так как полный поток, входящий в узел ху + , протекает и по связи (xj, xj) с пропускной способностью gj, то максимальный поток в сети N с пропускными способностями связей и узлов равен максимальному потоку в сети N’, имеющей только пропускные способности связей.

    Максимальный поток между каждой парой вершин

    Рассмотрим следующую задачу сервиса: требуется определить максимальное число средств потребления, передаваемых от одного узла к другому. Предполагается, что поток продукта, который может транспортироваться к нескольким стокам, ограничен только пропускными способностями связей. Аналогичная задача возникает при проектировании компьютерной сети.

    Многополюсная сеть

    Рис. 3.14. Многополюсная сеть

    Поставленную задачу можно решить с помощью процедуры нахождения максимального потока к каждой паре узлов. Рассмотрим сеть на рис. 3.14. Используя метод Форда—Фалкерсона, вычислим потоки между всеми узлами и запишем их в виде матрицы:

    Если пропускная способность каждой связи не зависит от направления движения потока по этой связи, то матрица будет симметричной и общее число задач о максимальном потоке будет равно п(п —1)/2, п — число узлов. Для рассматриваемого примера с 6 узлами это число равно 15 и соответствует числу элементов матрицы V, расположенных выше главной диагонали.

    Алгоритм Гомери-Ху. Алгоритм является более эффективным, так как максимальный поток вычисляется п —1 раз [19, 35].

    Рассмотрим неориентированную сеть N = (К, R) с п узлами и связями (i,j), i,j= 1,2. п, с пропускными способностями с^= с/7. Введем следующие обозначения: Vy — максимальный поток между узлами i и У; (X, X)tj — минимальный разрез, отделяющий узел i от У, где / е X; j gX, с пропускной способностью С(Х, Х)9.

    Основная идея алгоритма Гомери—Ху состоит в итеративном построении максимального остовного дерева Т = (V, Е), ветви которого соответствуют разрезам, а пропускные способности ветвей — величинам разрезов. Число вершин дерева | V = п; число ребер — Е = п — 1. Поэтому алгоритм выполняется за п — 1 шагов.

    После построения дерева для определения максимального потока между двумя произвольными узлами надо найти путь, соединяющий эти два узла, и выбрать на этом пути дугу с минимальным весом. Вес этой дуги равен величине максимального потока между рассматриваемыми узлами. Так можно найти максимальные потоки между всеми узлами и записать их в матрицу V.

    Построение дерева осуществляется следующим образом:

    • 1) выбор двух произвольных узлов в качестве источника s и стока t;
    • 2) вычисление максимальной пропускной способности между стоком и источником;
    • 3) построение минимального разреза, разделяющего источник и сток.

    Согласно теореме о максимальном потоке и минимальном разрезе, максимальный поток из узла s, рассматриваемого как источник, в узел ?сток вычисляется как vst = С(Х, X)st. Желательно, чтобы разрез имел минимальную пропускную способность, т.е. охватывал насыщенные связи, чтобы легче подсчитать его пропускную способность. Узлы, расположенные по обе стороны разреза, конденсируются, и разрез представляется ветвью с пропускной способностью разреза. Процесс конденсации осуществляется так, чтобы использовать решение задачи о максимальном потоке, найденное на предыдущем этапе.

    Поскольку число узлов сети с каждым шагом становится меньше, то упрощается задача нахождения максимального потока между оставшимися узлами. Как показано Гомери—Ху, если следующие узлы / и у выбираются по какую-либо сторону разреза в качестве следующих источника у и стока t, то множество узлов с другой стороны разреза может быть объединено в один узел. При этом максимальный поток из / в у будет одним и тем же для исходной и конденсированной сетей [19].

    Порядок конденсации узлов сети

    Рис. 3.15. Порядок конденсации узлов сети: а — сеть, разделенная разрезом на подсети; б— объединение узлов правой подсети в один узел; в — результат суммирования пропускных способностей дуг

    На рис. 3.15 показан процесс конденсации узлов. Связи, идущие к одноименному узлу левой подсети, объединяются в одну связь с суммарной пропускной способностью (рис. 3.15,6). Получив после объединения модифицированную сеть, можно вычислить максимальный поток от узла / к узлу у, используя описанный выше метод.

    Алгоритм построения можно записать следующим образом [35]:

    В качестве множества ветвей дерева выбрать пустое множество, Е = 0. Все узлы объединить в одну группу V = 1; for k = 1 to п-1

    do выбрать произвольную паруузлов1 и j, еще не отделенных друг от друга

    в строящемся дереве; положить s = i и t = j; вычислить максимальный поток из s в t; найти минимальный разрез, отделяющий s от t; представить данный разрез ветвью и поместить ее в дерево; вес ветви положить равным пропускной способности разреза; ветвь должна соединять узлы или группы узлов, расположенные по разные стороны разреза;

    сконденсировать в один узел каждую связную подсеть, соединенную с группой, содержащей узлы i и j; k = k + 1 return к

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

    Шаг 1. Рассмотрим узлы /= Зи/ = 4. Положим s= i= Зи t=j= 4. Максимальный поток между узлами 3 и 4, как следует из матрицы V, равен 22, поэтому v34 = v43 = 22.

    Шаг 1 итерации

    Рис. 3.16. Шаг 1 итерации: а — разрез сети; 6 — остовное дерево

    На данном шаге минимальный разрез нужно сделать по насыщенным связям (7, 2), (3, 2), (3, 4), (3, 5) или (2, 4), (3, 4), (5, 4), (6, 4), что упрощает вычисления, так как данные разрезы будут иметь минимальную пропускную способность. Сделаем разрез сети по второму варианту, как показано на рис. 3.16. Пропускная способность разреза С(Х, X)34 = 22 соответствует максимальному потоку v34 = v43 = 22. Разрез с минимальной пропускной способностью показывает, что построение дерева разрезов можно начать с ветви, соединяющей узел 4 и конденсированный узел, состоящий из узлов 7, 2, 3, 5, 6.

    Шаг 2. Рассмотрим узлы / = 1 и / = 3. Положим s = i = 1 и t =j = 3. Максимальный поток между узлами 7 и нравен 9. Поэтому v13 = v31 = 9.

    Шаг 2 итерации

    Р и с. 3.17. Шаг 2 итерации: а — разрез сети; б — остовное дерево

    Сделаем минимальный разрез сети так, как на рис. 3.17. Пропускная способность разреза С(Х, Х)хг = 9 соответствует максимальному потоку v13 = v31 = 9. Разрез с минимальной пропускной способностью показывает, что построение дерева разрезов можно продолжить, присоединив к нему ветвь, которая соединяет узел 7 с конденсированным узлом, состоящим из узлов 2,3, 5, 6. Все узлы, кроме 7, находятся по правую сторону разреза.

    Шаг 3. Рассмотрим узлы / = 4 и j= 6. Положим s=i= 4 и t=j= 6. Максимальный поток между узлами 4 и 6равен 12. Поэтому v46 = = v64=12.

    ШагЗ итерации

    Рис. 3.18. ШагЗ итерации: а — разрез сети; б — остовное дерево

    Пропускная способность минимального разреза сети, показанного на рис. 3.18, С(Х, Х)46 = 12 соответствует максимальному потоку v46 = v64 = 12. Разрез с минимальной пропускной способностью показывает, что построение дерева разрезов можно продолжить, присоединив к нему ветвь, которая соединяет узел 6 с конденсированным узлом, состоящим из узлов 2,3,5(рис. 3.18,6).

    Шаг 4. Рассмотрим узлы /= 2 иj= 3. Положим х = /= 3 и t=j= 2. Максимальный поток между узлами 2 и 3 равен 22, поэтому v23 = = v32 = 22. При минимальном разрезе сети (см. рис. 3.19, а) пропускная способность разреза С(Х, Х)32 = 22 соответствует максимальному потоку v23 = v32 = 22. При этом узлы 1 и Улежат по одну сторону разреза, а все остальные узлы по другую. Сконденсируем в один узел узлы 1 и 3, используя описанные выше и изображенные на рис. 3.15 правила. Преобразованная сеть (рис. 3.19, в) будет использоваться для вычисления максимального потока на следующем шаге итерации.

    Шаг4 итерации

    Рис. 3.19. Шаг4 итерации:

    а — разрез сети; б — остовное дерево; в — преобразованная сеть

    Шаг 5. Рассмотрим узлы/=2 и j= 5. Положим s = i=2 wt=j= 5. Максимальный поток между узлами 2 и 5 равен 17, поэтому v25 = = v52 = 17. Максимальный поток из узла 2 в узел 5 преобразованной сети равен максимальному потоку между этими же узлами исходной сети.

    При минимальном разрезе сетщпоказанном на рис. 3.20, пропускная способность разреза С(Х, Х)25 = 17 соответствует максимальному потоку v25 = v52 = 17. При этом узлы 5и 6лежат по одну сторону разреза, а все остальные узлы по другую. Сконденсируем в один узел узлы 5 и 6. Эту сеть можно использовать для последующих вычислений. Число ребер в дереве стало равным 5, следовательно, процесс образования дерева завершается. Как видно, максимальные потоки между узлами дерева соответствуют найденным выше и представленным матрицей У. На дереве показаны узкие места, которые ограничивают поток в сети.

    Шаг 5 итерации

    Рис. 3.20. Шаг 5 итерации:

    а — разрез сети; б — остовное дерево; в — преобразованная сеть

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *