En teoría de grafos , un gráfico bien cubierto es un gráfico no dirigido en el que las cubiertas mínimas de vértices tienen todas el mismo tamaño. Aquí, una cobertura de vértice es un conjunto de vértices que toca todos los bordes, y es mínimo si al eliminar cualquier vértice se deja algún borde sin cubrir. De manera equivalente, los gráficos bien cubiertos son aquellos en los que todos los conjuntos independientes máximos tienen el mismo tamaño. Michael D. Plummer definió y estudió por primera vez gráficos bien cubiertos en 1970.
Los gráficos bien cubiertos incluyen todos los gráficos completos , gráficos bipartitos completos equilibrados y los gráficos de la torre cuyos vértices representan cuadrados de un tablero de ajedrez y los bordes representan movimientos de una torre de ajedrez. Las caracterizaciones conocidas de los gráficos cúbicos bien cubiertos , los gráficos sin garras bien cubiertos y los gráficos bien cubiertos de gran circunferencia permiten que estos gráficos se reconozcan en tiempo polinómico , pero probar si otros tipos de gráficos están bien cubiertos es un coNP -problema completo .
Una cobertura de vértices en un gráfico no dirigido es un conjunto de vértices que toca cada borde del gráfico. Una cobertura de vértice es mínima, o irredundante, si eliminar cualquier vértice destruiría la propiedad de cobertura: la eliminación causaría que algún borde quedara descubierto. Es mínimo si no existe otra cobertura de vértices con menos vértices. Un gráfico bien cubierto es aquel en el que cada cobertura mínima también es mínima. En el artículo original que define gráficos bien cubiertos, Plummer escribe que esto es "obviamente equivalente" a la propiedad de que cada dos cubiertas mínimas tienen el mismo número de vértices entre sí. [1]
Un conjunto independiente en un gráfico es un conjunto de vértices de los cuales no hay dos adyacentes entre sí. Si C es una cobertura de vértices en un gráfico G , el complemento de C debe ser un conjunto independiente y viceversa. C es una cobertura de vértice mínima si y solo si su complemento I es un conjunto independiente máximo, y C es una cobertura de vértice mínima si y solo si su complemento es un conjunto independiente máximo. Por lo tanto, un gráfico bien cubierto es, de manera equivalente, un gráfico en el que cada conjunto máximo independiente tiene el mismo tamaño, o un gráfico en el que cada conjunto máximo independiente es máximo. [2]
En el artículo original que define gráficos bien cubiertos, estas definiciones se restringieron a gráficos conectados , [3] aunque también son significativas para gráficos desconectados. Algunos autores posteriores han reemplazado el requisito de conectividad con el requisito más débil de que un gráfico bien cubierto no debe tener vértices aislados. [4] Tanto para gráficos conectados y bien cubiertos como para gráficos bien cubiertos sin vértices aislados, no puede haber vértices esenciales , vértices que pertenecen a cada cobertura mínima de vértices. Además, cada gráfico bien cubierto es un gráfico crítico para la cobertura de vértices en el sentido de que, para cada vértice v , eliminar v del gráfico produce un gráfico con una cobertura de vértice mínima más pequeña. [3]
El complejo de independencia de un gráfico G es el complejo simplicial que tiene un símplex para cada conjunto independiente en G. Se dice que un complejo simplicial es puro si todos sus simples máximos tienen la misma cardinalidad, por lo que un gráfico bien cubierto es equivalente a un gráfico con un complejo de independencia puro. [5]
Un gráfico de ciclo de longitud cuatro o cinco está bien cubierto: en cada caso, cada conjunto independiente máximo tiene tamaño dos. También están bien cubiertos un ciclo de longitud siete y un camino de longitud tres. [6] Cada gráfico completo está bien cubierto: cada conjunto independiente máximo consta de un solo vértice. De manera similar, cada gráfico de conglomerados (una unión disjunta de gráficos completos) está bien cubierto. [7] Un gráfico bipartito completo está bien cubierto si los dos lados de su bipartición tienen el mismo número de vértices, ya que estos son sus dos únicos conjuntos máximos independientes. El gráfico complementario de un gráfico sin triángulos y sin vértices aislados está bien cubierto: no tiene conjuntos independientes mayores que dos, y cada vértice se puede extender a un conjunto independiente de dos vértices. [6]
El gráfico de una torre está bien explicado: si se coloca cualquier conjunto de torres en un tablero de ajedrez de manera que no haya dos torres que se ataquen entre sí, siempre es posible seguir colocando más torres no atacantes hasta que haya una en cada fila y columna del tablero. tablero de ajedrez. [8] El gráfico cuyos vértices son las diagonales de un polígono simple y cuyas aristas conectan pares de diagonales que se cruzan está bien cubierto, porque sus conjuntos independientes máximos son triangulaciones del polígono y todas las triangulaciones tienen el mismo número de aristas. [9]
Si G es cualquier gráfico de n vértices, entonces el producto raíz de G con un gráfico de un borde (es decir, el gráfico H formado al agregar n nuevos vértices a G , cada uno de grado uno y cada uno adyacente a un vértice distinto en G ) está bien cubierto. Porque, un conjunto independiente máximo en H debe consistir en un conjunto independiente arbitrario en G junto con los vecinos de grado uno del conjunto complementario y, por lo tanto, debe tener tamaño n . [10] De manera más general, dado cualquier gráfico G junto con una cobertura de camarilla (una partición p de los vértices de G en camarillas), el gráfico G p formado agregando otro vértice a cada camarilla está bien cubierto; el producto arraigado es el caso especial de esta construcción cuando p consta de n camarillas de un vértice. [11] Por lo tanto, cada gráfico es un subgrafo inducido de un gráfico bien cubierto.
Favaron (1982) define un grafo muy bien cubierto como un grafo bien cubierto (posiblemente desconectado, pero sin vértices aislados) en el que cada conjunto máximo independiente (y por lo tanto también cada cobertura mínima de vértices) contiene exactamente la mitad de los vértices. Esta definición incluye los productos raíz de un gráfico G y un gráfico de una arista. También incluye, por ejemplo, los grafos bipartitos bien cubiertos estudiados por Ravindra (1977) y Berge (1981): en un grafo bipartito sin vértices aislados, ambos lados de cualquier bipartición forman conjuntos máximos independientes (y coberturas mínimas de vértices), por lo que Si el gráfico está bien cubierto, ambos lados deben tener el mismo número de vértices. En un gráfico bien cubierto con n vértices, sin vértices aislados, el tamaño de un conjunto independiente máximo es como máximo n /2 , por lo que los gráficos muy bien cubiertos son los gráficos bien cubiertos en los que el tamaño máximo del conjunto independiente es lo más grande posible. . [12]
Un gráfico bipartito G está bien cubierto si y sólo si tiene una coincidencia perfecta M con la propiedad de que, para cada arista uv en M , el subgrafo inducido de los vecinos de u y v forma un gráfico bipartito completo . [13] La caracterización en términos de coincidencias se puede extender desde gráficos bipartitos hasta gráficos muy bien cubiertos: un gráfico G está muy bien cubierto si y sólo si tiene una coincidencia perfecta M con las dos propiedades siguientes:
Además, si G está muy bien cubierto, entonces toda coincidencia perfecta en G satisface estas propiedades. [14]
Los árboles son un caso especial de gráficos bipartitos, y probar si un árbol está bien cubierto puede manejarse como un caso especial mucho más simple de caracterización de gráficos bipartitos bien cubiertos: si G es un árbol con más de dos vértices, es bien cubierto si y sólo si cada nodo no foliar del árbol es adyacente a exactamente una hoja. [13] La misma caracterización se aplica a los gráficos que son localmente similares a árboles, en el sentido de que las vecindades de bajo diámetro de cada vértice son acíclicas: si un gráfico tiene una circunferencia de ocho o más (de modo que, para cada vértice v , el subgrafo de vértices dentro de una distancia tres de v es acíclico), entonces está bien cubierto si y sólo si cada vértice de grado mayor que uno tiene exactamente un vecino de grado uno. [15] Una caracterización estrechamente relacionada pero más compleja se aplica a gráficos bien cubiertos de circunferencia cinco o más. [dieciséis]
Los gráficos cúbicos ( 3-regulares ) bien cubiertos se han clasificado: constan de siete ejemplos de 3 conectados , junto con tres familias infinitas de gráficos cúbicos con menor conectividad. [17]
Las siete gráficas cúbicas bien cubiertas de 3 conexiones son la gráfica completa K 4 , las gráficas del prisma triangular y del prisma pentagonal , la gráfica de Durero , la gráfica de utilidad K 3,3 , una gráfica de ocho vértices obtenida a partir de la gráfica de utilidad por una transformada Y-Δ , y el gráfico de Petersen generalizado de 14 vértices G (7,2) . [18] De estos gráficos, los primeros cuatro son gráficos planos . Son los únicos cuatro gráficos poliédricos cúbicos (gráficos de poliedros convexos simples ) que están bien cubiertos. [19] Cuatro de los gráficos (los dos prismas, el gráfico de Durero y G (7,2) ) son gráficos de Petersen generalizados.
Los gráficos cúbicos bien cubiertos de 1 y 2 conectados se forman reemplazando los nodos de una ruta o ciclo por tres fragmentos de gráficos que Plummer (1993) denomina A , B y C. Los fragmentos A o B se pueden usar para reemplazar los nodos de un ciclo o los nodos interiores de una ruta, mientras que el fragmento C se usa para reemplazar los dos nodos finales de una ruta. El fragmento A contiene un puente , por lo que el resultado de realizar este proceso de reemplazo en una ruta y usar el fragmento A para reemplazar algunos de los nodos de la ruta (y los otros dos fragmentos para los nodos restantes) es un bien cubierto cúbico conectado con 1 vértice. grafico. Todos los gráficos cúbicos bien cubiertos con 1 vértice conectados tienen esta forma, y todos esos gráficos son planos. [17]
Hay dos tipos de gráficos cúbicos bien cubiertos de 2 vértices conectados. Una de estas dos familias se forma sustituyendo los nodos de un ciclo por los fragmentos A y B , siendo al menos dos de los fragmentos de tipo A ; un gráfico de este tipo es plano si y sólo si no contiene ningún fragmento de tipo B. La otra familia se forma sustituyendo los nodos de un camino por fragmentos de tipo B y C ; todos estos gráficos son planos. [17]
Complementando la caracterización de poliedros simples bien cubiertos en tres dimensiones, los investigadores también han considerado los poliedros simpliciales bien cubiertos o, de manera equivalente, los grafos planos máximos bien cubiertos. Cada gráfico plano máximo con cinco o más vértices tiene conectividad de vértice 3, 4 o 5. [20] No hay gráficos planos máximos de 5 conexiones bien cubiertos, y solo hay cuatro gráficos planos máximos de 4 conexiones bien cubiertos: las gráficas del octaedro regular , la bipirámide pentagonal , el disfenoide chato y un poliedro irregular (un deltaedro no convexo ) con 12 vértices, 30 aristas y 20 caras triangulares. Sin embargo, hay infinitos gráficos planos máximos bien cubiertos de 3 conectados. [21] Por ejemplo, si un gráfico plano máximo de 3 t vértices tiene t caras triangulares disjuntas, entonces estas caras formarán una cubierta de camarilla. Por lo tanto, la construcción de cobertura de camarilla, que para estos gráficos consiste en subdividir cada uno de estos triángulos t en tres nuevos triángulos que se encuentran en un vértice central, produce un gráfico plano máximo bien cubierto. [22]
Probar si un gráfico contiene dos conjuntos máximos independientes de diferentes tamaños es NP-completo ; es decir, de manera complementaria, probar si un gráfico está bien cubierto es coNP completo. [23] Aunque es fácil encontrar conjuntos máximos independientes en gráficos que se sabe que están bien cubiertos, también es NP-difícil para un algoritmo producir como salida, en todos los gráficos, ya sea un conjunto máximo independiente o una garantía de que la entrada no está bien cubierta. [24]
Por el contrario, es posible probar si un gráfico dado G está muy bien cubierto en tiempo polinomial . Para hacerlo, encuentre el subgrafo H de G que consta de las aristas que satisfacen las dos propiedades de una arista coincidente en un gráfico muy bien cubierto y luego use un algoritmo de coincidencia para probar si H tiene una coincidencia perfecta. [14] Algunos problemas que son NP-completos para gráficos arbitrarios, como el problema de encontrar un ciclo hamiltoniano , también pueden resolverse en tiempo polinomial para gráficos muy bien cubiertos. [25]
Se dice que un gráfico es equiemparejable si cada coincidencia máxima es máxima; es decir, es equiemparable si su gráfico lineal está bien cubierto. [26] Más fuertemente se llama emparejamiento aleatorio si cada emparejamiento máximo es un emparejamiento perfecto . Los únicos gráficos conectados que se pueden emparejar aleatoriamente son los gráficos completos y los gráficos bipartitos completos equilibrados. [27] Es posible comprobar si un gráfico lineal, o más generalmente un gráfico sin garras , está bien cubierto en tiempo polinomial. [28]
Las caracterizaciones de gráficos bien cubiertos con circunferencia cinco o más, y de gráficos bien cubiertos que son 3-regulares, también conducen a algoritmos de tiempo polinómico eficientes para reconocer estos gráficos. [29]
