Dado el siguiente grafo no dirigido, ¿cómo encontraría el flujo máximo/corte mínimo?
Ahora, sé que para resolver esto, necesito volver a dibujar el grafo de manera dirigida como se muestra a continuación. Sin embargo, después de esto, estoy atascado. Elegí el camino de color oliva de a -> z para comenzar el algoritmo. Sin embargo, no estoy seguro de qué hacer con las aristas complementarias que van de z <- a. Recuerdo haber escuchado en algún lugar que debería aumentar la capacidad en estas aristas por la cantidad de flujo enviada a lo largo del camino a -> z. Supongo que tiene cierto sentido intuitivo porque ahora tengo más flujo que se puede enviar de vuelta, pero me gustaría estar 100% seguro.
Por cierto, para aquellos que estén interesados, estoy usando PDF Annotator 4 y una tableta Wacom Intuos para dibujar mis grafos.
