Учитывая сетевой расход, найдите, если есть минимальное сокращение, что только один из данных ребер лежит на нем

Question

Учитывая сетевой расход $ G= (V, E) $ с функцией емкости $ C $ Источник $ s $ и отверстие $ t $ , И дано 2 ребра $ e_1, e_2 $ .

Найти, если существует минимальное разрезанное, что только один из краев принадлежит мин.

Надеюсь получить помощь.

Answer 1

Первое, вычислить минимальное значение CUT $ C $ сети.

Во-вторых, удалить край $ E_1 $ и увеличить емкость $ E_2 $ до бесконечности, затемВычислить минимальное значение CUT $ C_1 $ новой сети.

В-третьих, удалить край $ E_2 $ и увеличить емкость $ E_1 $ до бесконечности, затемВычислить минимальное значение RUT $ C_2 $ новой сети.

Теперь вы можете проверить, $ C-C_1 \ Ge C (E_1) $ или $ C-C_2 \ GEC (E_2) $ , чтобы увидеть, существует ли минимальная среза в исходной сети, которая содержит ровно один из $ e_1, e_2 $ .