Найти все ребра в min-cut

Question

Пусть (G,s,t,{c}) - сеть потоков, и пусть F - множество всех ребер e, для которых существует хотя бы один минимальный разрез (A,B), такой что e идет от A к B. Дайте алгоритм полиномиального времени, который находит все ребра в F.

ПРИМЕЧАНИЕ: Пока я знаю, что мне нужно запустить Ford-Fulkerson, чтобы у каждого края был поток. Кроме того, я знаю, что для всех ребер в F поток f(e) = c(e). Однако не все ребра в графе G, который учитывает это ограничение, будут в минимальном разрезе. Я застрял здесь.

Answer 1

Предположим, вы вычислили максимальный поток на графике G и вы знаете поток через каждое ребро на графике. Из исходной вершины s, выполните поиск в ширину или поиск в глубину на исходном графике и проходите только по тем ребрам, у которых поток меньше емкости ребра. Обозначим множество вершин, достижимых в этом обходе, как S и недоступные вершины как T,

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

Этот учебник в Topcoder предоставляет объяснение / доказательство вышеупомянутого алгоритма. Посмотрите на раздел, начинающийся со следующего текста:

Разрез в сети потоков - это просто разбиение вершин на два набора, назовем их A и B таким образом, что исходная вершина находится в A, а сток - в B.

Я попытаюсь дать объяснение соответствующего раздела в руководстве Topcoder (только для того, чтобы уточнить это также).

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

Факт 1: исходная вершина s должен быть в комплекте S и топить вершину t должен быть в комплекте T,

В противном случае вершины s а также t должен быть в том же наборе, что означает, что мы должны найти путь от s в t состоящий только из ребер, у которых поток меньше емкости. Это означает, что мы можем увеличить поток s в t и, следовательно, мы нашли путь расширения! Однако это противоречие, так как мы уже вычислили максимальный поток на графе. Следовательно, это невозможно для исходной вершины s и топить вершину t быть подключенным, и они должны быть в разных наборах.

Факт 2: Каждое ребро начинается с набора S и заканчивается в сет T должен иметь поток == емкость

Мы снова докажем это противоречием. Предположим, что есть вершина u в S и вершина v в T такой край (u,v) в остаточной сети поток меньше емкости. По нашему алгоритму выше, это ребро будет пройдено, а вершина v должен быть в комплекте S, Это противоречие. Следовательно, такой край должен иметь поток == емкость.

Факт 3: удаление краев в C из графика G будет означать, что нет пути из любой вершины в множестве S к любой вершине в множестве T

Предположим, что это не так, и есть некоторое преимущество (u,v) соединяющий вершину u в комплекте S к вершине v в комплекте T, Мы можем разделить это на 2 случая:

1. Поток через край (u,v) меньше, чем его емкость. Но мы знаем, что это приведет к вершине v быть частью набора S, так что этот случай невозможен.
2. Поток через край (u,v) равен его емкости. Это невозможно, так как край (u,v) будет рассматриваться как часть набора ребер C,

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

Факт 4: Каждое ребро в исходном графике G который начинается с набора вершин T но заканчивается в наборе вершин S должен иметь поток 0

Объяснение к учебнику по Topcoder может быть неочевидным при первом чтении, а следующее - обоснованное предположение с моей стороны и может быть неверным.

Предположим, что существует какое-то ребро (x,y) (где x принадлежит множеству вершин T а также y принадлежит множеству вершин S), так что поток через (x,y) больше 0. Для удобства обозначим поток через (x,y) как f, Это означает, что в остаточной сети должен существовать обратный фронт (y,x) с мощностью f и поток 0, С вершины y является частью набора S задний край (y,x) имеет поток 0 с мощностью f > 0 наш алгоритм будет пересекать край (y,x) и поместить вершину x как часть набора вершин S, Тем не менее, мы знаем, что вершина x является частью набора вершин T и, следовательно, это противоречие. Таким образом, все края от T в S должен иметь поток 0.

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

1. Максимальный поток должен быть меньше или равен производительности любого реза. По факту 3, C является разрезом графика, поэтому максимальный расход должен быть меньше или равен пропускной способности резания C,

2. Факт 4 позволяет нам сделать вывод, что "обратного потока" от T в S, Это наряду с фактом 2 означает, что поток полностью состоит из "прямого потока" от S в T, В частности, весь прямой поток должен быть результатом C, Это значение потока является максимальным потоком. Таким образом, по теореме о минимальном сечении Max-flow мы знаем, что C должно быть минимальное сокращение.