El problema mínimo de corte
El problema de corte mínimo es un problema fundamental en la teoría de grafos y la optimización combinatoria. Dado un gráfico (ya sea dirigido o no dirigido) con capacidades asignadas a sus bordes, y dos vértices designados, una fuente (s) y un sumidero (t), el problema es encontrar un conjunto de bordes cuya eliminación desconecta la fuente del fregadero y minimiza la suma de las capacidades de esos bordes.
En otras palabras, a Cut En un gráfico hay una partición de los vértices en dos conjuntos de disjunto, S y T, de modo que la fuente * S * pertenece a S y el sumidero * t * pertenece a T. la capacidad del corte es la suma de las capacidades de los bordes que van de un vértice en S a un vértice en T. El problema mínimo de corte tiene como objetivo encontrar el corte con la capacidad más pequeña.
Formalmente:
* Entrada:
* Un gráfico G =(V, E), donde V es el conjunto de vértices y E es el conjunto de bordes.
* Una función de capacidad C:E -> R+ asignando una capacidad no negativa a cada borde.
* Un vértice de origen S ∈ V.
* Un vértice de fregadero t ∈ V.
* Salida:
* Una partición (s, t) de v tal que s ∈ S, t ∈ T, y la capacidad del corte C (s, t) =σ c (u, v) (donde u ∈ S y v ∈ T) se minimiza.
Ejemplo:
Imagine una red de carreteras donde cada carretera tiene una cierta capacidad de tráfico. Desea encontrar el conjunto mínimo de carreteras que necesita cerrar (el corte) para evitar que el tráfico fluya de una ciudad a una ciudad 't'. La capacidad total de esas carreteras cerradas representa el costo del corte, y está buscando el conjunto de cierres de carreteras más baratos (capacidad mínima).
Cómo se usa un corte mínimo en la optimización del flujo de red (el teorema de corte mínimo máximo)
La conexión entre el problema de corte mínimo y la optimización del flujo de red es profunda y capturada por el teorema de corte mínimo de flujo máximo . Este teorema establece que:
La cantidad máxima de flujo que se puede enviar desde la fuente al sumidero en una red es igual a la capacidad del corte mínimo que separa la fuente y el fregadero.
Así es como se desarrolla:
1. Problema de flujo de red: El problema del flujo de red tiene como objetivo encontrar la cantidad máxima de "flujo" (por ejemplo, datos, líquido, electricidad) que se puede enviar desde la fuente al fregadero, sujeto a las limitaciones de capacidad de los bordes.
2. Encontrar el flujo máximo: Los algoritmos como Ford-Fulkerson o Edmonds-Karp se utilizan para encontrar el flujo máximo en la red.
3. Relacione el flujo para cortar: El teorema de corte mínimo de flujo máximo nos dice que una vez que hayamos encontrado el flujo máximo, el valor de ese flujo * es * la capacidad del corte mínimo.
4. Encontrar el corte mínimo: Si bien podemos inferir la capacidad del corte mínimo del flujo máximo, a menudo queremos saber * qué bordes * constituyen el corte mínimo. Esto se puede encontrar mirando el gráfico residual después de ejecutar un algoritmo de flujo máximo:
* Gráfico residual: El gráfico residual es un gráfico derivado del gráfico original que muestra la capacidad restante disponible en cada borde (o la capacidad de "deshacer" a lo largo de un borde).
* identificando el corte mínimo: Después de encontrar el flujo máximo, realice un análisis de accesibilidad en el gráfico residual a partir de la fuente. Todos los vértices accesibles desde la fuente en el gráfico residual pertenecen al conjunto 's' del corte mínimo. Todos los demás vértices pertenecen al conjunto 't'. Los bordes que se cruzan de 's' a 't' en el gráfico * original * constituyen el corte mínimo.
En resumen:
* Usted resuelve el problema de flujo máximo.
* El valor del flujo máximo es igual a la capacidad del corte mínimo (teorema de corte mínimo máximo).
* Al analizar el gráfico residual después de calcular el flujo máximo, puede identificar los bordes específicos que forman el corte mínimo.
¿Por qué es esto útil?
* Determinación de cuellos de botella: El corte mínimo identifica los cuellos de botella en una red. Estos son los bordes que, cuando se eliminan, restringen severamente el flujo de la fuente al fregadero.
* Asignación de recursos: Comprender el corte mínimo ayuda en una asignación eficiente de recursos. Puede concentrarse en reforzar los bordes en el corte mínimo para mejorar la capacidad general de la red.
* Partitionamiento de red: El corte mínimo se puede usar para dividir una red en dos componentes débilmente conectados. Esto puede ser útil para agrupar problemas o identificar grupos de nodos que son relativamente independientes entre sí.
* Resolver otros problemas: El problema mínimo de corte tiene aplicaciones en áreas diversas, incluida la segmentación de imágenes, la minería de datos y la programación de proyectos. Muchos de estos problemas pueden modelarse como problemas de flujo de red y resolverse utilizando el teorema de corte mínimo máximo.
Uso de ejemplo en un escenario:
Imagine una cuadrícula eléctrica que distribuye electricidad de una planta de energía (fuente) a una ciudad (fregadero). Las líneas tienen diferentes capacidades. Si calculamos el corte mínimo entre la planta de energía y la ciudad, podemos:
1. Conozca la cantidad máxima de electricidad que la ciudad puede recibir (el flujo máximo =minuto de corte).
2. Identifique las líneas más vulnerables (los bordes en el corte mínimo) que, si están dañados o sobrecargados, afectarían severamente el suministro de electricidad a la ciudad.
3. Priorice las actualizaciones y el mantenimiento de esas líneas críticas (los bordes de corte min) para aumentar la confiabilidad general de la red eléctrica.
En conclusión, el problema de corte mínimo, vinculado por el teorema de corte mínimo de flujo máximo para la optimización del flujo de red, proporciona una herramienta poderosa para analizar y mejorar la eficiencia y la robustez de varios sistemas de red.