En teoría de grafos , un corte mínimo o min-corte de un grafo es un corte (una partición de los vértices de un grafo en dos subconjuntos disjuntos) que es mínimo en alguna métrica.
Las variaciones del problema de corte mínimo consideran gráficos ponderados, gráficos dirigidos, terminales y partición de los vértices en más de dos conjuntos.
El problema de corte mínimo ponderado que permite pesos tanto positivos como negativos se puede transformar trivialmente en un problema de corte máximo ponderado invirtiendo el signo en todos los pesos.
El problema del corte mínimo en grafos no dirigidos y ponderados limitados a pesos no negativos se puede resolver en tiempo polinomial mediante el algoritmo de Stoer-Wagner . En el caso especial en el que el grafo no está ponderado, el algoritmo de Karger proporciona un método aleatorio eficiente para encontrar el corte. En este caso, el corte mínimo es igual a la conectividad de los bordes del grafo.
Una generalización del problema de corte mínimo sin terminales es el k -corte mínimo , en el que el objetivo es dividir el grafo en al menos k componentes conectados eliminando la menor cantidad posible de aristas. Para un valor fijo de k , este problema se puede resolver en tiempo polinomial, aunque el algoritmo no es práctico para valores grandes de k . [2]
Cuando se dan dos nodos terminales, normalmente se los denomina fuente y sumidero . En una red de flujo , el corte mínimo separa los vértices de fuente y sumidero y minimiza la suma total de las capacidades de los bordes que se dirigen desde el lado de fuente del corte hasta el lado de sumidero del corte. Como se muestra en el teorema de corte mínimo de flujo máximo , el peso de este corte es igual a la cantidad máxima de flujo que se puede enviar desde la fuente hasta el sumidero en la red dada.
En una red ponderada y no dirigida, es posible calcular el corte que separa un par particular de vértices entre sí y que tiene el peso mínimo posible. Un sistema de cortes que resuelve este problema para cada par de vértices posible se puede recopilar en una estructura conocida como el árbol de Gomory-Hu del grafo.
Una generalización del problema de corte mínimo con terminales es el corte k -terminal, o corte multiterminal. En un grafo planar , este problema se puede resolver en tiempo polinomial. Sin embargo, en general este problema es NP-hard , incluso para . [3]
Los problemas de partición de grafos son una familia de problemas de optimización combinatoria en los que un grafo se debe dividir en dos o más partes con restricciones adicionales, como equilibrar los tamaños de los dos lados del corte. La categorización de objetos basada en segmentación se puede considerar como un caso específico de agrupamiento espectral de corte mínimo normalizado aplicado a la segmentación de imágenes . También se puede utilizar como un método de agrupamiento genérico , donde los nodos son muestras de datos que se supone que se toman de un espacio métrico y los pesos de los bordes son sus distancias. Sin embargo, esto a menudo es poco práctico debido a la alta complejidad computacional para .
Debido al teorema de corte mínimo de flujo máximo , el valor de corte mínimo de 2 nodos es igual a su valor de flujo máximo . En este caso, algunos algoritmos utilizados en el problema de flujo máximo también podrían utilizarse para resolver esta cuestión.
Un grafo con vértices puede tener, como máximo, cortes mínimos distintos. Este límite es estricto en el sentido de que un ciclo (simple) sobre vértices tiene exactamente cortes mínimos.
