Gráfico de cuerdas
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 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 los gráficos que tienen ordenaciones de eliminación perfectas, como los gráficos en los que cada separador mínimo es una camarilla y como los gráficos de intersección de los subárboles de un árbol. A veces también se les llama gráficos de circuitos rígidos [1] o gráficos triangulados . [2]
Los grafos cordales son un subconjunto de los grafos perfectos . Pueden reconocerse en tiempo lineal , y varios problemas que son difíciles en otras clases de gráficos, como la coloración de gráficos, pueden resolverse en tiempo polinomial cuando la entrada es cordal. El ancho de árbol de un gráfico arbitrario se puede caracterizar por el tamaño de las camarillas en los gráficos cordales que lo contienen.
Una ordenación de eliminación perfecta en un gráfico es una ordenación de los vértices del gráfico tal que, para cada vértice v , v y los vecinos de v que se encuentran después de v en el orden forman una camarilla . Un grafo es cordal si y solo si tiene un orden de eliminación perfecto. [3]
Rose, Lueker & Tarjan (1976) (ver también Habib et al. 2000 ) muestran que un orden de eliminación perfecto de un grafo cordal se puede encontrar eficientemente usando un algoritmo conocido como búsqueda lexicográfica en amplitud . Este algoritmo mantiene una partición de los vértices del gráfico en una secuencia de conjuntos; inicialmente esta secuencia consta de un solo 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 que consta de los vecinos de v en Sy el segundo formado por los no 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, al revés de un orden de eliminación perfecto.
Dado que tanto este proceso de búsqueda primero en amplitud lexicográfica como el proceso de probar si una ordenación es una ordenación de eliminación perfecta se pueden realizar en tiempo lineal, es posible reconocer grafos cordales en tiempo lineal. El problema del gráfico sándwich en grafos cordales es NP-completo [4] mientras que el problema del gráfico de sonda 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 antimatroid ; Chandran et al. (2003) utilizan esta conexión con los antimatroides como parte de un algoritmo para enumerar de manera eficiente todas las órdenes de eliminación perfectas de un gráfico cordal dado.
