Моделирование сети как ориентированный граф

Question

У меня есть сеть, которая может выглядеть следующим образом:

По сути, я хочу знать минимальное количество зеленых кружков, которые могут отключить источник и слить, если их удалить / отключить.(в данном случае 1)
Я уже успешно реализовал алгоритм Эдмондса-Карпа, но я не знаю, как моделировать сеть с направленными ребрами, поэтому я получаю желаемый результат.
Если я просто заменю каждыйсоединение между узлами с двумя противоположно направленными ребрами емкостью 1, я получаю максимальный поток 2 с EdmondsKarp, но мне нужно всего лишь удалить 1 зеленый кружок, чтобы разорвать сеть.
Как мне моделировать мою сеть как узлы и направляющиеобрезной?

Answer 1

Вы можете свести эту проблему к стандартной задаче s – t разреза в ориентированных графах, которую затем можно решить, например, с помощью алгоритма Эдмондса – Карпа.Для каждой вершины v создайте две вершины v_in и v_out и направленный край (v_in, v_out), а для каждого ребра {v, w} добавьте два направленных ребра (v_out, w_in) и (w_out, v_in).Тогда нетрудно понять, что максимальный поток от s_in до t_out соответствует минимальному разрезу вершин между s и t.

Answer 2

Вы правильно определили максимальный поток - для вашей сети он равен 2.

Из определения сеть потока

Поток должен удовлетворять ограничению, чтоколичество потока в узел равно количеству потока из него, кроме случаев, когда это источник, у которого больше исходящего потока, или сток, у которого больше входящего потока

Так что для вашего среднегоузел у вас есть 2 как максимальный поток (входящий и выходящий).Таким образом, знание только максимального потока не даст вам ответа для минимального среза.

Теорема

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

, поэтомуда, вы знаете количество потока, которое нужно удалить, но не знаете, каким образом его удалить.Я думаю, что это не так тривиально, и вам нужно специально искать мини-срез.