En la teoría de grafos , un cograph , o gráfico complementar reducible , o P 4 gráfico exento , es un gráfico que puede ser generada a partir de la de un solo vértice gráfico K 1 por complementación y unión de la desunión . Es decir, la familia de las cografías es la clase más pequeña de gráficas que incluye K 1 y está cerrada bajo complementación y unión disjunta.
Los cografos han sido descubiertos de forma independiente por varios autores desde la década de 1970; Las primeras referencias incluyen a Jung (1978) , Lerchs (1971) , Seinsche (1974) y Sumner (1974) . También se les ha llamado gráficos D * , [1] gráficos de Dacey hereditarios (por el trabajo relacionado de James C. Dacey Jr. sobre celosías ortomodulares ), [2] y gráficos de 2 paridad . [3] Tienen una descomposición estructural simple que involucra una unión disjunta y un gráfico de complemento.operaciones que se pueden representar de forma concisa mediante un árbol etiquetado y que se usan algorítmicamente para resolver de manera eficiente muchos problemas, como encontrar la camarilla máxima que es difícil en clases de gráficos más generales.
Casos especiales de los cographs incluyen los gráficos completos , grafo bipartito completo , gráficos de racimo , y gráficos de umbral . Los cographs son, a su vez, casos especiales de los grafos distancia-hereditaria , gráficos de permutación , gráficos de comparabilidad y gráficos perfectos .
Definición
Construcción recursiva
Cualquier cografo puede construirse siguiendo las siguientes reglas:
- cualquier gráfico de un solo vértice es un cógrafo;
- Si es un cógrafo, también lo es su gráfico de complemento ;
- Si y son cografías, también lo es su unión inconexa .
Las cografías pueden definirse como las gráficas que se pueden construir utilizando estas operaciones, comenzando por las gráficas de un solo vértice. [4] Alternativamente, en lugar de utilizar la operación de complemento, se puede utilizar la operación de unión, que consiste en formar la unión disjunta y luego agregando un borde entre cada par de vértices de y un vértice de .
Otras caracterizaciones
Se pueden dar varias caracterizaciones alternativas de las cografías. Entre ellos:
- Un cografo es un grafo que no contiene la trayectoria P 4 en 4 vértices (y por tanto de longitud 3) como un subgrafo inducido . Es decir, una gráfica es una cografía si y solo si para cuatro vértices cualesquiera, Si y son bordes del gráfico, entonces al menos uno de o también es una ventaja. [4]
- Una cografía es una gráfica cuyos subgráficos inducidos tienen la propiedad de que cualquier camarilla máxima interseca a cualquier conjunto independiente máximo en un solo vértice.
- Un cograph es un gráfico en el que cada subgrafo inducido no trivial tiene al menos dos vértices con las mismas vecindades.
- Un cografo es un grafo en el que cada subgrafo inducido conectado tiene un complemento desconectado.
- Una cografía es una gráfica cuyos subgrafos inducidos conectados tienen un diámetro como máximo 2.
- Un cograph es un gráfico en el que cada componente conectado es un gráfico hereditario de distancia con un diámetro de 2 como máximo.
- Un cograph es un gráfico con un ancho de camarilla como máximo 2. [5]
- Un cograph es un gráfico de comparabilidad de un orden parcial serie-paralelo . [1]
- Un cograph es un gráfico de permutación de una permutación separable . [6]
- Una cografía es una gráfica cuyas terminaciones de cuerdas mínimas son gráficas trivialmente perfectas . [7]
- Un cograph es un gráfico hereditariamente bien coloreado , un gráfico tal que cada color codicioso de cada subgráfico inducido utiliza un número óptimo de colores. [8]
- Una gráfica es una cografía si y solo si cada orden de vértice de la gráfica es un orden perfecto , ya que no tener P 4 significa que no existirá ninguna obstrucción a un orden perfecto en ningún orden de vértice.
Cotrees
Un cotree es un árbol en el que los nodos internos están etiquetados con los números 0 y 1. Cada cotree T define un cograph G que tiene las hojas de T como vértices, y en el que el subárbol enraizado en cada nodo de T corresponde al subgraph inducido en G definido por el conjunto de hojas que descienden de ese nodo:
- Un subárbol que consta de un solo nodo hoja corresponde a un subgrafo inducido con un solo vértice.
- Un subárbol enraizado en un nodo etiquetado como 0 corresponde a la unión de los subgrafos definidos por los hijos de ese nodo.
- Un subárbol enraizado en un nodo etiquetado como 1 corresponde a la unión de los subgrafos definidos por los hijos de ese nodo; es decir, formamos la unión y agregamos un borde entre cada dos vértices correspondiente a hojas en diferentes subárboles. Alternativamente, la unión de un conjunto de gráficos puede verse como formada complementando cada gráfico, formando la unión de los complementos y luego complementando la unión resultante.
Una forma equivalente de describir el cograph formado a partir de un cotree es que dos vértices están conectados por un borde si y solo si el ancestro común más bajo de las hojas correspondientes está etiquetado con 1. A la inversa, cada cograph puede ser representado de esta manera por un cotree. . Si requerimos que las etiquetas en cualquier ruta raíz-hoja de este árbol se alternen entre 0 y 1, esta representación es única. [4]
Propiedades computacionales
Los cografos se pueden reconocer en tiempo lineal, y se puede construir una representación de árbol común, usando descomposición modular , [9] refinamiento de partición , [10] LexBFS , [11] o descomposición dividida . [12] Una vez que se ha construido una representación de cotrees, muchos problemas de gráficos familiares pueden resolverse mediante cálculos simples de abajo hacia arriba en los cotrees.
Por ejemplo, para encontrar la camarilla máxima en un cograph, calcule en orden ascendente la camarilla máxima en cada subgrafo representado por un subárbol del cotree. Para un nodo etiquetado como 0, la camarilla máxima es la máxima entre las camarillas calculadas para los hijos de ese nodo. Para un nodo etiquetado como 1, la camarilla máxima es la unión de las camarillas calculadas para los hijos de ese nodo, y tiene un tamaño igual a la suma de los tamaños de las camarillas de los niños. Así, maximizando y sumando alternativamente los valores almacenados en cada nodo del cotree, podemos calcular el tamaño máximo de la camarilla, y maximizando y tomando uniones alternativamente, podemos construir la camarilla máxima en sí. Cálculos de árbol ascendentes similares permiten que el conjunto independiente máximo , el número de coloración del vértice , la cobertura máxima de la camarilla y la hamiltonicidad (es decir, la existencia de un ciclo hamiltoniano ) se calculen en tiempo lineal a partir de una representación de cografía de un cograma. [4] Debido a que las cografías tienen un ancho de camarilla acotado, el teorema de Courcelle puede usarse para probar cualquier propiedad en la lógica monádica de segundo orden de las gráficas (MSO 1 ) en cografías en tiempo lineal. [13]
El problema de probar si una gráfica dada está a k vértices de distancia y / o t bordes de una cografía es manejable con parámetros fijos . [14] Decidir si un gráfico puede eliminarse con un borde k en un cografo se puede resolver en O * (2.415 k ) tiempo, [15] y editar con un borde k en un cografo en O * (4.612 k ). [16] Si se puede encontrar el subgrafo de cografía inducida más grande de un gráfico eliminando k vértices del gráfico, se puede encontrar en tiempo O * (3,30 k ). [15]
Dos cografías son isomorfas si y solo si sus cotrees (en la forma canónica sin dos vértices adyacentes con la misma etiqueta) son isomorfos. Debido a esta equivalencia, se puede determinar en tiempo lineal si dos cografías son isomorfas, construyendo sus cotrees y aplicando una prueba de isomorfismo de tiempo lineal para árboles etiquetados. [4]
Si H es un subgrafo inducido de un cografo G , entonces H es en si mismo un cografo; el cotree para H puede formarse quitando algunas de las hojas del cotree para G y luego suprimiendo los nodos que tienen un solo hijo. Se deduce del teorema del árbol de Kruskal que la relación de ser un subgrafo inducido es un cuasi-ordenamiento bien en los cografos. [17] Por lo tanto, si una subfamilia de cografos (como los cografos planos ) se cierra bajo operaciones de subgrafo inducido, entonces tiene un numero finito de subgrafos inducidos prohibidos . Computacionalmente, esto significa que probar la pertenencia a una subfamilia de este tipo se puede realizar en tiempo lineal, utilizando un cálculo ascendente en el cotree de un gráfico dado para probar si contiene alguno de estos subgrafos prohibidos. Sin embargo, cuando los tamaños de dos cografías son variables, probar si uno de ellos es un subgrafo inducido del otro es NP-completo . [18]
Los cografos juegan un papel clave en los algoritmos para reconocer funciones de una sola lectura . [19]
Enumeración
El número de cografías conectadas con n vértices, para n = 1, 2, 3, ..., es:
- 1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ... (secuencia A000669 en la OEIS )
Para n > 1 hay el mismo número de cógrafos desconectados, porque por cada cógrafo exactamente uno de ellos o su gráfico complementario está conectado.
Familias de gráficos relacionadas
Subclases
Cada grafo completo K n es un cografo, con un cotree que consta de un solo 1 nodo y n hojas. De manera similar, todo grafo bipartito completo K a , b es un cografo. Su coárbol tiene sus raíces en una 1-nodo que tiene dos hijos 0-nodo, una con una hoja de niños y una con b niños de hojas. Un gráfico de Turán puede estar formado por la unión de una familia de conjuntos independientes de igual tamaño; por lo tanto, también es un cografo, con un cotree enraizado en un nodo 1 que tiene un nodo 0 hijo para cada conjunto independiente.
Cada gráfico de umbral es también un gráfico. Se puede formar un gráfico de umbral agregando repetidamente un vértice, ya sea conectado a todos los vértices anteriores o a ninguno de ellos; cada una de estas operaciones es una de las operaciones conjuntas o de unión disjunta mediante las cuales puede formarse un cotree. [20]
Superclases
La caracterización de los cografos por la propiedad de que cada camarilla y conjunto máximo independiente tienen una intersección no vacía es una versión más fuerte de la propiedad definitoria de los gráficos fuertemente perfectos , en los que cada subgrafo inducido contiene un conjunto independiente que interseca a todos los grupos máximos. En una cografía, cada conjunto máximo independiente se cruza con todas las camarillas máximas. Por lo tanto, cada cografo es absolutamente perfecto. [21]
El hecho de que los cografos estén libres de P 4 implica que se pueden pedir perfectamente . De hecho, cada orden de vértice de una cografía es un orden perfecto, lo que implica además que la búsqueda de camarilla máxima y la coloración mínima se pueden encontrar en tiempo lineal con cualquier coloración codiciosa y sin la necesidad de una descomposición de árbol continuo.
Cada cografía es un gráfico de distancia hereditaria , lo que significa que cada camino inducido en una cografía es un camino más corto . Las cografías se pueden caracterizar entre las gráficas hereditarias de distancia por tener un diámetro de dos en cada componente conectado. Cada cografo es también un gráfico de comparabilidad de un orden parcial serie-paralelo , obtenido reemplazando la unión disjunta y las operaciones de unión por las cuales se construyó el cografo por unión disjunta y operaciones de suma ordinal en órdenes parciales. Debido a que las gráficas fuertemente perfectas, las gráficas perfectamente ordenables, las gráficas hereditarias de distancia y las gráficas de comparabilidad son todas gráficas perfectas , las cografías también son perfectas. [20]
Notas
- ↑ a b Jung (1978) .
- ^ Sumner (1974) .
- ^ Burlet y Uhry (1984) .
- ↑ a b c d e Corneil, Lerchs y Stewart Burlingham (1981) .
- ^ Courcelle y Olariu (2000) .
- ^ Bose, Buss y Lubiw (1998) .
- ^ Parra y Scheffler (1997) .
- ^ Christen y Selkow (1979) .
- ^ Corneil, Perl y Stewart (1985) .
- ^ Habib y Paul (2005) .
- ^ Bretscher y col. (2008) .
- ^ Gioan y Paul (2012) .
- ^ Courcelle, Makowsky y Rotics (2000) .
- ^ Cai (1996) .
- ↑ a b Nastos y Gao (2010) .
- ^ Liu y col. (2012) .
- ^ Damaschke (1990) .
- ^ Damaschke (1991) .
- ^ Golumbic y Gurvich (2011) .
- ↑ a b Brandstädt, Le y Spinrad (1999) .
- ^ Berge y Duchet (1984) .
Referencias
- Berge, C .; Duchet, P. (1984), "Gráficos fuertemente perfectos", Temas sobre gráficos perfectos , North-Holland Mathematics Studies, 88 , Amsterdam: North-Holland, págs. 57–61, doi : 10.1016 / S0304-0208 (08) 72922 -0 , MR 0778749 CS1 maint: parámetro desalentado ( enlace ).
- Bose, Prosenjit ; Buss, Jonathan; Lubiw, Anna (1998), " Coincidencia de patrones para permutaciones", Cartas de procesamiento de información , 65 (5): 277–283, doi : 10.1016 / S0020-0190 (97) 00209-3 , MR 1620935.
- Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy P. (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 978-0-89871-432-6.
- Burlet, M .; Uhry, JP (1984), "Gráficos de paridad", Temas sobre gráficos perfectos , Annals of Discrete Mathematics, 21 , págs. 253–277.
- Bretscher, A .; Corneil, DG ; Habib, M .; Paul, C. (2008), "A simple Linear Time LexBFS Cograph Recognition Algorithm", SIAM Journal on Discrete Mathematics , 22 (4): 1277–1296, CiteSeerX 10.1.1.188.5016 , doi : 10.1137 / 060664690.
- Cai, L. (1996), "Tractabilidad de parámetros fijos de problemas de modificación de gráficos para propiedades hereditarias", Information Processing Letters , 58 (4): 171-176, doi : 10.1016 / 0020-0190 (96) 00050-6.
- Christen, Claude A .; Selkow, Stanley M. (1979), "Algunas propiedades de coloración perfectas de los gráficos", Journal of Combinatorial Theory , Serie B, 27 (1): 49–59, doi : 10.1016 / 0095-8956 (79) 90067-4 , MR 0539075.
- Corneil, DG ; Lerchs, H .; Stewart Burlingham, L. (1981), "Gráficos reducibles de complemento", Matemáticas aplicadas discretas , 3 (3): 163-174, doi : 10.1016 / 0166-218X (81) 90013-5 , MR 0619603.
- Corneil, DG ; Perl, Y .; Stewart, LK (1985), "Un algoritmo de reconocimiento lineal para cografías", SIAM Journal on Computing , 14 (4): 926–934, doi : 10.1137 / 0214065 , MR 0807891.
- Courcelle, B .; Makowsky, JA; Rotics, U. (2000), "Problemas de optimización con solución de tiempo lineal en gráficos de ancho de camarilla acotado", Teoría de los sistemas informáticos , 33 (2): 125-150, doi : 10.1007 / s002249910009 , MR 1739644 , S2CID 15402031 , Zbl 1009.68102.
- Courcelle, B .; Olariu, S. (2000), " Límites superiores del ancho de la camarilla de los gráficos" , Matemáticas aplicadas discretas , 101 (1–3): 77–144, doi : 10.1016 / S0166-218X (99) 00184-5 , MR 1743732.
- Damaschke, Peter (1990), "Subgrafos inducidos y bien cuasi-ordenamiento", Journal of Graph Theory , 14 (4): 427–435, doi : 10.1002 / jgt.3190140406 , MR 1067237.
- Damaschke, Peter (1991), "El isomorfismo subrafo inducido para cografías es NP-completo", en Möhring, Rolf H. (ed.), Graph-Theoretic Concepts in Computer Science: 16th International Workshop WG '90 Berlín, Alemania, 20 de junio –22, 1990, Proceedings , Lecture Notes in Computer Science, 484 , Springer-Verlag, págs. 72–78, doi : 10.1007 / 3-540-53832-1_32.
- Gioan, Emeric; Paul, Christophe (2012), "Descomposición dividida y árboles etiquetados con gráficos: caracterizaciones y algoritmos completamente dinámicos para gráficos totalmente descomponibles", Discrete Applied Mathematics , 160 (6): 708–733, arXiv : 0810.1823 , doi : 10.1016 / j. presa 2011.05.007 , MR 2901084 , S2CID 6528410.
- Golumbic, Martin C .; Gurvich, Vladimir (2011), "Funciones de una sola lectura" (PDF) , en Crama, Yves; Hammer, Peter L. (eds.), Funciones booleanas , Encyclopedia of Mathematics and its Applications, 142 , Cambridge University Press, Cambridge, págs. 519–560, doi : 10.1017 / CBO9780511852008 , ISBN 978-0-521-84751-3, MR 2742439.
- Habib, Michel; Paul, Christophe (2005), "Un algoritmo de tiempo lineal simple para el reconocimiento de cografías" (PDF) , Matemáticas aplicadas discretas , 145 (2): 183-197, doi : 10.1016 / j.dam.2004.01.011 , MR 2113140.
- Jung, HA (1978), "Sobre una clase de posets y los gráficos de comparabilidad correspondientes", Journal of Combinatorial Theory , Serie B, 24 (2): 125-133, doi : 10.1016 / 0095-8956 (78) 90013-8 , MR 0491356.
- Lerchs, H. (1971), Sobre camarillas y núcleos , Tech. Informe, Departamento de Comp. Sci., Univ. de Toronto.
- Liu, Yunlong Liu; Wang, Jianxin; Guo, Jiong; Chen, Jianer (2012), "Complejidad y algoritmos parametrizados para la edición de Cograph", Informática teórica , 461 : 45–54, doi : 10.1016 / j.tcs.2011.11.040.
- Nastos, James; Gao, Yong (2010), "Una nueva estrategia de ramificación para problemas de modificación de gráficos parametrizados", Lecture Notes in Computer Science , 6509 : 332–346, arXiv : 1006.3020 , Bibcode : 2010LNCS.6509..332N , doi : 10.1007 / 978- 3-642-17461-2_27 , ISBN 978-3-642-17460-5.
- Parra, Andreas; Scheffler, Petra (1997), "Caracterizaciones y aplicaciones algorítmicas de incrustaciones de grafos cordales", Cuarto taller de Twente sobre gráficos y optimización combinatoria (Enschede, 1995), Matemáticas aplicadas discretas , 79 (1-3): 171-188, doi : 10.1016 / S0166-218X (97) 00041-3 , MR 1478250.
- Seinsche, D. (1974), "On a property of the class of n -colorable graphs", Journal of Combinatorial Theory , Serie B, 16 (2): 191-193, doi : 10.1016 / 0095-8956 (74) 90063 -X , MR 0337679.
- Sumner, DP (1974), "Gráficos Dacey", Journal of the Australian Mathematical Society , 18 (4): 492–502, doi : 10.1017 / S1446788700029232 , MR 0382082 CS1 maint: parámetro desalentado ( enlace ).
enlaces externos
- "Gráficos de Cograph" , Sistema de información sobre inclusiones de clases de gráficos
- Weisstein, Eric W. "Cograph" . MathWorld .