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

Пусть G=(V,A,s,t,U) — поточная сеть. Предположим, мы получили максимальный поток. Существует ли быстрый алгоритм для поиска всех ребер, находящихся в некотором минимальном разрезе?

Я знаю, что если x является максимальным потоком, то мы можем найти в остаточной сети G(x) набор S вершин, достижимых из источника s, и T набор вершин, из которых мы можем достичь t. И, следовательно, S и его дополнение являются мин-разрезом. Более того, T и его дополнение также образуют минимальную отсечку.

Если, к сожалению, случится так, что T не является дополнением S, то минимальная отсечка не уникальна. И мне интересно, есть ли хороший способ определить, принадлежат ли ребра, концы которых не лежат ни в S, ни в T, минимальному разрезу или нет.


graph algorithm network-flow
person ihdv    schedule 08.05.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Каждая дуга u-->v принадлежит некоторому s--t мин. разрезу тогда и только тогда, когда

  1. нет остаточного пути от u до t,
  2. нет остаточного пути от s до v, и
  3. нет остаточного пути от u до v.

Чтобы доказать направление if, рассмотрим разрез, состоящий из вершин, достижимых из s или u по остаточному пути, который является s--t разрезом по (1), имеет нулевую остаточную пропускную способность и, следовательно, является s--t мин. разрезом по построению, и содержит u-->v на (2) и (3).

Чтобы доказать единственное направление if, мы можем использовать разрез s--t min, содержащий u-->v, чтобы показать, что для каждого пути от u до t, от s до v или от u до v некоторая дуга в пути не является остаточной.

Это позволит вам довольно легко достичь O(n m) времени. Возможно, этого достаточно, а если нет, то есть полезная литература по ответам на запросы о достижимости в автономном режиме.

person David Eisenstat    schedule 08.05.2020