Problema de cierre

El cierre de peso máximo de un grafo G dado es igual al complemento del cierre de peso mínimo en el grafo transpuesto de G , por lo que ambos problemas son equivalentes en complejidad computacional. Si dos vértices del grafo pertenecen al mismo componente fuertemente conexo , deben comportarse igual entre sí con respecto a todos los cierres: no es posible que un cierre contenga un vértice sin contener el otro. Por esta razón, el grafo de entrada a un problema de cierre puede ser reemplazado por su condensación , en la que cada componente fuertemente conexo es reemplazado por un solo vértice. La condensación es siempre un grafo dirigido acíclico .

Como mostró Picard (1976) , ^{[ 2 ] [ 3 ]} se puede obtener un cierre de peso máximo a partir de G resolviendo un problema de flujo máximo en un grafo H construido a partir de G añadiéndole dos vértices adicionales s y t . Para cada vértice v con peso positivo en G , el grafo aumentado H contiene una arista de s a v con capacidad igual al peso de v , y para cada vértice v con peso negativo en G , el grafo aumentado H contiene una arista de v a t cuya capacidad es la negación del peso de v . A todas las aristas en G se les da capacidad infinita en H . ^{[ 1 ]}

Un corte mínimo que separe s de t en este grafo no puede tener ninguna arista de G que pase en la dirección de avance a través del corte: un corte con tal arista tendría capacidad infinita y no sería mínimo. Por lo tanto, el conjunto de vértices del mismo lado del corte que s forma automáticamente un cierre C. La capacidad del corte es igual al peso de todos los vértices de peso positivo menos el peso de los vértices en C , que se minimiza cuando el peso de C se maximiza. Según el teorema del flujo máximo y el corte mínimo , se puede encontrar un corte mínimo, y el cierre óptimo derivado de él, resolviendo un problema de flujo máximo. ^{[ 1 ]}

También se han estudiado algoritmos alternativos para el problema del cierre máximo que no calculan flujos. ^{[ 4 ] [ 5 ] [ 6 ]} Su tiempo de ejecución es similar al de los algoritmos de flujo más rápidos conocidos. ^{[ 4 ]}

Una mina a cielo abierto puede modelarse como un conjunto de bloques de material que pueden extraerse una vez que se hayan extraído todos los bloques situados directamente encima. Cada bloque tiene un valor total, igual al valor de los minerales que se pueden extraer de él menos el coste de extracción; en algunos casos, un bloque no tiene valor de extracción, pero aun así debe extraerse para acceder a otros bloques, lo que le confiere un valor negativo. Se puede definir una red acíclica cuyos vértices sean los bloques de la mina, con una arista que conecta cada bloque con los bloques situados encima que deben extraerse antes. El peso de cada vértice de esta red es el valor total de su bloque, y el plan de extracción más rentable se determina encontrando un cierre de peso máximo y, a continuación, estableciendo un ordenamiento topológico de los bloques en dicho cierre. ^{[ 1 ] [ 5 ] [ 7 ]}

En operaciones militares, los objetivos de alto valor, como los centros de mando, suelen estar protegidos por múltiples capas de sistemas de defensa, que a su vez pueden estar protegidos por otros sistemas. Para alcanzar un objetivo, es necesario neutralizar todas sus defensas, convirtiéndolo así en un objetivo secundario. Cada objetivo requiere una cantidad específica de recursos para llevar a cabo un ataque exitoso. El conjunto óptimo de objetivos a atacar, para obtener el máximo provecho de los recursos invertidos, puede modelarse como un problema de cierre. ^{[ 1 ] [ 8 ]}

El problema de planificar un sistema de entrega de carga puede modelarse mediante una red en la que los vértices representan ciudades y las aristas (no dirigidas) representan posibles rutas de entrega de carga entre pares de ciudades. Cada ruta puede obtener una cierta ganancia, pero solo puede utilizarse si se construyen depósitos de carga en ambos extremos, con un cierto costo. El problema de diseñar una red que maximice la diferencia entre las ganancias y los costos puede resolverse como un problema de cierre, subdividiendo cada arista no dirigida en dos aristas dirigidas, ambas dirigidas hacia afuera desde el punto de subdivisión. El peso de cada punto de subdivisión es un número positivo, la ganancia de la ruta correspondiente, y el peso de cada vértice del grafo original es un número negativo, el costo de construir un depósito en esa ciudad. ^{[ 1 ] [ 9 ]} Junto con la minería a cielo abierto, esta fue una de las aplicaciones originales que motivaron el estudio del problema de cierre; fue estudiado originalmente en 1970, en dos artículos independientes publicados en el mismo número de la misma revista por JMW Rhys y Michel Balinski . ^{[ 9 ] [ 10 ] [ 11 ]}

Sidney (1975) y Lawler (1978) describen una aplicación del problema de cierre a una versión de la programación de talleres en la que se proporciona un conjunto de tareas que deben programarse para su ejecución, una a la vez. Cada tarea tiene dos números asociados: un peso o prioridad y un tiempo de procesamiento, que es el tiempo necesario para realizarla. Además, las tareas tienen restricciones de precedencia: ciertas tareas deben realizarse antes que otras. Estas restricciones de precedencia pueden describirse mediante un grafo dirigido acíclico G en el que una arista de una tarea a otra indica que la primera tarea debe realizarse antes que la segunda. El objetivo es elegir un ordenamiento que sea consistente con estas restricciones (un ordenamiento topológico de G ) que minimice el tiempo total ponderado de finalización de las tareas. ^{[ 12 ] [ 13 ]}

Aunque (como muestra Lawler) este problema de planificación es NP-completo en general, Sidney describe un método de descomposición que puede ayudar a resolver el problema reduciéndolo a varios problemas más pequeños del mismo tipo. En particular, si S es un subconjunto de las tareas que (entre todos los subconjuntos) tiene la mayor razón posible de su peso total a su tiempo de procesamiento total, y además S es mínimo entre todos los conjuntos con la misma razón, entonces existe una planificación óptima en la que todas las tareas en S se realizan antes que todas las demás tareas. Siempre que S no sea el conjunto completo de tareas, esta partición de las tareas divide el problema de planificación en dos problemas más pequeños, uno de planificación de S y otro de planificación de las tareas restantes. ^{[ 12 ]} Aunque S es un cierre (para un grafo con aristas invertidas de G ) el problema de encontrar S no es exactamente un problema de cierre de peso máximo, porque el valor de S es una razón en lugar de una suma de pesos. Sin embargo, Lawler demuestra que S puede encontrarse en tiempo polinomial mediante un algoritmo de búsqueda binaria en el que cada paso de la búsqueda utiliza una instancia del problema de cierre como subrutina. ^{[ 13 ]}