En la teoría de grafos , un corte mínimo o minicorte 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 la división de los vértices en más de dos conjuntos.
El problema de corte mínimo ponderado que permite ponderaciones tanto positivas como negativas se puede transformar trivialmente en un problema de corte máximo ponderado cambiando el signo en todos los pesos.
Sin nodos terminales
El problema recorte mínimo en no dirigidos , gráficos ponderados se puede resolver en tiempo polinómico por el algoritmo de Stoer-Wagner . En el caso especial cuando 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 borde del gráfico.
Una generalización del problema mínimo corte sin terminales es el mínimo k -cut , en el que el objetivo es dividir el gráfico en al menos k componentes conectados mediante la eliminación como unos bordes como sea posible. Para un valor fijo de k , este problema se puede resolver en tiempo polinomial, aunque el algoritmo no es práctico para k grandes . [2]
Con nodos terminales
Cuando se dan dos nodos terminales, normalmente se los denomina fuente y sumidero . En una red de flujo ponderado y dirigido, el corte mínimo separa los vértices de la fuente y del sumidero y minimiza el peso total en los bordes que se dirigen desde el lado de la fuente del corte al lado del 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 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 tiene el mínimo peso posible. Un sistema de cortes que resuelve este problema para cada posible par de vértices se puede recopilar en una estructura conocida como el árbol de Gomory-Hu del gráfico.
Una generalización del problema de corte mínimo con terminales es el corte de terminal k , o corte de múltiples terminales. Este problema es NP-difícil , incluso para. [3]
Aplicaciones
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 agrupamiento espectral de corte mínimo normalizado aplicado a la segmentación de imágenes .
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 maxflow también podrían utilizarse para resolver esta cuestión.
Número de cortes mínimos
Un gráfico con los vértices pueden tener como máximo cortes mínimos distintos. Este límite es estrecho en el sentido de que un ciclo (simple) en vértices tiene exactamente cortes mínimos.
Ver también
- Corte máximo
- Separador de vértices , un concepto análogo a los cortes mínimos para los vértices en lugar de los bordes
Referencias
- ^ "4 algoritmos de corte mínimo" .
- ^ "Un algoritmo polinomial para el k-cut Problema para k fijo" . Cite journal requiere
|journal=
( ayuda ) - ^ "La complejidad de los cortes multiterminales" (PDF) . Archivado desde el original (PDF) el 25 de diciembre de 2018. Cite journal requiere
|journal=
( ayuda )