Corte mínimo
En 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 puede transformarse trivialmente en un problema de corte máximo ponderado cambiando el signo en todos los pesos.
El problema de corte mínimo en gráficos ponderados no dirigidos , limitados a pesos no negativos, puede resolverse en tiempo polinomial mediante 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 de corte mínimo sin terminales es el corte k 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 polinomial, aunque el algoritmo no es práctico para k grandes . [2]
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 hasta el 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.
