Cografo

En teoría de grafos, un cografo , o un grafo adicionalmente reducible , o un grafo libre de P 4 ,  es un grafo que se puede obtener a partir de un grafo con un solo vértice K 1 mediante operaciones de suma y unión de grafos . Así, una familia de cografos es la clase más pequeña de grafos que contiene K 1 y es cerrada bajo complemento y unión.

Los cografos han sido descubiertos de forma independiente por varios autores desde la década de 1970. Las primeras menciones se pueden encontrar en Young [1] , Lerchs [2] , Zainsche [3] y Sumner [4] . Estos gráficos se denominaron gráficos D* [1] , gráficos de Dacey hereditarios (después del trabajo de James C. Dacey, Jr. sobre redes ortomodulares . Ver Sumner [4] ) y gráficos con dos descendientes de Barlet y Ury [ 5] .

Ver el libro de Brandstedt, Lie y Spinrad [6] para una discusión más detallada de cographs, incluidos los hechos que se dan aquí.

Definición y descripción

Cualquier cografo se puede construir siguiendo las siguientes reglas:

  1. Cualquier vértice individual de un gráfico es un cografo;
  2. Si  es un cografo, entonces su complemento también es un cografo;
  3. Si y  son cografos, entonces su unión disjunta también es cografo.

Se pueden dar varias otras descripciones de cographs. Entre ellos:

Todos los gráficos completos , gráficos bipartitos completos, gráficos de umbral y gráficos de Turan son cográficos. Cualquier cografía es una gráfica de comparabilidad perfecta heredada por la distancia .

Árboles de código

Un árbol de código  es un árbol cuyos vértices internos están etiquetados como 0 y 1. Cualquier árbol de código T define un cografo G que tiene las hojas de T como vértices, y un subárbol con raíz en T corresponde a un subgrafo generado en G definido por un conjunto de hojas descendientes esta parte superior:

Una forma equivalente de construir un cografo a partir de un codificador es que dos vértices estén conectados por una arista si y solo si el antepasado menos común de las hojas correspondientes está etiquetado como 1. Por el contrario, cualquier cografo puede representarse mediante un codificador de esta manera. Si requerimos que todas las etiquetas en todos los caminos desde la raíz hasta las hojas se alternen, tal representación será única [7] .

Propiedades computacionales

Un cografo puede reconocerse en tiempo lineal y una representación codificada puede construirse usando descomposición modular [10] , refinamiento de descomposición [11] o descomposición dividida [12] . Una vez que se ha construido el codificador, muchos problemas familiares de teoría de grafos se pueden resolver atravesando el codificador de abajo hacia arriba.

Por ejemplo, para encontrar la clique máxima en un cografo, calculamos, de abajo hacia arriba, la clique máxima en cada subgrafo representado por un subárbol del codificador. Para cada vértice etiquetado como 0, la camarilla máxima es la camarilla máxima recibida de los descendientes del vértice. Para un vértice etiquetado como 1, la camarilla máxima será la unión de las camarillas calculadas para los descendientes del vértice, y el tamaño de esta camarilla es la suma de los tamaños de las camarillas. Por lo tanto, tomando alternativamente el tamaño máximo y sumando los valores para cada vértice del codificador, calcularemos el tamaño máximo de la camarilla y, alternativamente, eligiendo la camarilla máxima y concatenando, construiremos la camarilla máxima en sí. Un enfoque ascendente similar permite obtener el máximo conjunto independiente , el número cromático , la máxima cobertura de camarilla y la existencia de un camino hamiltoniano en el tiempo lineal. También se pueden usar coárboles para determinar en tiempo lineal si dos cografos son isomorfos .

Si H  es un subgrafo generado de un cografo G , entonces H mismo es un cografo. Se puede obtener un codificador para H quitando algunas de las hojas del codificador para G y luego fusionando los vértices que tienen un solo hijo. Del teorema del árbol de Kruskal [ se deduce que la relación que debe generar un subgrafo es un buen cuasi-orden sobre cografos [13] . Entonces, si una familia de cografos (como los cografos planares ) se cierra bajo la operación de construir un subgrafo generado, entonces tiene un número finito de subgrafos generados prohibidos . Desde un punto de vista computacional, esto significa que verificar si un gráfico pertenece a dicha familia se puede hacer en tiempo lineal utilizando un recorrido de abajo hacia arriba del codificador del gráfico dado.

Notas

  1. ↑ 1 2 3 Jung, 1978 .
  2. ↑ Lerchs, 1971 .
  3. ↑ Seinsche, 1974 .
  4. ↑ 12 Summer , 1974 .
  5. ↑ Burlet, Uhry, 1984 .
  6. ↑ Brandstädt, Le, Spinrad, 1999 .
  7. ↑ 1 2 Corneil, Lerchs, Burlingham, 1981 .
  8. ↑ Courcelle, Olariu, 2000 .
  9. ↑ Bose, Buss, Lubiw, 1998 .
  10. ↑ Corneil, Perl, Stewart, 1985 .
  11. ↑ Habib, Paul, 2005 .
  12. ↑ Gioan, Paul, 2008 .
  13. ↑ Damaschke, 1990 .

Literatura

Enlaces