Calculadora de Corte Mínimo

Pseudocódigo

El corte mínimo no se calcula directamente. Se calcula un flujo máximo y luego se lee el corte del grafo residual en un único recorrido.

CorteMinimo(grafo, s, t):
    ejecutar cualquier algoritmo de flujo máximo hasta saturar

    // S = todo lo alcanzable desde s
    // en el grafo RESIDUAL
    S = BFS/DFS desde s usando solo aristas con
        capacidad residual > 0
    T = el resto de los vértices

    corte = { (u,v) en aristas originales :
              u en S y v en T }
    devolver corte y la suma de sus capacidades originales

Dos hechos hacen que esto funcione. Toda arista que cruza de S a T tiene que estar saturada, porque de lo contrario su capacidad residual sería positiva y su extremo habría sido alcanzable, quedando dentro de S. Y toda arista que va de T de vuelta a S transporta flujo cero. Así que el flujo a través del corte iguala exactamente la capacidad del corte, y dado que ningún flujo puede superar ningún corte, ambos han de ser óptimos.

Ejemplo resuelto, paso a paso

Halla el corte mínimo sobre la misma red usada para el flujo máximo, leyendo el grafo residual una vez saturado el flujo.

Grafo de ejemplo: Capacidades dirigidas S a A (10), S a B (10), A a B (2), A a T (4), B a T (9).

1. Calcular el flujo máximo. Aumentar por S a A a T empuja 4, y por S a B a T empuja 9. El flujo total es 13 y no queda ningún camino aumentante.
2. Mirar el grafo residual. S-A tiene 10 - 4 = 6 de holgura. S-B tiene 10 - 9 = 1. A-B está intacta, así que conserva sus 2. A-T y B-T están ambas saturadas, con 0 de holgura.
3. Hallar S mediante un recorrido. Empieza en S. La arista S-A tiene holgura, así que A entra en S. Desde A, la arista A-B tiene holgura, así que B entra en S. Desde B, la única arista saliente B-T está saturada. No se alcanza nada más, de modo que S es el conjunto {S, A, B}.
4. Leer el corte. T es el conjunto de vértices restante, solo {T}. Las aristas originales que van de S a T son A-T con capacidad 4 y B-T con capacidad 9.
5. Verificar. La capacidad del corte es 4 + 9 = 13, exactamente igual al flujo máximo. Quitar esas dos aristas deja T inalcanzable desde S, lo que confirma que es un corte genuino.

El corte mínimo es el par de aristas A-T y B-T con capacidad total 13, coincidiendo con el flujo máximo de 13. Fíjate en que S-A y S-B suman una capacidad de 20 y también forman un corte, pero uno más caro. El cuello de botella está del lado del sumidero, y el recorrido del residual lo encuentra sin necesidad de buscar entre cortes candidatos.

Complejidad y de dónde sale

Tiempo: la misma que el algoritmo de flujo máximo usado · Espacio: O(V + E)

La extracción del corte en sí es un único recorrido del grafo en O(V + E), lo que resulta despreciable. Todo el coste está en el cálculo del flujo máximo que lo precede: O(V por E al cuadrado) con Edmonds-Karp, o O(V al cuadrado por E) con Dinic. Merece la pena decirlo con claridad porque explica por qué el corte mínimo no se trata como un problema aparte. No se conoce ninguna forma de hallar el corte mínimo entre s y t que sea asintóticamente más rápida que calcular el flujo máximo, ya que por el teorema de flujo máximo y corte mínimo ambos son el mismo cálculo visto desde lados opuestos.

Cuándo usar Corte Mínimo y cuándo no

La palabra corte abarca varios problemas genuinamente distintos. Elegir el equivocado es el error más común aquí.

Errores frecuentes

• Recorrer el grafo original en lugar del residual. El corte se define por lo que es alcanzable usando capacidad sobrante, no por las aristas originales. Ejecutar el recorrido sobre el grafo original normalmente llega al sumidero y no produce ningún corte. Este es el error de implementación más frecuente.
• Confundir el corte mínimo s-t con el corte mínimo global. El corte s-t separa dos vértices elegidos. El corte mínimo global divide el grafo en dos partes no vacías cualesquiera y requiere Stoer-Wagner o Karger. Resolver el equivocado da una respuesta válida a una pregunta que nadie hizo.
• Suponer que el corte mínimo es único. Su capacidad es única; el conjunto de aristas a menudo no lo es. Varios cortes distintos pueden compartir la capacidad mínima, y cuál obtienes depende del flujo hallado. Las pruebas deben comprobar la capacidad, no una lista concreta de aristas.
• Contar aristas que van de T de vuelta a S. Solo cuentan para la capacidad del corte las aristas que van del lado S al lado T. Las aristas inversas transportan flujo cero a través del corte y no aportan nada. Incluirlas infla la respuesta por encima del flujo máximo y rompe el teorema.
• Olvidar que las capacidades deben ser no negativas. La correspondencia entre flujo máximo y corte mínimo presupone capacidades no negativas. Una capacidad negativa no es una noción con sentido de caudal, y el razonamiento sobre el residual se derrumba sin ella.

Preguntas frecuentes

¿Qué es un corte mínimo en un grafo?

Un corte es una partición de los vértices en dos conjuntos, uno con el origen y otro con el sumidero, y su capacidad es la capacidad total de las aristas que cruzan del lado del origen al lado del sumidero. El corte mínimo es la partición más barata, lo que identifica el cuello de botella: el conjunto de aristas menos costoso que hay que eliminar para desconectar el origen del sumidero.

¿Cómo se encuentra el corte mínimo?

Calcula el flujo máximo y después ejecuta un BFS o un DFS desde el origen en el grafo residual, siguiendo únicamente las aristas que aún tienen capacidad sobrante. Los vértices que alcanzas forman un lado del corte, el resto forma el otro, y las aristas originales que cruzan entre ambos son el corte mínimo.

¿Qué es el teorema de flujo máximo y corte mínimo?

Afirma que el flujo máximo del origen al sumidero siempre iguala la capacidad del corte mínimo que los separa. Ningún flujo puede superar ningún corte, ya que todo debe cruzarlo, y cuando no queda camino aumentante el conjunto alcanzable en el residual define un corte cuya capacidad el flujo alcanza exactamente, de modo que ambos valores coinciden.

¿Cuál es la diferencia entre corte mínimo y corte mínimo global?

Un corte mínimo s-t separa dos vértices especificados y se halla mediante flujo máximo. Un corte mínimo global divide el grafo en dos partes no vacías cualesquiera sin designar vértices de antemano, y se halla con Stoer-Wagner o Karger. Un corte global puede ser mucho más barato que cualquier corte s-t concreto.

¿Para qué se usa el corte mínimo?

Para identificar vulnerabilidades de red y puntos únicos de fallo, para segmentación de imágenes donde los píxeles son vértices y el corte separa primer plano de fondo, para agrupamiento y detección de comunidades, para problemas de selección de proyectos y para el análisis de fiabilidad de infraestructuras de comunicación o transporte.