Preguntas de Entrevista sobre Flujo Máximo y Corte Mínimo

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Qué evalúa realmente una pregunta de flujo máximo

A nadie le piden implementar el algoritmo de Dinic de memoria. Las preguntas de flujo son preguntas de modelado: el entrevistador describe una situación con palabras sencillas, y todo el ejercicio consiste en darte cuenta de que es una red, dibujar la correcta y nombrar el teorema que la resuelve.

Por eso estas preguntas tienen fama de injustas. Un candidato que se ha aprendido veinte problemas de árboles puede hundirse con «asigna estos cinco ingenieros a estos cinco equipos», porque nunca da el salto de una historia sobre personas a un grafo con una fuente y un sumidero. El algoritmo es la mitad fácil y está disponible en cualquier biblioteca.

Cuatro formulaciones cubren casi todo lo que te van a plantear.

Todo lo que sigue se resuelve sobre esa red de seis nodos o sobre una pequeña variante, y cada número se calculó y se volvió a calcular con un segundo método antes de publicarlo.

2. La plantilla y los dos métodos que importan

Escribe Dinic una vez y guárdalo. Son unas treinta líneas, es lo bastante rápido para cualquier cosa que plantee una entrevista y te da el corte mínimo gratis.

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.to, self.cap, self.adj = [], [], [[] for _ in range(n)]

    def add(self, u, v, c):
        self.adj[u].append(len(self.to)); self.to.append(v); self.cap.append(c)
        self.adj[v].append(len(self.to)); self.to.append(u); self.cap.append(0)

    def bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for e in self.adj[u]:
                if self.cap[e] > 0 and self.level[self.to[e]] < 0:
                    self.level[self.to[e]] = self.level[u] + 1
                    q.append(self.to[e])
        return self.level[t] >= 0

    def dfs(self, u, t, f):
        if u == t:
            return f
        while self.it[u] < len(self.adj[u]):
            e = self.adj[u][self.it[u]]
            v = self.to[e]
            if self.cap[e] > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(f, self.cap[e]))
                if d > 0:
                    self.cap[e] -= d
                    self.cap[e ^ 1] += d
                    return d
            self.it[u] += 1
        return 0

    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            self.it = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f
        return flow

Hay dos detalles que conviene saber explicar, porque son justo lo que examina un buen entrevistador.

El primero son las aristas emparejadas. Cada arista de ida se guarda junto a su arista de vuelta, así que e ^ 1 alterna entre ambas. La arista de vuelta empieza con capacidad cero y crece a medida que se empuja flujo. Existe para que el algoritmo pueda deshacer una mala decisión: enviar flujo hacia atrás por ella cancela flujo enviado hacia delante. Sin ella, el primer camino voraz puede atraparte por debajo del óptimo, y es lo que con más frecuencia un candidato no sabe explicar.

El segundo es self.it, la optimización del arco actual. Una vez que una arista se agota en esta fase, no se vuelve a examinar, y eso es lo que lleva a Dinic de cuadrático a su cota declarada. Borrar esa única línea sigue dando respuestas correctas y destruye la complejidad.

Ejecútalo sobre la red de la figura y la respuesta es 16. Edmonds-Karp sobre la misma red también devuelve 16, que es la comprobación de cordura más barata disponible: dos algoritmos distintos, una respuesta.

3. Emparejamiento bipartito máximo

Es la pregunta que más probablemente te harán, normalmente disfrazada de planificación. «Cinco ingenieros, cinco equipos, cada ingeniero puede trabajar en algunos de ellos, maximiza el número de personas asignadas.»

La reducción es mecánica. Añade una fuente con una arista de capacidad 1 hacia cada ingeniero, un sumidero con una arista de capacidad 1 desde cada equipo y aristas de capacidad 1 para cada asignación permitida. Como las capacidades son enteras, el flujo máximo devuelve una solución entera, y un flujo entero de valor k es exactamente un emparejamiento de tamaño k: la capacidad 1 desde la fuente impide usar a alguien dos veces.

