Para un gráfico , un corte máximo es un corte cuyo tamaño es al menos del tamaño de cualquier otro corte. El problema de encontrar un corte máximo en un gráfico se conoce como el problema de corte máximo.
El problema se puede plantear simplemente de la siguiente manera. Uno quiere un subconjunto S del conjunto de vértices de manera que el número de aristas entre S y el subconjunto complementario sea lo más grande posible.
Hay una versión más general del problema llamada Max-Cut ponderada . En esta versión, cada borde tiene un número real, su peso , y el objetivo es maximizar no el número de bordes, sino el peso total de los bordes entre S y su complemento. El problema de Max-Cut ponderado a menudo, pero no siempre, está restringido a pesos no negativos, porque los pesos negativos pueden cambiar la naturaleza del problema.
Complejidad computacional [ editar ]
El siguiente problema de decisión relacionado con los cortes máximos se ha estudiado ampliamente en informática teórica :
- Dada una gráfica G y un número entero k , determinar si hay un corte de tamaño al menos k en G .
Se sabe que este problema es NP-completo . Es fácil ver que el problema está en NP : una respuesta afirmativa es fácil de probar presentando un corte lo suficientemente grande. La integridad de NP del problema puede demostrarse, por ejemplo, mediante una reducción de la satisfacción máxima de 2 (una restricción del problema de satisfacción máxima ). [1] La versión ponderada del problema de decisión fue uno de los 21 problemas completos de NP de Karp ; [2] Karp mostró la integridad de NP mediante una reducción del problema de partición .
La canónica variante de optimización del problema de decisión anterior se conoce generalmente como el -Cut Máximo Problema o Max-Cut y se define como:
- Dado un gráfico G , encuentre un corte máximo.
Se sabe que el problema opuesto, el de encontrar un corte mínimo, se puede resolver de manera eficiente a través del algoritmo Ford-Fulkerson .
Algoritmos [ editar ]
Algoritmos de tiempo polinómico [ editar ]
Como el problema de Max-Cut es NP-hard , no se conocen algoritmos de tiempo polinómico para Max-Cut en gráficos generales.
Gráficos planos [ editar ]
Sin embargo, en los gráficos planos , el problema de corte máximo es doble al problema de inspección de ruta (el problema de encontrar un recorrido más corto que visite cada borde de un gráfico al menos una vez), en el sentido de que los bordes que no pertenecen a un máximo de corte de un conjunto de un gráfico G son los duales de los bordes que están duplicando en un viaje de inspección óptima de la dual gráfico de G . El recorrido de inspección óptimo forma una curva de auto intersección que separa el plano en dos subconjuntos, el subconjunto de puntos para los cuales el número de bobinadode la curva es par y el subconjunto para el cual el número de devanado es impar; Estos dos subconjuntos forman un corte que incluye todos los bordes cuyos duales aparecen un número impar de veces en el recorrido. El problema de inspección de ruta puede resolverse en tiempo polinómico, y esta dualidad permite que el problema de corte máximo también se resuelva en tiempo polinómico para gráficos planos. [3] Sin embargo, se sabe que el problema de la bisección máxima es NP-duro. [4]
Algoritmos de aproximación [ editar ]
El problema de corte máximo es APX-hard , [5] lo que significa que no existe un esquema de aproximación de tiempo polinomial (PTAS), arbitrariamente cercano a la solución óptima, para ello, a menos que P = NP. Por lo tanto, cada algoritmo de aproximación de tiempo polinomial conocido logra una relación de aproximación estrictamente menor que uno.
Hay un algoritmo aleatorio simple de aproximación de 0.5 : para cada vértice, voltee una moneda para decidir a qué mitad de la partición asignarla. [6] [7] En expectativa, la mitad de los bordes son bordes cortados. Este algoritmo puede ser aleatorizado con el método de probabilidades condicionales ; por lo tanto, también existe un algoritmo determinista simple de tiempo de polinomio 0.5. [8] [9] Uno de estos algoritmos comienza con una partición arbitraria de los vértices del gráfico dadoy mueve repetidamente un vértice a la vez de un lado de la partición al otro, mejorando la solución en cada paso, hasta que no se puedan realizar más mejoras de este tipo. El número de iteraciones es como máximoporque el algoritmo mejora el corte en al menos un borde en cada paso. Cuando el algoritmo termina, al menos la mitad de los bordes incidentes con cada vértice pertenecen al corte, ya que de lo contrario, mover el vértice mejoraría el corte. Por lo tanto, el corte incluye al menos bordes
El algoritmo de aproximación de tiempo polinómico para Max-Cut con la relación de aproximación más conocida es un método de Goemans y Williamson que utiliza programación semidefinida y redondeo aleatorio que logra una relación de aproximación, dónde
Si la conjetura de los juegos únicos es cierta, esta es la mejor relación de aproximación posible para un corte máximo. [12] Sin tales suposiciones no comprobadas, se ha demostrado que es NP-difícil aproximar el valor de corte máximo con una relación de aproximación mejor que. [13] [14]
En [15] hay un análisis extendido de 10 heurísticas para este problema, incluida la implementación de código abierto.
Aplicaciones [ editar ]
Física teórica [ editar ]
En física estadística y sistemas desordenados , el problema de Max Cut es equivalente a minimizar el hamiltoniano de un modelo de vidrio giratorio , más simplemente el modelo Ising . [16] Para el modelo de Ising en un gráfico G y sólo las interacciones del vecino más cercano, el hamiltoniano es
Aquí cada vértice i del gráfico es un sitio de rotación que puede tomar un valor de rotación . Un giro de particiones de configuración en dos conjuntos, aquellos con spin up y aquellos con spin down . Denotamos conEl conjunto de bordes que conectan los dos conjuntos. Entonces podemos reescribir el hamiltoniano como
Minimizar esta energía es equivalente al problema de corte mínimo o al establecer los pesos del gráfico como , el problema de corte máximo. [dieciséis]
Diseño de circuito [ editar ]
En el campo matemático de la teoría de grafos , el número de intersección de un gráfico G = ( V , E ) es el número más pequeño de elementos en una representación de G como un gráfico de intersección de conjuntos finitos . De manera equivalente, es el menor número de camarillas necesarios para cubrir todos los bordes de G .
Gráficos de intersección [ editar ]
Sea F una familia de conjuntos (permitiendo que se repitan conjuntos en F ); entonces el gráfico de intersección de F es un gráfico no dirigido que tiene un vértice para cada miembro de F y un borde entre cada dos miembros que tienen una intersección no vacía. Cada gráfico se puede representar como un gráfico de intersección de esta manera. [3] El número de intersección de la gráfica es el número más pequeño k, de modo que existe una representación de este tipo para la cual la unión de F tiene k elementos. [1]El problema de encontrar una representación de intersección de un gráfico con un número dado de elementos se conoce como el problema de base del gráfico de intersección . [4]
Cubiertas de borde de camarilla [ editar ]
Una definición alternativa del número intersección de una gráfica G es que es el número más pequeño de camarillas en G ( completos subgraphs de G ) que juntos cubren todos los bordes de G . [1] [5] Un conjunto de camarillas con esta propiedad se conoce como una cubierta de borde camarilla o cubierta clique borde , y por esta razón el número de intersección está también llamado a veces el número cubierta clique borde . [6]
La igualdad del número de intersección y el número de cubierta camarilla borde es fácil de demostrar. En una dirección, supongamos que G es el grafo intersección de una familia F de conjuntos cuya unión U tiene k elementos. Luego, para cualquier elemento x de U , el subconjunto de vértices de G correspondiente a los conjuntos que contienen x forma una camarilla: cualquiera de los dos vértices en este subconjunto son adyacentes, porque sus conjuntos tienen una intersección no vacía que contiene x . Además, cada ventaja en Gestá contenido en una de estas camarillas, porque un borde corresponde a una intersección no vacía y una intersección es no vacía si contiene al menos un elemento de U . Por lo tanto, los bordes de G pueden ser cubiertos por k camarillas, uno por cada elemento de U . En la otra dirección, si un gráfico G puede ser cubierto por k camarillas, a continuación, cada vértice de G puede ser representado por el conjunto de camarillas que contienen ese vértice. [5]
Límites superiores [ editar ]
Trivialmente, un gráfico con m bordes tiene número de intersección a lo sumo m , para cada borde forma una camarilla y estas camarillas juntos cubre todos los bordes. [7]
También es cierto que cada gráfico con n vértices tiene número de intersección a lo sumo n 2 /4 . Más fuertemente, los bordes de cada n gráfico -vertex pueden dividirse en un máximo de n 2 /4 camarillas, todos los cuales son o bien bordes individuales o triángulos. [2] [5] Este generaliza el teorema de Mantel que un gráfico libre de triángulo tiene como máximo n 2 /4 bordes, para en un gráfico libre de triángulo de la cubierta solamente óptima borde camarilla tiene uno clique por borde y por lo tanto el número de intersección es igual a la número de aristas. [2]
Una cota aún más fuerte es posible cuando el número de bordes es estrictamente mayor que n 2 /4 . Sea p el número de pares de vértices que no están conectados por un borde en el gráfico G dado , y sea t el número entero único para el cual t ( t - 1) ≤ p < t ( t + 1) . A continuación, el número de intersección de G es como máximo de p + t . [2] [8]
Las gráficas que son el complemento de una gráfica dispersa tienen números de intersección pequeños: el número de intersección de cualquier gráfica de n -vértices G es como máximo 2 e 2 ( d + 1) 2 ln n , donde e es la base del logaritmo natural y d es el máximo grado de la gráfica complemento de G . [9]
Complejidad computacional [ editar ]
Prueba de si una gráfica dada G tiene número de intersección a lo sumo un número dado k es NP completo . [4] [10] [11] Por lo tanto, también es NP-difícil calcular el número de intersección de un gráfico dado.
Sin embargo, el problema de calcular el número de intersección es manejable con parámetros fijos : es decir, hay una función f tal que, cuando el número de intersección es k , el tiempo para calcularlo es, como máximo, el producto de f ( k ) y un polinomio en n . Esto se puede mostrar por observar que hay a lo sumo 2 k distintos barrios cerradosen el gráfico, dos vértices que pertenecen al mismo conjunto de camarillas tienen la misma vecindad, y que el gráfico formado al seleccionar un vértice por vecindario cerrado tiene el mismo número de intersección que el gráfico original. Por lo tanto, en tiempo polinómico, la entrada se puede reducir a un núcleo más pequeño con un máximo de 2 k vértices; aplicar un procedimiento de búsqueda de retroceso de tiempo exponencial a este núcleo lleva a una función f que es doble exponencial en k . [12] La dependencia doble exponencial de k no puede reducirse a exponencial simple mediante una kernelización de tamaño polinómico, a menos que ella jerarquía polinómica se colapsa, [13] y si la hipótesis del tiempo exponencial es verdadera, entonces la dependencia exponencial doble es necesaria independientemente de si se usa la kernelización. [14]
También se conocen algoritmos más eficientes para ciertas clases especiales de gráficos. El número de intersección de un gráfico de intervalos siempre es igual a su número de camarillas máximas , que pueden calcularse en tiempo polinómico. [15] [16] Más generalmente, en los gráficos cordales , el número de intersección puede calcularse mediante un algoritmo que considera los vértices en un orden de eliminación del gráfico y que, para cada vértice v , forma una camarilla para v y sus vecinos posteriores siempre que al menos uno de los bordes incidentes con v no esté cubierto por ninguna camarilla anterior.
No hay comentarios:
Publicar un comentario