Gráfico de cuerdas

En el ámbito matemático de la teoría de grafos , un grafo cordal es aquel en el que todos los ciclos de cuatro o más vértices poseen una cuerda , que es una arista que no forma parte del ciclo pero conecta dos vértices del mismo. De forma equivalente, cada ciclo inducido en el grafo debe tener exactamente tres vértices. Los grafos cordales también pueden caracterizarse como grafos con ordenamientos de eliminación perfectos, como grafos en los que cada separador mínimo es una camarilla , y como grafos de intersección de subárboles de un árbol. A veces también se les denomina grafos de circuito rígido ^{[ 1 ]} o grafos triangulados : ^{[ 2 ]} una completación cordal de un grafo se denomina típicamente triangulación de dicho grafo.

Los grafos cordales son un subconjunto de los grafos perfectos . Se pueden reconocer en tiempo lineal , y varios problemas que resultan 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 de á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 tal que, para cada vértice v , v y los vecinos de v que aparecen después de v en el orden 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 ) demuestran que se puede encontrar de forma eficiente un ordenamiento de eliminación perfecto de un grafo cordal mediante un algoritmo conocido como búsqueda en anchura lexicográfica . Este algoritmo mantiene una partición de los vértices del grafo 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 por los no vecinos. Una vez realizado este proceso de división para todos los vértices, la secuencia de conjuntos tiene un vértice por conjunto, en sentido inverso a 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 pueden realizarse 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 grafo 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 grafo cordal dado.

Otra aplicación de los ordenamientos de eliminación perfectos es encontrar una camarilla máxima de un grafo cordal en tiempo polinomial, mientras que el mismo problema para grafos generales es NP-completo . En términos más generales, un grafo cordal solo puede tener una cantidad lineal de camarillas máximas , mientras que los grafos no cordales pueden tener una cantidad exponencial. Esto implica que la clase de grafos cordales tiene pocas camarillas . Para enumerar todas las camarillas máximas de un grafo cordal, basta con encontrar un ordenamiento de eliminación perfecto, formar una camarilla para cada vértice v junto con los vecinos de v que son posteriores a v en el ordenamiento de eliminación perfecto, y comprobar si cada una de las camarillas resultantes es máxima.

Los grafos de clique de los grafos cordales son los grafos dualmente cordales . ^{[ 6 ]}

La mayor camarilla máxima 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 una ordenación de eliminación perfecta. ^{[ 7 ]}

El polinomio cromático de un grafo cordal es fácil de calcular. Encuentre un orden de eliminación perfecto v ₁ , v ₂ , …, 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 a${\displaystyle (x-N_{1})(x-N_{2})\cdots (x-N_{n}).}$ (El último factor es simplemente x , por lo que x divide al polinomio, como debe ser). 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 el grafo restante desconectado. Según un teorema de Dirac (1961) , los grafos cordales son grafos en los que cada separador mínimo es una camarilla. (Cabe señalar que un separador mínimo no es lo mismo que un subgrafo separador mínimo). 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 , de tal manera que${\displaystyle A\cup S}$y​​${\displaystyle S\cup B}$Ambos forman subgrafos inducidos por cuerdas , S es una camarilla y no hay aristas de A a B. Es decir, son grafos que se descomponen recursivamente mediante separadores de camarillas en subgrafos más pequeños. Por esta razón, a los grafos de cuerdas también se les ha llamado a veces grafos descomponibles . ^{[ 9 ]}

Una caracterización alternativa de los grafos cordales, debida a Gavril (1974) , involucra árboles y sus subárboles.

A partir de un conjunto de subárboles de un árbol, se puede definir un grafo de subárboles , que es un grafo de intersección con 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 grafos de subárboles son precisamente los grafos cordales.

Una representación de un grafo cordal como 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 de la camarilla más grande del 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 del árbol de unión .

Si G es un grafo arbitrario, una completació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 tratable con parámetros fijos y, además, es resoluble en tiempo subexponencial parametrizado. ^{[ 12 ] [ 13 ]} El ancho de árbol de G es uno menos que el número de vértices en una clique máxima de una completación cordal elegida para minimizar el tamaño de esta clique. 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 completaciones cordales y forman una subclase de los grafos cordales. Las completaciones cordales también se pueden usar para caracterizar varias otras clases relacionadas de grafos. ^{[ 14 ]} 