def max_matching(left, right, can):
    n = len(left) + len(right) + 2
    s, t = 0, n - 1
    g = Dinic(n)
    for i in range(len(left)):
        g.add(s, 1 + i, 1)
    for j in range(len(right)):
        g.add(1 + len(left) + j, t, 1)
    for i, l in enumerate(left):
        for r in can[l]:
            g.add(1 + i, 1 + len(left) + right.index(r), 1)
    return g.max_flow(s, t)

En la instancia de la figura la respuesta es 4, no 5. Entre Ada, Ben, Cleo y Dan solo llegan a backend, data e infra, así que tres puestos tienen que absorber a cuatro personas y una se queda sin sitio. Eso es la condición de Hall que falla, y nombrarla vale más que el código: existe un emparejamiento que coloca a todos los vértices de la izquierda si y solo si cada subconjunto del lado izquierdo tiene al menos tantos vecinos como miembros. El testigo más ajustado aquí es aún menor: entre Ada, Cleo y Dan solo llegan a backend y data, tres personas para dos puestos. La condición de Hall trata de saturar un lado, y solo coincide con un emparejamiento perfecto cuando ambos lados tienen el mismo tamaño, como ocurre aquí.

Si el entrevistador busca la respuesta más rápida posible en lugar de la más reutilizable, Hopcroft-Karp se ejecuta en O(E√V) aumentando por muchos caminos más cortos a la vez. Di que existe y luego usa Dinic, que en grafos de capacidad unitaria alcanza la misma cota de todos modos.

4. La cobertura escondida en el emparejamiento

Un buen seguimiento, y uno que pilla a la mayoría de los candidatos: «ahora dime el conjunto más pequeño de personas y equipos que toca todas las asignaciones posibles».

Eso es una cobertura mínima de vértices, que es NP-difícil en grafos generales. En un grafo bipartito no lo es, y el teorema de König dice que tiene exactamente el tamaño del emparejamiento máximo. No necesitas un segundo algoritmo; lees la cobertura en el corte que ya tienes. Haz una búsqueda desde la fuente en el grafo residual y toma los vértices izquierdos que no alcanza más los vértices derechos que sí alcanza.

En esta instancia eso da Ben, Eve, backend y data, cuatro vértices, y una comprobación a mano confirma que se tocan las nueve aristas. El complemento de una cobertura de vértices es un conjunto independiente, así que el conjunto independiente más grande es 10 − 4 = 6. Tres preguntas distintas, una llamada de flujo máximo.

5. El corte mínimo: las aristas, no solo el número

«¿Cuál es el conjunto de enlaces más barato de cortar para que ningún tráfico llegue al centro de datos?» El valor es el flujo máximo, por el teorema. Pero los entrevistadores preguntan qué enlaces, y ese es un paso distinto y más fácil que muchos candidatos nunca aprendieron.

Cuando el flujo es máximo, haz una búsqueda desde la fuente por aristas que aún tengan capacidad residual. Sea R el conjunto que alcanza. El corte mínimo es toda arista original que va de R a su complemento.

def min_cut(self, s):
    seen = [False] * self.n
    seen[s] = True
    q = deque([s])
    while q:
        u = q.popleft()
        for e in self.adj[u]:
            if self.cap[e] > 0 and not seen[self.to[e]]:
                seen[self.to[e]] = True
                q.append(self.to[e])
    return [(self.to[e ^ 1], self.to[e])
            for e in range(0, len(self.to), 2)
            if seen[self.to[e ^ 1]] and not seen[self.to[e]]]

En la red de ejemplo, el conjunto alcanzable es {S, A, B} y el corte es A→C con 7 más B→D con 9, que suman 16, el valor del flujo. La fuerza bruta sobre los dieciséis posibles subconjuntos del lado de la fuente confirma que no existe un corte más barato.

