Profundidad del árbol (teoría de grafos)

En la teoría de grafos, la profundidad del árbol de un grafo no dirigido conectado G es la invariante numérica de G , la altura mínima del árbol de Tremaux para un supergrafo de G . Este invariante y conceptos relacionados aparecen bajo varios nombres en la literatura, incluido el número de clasificación de vértices, el número cromático ordenado y la altura mínima de eliminación de árboles. El concepto también está cerca de conceptos como el rango cíclico de gráficos dirigidos y la altura de iteración del lenguaje de lenguajes regulares [1] [2] ; [3] . Intuitivamente, si el ancho del árbol el gráfico mide qué tan lejos está el gráfico del árbol, la profundidad del árbol mide qué tan lejos está el gráfico de la estrella.

Definiciones

La profundidad del árbol de un gráfico G se puede definir como la altura mínima de un bosque F con la propiedad de que cualquier borde de G conecta un par de vértices conectados por una relación padre-hijo en F [4] . Si G es conexo, este bosque debe ser un solo árbol. El bosque no necesita ser un subgrafo de G , pero si lo es, entonces es un árbol de Tremaux para G.

El conjunto de pares padre-hijo en F forma un gráfico trivialmente perfecto , y la altura de F es el tamaño de la camarilla más grande de este gráfico. Por lo tanto, la profundidad del árbol se puede definir alternativamente como el tamaño de la camarilla más grande en el supergrafo trivialmente perfecto de G , que es una imagen especular del ancho del árbol , que es uno menos que el tamaño de la camarilla más grande en el supergrafo cordal de G [ 5]

Otra definición es la siguiente:

donde V es el conjunto de vértices del grafo G y son las componentes conexas de G [6] . Esta definición refleja la definición de rango cíclico de grafos dirigidos, que usa conectividad fuerte y componentes fuertemente conectados en lugar de conectividad no dirigida y componentes conectados.

La profundidad de un árbol se puede determinar mediante la coloración de gráficos . Un coloreado de gráfico centrado es un coloreado de vértice que tiene la propiedad de que cualquier subgrafo generado conectado tiene un color que ocurre exactamente una vez. Entonces, la profundidad del árbol es el tamaño mínimo de los colores necesarios para una coloración centrada del gráfico. Si F es un bosque de altura d que tiene la propiedad de que cualquier arista de G conecta un ancestro y un hijo en el árbol, entonces se puede obtener una coloración centrada de G con d colores coloreando cada vértice con un número de color igual al distancia desde la raíz en F [7 ] .

Finalmente, se puede definir en términos de un juego de fichas . Más precisamente, exactamente como el juego "policías-ladrones" . Imagina el siguiente juego en un gráfico no dirigido. Hay dos jugadores, un ladrón y un policía. El ladrón tiene una pieza, que mueve a lo largo de los bordes del gráfico. El policía tiene una cantidad ilimitada de fichas, pero quiere minimizar la cantidad de fichas utilizadas. El policía no puede mover sus piezas colocadas en el gráfico. El juego va así. El ladrón coloca su pieza, luego el oficial de policía le dice dónde quiere colocar la siguiente pieza y el ladrón puede mover su pieza a lo largo de los bordes, pero no sobre los vértices ocupados. El juego termina cuando el policía coloca la siguiente pieza encima de la pieza del ladrón. La profundidad del árbol de un gráfico dado determina el número mínimo de fichas requeridas para una ganancia garantizada [8] [9] . Para las estrellas , dos fichas son suficientes: coloque la primera ficha en el centro de la estrella, obligando al ladrón a moverse hacia algún rayo, y luego coloque la segunda ficha en la ficha del ladrón. Para un camino con vértices, el policía usa una estrategia de búsqueda binaria que garantiza que no se usen más tokens.

Ejemplos

