Минимальный разрез для графика после увеличения кромки на 1 для всех краев?

Question

Пусть G = (V, E) - произвольная сеть потоков с источником s и мишенью t и положительной целочисленной емкостью c (e) для каждого ребра e. Пусть (S, T) - минимум s-t, разрезанный по этим емкостям. Предположим теперь, что мы увеличиваем емкость каждого ребра на единицу, т. Е. C_new (e) = c (e) + 1 для всех ребер, то есть (S, T) еще минимум s-t, разрезанный по этим новым возможностям {c_new}?

Моя интуиция есть, если G содержит края различной емкости, увеличенная емкость, возможно, привела к разной минимальной разрезе. Но когда все ребра обладают одинаковой мощностью, минимальный разрез останется таким же.

Правильно ли я? Как это доказать?

Answer 1

Если ВСЕ краевые свойства увеличены на постоянную, то минимальный разрез будет таким же. При условии, что размеры кромок на графике одинаковы. В противном случае это может измениться.

Простое объяснение будет -

Вычислит мин вырезано/макс-поток по Динич алгоритма, с использованием BFS. Мы применяем bfs из источника для раковины и подставляем край наименьшей емкости/емкости бутылки в путь bfs. Мы добавим этот край-wt. течь. Мы продолжаем это, пока нет пути от источника до потолка.

Если вы должны были нарезать кромки с помощью постоянной, разрез всегда оставался бы таким же. Поскольку пути BFS во всех итерациях этого алгоритма были бы одинаковыми. Изменяется только значение максимального потока.

Answer 2

Да, ваша интуиция верна.

Когда G содержит края различной емкости, увеличивая емкость каждого ребра на 1 может изменить минимальный разрез. Это легко продемонстрировать на примере, как показано ниже. Минимальный разрез (в красном) имеет емкость 3. Увеличение пропускной способности каждого ребра возрастает, что вырезанные до 6. Таким образом, соединение от S до А становится новым минимальный разрез с мощностью 5.

Когда все края имеют одинаковую емкость, увеличение емкости каждого края на 1 не будет изменить минимальный разрез. Основная идея доказательства заключается в том, что емкость разреза равна nc, где n - это количество режущих кромок, а c - емкость каждого ребра. Поскольку c является константой, минимальным разрезом является разрез с минимумом n. Мы будем ссылаться на этот минимум как N.

Теперь, если емкость каждого ребра увеличена на 1, тогда новая мощность каждого разреза равна n(c+1). Следовательно, новая мощность разреза, которая раньше была минимальным, равна N(c+1). Предположим, что разрез с грузоподъемностью более N(c+1) существует: поскольку все ребра имеют вес c+1, такой разрез должен быть M -резанный разрез, для некоторых M > N. Но тогда на исходном графике этот же разрез имел бы емкость Mc > Nc, что противоречило предположению, что разрез N - оптимальный вариант там, поэтому такой разрез M не может существовать, что означает, что разрез N (теперь с емкостью N(c+1)) остается оптимальным на новом графике.