Aquí hay dos trampas. Cuenta solo las aristas que van desde el conjunto alcanzable hacia el inalcanzable; las aristas que vuelven no están en el corte. Y el corte mínimo a menudo no es único, así que si te piden «el» corte, di que devuelves uno de posiblemente varios y que todos tienen el mismo valor.

6. Caminos disjuntos y el teorema de Menger

«¿Cuántas rutas independientes hay de la oficina al centro de datos?» es una pregunta de flujo con todas las capacidades a 1.

Pon cada capacidad a 1 y el flujo máximo cuenta caminos disjuntos en aristas, porque una unidad de flujo no puede compartir una arista con otra. El teorema de Menger dice entonces que ese número es igual al mínimo de aristas cuya eliminación desconecta los dos vértices. Max-flow min-cut es la generalización ponderada exactamente de esa afirmación.

En la red de ejemplo con capacidades unitarias la respuesta es 2, y un corte mínimo son las dos aristas que salen de la fuente, aunque seis pares distintos de aristas lo consiguen. Conviene señalarlo en lugar de ocultarlo: con capacidades unitarias la respuesta a menudo es solo una cota de grado, y decirlo demuestra que entiendes qué significa el número y no solo cómo calcularlo.

Si la pregunta dice disjuntos en vértices en su lugar, las capacidades en las aristas no pueden expresarlo y necesitas el primer truco de modelado de abajo. Aquí eso también da 2, y quitar C y D deja de verdad T inalcanzable. Hay una hipótesis que conviene decir en voz alta: la forma por vértices del teorema de Menger exige que los dos extremos no sean adyacentes, y aquí no lo son porque no hay arista directa de S a T.

7. Tres trucos de modelado que convierten una historia en una red

Casi toda pregunta de flujo en una entrevista es una de estas transformaciones envolviendo el mismo solucionador.

Un vértice tiene capacidad. «Este router soporta 3 unidades.» Las capacidades están en las aristas, así que divide el vértice: sustituye v por v_ent y v_sal unidos por una arista de capacidad 3, envía todo arco que llegaba a v hacia v_ent, y haz que todo arco que salía de v empiece en v_sal. Poner la capacidad interna a 1 es la forma de contar caminos disjuntos en vértices.

Muchas fuentes, muchos sumideros. «Tres almacenes abastecen a dos tiendas.» Añade una superfuente con aristas de capacidad infinita hacia cada fuente real y un supersumidero alimentado por cada sumidero real. Una llamada al solucionador sustituye la enumeración que un candidato podría empezar a escribir.

La arista no es dirigida. Añade ambas direcciones con la capacidad completa. Parece que permitiría el doble de tráfico y no es así, porque la contabilidad residual cancela el flujo enviado en direcciones opuestas. Ten preparada esta respuesta, porque es una objeción natural y la respuesta es corta.

El cuarto caso es el que pilla a la gente: una cota inferior. «Cada conductor debe hacer al menos dos turnos» no es una capacidad, y el solucionador estándar no puede expresarla. Necesita una construcción de circulación factible, y el movimiento útil en la entrevista es señalar la palabra «debe» en voz alta en lugar de programar todo eso.

8. Selección de proyectos, o por qué un corte puede elegir un subconjunto

Parece que debería ser programación dinámica y no lo es, y eso la convierte en una favorita.

«Cada proyecto da un beneficio conocido. Cada proyecto necesita ciertas máquinas. Cada máquina cuesta una cantidad fija y la comparte todo lo que la necesite. Elige el subconjunto más rentable.»

La trampa es la voracidad: tomar todo proyecto con beneficio positivo u ordenar por beneficio por máquina. Ninguna de las dos es correcta, porque las máquinas se comparten, así que el coste real de un proyecto depende de qué otros proyectos tomes.

La construcción es breve. Fuente hacia cada proyecto con capacidad igual a su beneficio; cada máquina hacia el sumidero con capacidad igual a su coste; proyecto hacia máquina con capacidad infinita para que esa arista no pueda cortarse nunca. Entonces la respuesta es

