En la teoría de grafos , una cubierta de camarilla o partición en camarillas de un gráfico no dirigido dado es una partición de los vértices del gráfico en camarillas , subconjuntos de vértices dentro de los cuales cada dos vértices son adyacentes. Una cubierta de camarilla mínima es una cubierta de camarilla que utiliza la menor cantidad posible de camarillas. El mínimo k para el cual existe una cubierta de camarilla se denomina número de cubierta de camarilla del gráfico dado.
Relación con la coloración [ editar ]
Una cubierta clique de un gráfico de G puede ser visto como un gráfico de la coloración de la gráfica complemento de G , el gráfico en el mismo conjunto de vértices que tiene bordes entre vértices no adyacentes de G . Al igual que las cubiertas de camarillas, los colores de los gráficos son particiones del conjunto de vértices, pero en subconjuntos sin adyacencias ( conjuntos independientes ) en lugar de camarillas. Un subconjunto de vértices es una camarilla en G si y solo si es un conjunto independiente en el complemento de G , por lo que una partición de los vértices de G es una cubierta de camarilla de G si y solo si es una coloración del complemento de G .
Complejidad computacional [ editar ]
El problema de la cobertura de camarilla en la teoría de la complejidad computacional es el problema algorítmico de encontrar una cobertura mínima de camarilla, o (reformulado como un problema de decisión ) encontrar una cobertura de camarilla cuyo número de camarillas está por debajo de un umbral dado. Encontrar una cobertura de camarilla mínima es NP-hard , y su versión de decisión es NP-complete . Fue uno de los 21 problemas originales de Richard Karp mostrados como NP completos en su artículo de 1972 "Reducibilidad entre problemas combinatorios". [1]
La equivalencia entre las cubiertas de la camarilla y la coloración es una reducción que se puede utilizar para demostrar la completitud NP del problema de la cubierta de la camarilla a partir de la completitud NP conocida de la coloración gráfica. [2]
En clases especiales de gráficos [ editar ]
Los gráficos perfectos se definen como los gráficos en los que, para cada subgrafo inducido , el número cromático (número mínimo de colores en una coloración) es igual al tamaño de la camarilla máxima . De acuerdo con el teorema del gráfico perfecto débil , el complemento de un gráfico perfecto también es perfecto. Por lo tanto, los gráficos perfectos son también los gráficos en los que, para cada subgrafo inducido, el número de cobertura de la camarilla es igual al tamaño del conjunto independiente máximo . Es posible calcular el número de portada de la camarilla en gráficos perfectos en tiempo polinómico .
Otra clase de gráficos en los que se puede encontrar la cobertura mínima de la camarilla en el tiempo polinómico son los gráficos sin triángulos . En estos gráficos, cada cubierta de camarilla consiste en una coincidencia (un conjunto de pares disjuntos de vértices adyacentes) junto con conjuntos de un solo tono para los vértices restantes no coincidentes. El número de camarillas es igual al número de vértices menos el número de pares coincidentes. Por lo tanto, en los gráficos sin triángulos, la cobertura de camarilla mínima se puede encontrar utilizando un algoritmo para una coincidencia máxima .
La partición óptima en camarillas también se puede encontrar en tiempo polinómico para gráficos de ancho de camarilla acotado . [3] Estos incluyen, entre otros gráficos, los cográficos y los gráficos hereditarios de distancia , que también son clases de gráficos perfectos.
Aproximación [ editar ]
La misma dureza de los resultados de aproximación que se conocen para la coloración de gráficos también se aplica a la cubierta de la camarilla. Por lo tanto, a menos que P = NP , no puede haber un algoritmo de aproximación de tiempo polinomial para cualquier ε > 0 que, en los gráficos de n -vértices, logre una relación de aproximación mejor que n 1 - ε . [4]
En los gráficos donde cada vértice tiene como máximo tres vecinos , la cubierta de la camarilla sigue siendo NP-dura, y hay una constante ρ > 1 tal que es NP-difícil de aproximar con una relación de aproximación ρ o mejor. Sin embargo, en el tiempo polinómico es posible encontrar una aproximación con relación 5/4. Es decir, este algoritmo de aproximación encuentra una cobertura de camarilla cuyo número de camarillas no es más de 5/4 veces el óptimo. [5]
Problemas relacionados [ editar ]
El problema relacionado con la cobertura del borde de la camarilla se refiere a la división de los bordes de un gráfico, en lugar de los vértices, en subgrafías inducidas por las camarillas. También es NP-completo.
En la teoría de grafos , el rango del ciclo de un grafo dirigido es un dígrafo conectividad medida propuesta por primera vez por Eggan y Büchi ( Eggan 1963 ). Intuitivamente, este concepto mide qué tan cerca está un dígrafo de un gráfico acíclico dirigido (DAG), en el sentido de que un DAG tiene un rango de ciclo cero, mientras que un dígrafo completo de orden n con un autociclo en cada vértice tiene un rango de ciclo n . El rango del ciclo de un gráfico dirigido está estrechamente relacionado con la profundidad del árbol de un gráfico no dirigido y con laaltura de estrella de un lenguaje regular . También se ha encontrado uso en cálculos de matriz dispersos (ver Bodlaender et al. 1995 ) y lógica ( Rossman 2008 ).
Definición [ editar ]
El rango de ciclo r ( G ) de un dígrafo G = ( V , E ) se define inductivamente de la siguiente manera:
- Si G es acíclico, entonces r ( G ) = 0 .
- Si G está fuertemente conectado y E no está vacío, entonces
-
- dónde es el dígrafo resultante de la eliminación del vértice v y todos los bordes que comienzan o terminan en v .
- Si G no está fuertemente conectado, entonces r ( G ) es igual al rango de ciclo máximo entre todos los componentes de G fuertemente conectados .
La profundidad del árbol de un gráfico no dirigido tiene una definición muy similar, utilizando conectividad no dirigida y componentes conectados en lugar de conectividad fuerte y componentes fuertemente conectados.
Historia [ editar ]
El rango de ciclo fue introducido por Eggan (1963) en el contexto de la altura de las estrellas de los idiomas regulares . Fue redescubierto por ( Eisenstat y Liu 2005 ) como una generalización de la profundidad de los árboles no dirigida , que se desarrolló a partir de la década de 1980 y se aplicó a cálculos de matriz dispersos ( Schreiber 1982 ).
Ejemplos [ editar ]
El rango de ciclo de un gráfico acíclico dirigido es 0, mientras que un dígrafo completo de orden n con un bucle automático en cada vértice tiene rango de ciclo n . Además de estos, se conoce el rango del ciclo de algunos otros dígrafos: el camino no dirigidode orden n , que posee una relación de borde simétrica y no tiene bucles automáticos, tiene rango de ciclo( McNaughton 1969 ). Para el dirigido-toro , Es decir, el producto cartesiano de dos circuitos dirigidos de longitudes m y n , tenemos y para m ≠ n ( Eggan 1963 , Gruber y Holzer 2008 ).
Calcular el rango del ciclo [ editar ]
Calcular el rango del ciclo es computacionalmente difícil: Gruber (2012) demuestra que el problema de decisión correspondiente es NP-completo , incluso para dígrafos dispersos de máximo grado máximo 2. En el lado positivo, el problema se puede resolver en el tiempoen dígrafos de grado máximo como máximo 2, y a tiempoen dígrafos generales. Hay un algoritmo de aproximación con relación de aproximación.
Aplicaciones [ editar ]
Altura de la estrella de los idiomas regulares [ editar ]
La primera aplicación del rango del ciclo fue en la teoría del lenguaje formal , para estudiar la altura de las estrellas de los idiomas regulares . Eggan (1963) estableció una relación entre las teorías de expresiones regulares, autómatas finitos y de gráficos dirigidos . En años posteriores, esta relación se conoció como el teorema de Eggan , cf. Sakarovitch (2009) . En la teoría de autómatas, un autómata finito no determinista con movimientos ε (ε-NFA) se define como una tupla de 5 , ( Q , Σ, δ , q 0 , F ), que consiste en
- un conjunto finito de estados Q
- un conjunto finito de símbolos de entrada Σ
- un conjunto de marcado bordes delta , denominado relación de transición : Q × (Σ ∪ {ε}) x Q . Aquí ε denota la palabra vacía .
- un estado inicial q 0 ∈ Q
- un conjunto de estados F distinguido como estados de aceptación F ⊆ Q .
El ε-NFA acepta una palabra w ∈ Σ * si existe una ruta dirigida desde el estado inicial q 0 a algún estado final en F utilizando bordes de δ , de modo que la concatenación de todas las etiquetas visitadas a lo largo de la ruta produce la palabra w . El conjunto de todas las palabras más de Σ * aceptadas por el autómata es el lenguaje aceptado por el autómata A .
Cuando hablamos de las propiedades del dígrafo de un autómata finito no determinista A con conjunto de estados Q , naturalmente abordamos el dígrafo con el conjunto de vértices Q inducido por su relación de transición. Ahora el teorema se establece de la siguiente manera.
- Eggan del Teorema : La altura estrella de un lenguaje regular L es igual al rango de ciclo mínimo entre todos los autómatas finitos no determinista con varepsilon mueve aceptar L .
Las pruebas de este teorema son dadas por Eggan (1963) , y más recientemente por Sakarovitch (2009) .
Factorización de Cholesky en cálculos de matriz dispersa [ editar ]
Otra aplicación de este concepto radica en los cálculos de matriz dispersa , a saber, para usar la disección anidada para calcular la factorización de Cholesky de una matriz (simétrica) en paralelo. Un dado escaso-matrix M puede ser interpretado como la matriz de adyacencia de algunos dígrafo simétrica G en n vértices, de tal manera que los no-cero entradas de la matriz están en correspondencia uno-a-uno con los bordes de G . Si el rango del ciclo del dígrafo G es como máximo k , entonces la factorización de Cholesky de M puede calcularse como máximo en k pasos en una computadora paralela conprocesadores ( Dereniowski y Kubale 2004 ).
En la teoría de grafos , un árbol de expansión con restricción de grado es un árbol de expansión donde el grado máximo de vértice está limitado a una cierta constante k . El problema del árbol de expansión limitado por el grado es determinar si un gráfico particular tiene dicho árbol de expansión para una k particular .
Definición formal [ editar ]
NP-completitud [ editar ]
Este problema es NP-completo ( Garey y Johnson 1979 ). Esto se puede demostrar mediante una reducción del problema del camino hamiltoniano . Sigue siendo NP completo incluso si k se fija a un valor ≥ 2. Si el problema se define como el grado debe ser ≤ k , el caso k = 2 del árbol de expansión confinado en grados es el problema del camino hamiltoniano.
Árbol de expansión mínimo con restricción de grado [ editar ]
En un gráfico ponderado, un árbol de expansión mínima con restricción de grado (DCMST) es un árbol de expansión con restricción de grado en el que la suma de sus bordes tiene la suma mínima posible. Encontrar un DCMST es un problema NP-Hard. [1]
Se han propuesto algoritmos heurísticos que pueden resolver el problema en tiempo polinómico, incluidos los algoritmos genéticos y basados en hormigas.
Algoritmo de aproximación [ editar ]
Fürer y Raghavachari (1994) dan un algoritmo iterativo de tiempo polinómico que, dado un gráfico, devuelve un árbol de expansión con un grado máximo no mayor que , dónde es el mínimo grado máximo posible sobre todos los árboles de expansión. Por lo tanto, si, dicho algoritmo devolverá un árbol de expansión de grado máximo o .
No hay comentarios:
Publicar un comentario