Теория графов - глобально минимальный разрез и его последствия

Question

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

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

Рассматривайте наборы узлов U,V, которые разделены минимально разрезанным по всему миру (т.е. st-cut, где s in U, t in V) , Примечание: мы не заботимся о краях от V до U.

Для любых u in U, v in V м u-v-cut не может быть меньше s-t-cut, в противном случае s-t-cut не будет (глобально) минимальным. По этой же причине разрез между двумя вершинами в u или двумя вершинами в V может быть меньше.

С другой стороны, u-v-cut также не может быть большим, иначе ему нужно будет включить некоторые края U->V, не являющиеся частью s-t-cut, что означает, что s-t-cut вообще не срезается.

Достаточно, чтобы исправить s произвольно и перебрать все остальные вершины x. s либо в U, то S-х-срез соответствует глобальному минимуму, если x в V, или х-х-срез делает, если s в V и x в U. Если они оба являются частью одного и того же набора, разрез будет по крайней мере столь же большим (но, возможно, большим), как глобальный минимум.

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

Казалось, это имело смысл для меня. Я ошибаюсь? И если да, то почему?

Answer 1

Моя интерпретация является то, что вы в основном просят следующий вопрос:

Можем ли мы найти глобальный минимум нарезанную фиксируя произвольную вершину s и вычисляя все е и ц мин прорезями для всех вершин Т = s?

Ответ: Да, и это легко доказать: Рассмотрим глобальную мин-разрез (U, V) со значением С. Тогда либо ы в U или s в V.

Case 1: s находится в U. По определению минимального разреза имеем V! = {}, Поэтому в V существует вершина t. Тогда (U, V) является действительным st cut, поэтому минимальный st cut будет иметь значение в большинстве с

Случай 2: s находится в V. Тогда существует вершина т в U и тот же аргумент, как указано выше, имеет место при минимальных тс сократить

Этот алгоритм описан, например, in Chapter 6.4 of these MIT lecture notes.