Recorte mínimo

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 según alguna métrica. En el problema de min-corte no ponderado más simple , el objetivo es minimizar el número de aristas que conectan las dos partes.

Las variaciones del problema del corte mínimo consideran grafos ponderados , grafos dirigidos , terminales y la partición de los vértices en más de dos conjuntos .

El problema del corte mínimo ponderado, que permite ponderaciones tanto positivas como negativas, se puede transformar fácilmente en un problema de corte máximo ponderado cambiando el signo de todas las ponderaciones.

La entrada es un grafo G = (V, E). La salida requerida es una partición V = S + T (una partición de los vértices en dos subconjuntos disjuntos S y T). Toda partición de este tipo tiene un costo, y el objetivo es encontrar la partición con el menor costo posible.

• En la versión sin ponderación, el costo de un corte (S,T) es el número de aristas con un extremo en S y otro en T. En este caso, el corte mínimo es igual a la conectividad de aristas del grafo. El algoritmo de Karger proporciona un método aleatorio eficiente para encontrar el corte.
• En la versión ponderada, cada arista en E tiene un peso, y el costo de un corte (S,T) es el peso total de las aristas con un extremo en S y otro en T. Cuando los pesos son no negativos, el problema se puede resolver en tiempo polinomial mediante el algoritmo de Stoer-Wagner .

En la variante denominada min st cut , la entrada contiene, además del grafo, dos nodos llamados s (origen) y t (destino/sumidero). La salida requerida es una partición V = S + T tal que s esté en S y t esté en T.

En una red de flujo , el corte mínimo separa los vértices de origen y destino, y minimiza la suma total de las capacidades de las aristas que se dirigen desde el lado de origen del corte hacia el lado de destino. Como se muestra en el teorema del 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 el origen al destino en la red dada.

En una red no dirigida ponderada, es posible calcular el corte que separa un par de vértices y que minimiza el costo total. Un sistema de cortes que resuelve este problema para cada par de vértices se puede organizar en una estructura conocida como el árbol de Gomory-Hu del grafo.

Los problemas de partición de grafos son una familia de problemas de optimización combinatoria en los que un grafo 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 considerarse un caso específico de agrupamiento espectral de corte mínimo normalizado aplicado a la segmentación de imágenes . También puede utilizarse como un método de agrupamiento genérico , donde los nodos son muestras de datos que se supone que provienen de un espacio métrico y los pesos de las aristas son sus distancias. Sin embargo, esto suele ser poco práctico debido a la alta complejidad computacional.${\displaystyle k>2}$.

Debido al teorema del flujo máximo y el corte mínimo , el valor de corte mínimo entre dos nodos es igual a su valor de flujo máximo . En este caso, algunos algoritmos utilizados en el problema del flujo máximo también podrían emplearse para resolver esta cuestión.

Un gráfico con${\displaystyle n}$los vértices pueden tener como máximo${\displaystyle {\binom {n}{2}}={\frac {n(n-1)}{2}}}$cortes mínimos distintos. Este límite es ajustado en el sentido de que un ciclo (simple) en${\displaystyle n}$vértices tiene exactamente${\displaystyle {\frac {n(n-1)}{2}}}$recortes mínimos.

• Corte máximo
• Separador de vértices , un concepto análogo a los cortes mínimos para vértices en lugar de aristas.