En el área matemática de la teoría de grafos , un grafo cordal es aquel en el que todos los ciclos de cuatro o más vértices tienen una cuerda , que es una arista que no forma parte del ciclo pero que conecta dos vértices del ciclo. De manera equivalente, cada ciclo inducido en el gráfico debe tener exactamente tres vértices. Los gráficos cordales también se pueden caracterizar como gráficos que tienen ordenamientos de eliminación perfectos, como gráficos en los que cada separador mínimo es una camarilla y como gráficos de intersección de subárboles de un árbol. A veces también se les llama gráficos de circuitos rígidos [1] o gráficos triangulados : [2] una terminación cordal de un gráfico generalmente se denomina triangulación de ese gráfico.
Las gráficas cordales son un subconjunto de las gráficas perfectas . Se pueden reconocer en tiempo lineal , y varios problemas que son difíciles en otras clases de gráficos, como la coloración de gráficos, se pueden resolver en tiempo polinómico cuando la entrada es cordal. El ancho del árbol de un gráfico arbitrario se puede caracterizar por el tamaño de las camarillas en los gráficos cordales que lo contienen.
Un orden de eliminación perfecto en un gráfico es un orden de los vértices del gráfico tal que, para cada vértice v , v y los vecinos de v que ocurren después de v en el orden forman una camarilla . Un grafo es cordal si y sólo si tiene un orden de eliminación perfecto. [3]
Rose, Lueker y Tarjan (1976) (ver también Habib et al. 2000) muestran que se puede encontrar eficientemente un orden de eliminación perfecto de un gráfico cordal utilizando un algoritmo conocido como búsqueda lexicográfica de amplitud primero . Este algoritmo mantiene una partición de los vértices del gráfico en una secuencia de conjuntos; Inicialmente esta secuencia consta de un único conjunto con todos los vértices. El algoritmo elige repetidamente un vértice v del primer conjunto 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 de v. -vecinos. Cuando este proceso de división se ha realizado para todos los vértices, la secuencia de conjuntos tiene un vértice por conjunto, en el orden inverso al de eliminación perfecta.
Dado que tanto este primer proceso de búsqueda de amplitud lexicográfica como el proceso de probar si un orden es un orden de eliminación perfecta se pueden realizar en tiempo lineal , es posible reconocer gráficos cordales en tiempo lineal. El problema del gráfico sándwich en gráficos cordales es NP-completo [4], mientras que el problema del gráfico sonda en gráficos cordales tiene 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 determinado.
Otra aplicación de los ordenamientos de eliminación perfecta es encontrar una camarilla máxima de un gráfico cordal en tiempo polinomial, mientras que el mismo problema para gráficos generales es NP-completo . De manera más general, un gráfico cordal solo puede tener muchas camarillas máximas linealmente , mientras que los gráficos no cordales pueden tener muchas exponencialmente. Esto implica que la clase de grafos cordales tiene pocas camarillas . Para enumerar todos los camarillas máximas de un gráfico cordal, simplemente encuentre un orden de eliminación perfecto, forme una camarilla para cada vértice v junto con los vecinos de v que son posteriores a v en el orden de eliminación perfecto y pruebe si cada una de las camarillas 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 gráficos cordales son perfectos, el tamaño de esta camarilla es igual al número cromático del gráfico cordal. Los gráficos cordales son perfectamente ordenables : se puede obtener una coloración óptima aplicando un algoritmo de coloración codiciosa a los vértices en el orden inverso al orden de eliminación perfecta. [7]
El polinomio cromático de un gráfico cordal es fácil de calcular. Encuentre un orden 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 orden. Por ejemplo, N n = 0 . El polinomio cromático es igual (el último factor es simplemente x , por lo que x divide el polinomio, como debería). Claramente, este cálculo depende de la cordalidad. [8]
En cualquier gráfico, un separador de vértices es un conjunto de vértices cuya eliminación deja el gráfico restante desconectado; un separador es mínimo si no tiene un subconjunto adecuado 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 las gráficas cordales son perfectas .
La familia de grafos cordales se puede definir inductivamente como los grafos cuyos vértices se pueden dividir en tres subconjuntos no vacíos A , S y B , de modo que y ambos forman subgrafos inducidos cordales , S es una camarilla y no hay aristas de A a B . Es decir, son los gráficos que tienen una descomposición recursiva mediante separadores de camarilla en subgrafos más pequeños. Por este motivo, a los grafos cordales también se les ha llamado en ocasiones gráficos descomponibles . [9]
Una caracterización alternativa de los grafos 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 un borde 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 gráfico cordal como una intersección de subárboles forma una descomposición en árbol del gráfico, con un ancho de árbol igual a uno menos que el tamaño de la camarilla más grande del gráfico; la descomposición en árbol de cualquier gráfico G puede verse de esta manera como una representación de G como un subgrafo de un gráfico cordal. La descomposición en árbol de un gráfico es también el árbol de unión del algoritmo de árbol de unión .
Los gráficos de intervalos son los gráficos de intersección de subárboles de los gráficos de rutas , un caso especial de árboles. Por tanto, son una subfamilia de grafos cordales.
Los gráficos divididos son gráficos que son tanto cordales como complementarios de gráficos cordales. Bender, Richmond y Wormald (1985) demostraron que, en el límite cuando n tiende al infinito, la fracción de gráficos cordales de n -vértices que se dividen se acerca a uno.
Los gráficos ptolemaicos son gráficos que son hereditarios tanto cordales como a distancia . Los gráficos cuasi-umbral son una subclase de los gráficos ptolemaicos que son a la vez cordales y cografos . Los gráficos de bloques son otra subclase de los gráficos ptolemaicos en los que cada dos camarillas máximas tienen como máximo un vértice en común. Un tipo especial son los gráficos de molino de viento , donde el vértice común es el mismo para cada par de camarillas.
Los gráficos fuertemente cordales son gráficos que son cordales y no contienen n -sun (para n ≥ 3 ) como subgrafo inducido. Aquí un n -sol es un gráfico cordal de n -vértices G junto con una colección de n vértices de dos grados, adyacentes a los bordes de un ciclo hamiltoniano en G .
Los árboles K son gráficos cordales en los que todas las camarillas máximas y todos los separadores de camarillas máximos tienen el mismo tamaño. [10] Las redes apolíneas son gráficos planos cordales máximos, o 3 árboles equivalentemente planos. [10] Los gráficos planos externos máximosson una subclase de 2 árboles y, por lo tanto, también son cordales.
Los gráficos cordales son una subclase de los conocidos gráficos perfectos . Otras superclases de gráficos cordales incluyen gráficos débilmente cordales, gráficos cop-win , gráficos sin agujeros impares, gráficos sin agujeros pares y gráficos de Meyniel . Las gráficas cordales son precisamente las gráficas que no tienen agujeros pares ni impares (ver agujeros en 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 gráficos estrangulados son gráficos que pueden formarse mediante sumas de camarillas de gráficos cordales y gráficos planos máximos. Por lo tanto, los gráficos estrangulados incluyen gráficos planos máximos . [11]
Si G es un gráfico arbitrario, una terminación cordal de G (o relleno mínimo ) es un gráfico cordal que contiene G como subgrafo. La versión parametrizada del relleno mínimo es manejable con parámetros fijos y, además, se puede resolver en un tiempo subexponencial parametrizado. [12] [13] El ancho del árbol de G es uno menos que el número de vértices en una camarilla máxima de una terminación cordal elegida para minimizar este tamaño de camarilla. Los k -árboles son los gráficos a los que no se les pueden agregar aristas adicionales sin aumentar el ancho de su árbol a un número mayor que k . Por lo tanto, los k -árboles son sus propias terminaciones cordales y forman una subclase de los grafos cordales. Las terminaciones de cuerdas también se pueden utilizar para caracterizar otras clases de gráficos relacionadas. [14]
