graph-theory - siguiente - flujo minimo
¿Cómo puedo encontrar el corte mínimo en un gráfico usando un algoritmo de flujo máximo? (7)
Necesito encontrar el corte mínimo en un gráfico. He estado leyendo acerca de las redes de flujo, pero todo lo que puedo encontrar son algoritmos de flujo máximo como Ford-Fulkerson, push-relabel, etc. Dado el teorema máximo de corte de flujo mínimo, ¿es posible usar uno de esos algoritmos para encontrar el corte mínimo en un gráfico usando un algoritmo de flujo máximo? ¿Cómo?
La mejor información que he encontrado hasta ahora es que si encuentro bordes "saturados", es decir, bordes donde el flujo es igual a la capacidad, esos bordes corresponden al corte mínimo. ¿Es eso cierto? No suena 100% correcto para mí. Es cierto que todos los bordes en el corte mínimo estarán saturados, pero creo que también podría haber bordes saturados que están fuera del "camino" de corte mínimo.
Creo que esto es lo que dicen otras personas, pero me pareció incierto, así que aquí está mi explicación:
Desde el nodo de origen, realice un relleno de inundación del gráfico, recorriendo solo los bordes con capacidad residual, marcando cada vértice visitado. Puede usar un DFS para esto. Recuerde que los bordes posteriores de un vértice tienen una capacidad residual, igual al flujo a lo largo del borde anterior (es decir, r (u, v) = capacidad restante para el borde (u, v), r (v, u) = flujo (u , v)).
En efecto, esto determina la parte S del corte ST del gráfico.
El corte mínimo ahora será el conjunto de bordes tal que un vértice se marca desde su relleno de inundación arriba, y el otro vértice no está marcado. Estos serán bordes sin capacidad residual (de lo contrario los habría atravesado en su DFS), y juntos forman el corte mínimo.
Después de eliminar estos bordes, el conjunto de vértices sin marcar formará la sección T del corte.
Desde el vértice de origen, realice una búsqueda en profundidad a lo largo de los bordes de la red residual (es decir, bordes no saturados y bordes posteriores de bordes que tienen flujo) y marque todos los vértices que se puedan alcanzar de esta forma. El corte consiste en todos los bordes que van desde un vértice marcado a uno sin marcar. Claramente, esos bordes están saturados y por lo tanto no fueron atravesados. Como notó, puede haber otros bordes saturados que no forman parte del corte mínimo.
Entonces, para dar el procedimiento exacto de cómo obtener el corte mínimo:
- Ejecute el algoritmo Ford-Fulkerson para encontrar el flujo máximo y obtener el gráfico residual 1 .
- Ejecute BFS en el gráfico residual para encontrar el conjunto de vértices que son accesibles desde el origen en el gráfico residual (respetando que no puede usar bordes con capacidad 0 en el gráfico residual) IMPORTANTE: Debe usar bordes revertidos en el residuo gráfico para encontrar el conjunto correcto de vértices accesibles !!! (Ver este algoritmo)
- Todos los bordes en el gráfico original que son desde un vértice alcanzable hasta un vértice no alcanzable son bordes de corte mínimo. Imprime todos los bordes.
1 Gráfico en el que la capacidad de un borde se define como su capacidad original menos su flujo (flujo desde la red de flujo máximo).
No quiero ser exigente, pero la solución sugerida no es del todo correcta, como se propuso.
Solución correcta : lo que en realidad debería hacer es bfs / dfs en Residual-Network Gf (léalo en wikipedia ) y marque los vértices. Y luego puedes elegir aquellos con marcado de-vértice y sin marcar a-vértice.
Por qué ''seguir bordes no saturados'' no es suficiente : considere que el algoritmo de flujo satura los bordes como se muestra en la imagen. Marqué los vértices que estoy visitando con el enfoque de "seguir los bordes insaturados" con verde. Claramente, el único corte mínimo correcto es el borde de EF, mientras que la solución sugerida también devolvería AD (y tal vez incluso DE).
Tenga en cuenta que el vértice D sería visitado por el dfs / bfs si consideramos la red Residual en su lugar, porque habría un borde de E a D, por lo que el borde EF sería el único con un vértice marcado y un marcado a-vértice.
Nota: El algorythm de Falk se puede usar para encontrar tanto un corte mínimo con vértices mínimos como con vértices máximos. Para este último, el algoritmo debe invertirse, es decir. buscar desde el vértice del sumidero en lugar de la fuente. Consulte una pregunta relacionada: Flujo de red: agregar una nueva ventaja
Una forma de entender es, definamos un corte como dos conjuntos S y T, que incluirán s y t, respectivamente.
Ahora, agregue todos los vértices en S accesibles desde s en la red residual y coloque los bordes restantes en T. Esto será un corte.
En segundo lugar, el corte se puede formar poniendo todos los vértices en T que son accesibles desde t en la red residual y poner los vértices restantes en S.
Echa un vistazo a este video para descubrir cómo encontramos los vértices accesibles desde s y t.
https://www.youtube.com/watch?v=FIJaXfUIXJA&index=4&list=PLe-ggMe31CTduQ68XQ-sVj32wYJIspTma
Después de que se calcula el flujo máximo, podemos buscar los bordes (u,v) modo que en el gráfico residual, haya un borde en el gráfico residual de v a u f(v,u) = c(u,v) [ lo que significa que el borde está saturado]
Después de hacer una lista corta de esos bordes, podemos seleccionar dichos bordes (u,v) utilizando el criterio de que no existe una ruta desde u hasta hundir t en el gráfico residual. Si se cumple esta condición, dichos bordes forman una parte del corte (S,T)
El tiempo de ejecución de este algoritmo puede ser O(E) * O( V + E ) = O( E^2 )