(Redirigido desde Máximo conjunto independiente )
En la teoría de grafos , un conjunto independiente , conjunto estable , coclique o anti clique es un conjunto de vértices en un gráfico , ninguno de los cuales es adyacente. Es decir, es un conjunto de vértices de tal manera que por cada dos vértices en , no hay borde que conecte los dos. De manera equivalente, cada borde en el gráfico tiene como máximo un punto final en. El tamaño de un conjunto independiente es el número de vértices que contiene. Los conjuntos independientes también se han denominado conjuntos internamente estables. [1]
Un conjunto independiente máximo es un conjunto independiente que no es un subconjunto adecuado de ningún otro conjunto independiente.
Un conjunto independiente máximo es un conjunto independiente del mayor tamaño posible para un gráfico dado. Este tamaño se llama el número de independencia dey denotado . [2] El problema de encontrar un conjunto de este tipo se denomina problema de conjunto independiente máximo y es un problema de optimización NP-hard . Como tal, es poco probable que exista un algoritmo eficiente para encontrar un conjunto máximo independiente de un gráfico.
Cada conjunto independiente máximo también es máximo, pero la implicación inversa no se cumple necesariamente.
Propiedades [ editar ]
Relación con otros parámetros del gráfico [ editar ]
Un conjunto es independiente si y solo si es una camarilla en el complemento del gráfico , por lo que los dos conceptos son complementarios. De hecho, los gráficos suficientemente grandes sin grandes camarillas tienen grandes conjuntos independientes, un tema que se explora en la teoría de Ramsey .
Un conjunto es independiente si y solo si su complemento es una cubierta de vértice . [3] Por lo tanto, la suma del tamaño del conjunto independiente más grande y el tamaño de una cubierta mínima de vértice es igual al número de vértices en el gráfico.
Una coloración de vértice de un gráficocorresponde a una partición de su conjunto de vértices en subconjuntos independientes. De ahí la cantidad mínima de colores necesarios en una coloración de vértice, el número cromático , es al menos el cociente del número de vértices en y el número independiente .
En un gráfico bipartito sin vértices aislados, el número de vértices en un conjunto independiente máximo es igual al número de aristas en una cubierta de arista mínima ; Este es el teorema de Kőnig .
Conjunto independiente máximo [ editar ]
Un conjunto independiente que no es un subconjunto adecuado de otro conjunto independiente se denomina máximo . Tales conjuntos son conjuntos dominantes . Cada gráfico contiene como máximo 3 n / 3 conjuntos independientes máximos, [4] pero muchos gráficos tienen muchos menos. El número de conjuntos independientes máximos en los gráficos de ciclo de n - vértices viene dado por los números de Perrin , y el número de conjuntos independientes máximos en los gráficos de trayectoria de n - vértices está dado por la secuencia de Padovan . [5] Por lo tanto, ambos números son proporcionales a las potencias de 1.324718 ..., el número plástico .
Encontrar conjuntos independientes [ editar ]
En informática , se han estudiado varios problemas computacionales relacionados con conjuntos independientes.
- En el problema de conjunto independiente máximo , la entrada es un gráfico no dirigido y la salida es un conjunto independiente máximo en el gráfico. Si hay varios conjuntos independientes máximos, solo se debe generar uno. Este problema a veces se denomina " empaquetamiento de vértices ".
- En el problema del conjunto independiente de peso máximo , la entrada es un gráfico no dirigido con pesos en sus vértices y la salida es un conjunto independiente con peso total máximo. El problema del conjunto máximo independiente es el caso especial en el que todos los pesos son uno.
- En el problema de la lista de conjuntos independientes máximos , la entrada es un gráfico no dirigido y la salida es una lista de todos sus conjuntos independientes máximos. El problema del conjunto máximo independiente puede resolverse utilizando como subrutina un algoritmo para el problema de listado de conjunto independiente máximo, porque el conjunto independiente máximo debe incluirse entre todos los conjuntos independientes máximos.
- En el problema de decisión de conjunto independiente , la entrada es un gráfico no dirigido y un número k , y el resultado es un valor booleano : verdadero si el gráfico contiene un conjunto independiente de tamaño k , y falso en caso contrario.
Los primeros tres de estos problemas son importantes en aplicaciones prácticas; el problema de decisión de conjunto independiente no lo es, pero es necesario para aplicar la teoría de la completitud de NP a problemas relacionados con conjuntos independientes.
Máximo conjunto independiente y máximo camarillas [ editar ]
El problema del conjunto independiente y el problema de la camarilla son complementarios: una camarilla en G es un conjunto independiente en el gráfico complementario de G y viceversa. Por lo tanto, muchos resultados computacionales pueden aplicarse igualmente bien a cualquiera de los problemas. Por ejemplo, los resultados relacionados con el problema de la camarilla tienen los siguientes corolarios:
- El problema de decisión de conjunto independiente es NP-completo , y por lo tanto no se cree que haya un algoritmo eficiente para resolverlo.
- El problema del conjunto independiente máximo es NP-hard y también es difícil de aproximar .
A pesar de la estrecha relación entre camarillas máximas y conjuntos independientes máximos en gráficos arbitrarios, los problemas de conjuntos independientes y camarillas pueden ser muy diferentes cuando se restringen a clases especiales de gráficos. Por ejemplo, para gráficos dispersos (gráficos en los que el número de aristas es como máximo constante por el número de vértices en cualquier subgrafo), la camarilla máxima tiene un tamaño acotado y se puede encontrar exactamente en tiempo lineal; [6] sin embargo, para las mismas clases de gráficos, o incluso para la clase más restringida de gráficos de grado acotado, encontrar el conjunto independiente máximo es MAXSNP completo , lo que implica que, para alguna constante c (dependiendo del grado), es NP -difícilpara encontrar una solución aproximada que se encuentre dentro de un factor de c óptimo. [7]
Encontrar conjuntos independientes máximos [ editar ]
Algoritmos exactos [ editar ]
El problema del conjunto independiente máximo es NP-hard. Sin embargo, se puede resolver de manera más eficiente que el tiempo O ( n 2 2 n ) que le daría un algoritmo de fuerza bruta ingenuo que examina cada subconjunto de vértices y comprueba si es un conjunto independiente.
A partir de 2017 se puede resolver en el tiempo O (1.1996 n ) utilizando el espacio polinomial [8] . Cuando se limita a gráficos con un grado máximo 3, se puede resolver en el tiempo O (1.0836 n ) [9] .
Para muchas clases de gráficos, se puede encontrar un conjunto independiente de peso máximo en el tiempo polinómico. Ejemplos famosos son gráficos sin garras , [10] gráficos sin P 5 [11] y gráficos perfectos . [12] Para gráficos cordales , se puede encontrar un conjunto independiente de peso máximo en tiempo lineal. [13]
La descomposición modular es una buena herramienta para resolver el problema del conjunto independiente de peso máximo; El algoritmo de tiempo lineal en los cogramas es el ejemplo básico para eso. Otra herramienta importante son los separadores de camarillas como lo describe Tarjan. [14]
El teorema de Kőnig implica que en un gráfico bipartito, el conjunto independiente máximo se puede encontrar en tiempo polinómico usando un algoritmo de coincidencia bipartito.
Algoritmos de aproximación [ editar ]
En general, el problema del conjunto independiente máximo no se puede aproximar a un factor constante en el tiempo polinómico (a menos que P = NP). De hecho, Max Independent Set en general es Poly-APX-complete , lo que significa que es tan difícil como cualquier problema que pueda aproximarse a un factor polinomial. [15] Sin embargo, existen algoritmos de aproximación eficientes para clases restringidas de gráficos.
En los gráficos planos , el conjunto independiente máximo puede aproximarse dentro de cualquier relación de aproximación c <1 en="" font="" mico="" nbsp="" polin="" tiempo="">existen esquemas de aproximación de tiempo polinomial similares en cualquier familia de gráficos cerrados bajo toma de menores . [dieciséis]
En los gráficos de grado acotado, se conocen algoritmos de aproximación efectivos con relaciones de aproximación que son constantes para un valor fijo del grado máximo; Por ejemplo, un algoritmo codicioso que forma un conjunto independiente máximo al, en cada paso, eligiendo el vértice de grado mínimo en el gráfico y eliminando sus vecinos, logra una relación de aproximación de (Δ + 2) / 3 en gráficos con un grado máximo Δ. [17] Los límites de dureza de aproximación para tales casos se probaron en Berman y Karpinski (1999) . De hecho, incluso Max Independent Set en 3 gráficos regulares de 3 bordes colorables es APX-complete . [18]
Conjuntos independientes en gráficos de intersección de intervalos [ editar ]
Un gráfico de intervalos es un gráfico en el que los nodos son intervalos unidimensionales (por ejemplo, intervalos de tiempo) y hay un borde entre dos intervalos si se cruzan. Un conjunto independiente en un gráfico de intervalos es solo un conjunto de intervalos no superpuestos. Se ha estudiado el problema de encontrar conjuntos independientes máximos en gráficos de intervalos, por ejemplo, en el contexto de la programación de trabajos : dado un conjunto de trabajos que deben ejecutarse en una computadora, encuentre un conjunto máximo de trabajos que puedan ejecutarse sin interferir juntos. Este problema se puede resolver exactamente en tiempo polinómico usando la primera programación de fecha límite más temprana .
Conjuntos independientes en gráficos de intersección geométrica [ editar ]
Un gráfico de intersección geométrica es un gráfico en el que los nodos son formas geométricas y hay un borde entre dos formas si se cruzan. Un conjunto independiente en un gráfico de intersección geométrica es solo un conjunto de formas disjuntas (no superpuestas). Se ha estudiado el problema de encontrar conjuntos independientes máximos en gráficos de intersección geométrica, por ejemplo, en el contexto de la colocación automática de etiquetas : dado un conjunto de ubicaciones en un mapa, encuentre un conjunto máximo de etiquetas rectangulares disjuntas cerca de estas ubicaciones.
Encontrar un conjunto independiente máximo en los gráficos de intersección todavía es NP-completo, pero es más fácil de aproximar que el problema general del conjunto independiente máximo. Se puede encontrar una encuesta reciente en la introducción de Chan y Har-Peled (2012) .
Encontrar conjuntos independientes máximos [ editar ]
El problema de encontrar un conjunto independiente máximo se puede resolver en tiempo polinómico mediante un algoritmo codicioso trivial . [19] Todos los conjuntos independientes máximos se pueden encontrar en el tiempo O (3 n / 3 ) = O (1.4423 n ).
Software para buscar el máximo conjunto independiente [ editar ]
| Nombre | Licencia | Lenguaje API | Breve informacion |
|---|---|---|---|
| igraph | GPL | C, Python, R, Ruby | solución exacta "La implementación actual fue portada a igraph desde la Very Very Nauty Graph Library por Keith Briggs y utiliza el algoritmo del artículo S. Tsukiyama, M. Ide, H. Ariyoshi e I. Shirawaka. Un nuevo algoritmo para generar todos los conjuntos independientes máximos . SIAM J Computing, 6: 505–517, 1977 ". |
| NetworkX | BSD | Pitón | solución aproximada, vea la rutina maximum_independent_set |
| mal | Abierto | Óxido (binarios) | solución aproximada por muestreo aleatorio del espacio máximo independiente establecido, vea la página web para más detalles |
En la matemática área de la teoría de grafos , un camino inducida en un grafo no dirigido G es un camino que es un subgrafo inducido de G . Es decir, es una secuencia de vértices en G tal que cada dos vértices adyacentes en la secuencia están conectados por una arista en G , y cada dos vértices no adyacentes en la secuencia no están conectados por cualquier borde en G . Una ruta inducida a veces se llama serpiente , y el problema de encontrar rutas inducidas largas en gráficos de hipercubos se conoce como el problema de la serpiente en la caja .
Del mismo modo, un ciclo inducido es un ciclo que es un subgrafo inducido de G ; Los ciclos inducidos también se denominan ciclos sin cuerda o (cuando la duración del ciclo es de cuatro o más) agujeros . Un antiagujero es un agujero en el complemento de G , es decir, un antiagujero es un complemento de un agujero.
La longitud del camino inducido más largo en un gráfico a veces se denomina número de desvío del gráfico; [1] para gráficos dispersos , tener un número de desvío acotado es equivalente a tener una profundidad de árbol acotada . [2] El número de ruta inducida de un gráfico G es el número más pequeño de rutas inducidas en las que se pueden dividir los vértices del gráfico, [3] y el número de cobertura de ruta estrechamente relacionado de G es el número más pequeño de rutas inducidas que juntas incluir todos los vértices de G . [4] La circunferenciade un gráfico es la longitud de su ciclo más corto, pero este ciclo debe ser un ciclo inducido ya que cualquier cuerda podría usarse para producir un ciclo más corto; Por razones similares, la circunferencia impar de un gráfico es también la longitud de su ciclo inducido impar más corto.
Ejemplo [ editar ]
La ilustración muestra un cubo, un gráfico con ocho vértices y doce aristas, y una trayectoria inducida de longitud cuatro en este gráfico. Un análisis de caso directo muestra que ya no puede haber una ruta inducida en el cubo, aunque tiene un ciclo inducido de longitud seis. El problema de encontrar la ruta o ciclo inducido más largo en un hipercubo, planteado por primera vez por Kautz (1958) , se conoce como el problema de la serpiente en la caja , y se ha estudiado ampliamente debido a sus aplicaciones en la teoría y la ingeniería de codificación. .
Caracterización de familias de grafos [ editar ]
Muchas familias importantes de gráficos se pueden caracterizar en términos de los caminos o ciclos inducidos de los gráficos en la familia.
- Trivialmente, los gráficos conectados sin trayectoria inducida de longitud dos son los gráficos completos , y los gráficos conectados sin ciclo inducido son los árboles .
- Un gráfico sin triángulo es un gráfico sin ciclo inducido de longitud tres.
- Los cogramas son exactamente los gráficos sin trayectoria inducida de longitud tres.
- Los gráficos cordales son los gráficos sin ciclo inducido de longitud cuatro o más.
- Los gráficos libres de agujeros pares son los gráficos que no contienen ciclos inducidos con un número par de vértices.
- Los gráficos trivialmente perfectos son los gráficos que no tienen una trayectoria inducida de longitud tres ni un ciclo inducido de longitud cuatro.
- Por el fuerte teorema del gráfico perfecto, los gráficos perfectos son los gráficos sin agujeros impares y sin antihojos impares.
- Los gráficos hereditarios de distancia son los gráficos en los que cada camino inducido es un camino más corto, y los gráficos en los que cada dos caminos inducidos entre los mismos dos vértices tienen la misma longitud.
- Los gráficos de bloque son los gráficos en los que hay como máximo una ruta inducida entre dos vértices, y los gráficos de bloques conectados son los gráficos en los que hay exactamente una ruta inducida entre cada dos vértices.
Algoritmos y complejidad [ editar ]
Es NP-completo determinar, para un gráfico G y el parámetro k , si el gráfico tiene una trayectoria inducida de longitud al menos k . Garey y Johnson (1979) atribuyen este resultado a una comunicación no publicada de Mihalis Yannakakis . Sin embargo, este problema se puede resolver en tiempo polinómico para ciertas familias de gráficos, como los gráficos libres de asteroides triples [5] o gráficos sin agujeros largos. [6]
También es NP-complete para determinar si los vértices de un gráfico pueden dividirse en dos caminos inducidos, o dos ciclos inducidos. [7] Como consecuencia, determinar el número de ruta inducida de un gráfico es NP-duro.
La complejidad de aproximar el camino inducido más largo o los problemas del ciclo puede estar relacionada con la de encontrar grandes conjuntos independientes en gráficos, mediante la siguiente reducción. [8] Desde cualquier gráfico G con n vértices, formar otro gráfico H con el doble de vértices como G , mediante la adición a G n ( n - 1) / 2 vértices que tienen dos vecinos cada uno, uno para cada par de vértices en G . Entonces, si G tiene un conjunto independiente de tamaño k , H debe tener una trayectoria inducida y un ciclo inducido de longitud 2 k, Formada por la alternancia de vértices del conjunto independiente en G con vértices de I . Por el contrario, si H tiene una trayectoria o ciclo inducido de longitud k , cualquier conjunto máximo de vértices no adyacentes en G a partir de esta trayectoria o ciclo forma un conjunto independiente en G de tamaño al menos k / 3. Así, el tamaño del máximo conjunto independiente en G está dentro de un factor constante del tamaño de la trayectoria más larga inducida y el ciclo inducida más largo en H . Por lo tanto, según los resultados de Håstad (1996)sobre la inaccesibilidad de conjuntos independientes, a menos que NP = ZPP, no exista un algoritmo de tiempo polinómico para aproximar la ruta inducida más larga o el ciclo inducido más largo dentro de un factor de O ( n 1/2-ε ) de la solución óptima.
Los agujeros (y antiholes en gráficos sin ciclos sin cuerda de longitud 5) en un gráfico con n vértices ym bordes pueden detectarse en el tiempo (n + m 2 ). [9]
Ciclos atómicos [ editar ]
Los ciclos atómicos son una generalización de los ciclos sin acordes , que no contienen n- acordes. Dado algún ciclo, un acorde n se define como una ruta de longitud n que conecta dos puntos en el ciclo, donde n es menor que la longitud de la ruta más corta en el ciclo que conecta esos puntos. Si un ciclo no tiene n acordes, se llama ciclo atómico, porque no puede descomponerse en ciclos más pequeños. [10] En el peor de los casos, los ciclos atómicos en un gráfico se pueden enumerar en el tiempo O ( m 2 ), donde m es el número de aristas en el gráfico.
No hay comentarios:
Publicar un comentario