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 pueden caracterizarse como los gráficos que tienen un orden de eliminación perfecto, 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] ográficos triangulados . [2]
Los gráficos de cuerdas son un subconjunto de los gráficos perfectos . Pueden reconocerse en tiempo lineal , y varios problemas que son difíciles para otras clases de gráficos, como el color de los gráficos, pueden resolverse en tiempo polinomial cuando la entrada es cordal. El ancho de árbol de un gráfico arbitrario puede caracterizarse por el tamaño de las camarillas en los gráficos cordales que lo contienen.
Eliminación perfecta y reconocimiento eficiente
Un ordenamiento de eliminación perfecto en un gráfico es un ordenamiento de los vértices del gráfico de modo 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 gráfico es cordal si y solo si tiene un orden de eliminación perfecto. [3]
Rose, Lueker y Tarjan (1976) (ver también Habib et al. 2000 ) muestran que un orden de eliminación perfecto de un grafo cordal se puede encontrar de manera eficiente usando un algoritmo conocido como búsqueda lexicográfica primero 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 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 que consta de los vecinos de v en S y el segundo que consta de 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, a la inversa de un orden de eliminación perfecto.
Dado que tanto este primer proceso de búsqueda de amplitud lexicográfica como el proceso de prueba de si un pedido es un ordenamiento de eliminación perfecto se pueden realizar en tiempo lineal, es posible reconocer gráficos cordales en tiempo lineal. El problema de sándwich de grafos en grafos cordales es NP-completo [4] mientras que el problema de grafos de prueba en grafos cordales tiene complejidad de tiempo polinomial. [5]
El conjunto de todos los ordenamientos de eliminación perfectos de un gráfico cordal puede modelarse como las palabras básicas de un antimatroide ; Chandran y col. (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.
Camarillas máximas y coloración de gráficos
Otra aplicación de los ordenamientos de eliminación perfectos 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 gráfico cordal solo puede tener linealmente muchas camarillas máximas , mientras que los gráficos no cordales pueden tener exponencialmente muchos. Para enumerar todas las 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 sean 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 de cuerdas son perfectos, el tamaño de esta camarilla es igual al número cromático de la gráfica de cuerdas. Los gráficos de cuerdas se pueden ordenar perfectamente : se puede obtener una coloración óptima aplicando un algoritmo de coloración codicioso a los vértices en el reverso de una ordenación de eliminación perfecta. [7]
El polinomio cromático de un gráfico cordal es fácil de calcular. Encuentra un pedido de eliminación perfectoSea N i el 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(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]
Separadores mínimos
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 gráficos cordales son gráficos en los que cada separador mínimo es una camarilla; Dirac usó esta caracterización para demostrar que los gráficos de cuerdas son perfectos .
La familia de grafos cordales puede definirse inductivamente como los grafos cuyos vértices se pueden dividir en tres subconjuntos no vacíos A , S y B , de modo que A ∪ S y S ∪ B forman ambos subgrafos inducidos por cuerdas , S es una camarilla, y allí hay bordes de a a B . Es decir, son los gráficos que tienen una descomposición recursiva por separadores de pandillas en subgrafos más pequeños. Por esta razón, las gráficas de cuerdas a veces también se denominan gráficas descomponibles . [9]
Gráficos de intersección de subárboles
Una caracterización alternativa de los grafos cordales, de 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 que se superponen en uno o más nodos del árbol. Gavril demostró que los gráficos del subárbol 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 de árbol del gráfico, con un ancho de árbol igual a uno menos que el tamaño de la camarilla más grande en el gráfico; la descomposición del árbol de cualquier gráfico G puede verse de esta manera como una representación de G como un subgrafo de un grafo cordal. La descomposición del árbol de un gráfico también es el árbol de unión del algoritmo del árbol de unión .
Relación con otras clases de gráficos
Subclases
Los gráficos de intervalo son los gráficos de intersección de los subárboles de los gráficos de trayectoria , un caso especial de árboles. Por lo tanto, son una subfamilia de grafos cordales.
Los gráficos divididos son gráficos que son tanto cordales como complementos de los gráficos cordales. Bender, Richmond y Wormald (1985) demostraron que, en el límite cuando n va al infinito, la fracción de grafos cordales de n-vértices que se dividen se aproxima a uno.
Los gráficos ptolemaicos son gráficos que son hereditarios tanto de cuerdas como de distancia . Los gráficos de cuasi-umbral son una subclase de gráficos ptolemaicos que son tanto cordales como cográficos . Los gráficos de bloques son otra subclase de 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 grafos fuertemente cordales son grafos que son cordales y no contienen n -sun (para n ≥ 3) como un subgrafo inducido. Aquí un n -Sun es un n -vertex cordal gráfico G junto con una colección de n grado de dos vértices, adyacente a los bordes de un ciclo de Hamilton en G .
Los árboles K son gráficos 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 máximos cordales, o equivalentemente 3 árboles planos. [10] Maximal gráficos outerplanar son una subclase de 2-árboles, y por lo tanto también son cordal.
Superclases
Los gráficos cordales son una subclase de los conocidos gráficos perfectos . Otros superclases de gráficos de cuerdas incluyen gráficos débilmente cordales, gráficos poli-ganar , gráficos impar-Free Hole, gráficos de forma gratuita, incluso hoyos y gráficos Meyniel . Los gráficos cordales son precisamente los gráficos que están libres de agujeros impares y libres de agujeros pares (consulte los agujeros en la teoría de grafos).
Cada gráfico cordal es un gráfico estrangulado , un gráfico en el que cada ciclo periférico es un triángulo, porque los ciclos periféricos son un caso especial de ciclos inducidos. Las gráficas estranguladas son gráficas que pueden formarse mediante sumas de clique de gráficas cordales y gráficas planas máximas. Por lo tanto, las gráficas estranguladas incluyen gráficas planas máximas . [11]
Terminaciones de cuerdas y ancho de árbol
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 un subgráfico. La versión parametrizada de relleno mínimo es manejable con parámetros fijos y, además, se puede resolver en 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 pueden agregar bordes adicionales sin aumentar su ancho de árbol a un número mayor que k . Por lo tanto, los árboles k son sus propias terminaciones de acordes y forman una subclase de los gráficos de acordes. Las terminaciones de cuerdas también se pueden utilizar para caracterizar varias otras clases de gráficos relacionados. [14]
Notas
- ^ Dirac (1961) .
- ^ Berge (1967) .
- ^ Fulkerson y Gross (1965) .
- ^ Bodlaender, Fellows y Warnow (1992) .
- ^ Berry, Golumbic y Lipshteyn (2007) .
- ^ Szwarcfiter y Bornstein (1994) .
- ^ Maffray (2003) .
- ↑ Por ejemplo, Agnarsson (2003) , Remark 2.5, llama a este método bien conocido.
- ^ Peter Bartlett. "Modelos gráficos no dirigidos: gráficos de cuerdas, gráficos descomponibles, árboles de unión y factorizaciones" (PDF) .
- ↑ a b Patil (1986) .
- ^ Seymour y Weaver (1984) .
- ^ Kaplan, Shamir y Tarjan (1999) .
- ^ Fomin y Villanger (2013) .
- ^ Parra y Scheffler (1997) .
Referencias
- 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. Matemáticas. Soc. , A, 38 (2): 214–221, doi : 10.1017 / S1446788700023077 , MR 0770128.
- Berge, Claude (1967), "Some Classes of Perfect Graphs", en Harary, Frank (ed.), Graph Theory and Theoretical Physics , Academic Press, págs. 155-165, MR 0232694.
- Berry, Anne; Golumbic, Martin Charles ; Lipshteyn, Marina (2007), "Recognizing chordal probe graphs and cycle-bicolorable graphs", SIAM Journal on Discrete Mathematics , 21 (3): 573–591, doi : 10.1137 / 050637091.
- Bodlaender, HL ; Becarios, MR ; Warnow, TJ (1992), "Dos golpes contra la filogenia perfecta" (PDF) , Proc. del XIX Coloquio Internacional sobre Lenguajes y Programación de Autómatas , Lecture Notes in Computer Science, 623 , págs. 273–283, doi : 10.1007 / 3-540-55719-9_80 , hdl : 1874/16653.
- Chandran, LS; Ibarra, L .; Ruskey, F .; Sawada, J. (2003), "Enumerar y caracterizar 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), "On rigid circuit graphs" (PDF) , 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 parametrizado subexponencial para relleno mínimo", SIAM J. Comput. , 42 (6): 2197–2216, arXiv : 1104.2230 , doi : 10.1137 / 11085390X , S2CID 934546.
- Fulkerson, RD ; Gross, OA (1965), "Matrices de incidencia y gráficos de intervalo" , Pacific J. Math. , 15 (3): 835–855, doi : 10.2140 / pjm.1965.15.835.
- Gavril, Fănică (1974), "Los gráficos de intersección de los subárboles en los árboles son exactamente los gráficos cordales", Journal of Combinatorial Theory , Serie B, 16 : 47–56, doi : 10.1016 / 0095-8956 (74) 90094-X.
- Golumbic, Martin Charles (1980), Teoría de gráficos algorítmicos y gráficos perfectos , Academic Press.
- Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS y el refinamiento de particiones, con aplicaciones a la orientación transitiva, el reconocimiento de gráficos de intervalo y las pruebas consecutivas" , Ciencias de la computación teóricas , 234 (1–2): 59–84, doi : 10.1016 / S0304-3975 (97) 00241-7.
- Kaplan, Haim; Shamir, Ron; Tarjan, Robert (1999), "Tratabilidad de problemas de finalización parametrizados en gráficos de intervalos acordes, fuertemente cordales y adecuados", SIAM J. Comput. , 28 (5): 1906–1922, doi : 10.1137 / S0097539796303044.
- Maffray, Frédéric (2003), "Sobre la coloración de gráficos perfectos", en Reed, Bruce A .; Sales, Cláudia L. (eds.), Recent Advances in Algorithms and Combinatorics , CMS Books in Mathematics, 11 , Springer-Verlag, págs. 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 árboles k ", Journal of Combinatorics, Information and System Sciences , 11 (2-4): 57-64, MR 0966069.
- Rose, D .; Lueker, George; Tarjan, Robert E. (1976), "Aspectos algorítmicos de la eliminación de vértices en gráficos", SIAM Journal on Computing , 5 (2): 266-283, doi : 10.1137 / 0205021 , MR 0408312.
- Seymour, PD ; Weaver, RW (1984), "A generalization of chordal graphs", Journal of Graph Theory , 8 (2): 241-251, doi : 10.1002 / jgt.3190080206 , MR 0742878.
- Szwarcfiter, JL ; Bornstein, CF (1994), "Clique graphs of chordal and path graphs", SIAM Journal on Discrete Mathematics , 7 (2): 331–336, doi : 10.1137 / s0895480191223191 , hdl : 11422/1497.
enlaces externos
- Sistema de información sobre inclusiones de clases de gráficos : gráfico de cuerdas
- Weisstein, Eric W. "Gráfico de cuerdas" . MathWorld .