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

Question

У меня есть ненаправленный взвешенный граф, и мне нужно найти минимальный разрез, который разделяет два набора вершин. Я могу изменить свою настройку, чтобы уменьшить проблему, чтобы найти минимальный разрез, который разделяет две заданные вершины. Я хочу добавить, что веса являются положительными и дробными.

Алгоритм Stoer–Wagner делает все, кроме хранения указанных узлов по разные стороны разреза, и мне было любопытно, есть ли способ изменить SW, чтобы сделать это.

Спасибо.

Answer 1

Не уверен насчет Стоера-Вагнера, но другой типичный способ решения этой проблемы - это MaxFlow.

Вы связываете один набор узлов с источником, а другой - с пунктом назначения с неограниченной пропускной способностью. Каждое другое ребро должно иметь вес 1, затем выполните MaxFlow в результирующем графе.

Когда вы закончите, отметьте все узлы, которые все еще доступны из источника в остаточной сети (узлы, которые были посещены при последнем запуске поиска пути). Любое ребро, которое проходит между отмеченным и немаркированным узлом в исходном графике, является частью минимального разреза.