Как найти минимальный разрез в сети
Перейти к содержимому

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

  • автор:

Разрез, лемма о потоке через разрез

Пусть [math]\langle S,T\rangle[/math] — разрез в [math]G[/math] . Тогда [math]f(S,T)\leqslant c(S,T)[/math] .

Если [math]f(S,T)=c(S,T)[/math] , то поток [math]f[/math] — максимален, а разрез [math]\langle S,T\rangle[/math] — минимален.

Потоки и разрезы

Из закона слабой двойственности следует, что [math]f(S_1,T_1)\leqslant c(S_2,T_2)[/math] для любых двух разрезов [math]\langle S_1,T_1\rangle[/math] и [math]\langle S_2,T_2\rangle[/math] в сети [math]G[/math] , так как [math]f(S_1,T_1)=|f|=f(S_2,T_2)\leqslant c(S_2,T_2)[/math] . Значит, если расположить все величины потоков и разрезов на оси OX, то у потоков с разрезами может быть максимум 1 точка пересечения.

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

Минимальный разрез — 1 с пропускной способностью 60

Разрез «Разрезанные» ребра Пропускная способность
1 (1,2),(1,3),(1,4) 10+30+20=60
2 (1,3),(1,4),(2,3),(2,5) 30+10+40+30=110
3 (2,5),(3,5),(4,5) 30+20+20=70

Источники информации

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн КлиффордАлгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом «Вильямс», 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
  • Википедия: Разрез графа
  • Википедия: Разрез графа (англ.)
  • Алгоритмы и структуры данных
  • Задача о максимальном потоке

Разрез сети

см. также как найти минимальный путь в графе методом потенциалов.

Профессии будущего

РБК Тренды изучили прогнозы российских и зарубежных футурологов, и составили список самых востребованных профессий в ближайшие 30 лет. Это профессии из 19 отраслей: от медицины и транспорта до культуры и космоса

Налоговый вычет на обучение

√ 120 тыс. руб. — максимальная сумма расходов на обучение
√ вычет от государства
√ вычет от работодателя

Требуются авторы студенческих работ!

  • регулярный поток заказов;
  • стабильный доход
  • Задать вопрос или оставить комментарий
  • Помощь в решении
  • Поиск
  • Поддержать проект

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

rui_er → Codeforces Round 942 (Div. 1, Div. 2)

EnDeRBeaT → [Tool] Graph Debugger

rui_er → Codeforces Round 942 (Div. 1, Div. 2) Editorial

Haidora → A general approach to solve subree distinct values queries!

awoo → Разбор Educational Codeforces Round 165

Abito → Who’s going to IIOT 2024?

Некропост

dv.jakhar_ → How to solve this problem, any ideas?

gareeeeeeeeeeeeeeeev → Релиз версии бот 1.2

Zanite → [Photos Dump] Jollybee CP Team, the Luxor WF, and the Indomie Aftermath

wuhudsm → TheForces Round #30 (Good-Forces) Editorial

Некропост

Igor_Kudryashov → Разбор задач Coder-Strike 2014 Финал

h ehezhou → 2024-The 6th Turing Cup Tournament

Некропост

MikeMirzayanov → Изменение правил об использовании стороннего кода в соревнованиях Codeforces

transfermarket → Report cheater obfuscate code

Asuna_Yuuki → MEME

Loserinlife → Need help

Некропост

Sharon → Who is going to UCF Saturday Practice — November 2nd, 2019 ?

Cipesta. → Beyond CP: What’s Next

tickbird → Been stuck at green almost a year

123gjweq2 → Can someone please help me?

Некропост

Monogon → Codeforces Round #639 Editorial

Некропост

Vladosiya → Codeforces Round 863 (Div. 3) Разбор

MofK → Codeforces Global Round 25 Editorial

Kolyanchick → До скорых встреч

awoo → Educational Codeforces Round 165 [рейтинговый для Div. 2]

Блог пользователя imslavko

Минимальный вершинный разрез в S-T графе

Автор imslavko, 12 лет назад ,

Здавствуйте! Все знают, что |MinCut| = |MaxFlow| в сети. Кто знаком с темой может прокрутить вниз, там вопрос.

[newbie mode] Как найти какие именно ребра являются разрезом? Тут вроде тоже все понятно, разделим множество вершин на два множества: S — множество достижимых вершин из истока по ненасыщенным ребрам и T = V / S . Ребра, которые соединяют вершины из разных множеств и будут одним из ответов.