beneficio máximo = (suma de todos los beneficios) − (corte mínimo)

y los proyectos a tomar son los del lado de la fuente del corte. Las aristas infinitas son las que imponen la coherencia: si mantienes un proyecto en el lado de la fuente, sus máquinas también deben estar ahí, o el corte sería infinito. Esa es la definición de un conjunto cerrado, y este es el problema de la clausura máxima.

En la instancia de la figura los beneficios suman 235, el corte mínimo es 195 y lo mejor que se puede lograr es 40, tomando alpha, beta y gamma y descartando delta. Delta aporta 30, pero es el único proyecto que necesita fab, que cuesta 50, así que añadirlo a los otros tres cuesta 20 más de lo que aporta. La fuerza bruta sobre los dieciséis subconjuntos coincide.

9. Eliminación en béisbol

Un clásico, e inusual porque la respuesta ingenua no es solo lenta, es incorrecta.

Dada la clasificación y los partidos restantes, ¿puede un equipo todavía terminar primero? La comprobación obvia es si su mejor total posible sigue superando el total actual de cada rival. Eso detecta los casos fáciles y se pierde los interesantes, porque los rivales tienen que jugar entre sí y alguien tiene que ganar esos partidos.

Aquí hay una tabla en la que la comprobación ingenua no ve nada raro:

Los Ducks pueden llegar a 79, y ningún rival tiene todavía 79 victorias, así que ninguna comparación individual los elimina. Pero entre los partidos restantes, los Aces juegan dos veces contra los Bolts, los Aces una contra los Comets y los Bolts tres contra los Comets. Seis partidos entre los tres rivales, y cada uno le da a alguien una victoria.

Construye una red: una fuente hacia un nodo por cada pareja pendiente, con el número de partidos que aún juegan; cada nodo de pareja hacia sus dos equipos con capacidad infinita; cada equipo hacia el sumidero con capacidad igual a cuántas victorias más puede permitirse antes de superar el mejor caso de los Ducks, 79. Los Ducks sobreviven solo si los seis partidos pueden absorberse, es decir, solo si el flujo máximo satura la fuente.

No lo hace. El flujo es 5 frente a 6 partidos, así que un partido no tiene adónde ir, y los Ducks quedan eliminados. Enumerar los 2⁹ resultados posibles de todos los partidos restantes de la liga lo confirma: no hay ningún escenario en el que los Ducks terminen primeros, y hay uno para cada uno de los otros tres.

El déficit también te dice por qué: las aristas de equipo saturadas nombran al grupo de rivales que entre ellos deben ganar más partidos de los que pueden permitirse. Los entrevistadores que conocen este problema siempre piden esa explicación.

10. Cobertura mínima por caminos en un DAG

«¿Cuál es el menor número de trabajadores necesario para realizar todas estas tareas, si un trabajador solo puede pasar entre tareas que se siguen una a otra?»

Eso es una cobertura mínima por caminos: el menor número de caminos disjuntos en vértices que cubren todos los vértices de un grafo dirigido acíclico. Se reduce a emparejamiento con un truco que vale la pena recordar. Divide cada vértice en una copia de salida a la izquierda y una copia de entrada a la derecha, pon una arista en el grafo bipartito por cada arista del DAG y encuentra un emparejamiento máximo. Entonces

cobertura mínima por caminos = número de vértices − emparejamiento máximo

, porque cada arista emparejada une dos fragmentos de camino y así elimina un camino del recuento. En un DAG de seis vértices con siete aristas el emparejamiento máximo es 4, así que la cobertura mínima por caminos es 6 − 4 = 2, y la búsqueda exhaustiva sobre todos los subconjuntos de aristas coincide.

Una matización importa y a menudo se omite: esto cuenta caminos disjuntos en vértices. Si los caminos pueden compartir vértices, calcula primero la clausura transitiva del DAG y luego aplica la misma reducción.