• Agnarsson, Geir (2003), "Sobre grafos cordales y sus polinomios cromáticos" , Mathematica Scandinavica , 93 (2): 240–246 , doi : 10.7146/math.scand.a-14421 , MR 2009583 .
• Bender, EA; Richmond, LB; Wormald, NC (1985), "Casi todos los grafos cordales se dividen", J. Austral. Math. Soc. , 38 (2): 214– 221, doi : 10.1017/S1446788700023077 , MR 0770128 .
• Berge, Claude (1967), "Algunas clases de grafos perfectos", en Harary, Frank (ed.), Teoría de grafos y física teórica , Academic Press, pp. 155–165 , MR 0232694  .
• Berry, Anne; Golumbic, Martin Charles ; Lipshteyn, Marina (2007), "Reconocimiento de grafos de sonda cordal y grafos bicoloreables cíclicos", SIAM Journal on Discrete Mathematics , 21 (3): 573– 591, doi : 10.1137/050637091.
• Bodlaender, HL ; Fellows, MR ; Warnow, TJ (1992), "Dos argumentos en contra de la filogenia perfecta" (PDF) , Actas del 19.º Coloquio Internacional sobre Lenguajes y Programación de Autómatas , Lecture Notes in Computer Science, vol.  623, pp. 273–283 , doi : 10.1007/3-540-55719-9_80 , hdl : 1874/16653 , ISBN  978-3-540-55719-7.
• Chandran, LS; Ibarra, L.; Ruskey, F .; Sawada, J. (2003), "Enumeración y caracterización de los ordenamientos de eliminación perfectos de un grafo cordal" (PDF) , Theoretical Computer Science , 307 (2): 303–317 , doi : 10.1016/S0304-3975(03)00221-4.
• Dirac, GA (1961), "Sobre gráficos de circuitos rígidos", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 25 ( 1– 2): 71– 76, doi : 10.1007/BF02992776 , MR 0130190 , S2CID 120608513  .
• Fomin, Fedor V.; Villanger, Yngve (2013), "Algoritmo subexponencial parametrizado para relleno mínimo", SIAM J. Comput. , 42 (6): 2197– 2216, arXiv : 1104.2230 , doi : 10.1137/11085390X , S2CID 934546 .
• Fulkerson, DR ; Gross, OA (1965), "Matrices de incidencia y grafos de intervalos" , Pacific J. Math. , 15 (3): 835–855 , doi : 10.2140/pjm.1965.15.835.
• Gavril, Fănică (1974), "Los grafos de intersección de subárboles en árboles son exactamente los grafos cordales", Journal of Combinatorial Theory , Serie B, 16 : 47–56 , doi : 10.1016/0095-8956(74)90094-X.
• Golumbic, Martin Charles (1980), Teoría algorítmica de grafos y grafos perfectos , Academic Press.
• Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS y refinamiento de particiones, con aplicaciones a la orientación transitiva, el reconocimiento de grafos de intervalos y la comprobación de unos consecutivos" , Theoretical Computer Science , 234 ( 1–2 ): 59–84 , doi : 10.1016/S0304-3975(97)00241-7.
• Kaplan, Haim; Shamir, Ron; Tarjan, Robert (1999), "Tratabilidad de problemas de completación parametrizados en grafos de intervalos cordales, fuertemente cordales y propios", SIAM J. Comput. , 28 (5): 1906– 1922, doi : 10.1137/S0097539796303044.
• Maffray, Frédéric (2003), "Sobre la coloración de grafos perfectos", en Reed, Bruce A.; Sales, Cláudia L. (eds.), Avances recientes en algoritmos y combinatoria , CMS Books in Mathematics, vol.  11, Springer-Verlag, pp. 65–84 , doi : 10.1007/0-387-22444-0_3 , ISBN  0-387-95434-1.
• Parra, Andreas; Scheffler, Petra (1997), "Caracterizaciones y aplicaciones algorítmicas de incrustaciones de grafos cordales", Matemáticas Aplicadas Discretas , 79 ( 1–3 ): 171–188 , doi : 10.1016/S0166-218X(97)00041-3 , MR 1478250 .
• Patil, HP (1986), "Sobre la estructura de los k -árboles", Journal of Combinatorics, Information and System Sciences , 11 ( 2–4 ): 57–64 , MR 0966069 .
• Rose, Donald J. (diciembre de 1970), "Grafos triangulados y el proceso de eliminación", Journal of Mathematical Analysis and Applications , 32 (3): 597– 609, doi : 10.1016/0022-247x(70)90282-9
• Rose, D.; Lueker, George; Tarjan, Robert E. (1976), "Aspectos algorítmicos de la eliminación de vértices en grafos", SIAM Journal on Computing , 5 (2): 266–283 , doi : 10.1137/0205021 , MR 0408312 .
• Seymour, PD ; Weaver, RW (1984), "Una generalización de los grafos cordales", Journal of Graph Theory , 8 (2): 241–251 , doi : 10.1002/jgt.3190080206 , MR 0742878 .
• Szwarcfiter, JL ; Bornstein, CF (1994), "Grafos de cliques de grafos cordales y de caminos", SIAM Journal on Discrete Mathematics , 7 (2): 331–336 , doi : 10.1137/s0895480191223191 , hdl : 11422/1497.

• Sistema de información sobre inclusiones de clases de grafos : grafo cordal
• Weisstein, Eric W. "Gráfico cordal" . MundoMatemático .