Flujo máximo en gráfico no dirigido con bordes restringidos

Una forma de resolver esto es modificando el gráfico: cada ruta forzada se puede reemplazar por un solo borde que tenga la capacidad mínima de todos los bordes en la ruta forzada original (que siempre es 1 en este caso). Entonces, cualquier gráfico con caminos forzados se reduce a un gráfico sin caminos forzados.

Puede transformar el gráfico tomando cada par de puntos finales de una ruta forzada.

Para cada camino forzado, todos los vértices, excepto los que están en el camino forzado, adyacentes a un punto final tendrán un borde entrante desde ese punto final y un borde saliente hacia el otro punto final, y ningún borde saliente hacia el punto final al que están conectados en el original. grafico. Los dos extremos estarán conectados por un borde no dirigido con la capacidad mínima de un borde a lo largo de la ruta forzada y el resto de la ruta forzada se eliminará.

A estas alturas, podría estar claro que si ejecuta Ford-Fulkerson en el gráfico transformado, encontrará el flujo máximo que obedece a las restricciones que estableció. Si no, puedes pedirme que te aclare.

Respondo a tu comentario en otra respuesta porque todo esto no cabe en un comentario, pero es solo una aclaración.

Para empezar, me quedé con la impresión de que estás preguntando sobre un gráfico no dirigido donde las rutas forzadas son bidireccionales.

Aun así, cuando se dirige el gráfico, por supuesto, asumiendo que todas las rutas forzadas no se superponen y todos los bordes a lo largo de una ruta forzada apuntan en la misma dirección, mi solución propuesta puede modificarse ligeramente para que funcione. La modificación es que todos los bordes entrantes a un punto final de una ruta forzada se redirigirán hacia el otro punto final de la ruta solo si la ruta está en esa dirección.

También una nota cuando un flujo tiene que comenzar desde un vértice u que es un punto final de una ruta comenzará desde el otro punto final de la ruta v si la ruta forzada apunta de u a v.

En primer lugar, sobre el ejemplo que proporcionó donde 4->6 y 3->5 son las rutas forzadas dirigidas, hay 2 unidades de flujo que pueden ir de 4 a 5. Una unidad de flujo va a lo largo de la ruta 4->3 ->5 y el otro por el camino 4->6–>5. Entonces, bajo mi transformación propuesta, el gráfico resultante tendrá los siguientes bordes dirigidos: 6->5, 6->5 Y cuando ejecute MF(4,5), el flujo comenzará desde 6 porque 4->6 es un camino forzado y encontrará 2 unidades de flujo de 6 a 5 a lo largo de los 2 bordes entre ellos.

Para dar otro ejemplo para que quede más claro, usemos el gráfico en su pregunta donde las rutas forzadas son bidireccionales y el gráfico no está dirigido. Bajo la transformación, el resultado será un gráfico con las siguientes aristas dirigidas: 4->3, 6->3, 4->5, 6->5, 3->6, 3->4, 5->6, 5->4, 4->6, 6->4

Incluso ese ejemplo podría no ser claro, ya que es un caso especial en el que todos los vértices que están conectados a uno de los puntos finales de la ruta forzada están conectados a ambos puntos finales de la ruta. Pero la idea es que los bordes que apuntan a un punto final de un camino forzado que te obligarán a seguirlo serán redirigidos como atajos al otro punto final del camino. Y se conservarán los bordes que se alejen de un punto final. Entonces, si los puntos finales de la ruta son u y v y la ruta forzada es u<->v, no puede ir a u y luego a uno de sus vecinos a menos que haya seguido la ruta forzada y lo mismo para v. Entonces, en el gráfico transformado no hay bordes que apunten a u excepto los que solían apuntar a v, y no hay bordes que apunten a v excepto los que solían apuntar a u.