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

8. Алгоритм нахождения минимального разреза сети

 Начальное состояние: ¾ все вершины не имеют пометок.

 Вершине s приписывается пометка.

 Всем вершинам x i Î < G s>, для которых дуга (s, x i ) не насыщена:

с si > j si присваиваются пометки.

 Всем вершинам x k Î < G x i >, для которых дуга ( x i , x k ,) не насыщена:

с ij > j ij присваиваются пометки.

В ходе присвоения пометок вершинам сети возможны две

1. Удалось присвоить пометку вершине t, из чего следует, что в сети есть путь от вершины s к вершине t, все дуги которого не насыщены. Следовательно, поток на сети может быть увеличен за счёт его увеличения на пути s,…, t (с помощью рассмотренного выше алгоритма).

2. Не удалось присвоить пометку вершине t. Следовательно, на сети получен максимальный поток и, для его вычисления, возможно, построить минимальный разрез.

На рисунке 10.17 приведён результат пометок вершин для рассматриваемой сети:

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

Решить задачу нахождения максимального потока в транспортной сети с помощью алгоритма Форда—Фалкерсона, и построить разрез сети 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 приписывается пометка. Всем вершинам , для которых дуга не насыщена присваиваются пометки ( красные круги)

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

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. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.

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

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

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

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

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

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

   Теорема о максимальном потоке и минимальном разрезе

   Пусть в ориентированной сети S = (N, U) от источника к стоку протекает поток, величина которого равна V. Поскольку пропускная способность каждой дуги c(i, j) является величиной конечной, то максимальная величина допустимого потока всей сети тоже ограничена. Максимальный поток сети определяется на основе одного из основных понятий теории сетей — понятия разреза. Введем понятие разреза.

   Множество вершин N сети S = (N, U) можно разбить на два непересекающихся подмножества N_p и N_p, которые соединяются между собой дугами, образующими множество дуг разреза U_p. Причем исток s принадлежит множеству вершин N_p, а сток t принадлежит множеству вершин N_p. Тогда величина потока из множества N_p в множество N_p, протекающего по дугам и_р, не может быть больше, чем сумма пропускных способностей дуг этого множества, что можно записать

   

   Этот барьер для потока, отделяющий множество вершин N_p от множества вершин N_p, называется разрезом и обозначается (N_p, N_p). Разрез представляет такое множество дуг U_p, исключение которых отделяет вход от выхода сети и, следовательно, отделяет множество N_p от N_p сети S — (N, U) таким образом, что существование потока в таком случае невозможно, и тогда V = 0. Причем начало дуги разреза принадлежит множеству N_p, а конец — N_p. Таким образом, в разрез входят дуги, соединяющие вершины этих множеств.