Удаление минимального числа ребер, чтобы разъединить две вершины графа

Question

Здесь я пытаюсь разъединить две вершины графа с минимальным удалением ребер.

В этом графе между двумя вершинами A и Z вы можете найти ответ разными способами. Оптимальным образом вы можете удалить только один край от A до B.

Есть ли какой-то конкретный алгоритм для этого?

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

Answer 1

Это может быть решено с помощью задачи Max Flow - Min Cut.

Вы можете смоделировать свой график в сетевой поток следующим образом:
1. Рассмотрим A быть исходной вершиной, Z быть вершиной раковины.
2. Установите емкость каждого ребра равной 1 единице.

Теперь решите проблему Max Flow - Min Cut в вышеуказанной сети. С его помощью вы сможете найти количество непересекающихся путей от A в Z, Для каждого такого пути удалите первое ребро (ребро, происходящее из источника A).

Доказательство:
Обратите внимание, что после удаления выше краев, вы не сможете достичь A в Z, Если бы у вас был путь, то алгоритм Max flow включил бы этот путь в набор edge-disjoint-paths.
Кроме того, по построению сети, вы не можете удалить меньшее количество ребер, чтобы отключить A от Z