En el área matemática de la teoría de grafos , un grafo cordal es uno en el que todos los ciclos de cuatro o más vértices tienen una cuerda , que es una arista que no es parte del ciclo pero que conecta dos vértices del ciclo. Equivalentemente, cada ciclo inducido en el grafo debe tener exactamente tres vértices. Los grafos cordales también pueden caracterizarse como los grafos que tienen ordenamientos de eliminación perfectos, como los grafos en los que cada separador mínimo es una camarilla y como los grafos de intersección de subárboles de un árbol. A veces también se les llama grafos de circuito rígido [1] o grafos triangulados : [2] una completitud cordal de un grafo normalmente se llama triangulación de ese grafo.
Los grafos cordales son un subconjunto de los grafos perfectos . Se pueden reconocer en tiempo lineal y varios problemas que son difíciles para otras clases de grafos, como la coloración de grafos, se pueden resolver en tiempo polinomial cuando la entrada es cordal. El ancho del árbol de un grafo arbitrario se puede caracterizar por el tamaño de las camarillas en los grafos cordales que lo contienen.
Un ordenamiento de eliminación perfecto en un grafo es un ordenamiento de los vértices del grafo de modo que, para cada vértice v , v y los vecinos de v que aparecen después de v en el ordenamiento forman una camarilla . Un grafo es cordal si y solo si tiene un ordenamiento de eliminación perfecto. [3]
Rose, Lueker y Tarjan (1976) (véase también Habib et al. 2000) muestran que se puede encontrar un ordenamiento de eliminación perfecto de un grafo cordal de manera eficiente utilizando un algoritmo conocido como búsqueda lexicográfica en amplitud . Este algoritmo mantiene una partición de los vértices del grafo en una secuencia de conjuntos; inicialmente esta secuencia consiste en un único conjunto con todos los vértices. El algoritmo elige repetidamente un vértice v del conjunto más antiguo de la secuencia que contiene vértices no elegidos previamente, y divide cada conjunto S de la secuencia en dos subconjuntos más pequeños, el primero formado por los vecinos de v en S y el segundo formado por los no vecinos. Cuando se ha realizado este proceso de división para todos los vértices, la secuencia de conjuntos tiene un vértice por conjunto, en el reverso de un ordenamiento de eliminación perfecto.
Dado que tanto este proceso de búsqueda en amplitud lexicográfica como el proceso de prueba de si un ordenamiento es un ordenamiento de eliminación perfecto se pueden realizar en tiempo lineal , es posible reconocer grafos cordales en tiempo lineal. El problema del sándwich de grafos en grafos cordales es NP-completo [4], mientras que el problema del grafo de prueba en grafos cordales tiene una complejidad de tiempo polinomial. [5]
El conjunto de todos los ordenamientos de eliminación perfectos de un gráfico cordal se puede modelar como las palabras básicas de un antimatroide ; Chandran et al. (2003) utilizan esta conexión con los antimatroides como parte de un algoritmo para enumerar de manera eficiente todos los ordenamientos de eliminación perfectos de un gráfico cordal dado.
Otra aplicación de los ordenamientos de eliminación perfecta es encontrar un clique máximo de un grafo cordal en tiempo polinomial, mientras que el mismo problema para grafos generales es NP-completo . De manera más general, un grafo cordal puede tener solo un número lineal de cliques máximos , mientras que los grafos no cordales pueden tener un número exponencial. Esto implica que la clase de grafos cordales tiene pocos cliques . Para enumerar todos los cliques máximos de un grafo cordal, simplemente encuentre un ordenamiento de eliminación perfecto, forme un clique para cada vértice v junto con los vecinos de v que sean posteriores a v en el ordenamiento de eliminación perfecto y pruebe si cada uno de los cliques resultantes es máximo.
Los gráficos de camarilla de los gráficos cordales son los gráficos dualmente cordales . [6]
La camarilla máxima más grande es una camarilla máxima y, como los grafos cordales son perfectos, el tamaño de esta camarilla es igual al número cromático del grafo cordal. Los grafos cordales son perfectamente ordenables : se puede obtener una coloración óptima aplicando un algoritmo de coloración voraz a los vértices en el orden inverso de un ordenamiento de eliminación perfecto. [7]
El polinomio cromático de un grafo cordal es fácil de calcular. Halla un ordenamiento de eliminación perfecto v 1 , v 2 , …, v n . Sea N i igual al número de vecinos de v i que vienen después de v i en ese ordenamiento. Por ejemplo, N n = 0 . El polinomio cromático es igual a (El último factor es simplemente x , por lo que x divide al polinomio, como debería). Claramente, este cálculo depende de la cordalidad. [8]
En cualquier grafo, un separador de vértices es un conjunto de vértices cuya eliminación deja al grafo restante desconectado; un separador es mínimo si no tiene un subconjunto propio que también sea un separador. Según un teorema de Dirac (1961), los grafos cordales son grafos en los que cada separador mínimo es una camarilla; Dirac utilizó esta caracterización para demostrar que los grafos cordales son perfectos .
La familia de grafos cordales puede definirse inductivamente como los grafos cuyos vértices pueden dividirse en tres subconjuntos no vacíos A , S y B , tales que y ambos forman subgrafos inducidos cordales , S es una camarilla y no hay aristas de A a B . Es decir, son los grafos que tienen una descomposición recursiva por separadores de camarilla en subgrafos más pequeños. Por esta razón, los grafos cordales también se han llamado a veces grafos descomponibles . [9]
Una caracterización alternativa de los gráficos cordales, debida a Gavril (1974), involucra árboles y sus subárboles.
A partir de una colección de subárboles de un árbol, se puede definir un gráfico de subárbol , que es un gráfico de intersección que tiene un vértice por subárbol y una arista que conecta dos subárboles cualesquiera que se superpongan en uno o más nodos del árbol. Gavril demostró que los gráficos de subárboles son exactamente los gráficos cordales.
Una representación de un grafo cordal como una intersección de subárboles forma una descomposición en árbol del grafo, con un ancho de árbol igual a uno menos que el tamaño del grupo más grande en el grafo; la descomposición en árbol de cualquier grafo G puede verse de esta manera como una representación de G como un subgrafo de un grafo cordal. La descomposición en árbol de un grafo es también el árbol de unión del algoritmo de árbol de unión .
Los grafos de intervalos son los grafos de intersección de subárboles de grafos de trayectorias , un caso especial de árboles. Por lo tanto, son una subfamilia de grafos cordales.
Los grafos divididos son grafos que son tanto cordales como complementarios de grafos cordales. Bender, Richmond y Wormald (1985) demostraron que, en el límite, cuando n tiende a infinito, la fracción de grafos cordales de n vértices que están divididos se acerca a uno.
Los grafos ptolemaicos son grafos que son tanto cordales como hereditarios de distancia . Los grafos cuasi-umbral son una subclase de grafos ptolemaicos que son tanto cordales como cografos . Los grafos de bloques son otra subclase de grafos ptolemaicos en los que cada dos camarillas máximas tienen como máximo un vértice en común. Un tipo especial son los grafos de molino de viento , donde el vértice común es el mismo para cada par de camarillas.
Los grafos fuertemente cordales son grafos que son cordales y no contienen ningún n -sol (para n ≥ 3 ) como subgrafo inducido. Aquí un n -sol es un grafo cordal de n -vértices G junto con una colección de n vértices de grado dos, adyacentes a los bordes de un ciclo hamiltoniano en G .
Los árboles K son grafos cordales en los que todas las camarillas máximas y todos los separadores de camarillas máximas tienen el mismo tamaño. [10] Las redes apolíneas son grafos planos maximales cordales, o equivalentemente, 3-árboles planos. [10] Los grafos planos exteriores maximalesson una subclase de 2-árboles y, por lo tanto, también son cordales.
Los grafos cordales son una subclase de los conocidos grafos perfectos . Otras superclases de grafos cordales incluyen grafos débilmente cordales, grafos cop-win , grafos sin agujeros impares, grafos sin agujeros pares y grafos de Meyniel . Los grafos cordales son precisamente los grafos que están libres de agujeros impares y pares (ver agujeros en la teoría de grafos).
Todo grafo cordal es un grafo estrangulado , un grafo en el que cada ciclo periférico es un triángulo, porque los ciclos periféricos son un caso especial de ciclos inducidos. Los grafos estrangulados son grafos que pueden formarse mediante sumas de clique de grafos cordales y grafos planos maximalistas. Por lo tanto, los grafos estrangulados incluyen grafos planos maximalistas . [11]
Si G es un grafo arbitrario, una compleción cordal de G (o relleno mínimo ) es un grafo cordal que contiene a G como subgrafo. La versión parametrizada del relleno mínimo es manejable con parámetros fijos y, además, es solucionable en tiempo subexponencial parametrizado. [12] [13] El ancho de árbol de G es uno menos que el número de vértices en una camarilla máxima de una compleción cordal elegida para minimizar el tamaño de esta camarilla. Los k -árboles son los grafos a los que no se pueden agregar aristas adicionales sin aumentar su ancho de árbol a un número mayor que k . Por lo tanto, los k -árboles son sus propias compleciones cordales y forman una subclase de los grafos cordales. Las compleciones cordales también se pueden usar para caracterizar varias otras clases relacionadas de grafos. [14]
