Учитывая поточную сеть и Edge e, описать алгоритм, определяющий, пересекает ли e минимальный разрез

Question

Учитывая сеть потока G = (V, E) с источником s, приемник t и ребро e = (u, v), описывают алгоритм, определяющий, пересекает ли ребро e минимальный разрез (S, T).

Моя первая идея состояла в том, чтобы вычислить максимальный поток f и затем уменьшить емкость e на некоторое a> 0. Затем мы проверяем, имеет ли остаточный график путь от s до t (это означает, что мы можем увеличить поток f еще больше).

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

Проблема в другом направлении. Если есть путь от s до t, это может быть потому, что мы создали новый минимальный разрез, который пересекает e, не будучи осторожным при выборе a> 0.

Итак, как я могу выбрать достаточно маленький a> 0?

Answer 1

Его классный вопрос.

« Моя первая мысль была для расчета максимального потока F, а затем уменьшение емкость е некоторые и ... »

вы имели в виду увеличить? потому что поток не может расти, если вы уменьшаете мощность ..

Любого путь:

Run алго найти максимальный поток и поток допускает это F.

Проверить, если поток, протекающий по е равно его способности , если нет, то мы возвращаем false.

Означает ли это, что если оно равно, e должно пересечь какой-то минимум?

Пусть е = (и, v): Из-за правило ребер, поток входит и должен уйти полностью,

это означает, что для каждого разреза вы будете принимать, будет иметь некоторые е crooses it and e = (х, y),

У нас будет некоторый путь от u-> v ....-> x или y -> .... u-> v.

Если мы удалим это ребро (e), и поток будет уменьшен, это означает, что мы не можем, в любом случае, вернуть поток, который пришел к x (или поток, который оставил y can not найти способ раковина сейчас) как прежде. это означает, что e был в небольшом разрезе.

Если поток не меняется, это означает только то, что мы нашли другой способ вернуть поток, который мы «потеряли», так что это означает, что e не принадлежит к минимальному разрезу, потому что он не влияет на любую минимальную мощность, равную максимальный поток.

Ваша интуиция к проблеме хорошая, но посмотрите, что она не работает, потому что увеличение/уменьшение e не может привести к чему-либо другому, потому что есть простой пример, когда вы меняете емкость e, и до сих пор нет пути от s до t в остаточной сети, но e все еще принадлежит некоторому минимуму.