La profundidad del árbol de un gráfico completo es igual al número de sus vértices, en cuyo caso el único bosque F posible para el cual cualquier par de vértices debe estar en una relación ancestro-hijo es un camino único. De manera similar, la profundidad del árbol de un grafo bipartito completo K x , y es min( x , y ) + 1, y como sea que coloquemos los vértices, las hojas del bosque F deben tener al menos min( x , y ) ancestros en F . El bosque en el que se alcanza min( x , y ) + 1 se puede construir formando un camino desde los vértices de la parte más pequeña del gráfico, y los vértices de la parte más grande forman las hojas del árbol F conectado a la parte inferior vértice del camino.

La profundidad de un árbol de caminos con n vértices es exactamente . Se puede formar un bosque F que represente este camino con esta profundidad colocando la raíz en el punto medio del camino F y continuando la recursión en dos caminos más pequeños a cada lado de la raíz [10] .

Profundidad de los árboles y relación con el ancho del árbol

Cualquier bosque con n vértices tiene una profundidad de árbol O(log  n ). Para un bosque, siempre se puede encontrar un número constante de vértices, cuya eliminación produce un bosque que se puede dividir en dos subbosques más pequeños con un máximo de 2 n /3 vértices cada uno. Al dividir recursivamente estos dos matorrales, se puede alcanzar fácilmente un límite superior logarítmico en la profundidad del árbol. La misma técnica, aplicada a la descomposición del árbol de gráficos , muestra que si el ancho del árbol de un gráfico G de n vértices es t , entonces la profundidad del árbol de G es O( t  log  n ). [11] [12] Debido a que los gráficos de planos exteriores , los gráficos secuenciales paralelos y los gráficos de Halin tienen un ancho de árbol acotado, todos ellos también tienen una profundidad de árbol logarítmica máxima.

En la otra dirección, el ancho del árbol de un gráfico no excede la profundidad del árbol. Más precisamente, el ancho del árbol no excede el ancho del camino del gráfico , que es como máximo uno menos que la profundidad del árbol [11] [13] .

Contar menores

Un menor de un grafo G es otro grafo formado a partir de un subgrafo de G contrayendo algunas aristas. La profundidad de un árbol es monótona en los menores: cualquier menor de un gráfico G tiene una profundidad de árbol que no excede la profundidad del árbol del propio gráfico G [14] . Así, por el teorema de Robertson-Seymour , para cualquier d fijo , el conjunto de gráficos con profundidad de árbol que no exceda de d tiene un número finito de menores prohibidos .

Si C es una clase de grafos cerrados bajo la formación de menores, entonces los grafos en C tienen profundidad de árbol si y solo si C no incluye todos los caminos [15] .

Subgrafos generados

La profundidad del árbol tiene una estrecha relación con la teoría de los subgrafos generados de un gráfico. En la clase de grafos con profundidad de árbol como máximo d (para cualquier d natural fija ), la propiedad de ser un subgrafo generado está bien cuasi-ordenada [16] . La idea principal detrás de la prueba de que esta conexión está completamente cuasi-ordenada es usar la inducción en d . Los bosques de altura d pueden interpretarse como una secuencia de bosques de altura d  − 1 (formados por el desarraigo de árboles de altura d ) y el lema de Higman puede usarse para mostrar que estas secuencias están bien cuasi-ordenadas.

Del cuasiordenamiento de pozos se deduce que cualquier propiedad de un gráfico que sea monótona en los subgrafos generados tiene un número finito de subgrafos generados prohibidos y, por lo tanto, puede verificarse en tiempo polinomial en gráficos con una profundidad de árbol acotada. Los gráficos con profundidad de árbol como máximo d tienen un número finito de subgráficos secundarios prohibidos. Nexetril y Ossona de Méndez [17] mostraron 14 subgrafos prohibidos para grafos con un ancho de árbol de tres o menos (con referencia a las tesis de disertación de 2007 de Zdenek Dvorak).

Si C es una clase de gráficos con degeneración acotada , los gráficos en C tienen un ancho de árbol acotado si y solo si hay una ruta que no puede aparecer como un subgráfico generado en C [15] .

Dificultad

