Имеет ли данная сеть уникальная Min-Cut?

Question

Пусть G = (V, E) - сеть с s и t, являющаяся источником и стоком. Пусть Г максимальный поток в G. Найти алгоритм, который определяет, существует ли уникальный мин-разрез в G.

мне удалось найти аналогичный вопрос на этом сайте:

Determining the uniqueness of a min-cut

резюме ответа даются там:

Найти все вершины достижимы из S в остаточном графе, и мы нашли мин-разрез (S, T) в G.

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

Эта группа также является мини-срезом.

Если этот разрез идентичен вашему первоначальному разрезу, тогда есть только один. В противном случае вы просто нашли 2 разреза, поэтому оригинал не может быть уникальным.

Я не понимаю, почему, если разрез идентичен оригинальному разрезу, то разрез уникален. Кто может пообещать нам, что нет другого минимального разреза?

Заранее спасибо

Answer 1

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

Я просто скопировать и вставить его здесь

Given a minimum S-T cut, (U,V) with cut-edges E', we make one simple observation: 
If this minimum cut is not unique, then there exists some other minimum cut with 
a set of cut-edges E'', such that E'' != E'. 

If so, we can iterate over each edge in E', add to its capacity, recalculate the 
max flow, and check if it increased. 

As a result of the observation above, there exists an edge in E' that when 
increased, the max flow doesn't increase iff the original cut is not unique. 

некоторое объяснение моего собственного:

Что вам нужно доказать, на самом деле является

there exists an edge in E' that when increased, the max flow doesn't increase 
<=> 
the original cut is not unique 

=>:
Вы увеличьте емкость края e на 1, вычислите новый максимальный поток, и он останется s то же самое, что означает, что e не находится в новом мини-разрезе. (если e находится в соответствии с свойством min-cut, f (e) = емкость e, что приводит к увеличению). Поскольку e не находится в новом мини-разрезе, это также минимальный разрез исходного графика, который имеет тот же объем с разрезом, который мы знаем. Таким образом, оригинальный разрез не является уникальным.

< =:
Оригинальный покрой не является уникальным (назовем их E и E'), что означает, что вы можете найти край e, который находится в E, но не в E'. Затем вы просто увеличиваете емкость e на 1. При вычислении минимального разреза нового графика E' уже существует. Поскольку E' не содержит края e, максимальный поток остается без изменений.

Надеюсь, вы понимаете :)

Answer 2

другой вариант, чтобы доказать противного первый путь: ->: допустим есть один минимальный (S, T) разрезали обрезанными краями Е». После увеличения емкости ребра e, который принадлежит E 'на 1, и обнаружив, что максимальный поток остается неизменным, приводит к тому, что e не находится в новом минимальном разрезе. (если e находится в E ', то согласно свойству min-cut максимальный поток будет увеличен). Однако в начале мы сказали, что e находится в E '- противоречие

Answer 3

Алгоритм, о котором вы говорили, более эффективен, чем предлагаемые. Алгоритм:

Для графа G = (V, E)

1. Найти максимальный поток в графе, и пусть R будет последним остаточный граф.
2. Run BFS из S (найти узлы, достижимые из s), позволяет называть их X
3. Run BFS из т с обратными краями (найти узлы, которые есть путь к т), позволяет называть их Y.
4. если X + Y = V ('+', как и в союзе) возвращают значение TRUE, иначе FALSE

Краткое объяснение:

на шаге 2 мы находим узлы, которые определяют минимальный разрез (X, V/X) .X - множество всех узлов, доступных из s в нашем последнем остаточном графе. На шаге 3 мы находим множество узлов, из которых t достигается в последнем остаточном графе. Этот набор определяет разрез (V-Y, Y), который является минимальным разрезом, ближайшим к t. На шаге 4 идет один и тот же срез с обоих концов (X + Y = V), тогда график имеет уникальный минимальный разрез.

Сложность в основном заключается в поиске максимального потока. С Edmonds Karp O (| E |^2 | V |) и BFS O (| E | + | V |).

Сложность предлагаемого ответа будет O (| V || E |^3).