En teoría de grafos y optimización combinatoria , un cierre de un grafo dirigido es un conjunto de vértices C , de modo que ninguna arista salga de C. El problema de cierre es la tarea de encontrar el cierre de peso máximo o peso mínimo en un grafo dirigido ponderado por vértices. [1] [2] Puede resolverse en tiempo polinomial utilizando una reducción al problema de flujo máximo . Puede utilizarse para modelar varios problemas de aplicación de elección de un subconjunto óptimo de tareas a realizar, con dependencias entre pares de tareas, un ejemplo es la minería a cielo abierto .
El cierre de peso máximo de un grafo dado G es el mismo que el complemento del cierre de peso mínimo en el grafo transpuesto de G , por lo que los dos problemas son equivalentes en complejidad computacional. Si dos vértices del grafo pertenecen al mismo componente fuertemente conectado , deben comportarse de la misma manera 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 conectado es reemplazado por un solo vértice. La condensación es siempre un grafo 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 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 de G se les da capacidad infinita en H . [1]
Un corte mínimo que separa s de t en este grafo no puede tener ninguna arista de G que pase en la dirección hacia adelante 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 se maximiza el peso de C . Por el teorema de corte mínimo de flujo máximo , un corte mínimo, y el cierre óptimo derivado de él, se pueden encontrar 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 puede ser modelada como un conjunto de bloques de material que pueden ser removidos mediante la minería una vez que todos los bloques directamente sobre él han sido removidos. Un bloque tiene un valor total, igual al valor de los minerales que pueden ser extraídos de él menos el costo de remoción y extracción; en algunos casos, un bloque no tiene valor de extracción pero aún así debe ser removido para alcanzar otros bloques, lo que le da un valor negativo. Se puede definir una red acíclica que tiene como vértices los bloques de una mina, con un borde de cada bloque a los bloques sobre él que deben ser removidos antes que él. El peso de cada vértice en esta red es el valor total de su bloque, y el plan más rentable para la minería puede determinarse 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, es necesario derribar todas sus defensas, lo que lo convierte en un objetivo secundario. Cada objetivo necesita una cierta cantidad de recursos que se le asignen para realizar un ataque exitoso. El conjunto óptimo de objetivos a atacar, para obtener el máximo valor por los recursos gastados, se puede modelar como un problema de cierre. [1] [8]
El problema de planificar un sistema de entrega de carga puede ser modelado por 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 lograr un cierto beneficio, pero solo puede usarse 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 los beneficios y los costos puede resolverse 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 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 motivadoras originales para estudiar el problema de cierre; se estudió 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 de trabajo en la que se da una colección de tareas que se deben programar para que se realicen, 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 se pueden describir 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 orden que sea coherente con estas restricciones (un orden 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 al reducirlo 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 total de procesamiento, y además S es mínimo entre todos los conjuntos con la misma razón, entonces existe una programación óptima en la 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 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]