Determinar la profundidad de un árbol es un problema computacional complejo; el problema de reconocimiento correspondiente es NP-completo [18] . El problema sigue siendo NP-completo para grafos bipartitos [1] , así como para grafos cordales [19] .

En el lado positivo, la profundidad de un árbol se puede calcular en tiempo polinomial para gráficos de intervalo [20] , así como para gráficos de permutación, gráficos trapezoidales, gráficos de intersección de arco circular, gráficos de permutación cíclica y gráficos de comparabilidad de dimensiones acotadas [21 ] . Para árboles no dirigidos, la profundidad del árbol se puede calcular en tiempo lineal [22] [23] .

Bodlender, Gilbert, Hufsteinsson y Klox [11] propusieron un algoritmo de aproximación para encontrar la profundidad de un árbol con un coeficiente de aproximación . El algoritmo se basa en el hecho de que la profundidad de un árbol depende logarítmicamente del ancho del árbol del gráfico.

Dado que la profundidad de un árbol es monótona en los menores del gráfico, el problema de encontrarlo es fijo-paramétricamente solucionable — existe un algoritmo para calcular la profundidad de un árbol que funciona en el tiempo , donde d es la profundidad del gráfico dado y n es el número de vértices. Así, para cualquier valor fijo de d , el problema de verificar si la profundidad de un árbol es mayor que d puede resolverse en tiempo polinomial . Más específicamente, la dependencia de n en este algoritmo se puede hacer lineal de la siguiente manera: construimos un árbol de búsqueda primero en profundidad y verificamos si la profundidad del árbol es mayor que 2 d o no. Si es mayor, la profundidad del árbol es mayor que d y el problema está resuelto. De lo contrario, se puede usar la construcción de árboles de búsqueda superficial para descomponer el árbol , y se puede usar la técnica de programación dinámica estándar para gráficos de ancho de árbol acotado para calcular la profundidad en tiempo lineal [24] . Bodlander, Deogan, Jensen y Klox [1] propusieron anteriormente un algoritmo de solución de tiempo lineal más sofisticado basado en la planaridad de los menores eliminados en la búsqueda en profundidad . Para un algoritmo paramétrico mejorado, consulte Reidl, Rossmanite, Villamil y Sikdar [25] .

Es posible calcular la profundidad del árbol exactamente para gráficos cuyo valor de profundidad puede ser grande en el tiempo O ( c n ) con una constante c ligeramente menor que 2. [26]

Notas

  1. ↑ 1 2 3 Bodlaender y otros, 1998 .
  2. ↑ Rossmann, 2008 .
  3. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 116.
  4. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 115, Definición 6.1.
  5. ↑ David Epstein. Graficar parámetros y camarillas en supergrafos. — 2012 (15 de noviembre). Archivado desde el original el 9 de enero de 2014. .
  6. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 117, Lema 6.1.
  7. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 125–128, Sección 6.5, "Colores centrados".
  8. ↑ Gruber y Holzer 2008 , pág. Teorema 5.
  9. ↑ Hunter, 2011 , Teorema principal.
  10. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 117, Fórmula 6.2.
  11. ↑ 1 2 3 Bodlaender y otros, 1995 .
  12. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 124, Corolario 6.1.
  13. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 123.
  14. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 117, Lema 6.2.
  15. ↑ 1 2 Nešetřil, Ossona de Mendez, 2012 , p. 122, Proposición 6.4.
  16. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 137, Lema 6.13.
  17. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 138. Figura 6.6 en la pág. 139.
  18. ↑ Poten, 1988 .
  19. ↑ Dereniowski, Nadolski, 2006 .
  20. ↑ Aspvall, Heggernes, 1994 .
  21. ↑ Deogun y otros, 1999 .
  22. ↑ Iyer y otros, 1988 .
  23. ↑ Schaffer, 1989 .
  24. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 138.
  25. ↑ Reidl y otros, 2014 .
  26. ↑ Fomin y otros, 2013 .

Literatura