En teoría de grafos , un cografo , o grafo reducible por complemento , o grafo libre de P 4 , es un grafo que se puede generar a partir del grafo de un solo vértice K 1 mediante complementación y unión disjunta . Es decir, la familia de cografos es la clase más pequeña de grafos que incluye a K 1 y está cerrada bajo complementación y unión disjunta.
Los cografos han sido descubiertos independientemente por varios autores desde la década de 1970; las primeras referencias incluyen Jung (1978), Lerchs (1971), Seinsche (1974) y Sumner (1974). También se han llamado D*-grafos , [1] grafos de Dacey hereditarios (en honor al trabajo relacionado de James C. Dacey Jr. sobre redes ortomodulares ), [2] y grafos de 2 paridades . [3] Tienen una descomposición estructural simple que involucra operaciones de unión disjunta y grafos complementarios que pueden representarse de manera concisa mediante un árbol etiquetado y usarse algorítmicamente para resolver de manera eficiente muchos problemas, como encontrar la camarilla máxima , que son difíciles en clases de grafos más generales.
Los casos especiales de los cografos incluyen los grafos completos , los grafos bipartitos completos , los grafos de conglomerados y los grafos de umbral . Los cografos son, a su vez, casos especiales de los grafos hereditarios de distancia , los grafos de permutación , los grafos de comparabilidad y los grafos perfectos .
Cualquier cografo puede construirse utilizando las siguientes reglas:
Los cografos pueden definirse como los grafos que pueden construirse utilizando estas operaciones, a partir de los grafos de un solo vértice. [4] Alternativamente, en lugar de utilizar la operación de complemento, se puede utilizar la operación de unión, que consiste en formar la unión disjunta y luego agregar una arista entre cada par de un vértice de y un vértice de .
Se pueden dar varias caracterizaciones alternativas de los cografos, entre ellas:
Un coárbol es un árbol en el que los nodos internos están etiquetados con los números 0 y 1. Cada coárbol T define un cografo G que tiene las hojas de T como vértices, y en el que el subárbol enraizado en cada nodo de T corresponde al subgrafo inducido en G definido por el conjunto de hojas que descienden de ese nodo:
Una forma equivalente de describir el cografo formado a partir de un coárbol es que dos vértices están conectados por una arista si y solo si el ancestro común más bajo de las hojas correspondientes está etiquetado con 1. A la inversa, cada cografo puede representarse de esta manera mediante un coárbol. Si requerimos que las etiquetas en cualquier camino de raíz a hoja de este árbol alternen entre 0 y 1, esta representación es única. [4]
Los cografos se pueden reconocer en tiempo lineal y se puede construir una representación de co-árbol mediante descomposición modular , [9] refinamiento de partición , [10] LexBFS , [11] o descomposición dividida . [12] Una vez que se ha construido una representación de co-árbol, muchos problemas gráficos familiares se pueden resolver mediante cálculos simples de abajo hacia arriba en los co-árboles.
Por ejemplo, para encontrar la camarilla máxima en un cografo, calcule en orden ascendente la camarilla máxima en cada subgrafo representado por un subárbol del co-árbol. Para un nodo etiquetado como 0, la camarilla máxima es la máxima entre las camarillas calculadas para los hijos de ese nodo. Para un nodo etiquetado como 1, la camarilla máxima es la unión de las camarillas calculadas para los hijos de ese nodo, y tiene un tamaño igual a la suma de los tamaños de camarilla de los hijos. Por lo tanto, al maximizar y sumar alternativamente los valores almacenados en cada nodo del co-árbol, podemos calcular el tamaño máximo de camarilla, y al maximizar y tomar uniones alternativamente, podemos construir la camarilla máxima en sí. Cálculos de árboles ascendentes similares permiten calcular el conjunto independiente máximo , el número de coloración de vértices , la cobertura máxima de camarillas y la hamiltonicidad (es decir, la existencia de un ciclo hamiltoniano ) en tiempo lineal a partir de una representación de co-árbol de un cografo. [4] Debido a que los cografos tienen un ancho de camarilla limitado, el teorema de Courcelle puede usarse para probar cualquier propiedad en la lógica monádica de segundo orden de los grafos (MSO 1 ) en cografos en tiempo lineal. [13]
El problema de probar si un grafo dado está a k vértices de distancia y/o t aristas de distancia de un cografo es manejable con parámetros fijos . [14] Decidir si un grafo puede ser eliminado por k aristas para convertirse en un cografo se puede resolver en un tiempo O * (2.415 k ), [15] y editado por k aristas para convertirse en un cografo en O * (4.612 k ). [16] Si el subgrafo de cografo inducido más grande de un grafo se puede encontrar eliminando k vértices del grafo, se puede encontrar en un tiempo O * (3.30 k ). [15]
Dos cografos son isomorfos si y solo si sus coárboles (en la forma canónica sin dos vértices adyacentes con la misma etiqueta) son isomorfos. Debido a esta equivalencia, se puede determinar en tiempo lineal si dos cografos son isomorfos, construyendo sus coárboles y aplicando una prueba de isomorfismo en tiempo lineal para árboles etiquetados. [4]
Si H es un subgrafo inducido de un cografo G , entonces H es en sí mismo un cografo; el co-árbol para H puede formarse eliminando algunas de las hojas del co-árbol para G y luego suprimiendo los nodos que tienen solo un hijo. Se deduce del teorema del árbol de Kruskal que la relación de ser un subgrafo inducido es un buen cuasi-ordenamiento en los cografos. [17] Por lo tanto, si una subfamilia de los cografos (como los cografos planares ) está cerrada bajo operaciones de subgrafos inducidos, entonces tiene un número finito de subgrafos inducidos prohibidos . Computacionalmente, esto significa que la prueba de pertenencia a dicha subfamilia puede realizarse en tiempo lineal, utilizando un cálculo de abajo hacia arriba en el co-árbol de un grafo dado para probar si contiene alguno de estos subgrafos prohibidos. Sin embargo, cuando los tamaños de dos cografos son ambos variables, probar si uno de ellos es un subgrafo inducido del otro es NP-completo . [18]
Los cografos juegan un papel clave en los algoritmos para reconocer funciones de lectura única . [19]
Algunos problemas de conteo también se pueden resolver cuando la entrada se limita a un cografo. Por ejemplo, existen algoritmos de tiempo polinómico para contar la cantidad de camarillas o la cantidad máxima de camarillas en un cografo. [4]
El número de cografos conexos con n vértices, para n = 1, 2, 3, ..., es:
Para n > 1 hay el mismo número de cografos conexos, porque para cada cografo exactamente uno de él o su grafo complementario es conexo.
Todo grafo completo K n es un cografo, con un co-árbol que consiste en un solo nodo 1 y n hojas. De manera similar, todo grafo bipartito completo K a , b es un cografo. Su co-árbol tiene su raíz en un nodo 1 que tiene dos hijos de nodos 0, uno con hijos de hoja a y otro con hijos de hoja b . Un grafo de Turán puede formarse mediante la unión de una familia de conjuntos independientes de igual tamaño; por lo tanto, también es un cografo, con un co-árbol con raíz en un nodo 1 que tiene un nodo 0 hijo para cada conjunto independiente.
Todo grafo de umbral es también un cografo. Un grafo de umbral puede formarse añadiendo repetidamente un vértice, ya sea conectado a todos los vértices anteriores o a ninguno de ellos; cada una de estas operaciones es una de las operaciones de unión disjunta o de unión mediante las cuales se puede formar un co-árbol. [20]
La caracterización de los cografos por la propiedad de que cada camarilla y conjunto independiente maximal tienen una intersección no vacía es una versión más fuerte de la propiedad definitoria de los grafos fuertemente perfectos , en los que cada subgrafo inducido contiene un conjunto independiente que interseca a todas las camarillas maximal. En un cografo, cada conjunto independiente maximal interseca a todas las camarillas maximal. Por lo tanto, cada cografo es fuertemente perfecto. [21]
El hecho de que los cografos no tengan P 4 implica que son perfectamente ordenables . De hecho, cada orden de vértice de un cografo es un orden perfecto, lo que implica además que la búsqueda de clique máximo y la coloración mínima se pueden encontrar en tiempo lineal con cualquier coloración voraz y sin la necesidad de una descomposición en coárbol.
Cada cografo es un grafo hereditario de distancia , lo que significa que cada camino inducido en un cografo es un camino más corto . Los cografos pueden caracterizarse entre los grafos hereditarios de distancia por tener un diámetro de como máximo dos en cada componente conectado. Cada cografo es también un grafo de comparabilidad de un orden parcial serie-paralelo , obtenido al reemplazar las operaciones de unión disjunta y de unión por las que se construyó el cografo por operaciones de unión disjunta y de suma ordinal en órdenes parciales. Debido a que los grafos fuertemente perfectos, los grafos perfectamente ordenables, los grafos hereditarios de distancia y los grafos de comparabilidad son todos grafos perfectos , los cografos también son perfectos. [20]
