En teoría de grafos y optimización combinatoria , un cierre de un gráfico dirigido es un conjunto de vértices C , tal que ninguna arista sale de C. El problema de cierre es la tarea de encontrar el cierre de peso máximo o mínimo en un gráfico dirigido ponderado por vértices. [1] [2] Puede resolverse en tiempo polinómico utilizando un problema de reducción al flujo máximo . Puede usarse para modelar varios problemas de aplicación para elegir un subconjunto óptimo de tareas a realizar, con dependencias entre pares de tareas, siendo un ejemplo la minería a cielo abierto .
El cierre de peso máximo de un gráfico dado G es el mismo que el complemento del cierre de peso mínimo en el gráfico transpuesto de G , por lo que los dos problemas son equivalentes en complejidad computacional. Si dos vértices del gráfico pertenecen al mismo componente fuertemente conectado , 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 el que cada componente fuertemente conectado es reemplazado por un único vértice. La condensación es siempre un gráfico acíclico dirigido .
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 gráfico H construido a partir de G agregándole dos vértices adicionales s y t . Para cada vértice v con peso positivo en G , el gráfico 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 gráfico 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 una capacidad infinita en H. [1]
Un corte mínimo que separa s de t en este gráfico no puede tener ningún borde de G que pase en dirección hacia adelante a través del corte: un corte con tal borde tendría una capacidad infinita y no sería mínimo. Por lo tanto, el conjunto de vértices en el mismo lado del corte como 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 se maximiza el peso de C. Según el teorema de flujo máximo y 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 de 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 se puede modelar como un conjunto de bloques de material que se pueden extraer minándolos una vez que se hayan eliminado todos los bloques directamente encima de ella. Un bloque tiene un valor total, igual al valor de los minerales que se pueden extraer de él menos el costo de remoción y extracción; en algunos casos, un bloque no tiene valor de extracción pero aun así debe eliminarse para llegar a otros bloques, lo que le otorga un valor negativo. Se puede definir una red acíclica que tiene como vértices los bloques de una mina, con un borde desde cada bloque hasta los bloques superiores que debe eliminarse antes. El peso de cada vértice en esta red es el valor total de su bloque, y el plan de minería más rentable se puede determinar encontrando un cierre de peso máximo y luego formando un ordenamiento topológico de los bloques en este cierre. [1] [5] [7]
En las operaciones militares, los objetivos de alto valor, como los centros de mando, suelen estar protegidos por capas de sistemas de defensa, que a su vez pueden estar protegidos por otros sistemas. Para alcanzar un objetivo, se deben derribar todas sus defensas, convirtiéndolo en un objetivo secundario. Cada objetivo necesita que se le asignen una cierta cantidad de recursos para poder realizar un ataque exitoso. El conjunto óptimo de objetivos a atacar, para obtener el mayor valor de los recursos gastados, 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 los bordes (no dirigidos) representan rutas potenciales de entrega de carga entre pares de ciudades. Cada ruta puede generar un cierto beneficio, pero sólo puede utilizarse si se construyen depósitos de carga en ambos extremos, con un coste determinado. El problema de diseñar una red que maximice la diferencia entre los beneficios y los costos se puede resolver como un problema de cierre, subdividiendo cada borde no dirigido en dos bordes dirigidos, ambos dirigidos hacia afuera desde el punto de subdivisión. El peso de cada punto de subdivisión es un número positivo, el beneficio de la ruta correspondiente, y el peso de cada vértice del gráfico 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 motivadoras originales para estudiar el problema del 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 del cierre a una versión de programación de talleres en la que a uno se le asigna una colección de tareas que debe programar para su realización, una a la vez. Cada tarea tiene dos números asociados: un peso o prioridad y un tiempo de procesamiento, la cantidad de tiempo que lleva realizar esa tarea. Además, las tareas tienen restricciones de precedencia: ciertas tareas deben realizarse antes que otras. Estas restricciones de precedencia pueden describirse mediante un gráfico acíclico dirigido G en el que un borde 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 programació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 tareas que (entre todos los subconjuntos) tiene la mayor proporción posible entre su peso total y su tiempo total de procesamiento, y además S es mínimo entre todos los conjuntos con la misma proporción, entonces existe un cronograma óptimo en el que todas las tareas en S se realizan antes que todas las demás tareas. Mientras S no sea el conjunto completo de tareas, esta partición de las tareas divide el problema de programación en dos problemas más pequeños, uno de programación de S y otro de programación de las tareas restantes. [12] Aunque S es un cierre (para un gráfico 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 relación en lugar de una suma de pesos. Sin embargo, Lawler muestra que S puede encontrarse en tiempo polinómico 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]