Как найти вершинный разрез? Учили так: разделим каждую вершину v на 2 вершины: v1 для входящих и v2 для выходящих. Сделаем так же ребро v1 — > v2 с пропускной способностью 1. Далее найдем макс.поток и размер потока будет равен минимальному вершинному разрезу. Но как теперь найти ответ?

В задаче на USACO trainings (telecow, 5.4.5) проходит такое решение для |V| ≤ 100, |E| ≤ 600 :

Будем по очереди удалять ребро между v1 и v2 для каждой вершины и будем заного находить поток. Если поток уменьшился на единицу, то эта вершина входит в раздрез.

Мне не очень понравилось это решение, ведь делая это алгоритмом Диници, это будет работать не мало: O((|V||E|) 2 ) , где кол-во вершин увеличивается в 2 раза, а кол-во ребер примерно в 4 раза(обратные ребра и по 2 ребра на каждое, так как ребра не ориентированны), получается где-то 100 * 2 * 600 * 4 в квадрате итераций? Сначала я испугался такой цифры, но вспомнив, что ребра с пропускной способностью в единицу делают ее еще быстрее, то выходит помножиное на |V| вызовов, то выходит около 6 * 10 6 , что приемлемо. [/newbie mode]

Но как находить вершинный разрез, когда вершин и ребер еще больше? Есть ли более оптимальное решение?

Теги

maxflow, mincut, ford-fulkerson

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

96 8.1 . Процедура “ пометок вершин “  Начальное состояние: ¾ все вершины не имеют пометок.  Вершине 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 приведён результат пометок вершин для рассматриваемой сети:

1 (10) 4 3
(12) 12 (8) 8 (22) 7 (10) (11) 11
(14) 9 5 (12) 10 6 (10) 10
(18) 17 (12) 12 t
( (12) 12 (17) 17

Рисунок 10.17.

97 8.2. Определение дуг минимального разреза По результату алгоритма пометок, когда не возможно пометить вершину t (сток), определяем дуги минимального разреза: ¾ это дуги, начала которых находятся в помеченных вершинах, а концы – в не

помеченных вершинах.
В наше примере это дуги u s,1 ; u 5,6 ; u 2,6 ; u 3,t ; u 4,t ( см. рисунок 10.18 ).
Таким образом минимальный разрез данной сети Т = (u s,1 ; u 5,6 ;
u 2,6 ; A=(1, 6, t) u 3,t ; u 4,t ).
9 . 1 (10) 4 3
(12) 12 (8) 8 (22) 7 (10) (11) 11
s (14) 9 5 (12) 10 6 (10) 10 t
(18) 17 (12) 12 (12) 12
( (17) 17

Рисунок 10.18. Вычисление величины максимального потока Ф max :

Ф max = с s,1 + с 5,6 + с 4,t + с 2,6 + с 3,t = 12+10+17+12+ 11 = 62.
Допустимый поток максимальной величины на заданной сети G ¾
найден.
Упражнения
1. Для сети G = ( X,U, С ), где | X | = 6, | U | = 10 и U = <( x 1 , x 2 ),
( x 1 , x 3 ), ( x 2 , x 4 ), ( x 2 , x 5 ), ( x 3 , x 2 ), ( x 3 , x 5 ), ( x 4 , x 3 ), ( x 5 , x 4 ), ( x 4 , x 6 ), ( x 5 , x 6 )>,
определить: ¾ является G насыщенной, т.е. в G задан максимальный

98 допустимый поток, или G ненасыщенная, если известно, что дуги сети

( x 1 , x 2 ), ( x 4 , x 6 ), ( x 3 , x 5 ), ( x 2 , x 4 ), ( x 5 , x 4 ) ¾ насыщенные.
2. Определить максимальный поток в сети G = ( X,U, С ), где | X | = 6,
| U | = 10, пропускные способности дуг равны: ¾ c 12 =7,
c 13 =5, c 24 = 4, c 25 =10, c 32 = 8, c 35 = 6, c 43 = 5, c 45 =3, c 46 = 11, c 56 = 6.
3. Определить минимальный разрез в сети G = ( X,U, С ), где
| X | = 6, U = <( x 1 , x 2 ), ( x 1 , x 3 ), ( x 2 , x 4 ), ( x 2 , x 5 ), ( x 3 , x 2 ), ( x 3 , x 5 ), ( x 4 , x 3 ), ( x 4 ,
x 5 ), ( x 4 , x 6 ), ( x 5 , x 6 )> , если известно, что дуги сети ( x 1 , x 2 ), ( x 4 , x 6 ), ( x 3 , x 5 ),
( x 2 , x 4 ), ( x 4 , x 5 ) , ( x 5 , x 6 ) ¾ насыщенные.

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

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