Cograph

Un cografo es, en la teoría de grafos , un grafo que se puede generar mediante complementación y unión disjunta del grafo en un nodo.

La mayoría de los problemas algorítmicos se pueden resolver en esta clase en tiempo polinómico, e incluso lineal, debido a sus propiedades estructurales.

Definiciones y caracterizaciones

Esta familia de gráficos fue introducida por varios autores de forma independiente en la década de 1970 con varios nombres, incluidos los gráficos D *, los gráficos Dacey hereditarios y los gráficos de 2 paridad .

Definición

Un cograph es un gráfico simple que se puede construir de forma recursiva de acuerdo con las siguientes reglas:

• la gráfica en un vértice es una cografía,
• el complemento de un cografo es un cografo,
• la unión de dos cografías es una cografía.

Definición usando la operación de unión

La "unión" de dos grafos disjuntos y , es la operación que consiste en crear un nuevo grafo , donde y . Esta operación es de hecho el complemento de la unión de las complementarias. GRAMO1=(V1,mi1){\ Displaystyle G_ {1} = (V_ {1}, E_ {1})}GRAMO2=(V2,mi2){\ Displaystyle G_ {2} = (V_ {2}, E_ {2})}GRAMO=(V,mi){\ Displaystyle G = (V, E)}V=V1∪V2{\ Displaystyle V = V_ {1} \ cup V_ {2}}mi=mi1∪mi2∪{(I,j)|I∈V1,j∈V2}{\ Displaystyle E = E_ {1} \ cup E_ {2} \ cup \ {(i, j) | i \ in V_ {1}, j \ in V_ {2} \}}

Un cograph es entonces un gráfico que se puede formar a partir de los gráficos en un vértice, por "unión" y por unión.

Caracterizaciones

Hay muchas caracterizaciones de las cografías, que incluyen:

• los cografos son los grafos libres , es decir, los que no tienen el camino en cuatro vértices como subgrafo inducido;PAG4{\ Displaystyle P_ {4}}
• Los cografos son grafos para los cuales todos los subgrafos inducidos no triviales tienen dos vértices que tienen la misma vecindad .
• Las cografías son las gráficas de inversiones de permutaciones separables .

Coarbre

Un coarbre describe un cografo, gracias a las operaciones que son necesarias para construirlos.

Las hojas representan los nodos de la cografía y los nodos internos representan operaciones. Los nodos marcados con un 0 representan la unión de las cografías representadas por los subárboles y los marcados con un 1 representan la "unión" de estas cografías. Hay un borde entre dos nodos del árbol si y solo si el ancestro común más pequeño de estos nodos está etiquetado con 1.

Esta representación es única. Es una forma compacta de representar cografías.

Además, al intercambiar los 1 y los 0, obtenemos el coárbol del gráfico complementario .

Propiedades e inclusiones matemáticas

• La familia del cografo es estable por subgrafos inducidos;
• Las cografías son gráficas perfectas .
• Las gráficas Turán son cografías.
• Las cografías son gráficos de permutación y gráficos de comparabilidad .

Propiedades algorítmicas

Las cografías se pueden reconocer en tiempo lineal. La mayoría de los problemas clásicos se pueden resolver en tiempo lineal en esta clase, por ejemplo, los problemas relacionados con las camarillas y los ciclos hamiltonianos . El problema de corte máximo es polinomial en esta clase.

En un contexto de computación distribuida síncrona, la caracterización por 4 caminos excluidos permite reconocer las cografías en un número constante de vueltas.

Notas y referencias

1. ver en particular ( Jung 1978 ), ( Sumner 1974 ) y ( Burlet y Uhry 1984 )
2. Ver ( Corneil, Lerchs y Burlingham 1981 ) y ( Seinsche 1974 ).
3. Esto se deriva directamente de la caracterización libre de P4.
4. ( Corneil, Perl y Stewart 1985 )
5. Consulte la página relacionada sobre el sistema de información sobre clases de gráficos y sus inclusiones
6. Ver ( Bodlaender y Jansen 2000 )
7. ( Fraigniaud, Halldorsson y Korman 2012 )

Bibliografía

• HA Jung , "  Sobre una clase de posets y las correspondientes gráficas de comparabilidad  ", Journal of Combinatorial Theory, Serie B , vol.  24, n o  21978, p.  125-133 ( DOI  10.1016 / 0095-8956 (78) 90013-8 ).

• DP Sumner , "  Gráficos de Dacey  ", J. Austral. Matemáticas. Soc. , vol.  18, n o  4,1974, p.  492–502 ( DOI  10.1017 / S1446788700029232 ).

• M. Burlet y JP Uhry , "  Temas sobre gráficos perfectos (gráficos de paridad)  ", Annals of Discrete Mathematics , vol.  21,1984, p.  253–277.

• DG Corneil , H. Lerchs y L. Stewart Burlingham , "  Gráficos reducibles de complemento  ", Matemáticas aplicadas discretas , vol.  3, n o  3,1981, p.  163-174 ( DOI  10.1016 / 0166-218X (81) 90013-5 ).

• DG Corneil , Y. Perl y LK Stewart , "  Un algoritmo de reconocimiento lineal para cografías  ", SIAM Journal on Computing , vol.  14, n o  4,1985, p.  926–934 ( DOI  10.1137 / 0214065 , revisiones de matemáticas  0807891 ).

• Hans L. Bodlaender y Klaus Jansen , "  Sobre la complejidad del problema de corte máximo  ", Nord. J. Comput. , vol.  7, n o  1,2000, p.  14-31.

• D. Seinsche , "  Sobre una propiedad de la clase de gráficos n -colorables  ", Journal of Combinatorial Theory, Serie B , vol.  16, n o  21974, p.  191-193 ( DOI  10.1016 / 0095-8956 (74) 90063-X , Revisiones de matemáticas  0337679 ).

• Pierre Fraigniaud , Magnus M Halldorsson y Amos Korman , "Sobre el impacto de los identificadores en la decisión local" , en Principios de sistemas distribuidos ,2012, p.  224-238

Ver también

enlaces externos

• La familia de cograph sobre el sistema de información sobre clases de gráficos y sus inclusiones
• (en) Eric W. Weisstein , "  Cograph  " , en MathWorld