En teoría de grafos , un corte mínimo o corte mínimo de un gráfico es un corte (una partición de los vértices de un gráfico 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 positivos y negativos se puede transformar trivialmente en un problema de corte máximo ponderado invirtiendo el signo en todos los pesos.
El problema de corte mínimo en gráficos ponderados no dirigidos limitados a pesos no negativos se puede resolver en tiempo polinómico mediante el algoritmo de Stoer-Wagner . En el caso especial en el que el gráfico 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 gráfico.
Una generalización del problema de corte mínimo sin terminales es el k -cut mínimo , en el que el objetivo es dividir el gráfico en al menos k componentes conectados eliminando la menor cantidad de bordes posible. Para un valor fijo de k , este problema se puede resolver en tiempo polinómico, aunque el algoritmo no es práctico para k grande . [2]
Cuando se dan dos nodos terminales, normalmente se les denomina fuente y sumidero . En una red de flujo , el corte mínimo separa los vértices fuente y sumidero y minimiza la suma total de las capacidades de los bordes que se dirigen desde el lado fuente del corte hasta el lado sumidero del corte. Como se muestra en el teorema del corte mínimo del flujo máximo , el peso de este corte es igual a la cantidad máxima de flujo que se puede enviar desde la fuente al 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 mínimo peso posible. Un sistema de cortes que resuelve este problema para cada par de vértices posible se puede recopilar en una estructura conocida como árbol del gráfico de Gomory-Hu .
Una generalización del problema de corte mínimo con terminales es el corte k -terminal o corte multiterminal. En un gráfico plano , este problema se puede resolver en tiempo polinomial. Sin embargo, en general este problema es NP-difícil , incluso para . [3]
Los problemas de partición de gráficos son una familia de problemas de optimización combinatoria en los que un gráfico debe dividirse 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 puede verse como un caso específico de agrupación espectral de corte mínimo normalizada aplicada a la segmentación de imágenes . También se puede utilizar como un método de agrupación 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 suele ser poco práctico debido a la alta complejidad computacional de .
Debido al teorema de flujo máximo y corte mínimo , 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 maxflow también podrían usarse para resolver esta pregunta.
Un gráfico con vértices puede tener como máximo distintos cortes mínimos. Este límite es estricto en el sentido de que un ciclo (simple) en los vértices tiene exactamente cortes mínimos.
