Моделирование сети в ориентированном графе

Question

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

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

Answer 1

Вы можете уменьшить эту проблему до стандартной проблемы s-t cut в ориентированных графах, которые затем могут быть решены, например. по алгоритму Эдмондса-Карпа. Для каждой вершины 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 для вашей сети.

Из определения flow network

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

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

теорема

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

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