11. Cuando es flujo de coste mínimo, no flujo máximo

El seguimiento más habitual de todo el tema: «ahora cada asignación tiene un coste, y quiero la forma más barata de colocar a todo el mundo».

El flujo máximo no puede responder a eso. Maximiza la cantidad y le da igual entre dos soluciones del mismo tamaño, así que devolverá sin problema el emparejamiento perfecto más caro. Lo que necesitas es el flujo máximo de coste mínimo: entre todos los flujos de valor máximo, encontrar el de menor coste total.

El cambio en el modelo es pequeño. Cada arista gana un coste por unidad junto a su capacidad, y el algoritmo aumenta repetidamente por el camino más barato del grafo residual en lugar del más corto o de uno cualquiera. Como las aristas residuales tienen coste negativo, Dijkstra sin más no se aplica directamente, así que las implementaciones estándar usan Bellman-Ford, lo que da el algoritmo de caminos más cortos sucesivos, o mantienen potenciales al estilo de Johnson para que Dijkstra siga siendo utilizable.

Hay tres cosas que conviene saber decir al respecto.

El caso especial tiene nombre. Un grafo bipartito completo con un coste en cada emparejamiento y el requisito de que todos queden emparejados es el problema de asignación, y el algoritmo húngaro lo resuelve en O(n³). Si el problema del entrevistador es exactamente «n trabajadores, n tareas, minimiza el coste total», nombrar el algoritmo húngaro es la respuesta esperada.

La integralidad se mantiene. Con capacidades enteras, el flujo máximo de coste mínimo puede seguir tomándose entero, y eso es lo que mantiene válida la interpretación como emparejamiento una vez añadidos los costes.

La trampa es maximizar otra cosa. «Maximizar el valor total» y «maximizar el número de asignaciones» no son el mismo objetivo, y una solución puede ser óptima para uno y mala para el otro. Pregunta cuál se busca antes de escribir nada, porque el entrevistador suele ser ambiguo a propósito para ver si te das cuenta.

Un límite útil que enunciar: si no hay costes, usa flujo máximo; si hay costes pero toda unidad debe moverse, es flujo de coste mínimo; si los costes están en los vértices y no en los emparejamientos, probablemente vuelves al terreno de la clausura de la sección 8.

12. Las respuestas de complejidad

Tenlas preparadas, y prepárate para decir cuál usarías de verdad.

Conviene enunciar la advertencia con precisión, porque es un seguimiento habitual. Ford-Fulkerson es el único cuyo tiempo de ejecución depende de los valores de capacidad y no del tamaño del grafo. Cada camino de aumento suma al menos 1 al flujo, así que el bucle se ejecuta como mucho maxflow veces, y si las capacidades son de mil millones, esa cota son mil millones de iteraciones en un grafo de cuatro vértices. Como una capacidad de mil millones son diez dígitos de entrada, el tiempo de ejecución es exponencial en el tamaño de la entrada. Edmonds-Karp lo arregla eligiendo siempre un camino de aumento más corto, lo que elimina por completo la dependencia de las capacidades.

Dos hechos más suman puntos. Integralidad: si todas las capacidades son enteras, existe un flujo máximo entero, que es lo que justifica las reducciones a emparejamiento y a caminos disjuntos. Y el coste de la reducción: cuando construyes una red a partir de una historia, da la complejidad en términos de la red que construiste, no de la entrada original. Un emparejamiento bipartito con n personas y m puestos construye un grafo con n + m + 2 vértices, y decirlo es lo que demuestra que entiendes la transformación.

13. Errores que suspenden la entrevista

Olvidar las aristas de vuelta. El error fatal más común, y no provoca un fallo, simplemente devuelve un número demasiado pequeño. Si no sabes explicar por qué un algoritmo necesita poder cancelar sus propias decisiones anteriores, no has entendido el algoritmo.

