Таким образом, чтобы использовать алгоритм минимального разреза s-t, вам нужно преобразовать свой график в потоковую сеть. Это дает неявный ориентированный граф (направление прямого потока ребра). Вы можете использовать это направленное представление, чтобы преобразовать граф во что-то, что должно решить эту проблему. По существу, вы превращаете каждую вершину V (исключая источник и приемник) в две вершины, называя их A и B. A получает все внутренние ребра V, B получает все внешние ребра V. Затем вы создаете ребро A -> B с максимальной емкостью бесконечности.
Я думаю, что если вы запустите обычный алгоритм минимальной резки s-t, он выберет только те ребра, которые вы создадите. Единственная модификация, которую я считаю необходимой, это в случаях, когда степень A равна единице, она может выбрать этот край для резки, но тогда просто выбрать A в качестве вершины. (Это зависит от реализации алгоритма s-t)
Надеюсь, это имеет смысл. Я не уверен, сработает ли это (то есть я не думаю, что нужно придумывать правильное доказательство), но в этом есть интуитивный смысл. Интуитивная идея, которая у меня есть, заключается в том, что если вы обрежете «не вершинное» ребро, вы также можете обрезать «вершинное» ребро, поскольку оно имеет тот же эффект, что и отключение графа.