Наименьшая $s$-компонента в mincut

Question

Предположим, что существует ориентированный граф $G=(V,E)$, с источником $s$ и тонуть $т$, и я вычисляю по нему максимальный поток.Тогда я знаю, что смогу найти минимальную версию $(А,Б)$, позволяя $А$ быть набором вершин, достижимых из источника $s$.

У меня вопрос, этот набор $А$ самый маленький из возможных $s$-компонент?Я думаю, что это.Точнее, существует ли подмножество вершин $А^*$, такой, что $(A^*, V\setminus A^*)$ является минимальным разрезом, а для всех других возможных подмножеств вершин $А$ такой, что $(A, V\setminus A)$ это минимальная версия, у нас есть $size(A^*) \leq size(A)$.

Кроме того, для любого другого минимального разреза $(C,D)$, у нас есть $A \подмножество C$?.Я тоже думаю, что это так.Но я не могу этого доказать.

Любая интуиция/подсказки очень ценятся!

Редактировать

Значение $s$-компонент:Минимальный разрез — это разбиение вершин $G$ на два непересекающихся множества $(А,Б)$, где $А$ содержит источник $s$ и $Б$ содержит раковину $т$.А $s$-компонент относительнотогда минимальная версия - это набор $А$.

По «самому маленькому» $s$-компонент я имею в виду $s$-компонента с наименьшей мощностью.Мне интересно, может ли быть несколько разных минимальный $s$-компонент относительноустановить включение, т.е. $s$-компоненты одинаковой мощности, но не равные множества.Аналогично, интересно, существует ли минимум $s$-компонент;набор вершин, который находится во ALL $s$-компоненты.

Answer 1

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

Там могут быть несколько минут, все с той же стоимостью. Они образуют структуру решетки: пересечение двух мин - это еще один мин, а объединение двух мин - это еще один мин. Вы можете определить «наименьший» элемент в этой решетке, взяв пересечение всех минимальных сокращений; Это будет еще один мин, и у него будет самая маленькая кардинальность всех мин.

Как я понимаю это, можно доказать, что мин, полученный из максимального потока, всегда это «наименьшее» мин. Или, чтобы поставить его другим способом, если вы думаете о источнике $ S $ слева и раковину $ T $ T $ справа, затем любой мин, полученный из $ s, T $ - Max-поток всегда будет «левым» вырезом. Кроме того, он будет следовать за тем, что любой другой мин-среза будет суперсетом этого выреза, найденного максимальным потоком, точно так, как вы предположили.

Для ссылок на эти результаты и другие связанные с ними материалы см. Следующие вопросы (Примечание. Вам, возможно, понадобится дважды проверить некоторые претензии самостоятельно, так как я их не проверил):

PRORD-FULKERSON всегда производит левый минимальный нарезки

https://stackoverflow.com/a/8101250/781723

https://stackoverflow.com/q/26696312/781723

https://stackoverflow.com/q/9210755/781723

https://stackoverflow.com/q/41964288/781723

Answer 2

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

Позволять $A, V\setminus A$ и $B, В\setminus B$ быть минимальными разделами:$$\delta(A,V\setminus A)=\delta(B,V\setminus B) = \min_{X\subseteq V,s\in X} \delta(X,V\setminus X)$$Теперь добавьте ребра с весом. $\varepsilon>0$ из вершины $т$ ко всем остальным вершинам.Новые разрезы, соответствующие $А$ и $Б$ иметь обновленные веса:$$ delta (a, v setminus a) + | a | cdot varepsilon, delta (b, v setminus b) + | b | cdot varepsilon $$соответственно.Поскольку оба первых члена равны, вторые члены $\varepsilon |A|$ и $\варепсилон |B|$ определит порядок.Таким образом, минимальный разрез в новом графе — это минимальное разбиение минимальной мощности в исходном графе.Единственное предостережение заключается в том, что $\varepsilon$ должен быть выбран достаточно малым, чтобы гарантировать, что минимальный разрез в новом графе является минимальным разрезом в исходном графе.Если веса являются целыми числами, любое значение меньше $1/|В|$ было бы достаточно.

($\звезда)$ : $\delta(X,V\setminus X)$ обозначает сумму весов перекрестных ребер между $X$ и $V\setminus X$.