Reutilizar el objeto solucionador. Llamar a max_flow por segunda vez sobre la misma instancia devuelve 0, porque el grafo residual ya está saturado. Esto le pasa a quien calcula un flujo, quiere de nuevo el valor para imprimirlo y concluye que su código está roto. Crea un objeto nuevo o guarda el resultado.

Dar el valor cuando te piden el conjunto. «¿Qué enlaces cortarías?» no se responde con «16». Recupera el conjunto alcanzable y enumera las aristas.

Leer una cota inferior como una capacidad. «Como mucho tres turnos» es una capacidad. «Al menos dos turnos» no lo es, y necesita otra construcción. Presta atención a «debe» y «al menos».

Modelar límites de vértice como límites de arista. Si la restricción está en una máquina y no en un enlace, divide el vértice. Los candidatos que se lo saltan obtienen una respuesta demasiado grande sin darse cuenta.

Citar Ford-Fulkerson como la complejidad. Es la única cota que puede ser exponencial en el tamaño de la entrada. Nombra Dinic y explica la diferencia.

Recurrir al flujo cuando el problema no es de flujo. El flujo máximo es la herramienta equivocada para caminos más cortos, para árboles de expansión y para todo aquello cuya respuesta es una única ruta y no una cantidad compartida. Si no se reparte ni se comparte nada, mira primero BFS, Dijkstra o union-find. Un candidato que agarra el martillo más pesado de la caja le está diciendo algo al entrevistador.

Modelar en silencio. La reducción es la respuesta. Dibuja la red en la pizarra, di «fuente hacia cada ingeniero con capacidad uno, porque nadie puede tener dos trabajos», y deja que el entrevistador corrija el modelo antes de haber escrito treinta líneas contra el equivocado.

15. Referencias

Los resultados detrás de estas preguntas, en orden cronológico.

1. Menger, K. (1927). “Zur allgemeinen Kurventheorie.” Fundamenta Mathematicae, 10, 96–115.
2. König, D. (1931). “Gráfok és mátrixok.” Matematikai és Fizikai Lapok, 38, 116–119.
3. Hall, P. (1935). “On representatives of subsets.” Journal of the London Mathematical Society, 10(1), 26–30.
4. Ford, L. R. y Fulkerson, D. R. (1956). “Maximal flow through a network.” Canadian Journal of Mathematics, 8, 399–404.
5. Ford, L. R. y Fulkerson, D. R. (1962). Flows in Networks. Princeton University Press.
6. Schwartz, B. L. (1966). “Possible winners in partially completed tournaments.” SIAM Review, 8(3), 302–308.
7. Dinic, E. A. (1970). “Algorithm for solution of a problem of maximum flow in networks with power estimation.” Soviet Mathematics Doklady, 11, 1277–1280.
8. Edmonds, J. y Karp, R. M. (1972). “Theoretical improvements in algorithmic efficiency for network flow problems.” Journal of the ACM, 19(2), 248–264.
9. Hopcroft, J. E. y Karp, R. M. (1973). “An n^5/2 algorithm for maximum matchings in bipartite graphs.” SIAM Journal on Computing, 2(4), 225–231.
10. Picard, J.-C. (1976). “Maximal closure of a graph and applications to combinatorial problems.” Management Science, 22(11), 1268–1272.
11. Goldberg, A. V. y Tarjan, R. E. (1988). “A new approach to the maximum-flow problem.” Journal of the ACM, 35(4), 921–940.
12. Ahuja, R. K., Magnanti, T. L. y Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.
13. Wayne, K. D. (2001). “A new property and a faster algorithm for baseball elimination.” SIAM Journal on Discrete Mathematics, 14(2), 223–229.
14. Kleinberg, J. y Tardos, É. (2005). Algorithm Design, capítulo 7. Addison-Wesley.
15. Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2009). Introduction to Algorithms, 3.ª edición, capítulo 26. MIT Press.