red de modelado como grafo dirigido

Question

Tengo una red que podría tener este aspecto:

Básicamente, quiero saber el número mínimo de círculos verdes que puede desconectar la fuente y el drenaje si es eliminado/desactivado. (en este caso 1)
Ya he implementado con éxito el algroritmo Edmonds-Karp, pero no sé cómo modelar la red con los bordes dirigidos, por lo que obtengo el resultado deseado.
Si simplemente reemplazo cada conexión entre los nodos con dos bordes dirigidos opuestos con capacidad 1, obtengo un flujo máximo de 2 con EdmondsKarp, pero solo necesito eliminar 1 círculo verde para romper la red.
¿Cómo puedo modelar mi red como nodos y dirigir mi borde?

Answer 1

Puede reducir este problema al problema de corte s-t estándar en los gráficos dirigidos, que luego puede resolverse, p. por el algoritmo Edmonds-Karp. Para cada vértice v, cree dos vértices v_in y v_out y un borde dirigido (v_in, v_out), y para cada borde {v, w}, agregue dos bordes dirigidos (v_out, w_in) y (w_out, v_in). Entonces no es difícil ver que un flujo máximo de s_in a t_out corresponde a un corte de vértice mínimo entre s y t.

Answer 2

Ha determinado correctamente el flujo máximo: es 2 para su red.

De definición de flow network

Un flujo debe satisfacer la restricción que la cantidad de flujo en un nodo es igual a la cantidad de flujo de fuera de él, excepto cuando se trata de una fuente, que tiene un mayor flujo de salida, o en el fregadero, que tiene un mayor flujo entrante

Así que para su nodo intermedio que tienen 2 como máximo flujo (que entra y que sale). Entonces, saber solo el flujo máximo no le dará la respuesta para un corte mínimo.

El teorema

max-flujo min-cortó teorema que en una red de flujo, la cantidad máxima de flujo que pasa desde la fuente hasta el disipador de es igual a la capacidad mínima que cuando eliminado de una manera específica de la red hace que la situación que no hay flujo puede pasar de la fuente al fregadero

así, sí, usted sabe la cantidad de flujo que necesita eliminar, pero no sabe de qué manera eliminarlo. Creo que esto no es tan trivial y que tendrá que buscar específicamente min-cut.