Profundidad del árbol

Invariante numérico de grafos

En teoría de grafos , la profundidad de árbol de un grafo no dirigido conexo es un invariante numérico de , la altura mínima de un árbol de Trémaux para un supergrafo de . Este invariante y sus parientes cercanos han tenido muchos nombres diferentes en la literatura, incluidos número de clasificación de vértices, número cromático ordenado y altura mínima del árbol de eliminación; también está estrechamente relacionado con el rango de ciclo de los grafos dirigidos y la altura de estrella de los lenguajes regulares . ^[1] Intuitivamente, donde el ancho de árbol de un grafo mide qué tan lejos está de ser un árbol , este parámetro mide qué tan lejos está un grafo de ser una estrella . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Definiciones

La profundidad del árbol de un gráfico se puede definir como la altura mínima de un bosque con la propiedad de que cada borde de conecta un par de nodos que tienen una relación ancestro-descendiente entre sí en . ^[2] Si está conectado, este bosque debe ser un solo árbol; no necesita ser un subgráfico de , pero si lo es, es un árbol Trémaux para . ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

El conjunto de pares ancestro-descendiente en forma un grafo trivialmente perfecto , y la altura de es el tamaño de la camarilla más grande en este grafo. Por lo tanto, la profundidad del árbol puede definirse alternativamente como el tamaño de la camarilla más grande en un supergrafo trivialmente perfecto de , reflejando la definición de ancho del árbol como uno menos que el tamaño de la camarilla más grande en un supergrafo cordal de . ^[3] ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle G}$

Otra definición es la siguiente:

$${\displaystyle \operatorname {td} (G)={\begin{cases}1,&{\text{if }}|G|=1;\\1+\min _{v\in V}\operatorname {td} (G-v),&{\text{if }}G{\text{ is connected and }}|G|>1;\\\max _{i}{\rm {td}}(G_{i}),&{\text{otherwise}};\end{cases}}}$$

donde es el conjunto de vértices de y son los componentes conectados de . ^[4] Esta definición refleja la definición de rango de ciclo de gráficos dirigidos, que utiliza conectividad fuerte y componentes fuertemente conectados en lugar de conectividad no dirigida y componentes conectados. ${\displaystyle V}$ ${\displaystyle G}$ ${\displaystyle G_{i}}$ ${\displaystyle G}$

La profundidad del árbol también puede definirse utilizando una forma de coloración de grafos . Una coloración centrada de un grafo es una coloración de sus vértices con la propiedad de que cada subgrafo inducido conectado tiene un color que aparece exactamente una vez. Entonces, la profundidad del árbol es el número mínimo de colores en una coloración centrada del grafo dado. Si es un bosque de altura con la propiedad de que cada arista de conecta un ancestro y un descendiente en , entonces una coloración centrada de utilizando colores puede obtenerse coloreando cada vértice por su distancia desde la raíz de su árbol en . ^[5] ${\displaystyle F}$ ${\displaystyle d}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle F}$

Finalmente, esto se puede definir en términos de un juego de guijarros , o más precisamente como un juego de policías y ladrones . Considere el siguiente juego, jugado en un grafo no dirigido. Hay dos jugadores, un ladrón y un policía. El ladrón tiene un guijarro que puede mover a lo largo de los bordes del grafo dado. El policía tiene un número ilimitado de guijarros, pero quiere minimizar la cantidad de guijarros que usa. El policía no puede mover un guijarro después de que se haya colocado en el grafo. El juego procede de la siguiente manera. El ladrón coloca su guijarro. Luego, el policía anuncia dónde quiere colocar un nuevo guijarro de policía. El ladrón puede mover su guijarro a lo largo de los bordes, pero no a través de los vértices ocupados. El juego termina cuando el jugador policía coloca un guijarro sobre el guijarro del ladrón. La profundidad del árbol del grafo dado es el número mínimo de guijarros que necesita el policía para garantizar una victoria. ^[6] Para un grafo en estrella , bastan dos piedras: la estrategia consiste en colocar una piedra en el vértice central, obligando al ladrón a apoyarse en un brazo, y luego colocar la piedra restante sobre el ladrón. Para un camino con vértices, el policía utiliza una estrategia de búsqueda binaria , que garantiza que se necesiten como máximo piedras. ${\displaystyle n}$ ${\displaystyle \lceil \log _{2}(n+1)\rceil }$

Ejemplos

Las profundidades de árbol del gráfico completo y del gráfico bipartito completo son ambas cuatro, mientras que la profundidad de árbol del gráfico de ruta es tres. ${\displaystyle K_{4}}$ ${\displaystyle K_{3,3}}$ ${\displaystyle P_{7}}$

La profundidad del árbol de un grafo completo es igual a su número de vértices. En este caso, el único bosque posible para el cual cada par de vértices está en una relación ancestro-descendiente es un camino único. De manera similar, la profundidad del árbol de un grafo bipartito completo es . En efecto, los nodos que se colocan en las hojas del bosque deben tener al menos ancestros en . Un bosque que logre este límite puede construirse formando un camino para el lado más pequeño de la bipartición, con cada vértice en el lado más grande de la bipartición formando una hoja en conectada al vértice inferior de este camino. ${\displaystyle F}$ ${\displaystyle K_{x,y}}$ ${\displaystyle \min(x,y)+1}$ ${\displaystyle F}$ ${\displaystyle \min(x,y)}$ ${\displaystyle F}$ ${\displaystyle \min(x,y)+1}$ ${\displaystyle F}$

La profundidad del árbol de una ruta con vértices es exactamente . Se puede formar un bosque que represente esta ruta con esta profundidad colocando el punto medio de la ruta como la raíz de y recurriendo dentro de las dos rutas más pequeñas a cada lado de esta. ^[7] ${\displaystyle n}$ ${\displaystyle \lceil \log _{2}(n+1)\rceil }$ ${\displaystyle F}$ ${\displaystyle F}$

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

Cualquier bosque de -vértices tiene una profundidad de árbol . Porque, en un bosque, siempre se puede encontrar un número constante de vértices cuya eliminación deja un bosque que se puede dividir en dos subbosques más pequeños con, como máximo, vértices cada uno. Al dividir recursivamente cada uno de estos dos subbosques, se puede derivar fácilmente un límite superior logarítmico de la profundidad de árbol. La misma técnica, aplicada a una descomposición en árbol de un grafo, muestra que, si el ancho de árbol de un grafo de -vértices es , entonces la profundidad de árbol de es . ^[8] Dado que los grafos externalplanares , los grafos serie-paralelos y los grafos de Halin tienen todos un ancho de árbol acotado, todos también tienen, como máximo, una profundidad de árbol logarítmica. Los grafos típicos con una gran profundidad de árbol y un ancho de árbol pequeño son los árboles binarios perfectos y los caminos. Precisamente, existe una constante con la siguiente propiedad: si un grafo tiene una profundidad de árbol al menos y un ancho de árbol menor que entonces contiene un árbol binario perfecto con una altura o un camino de longitud como menor. ^[9] ${\displaystyle n}$ ${\displaystyle O(\log n)}$ ${\displaystyle 2n/3}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle t}$ ${\displaystyle G}$ ${\displaystyle O(t\log n)}$ ${\displaystyle C}$ ${\displaystyle Ck^{5}\log ^{2}k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 2^{k}}$

En la otra dirección, el ancho del árbol de un gráfico es como máximo igual a su profundidad de árbol. Más precisamente, el ancho del árbol es como máximo el ancho de ruta , que es como máximo uno menos que la profundidad del árbol. ^[10]

Gráficos menores

Un menor de un grafo es otro grafo formado a partir de un subgrafo de mediante la contracción de algunas de sus aristas. La profundidad de árbol es monótona bajo menores: cada menor de un grafo tiene una profundidad de árbol como máximo igual a la profundidad de árbol de sí mismo. ^[11] Por lo tanto, por el teorema de Robertson-Seymour , para cada fijo el conjunto de grafos con profundidad de árbol como máximo tiene un conjunto finito de menores prohibidos . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle d}$

Si es una clase de grafos cerrados bajo la toma de grafos menores, entonces los grafos en tienen profundidad de árbol si y solo si no incluye todos los grafos de ruta . ^[12] Más precisamente, hay una constante tal que cada grafo de profundidad de árbol contiene al menos uno de los siguientes menores (cada uno de profundidad de árbol al menos ): ^[9] ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle O(1)}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle c}$ ${\displaystyle k^{c}}$ ${\displaystyle k}$

• La rejilla, ${\displaystyle k\times k}$
• el árbol binario completo de altura , ${\displaystyle k}$
• El camino del orden . ${\displaystyle 2^{k}}$

Subgrafos inducidos

Además de comportarse bien bajo menores de grafos, la profundidad de árbol tiene conexiones cercanas con la teoría de subgrafos inducidos de un grafo. Dentro de la clase de grafos que tienen profundidad de árbol como máximo (para cualquier entero fijo ), la relación de ser un subgrafo inducido forma un cuasidiordenamiento bien ordenado . ^[13] La idea básica de la prueba de que esta relación es un cuasidiordenamiento bien ordenado es usar la inducción en ; los bosques de altura pueden interpretarse como secuencias de bosques de altura (formadas al eliminar las raíces de los árboles en el bosque de altura) y el lema de Higman puede usarse junto con la hipótesis de inducción para mostrar que estas secuencias están cuasidiordenadas bien. ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d-1}$ ${\displaystyle d}$

El ordenamiento cuasi-bueno implica que cualquier propiedad de los grafos que sea monótona con respecto a los subgrafos inducidos tiene un número finito de subgrafos inducidos prohibidos y, por lo tanto, puede probarse en tiempo polinomial en grafos con una profundidad de árbol acotada. Los grafos con una profundidad de árbol como máximo también tienen un conjunto finito de subgrafos inducidos prohibidos. ^[14] ${\displaystyle d}$

Si es una clase de gráficos con degeneración acotada , los gráficos en tienen profundidad de árbol acotada si y solo si hay un gráfico de ruta que no puede ocurrir como un subgráfico inducido de un gráfico en . ^[12] ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

Complejidad

Calcular la profundidad del árbol es computacionalmente difícil: el problema de decisión correspondiente es NP-completo . ^[15] El problema sigue siendo NP-completo para los grafos bipartitos (Bodlaender et al. 1998), así como para los grafos cordales . ^[16]

En el lado positivo, la profundidad del árbol se puede calcular en tiempo polinomial en gráficos de intervalo, ^[17] así como en gráficos de permutación, trapezoidales, de arco circular, de permutación circular y de co-comparabilidad de dimensión acotada. ^[18] Para árboles no dirigidos, la profundidad del árbol se puede calcular en tiempo lineal. ^[19]

Bodlaender et al. (1995) ofrecen un algoritmo de aproximación para la profundidad del árbol con una relación de aproximación de , basado en el hecho de que la profundidad del árbol siempre está dentro de un factor logarítmico del ancho del árbol de un gráfico. ${\displaystyle O((\log n)^{2})}$

Debido a que la profundidad del árbol es monótona bajo los menores del grafo, es manejable con parámetros fijos : hay un algoritmo para calcular la profundidad del árbol que se ejecuta en tiempo , donde es la profundidad del grafo dado y es su número de vértices. Por lo tanto, para cada valor fijo de , el problema de probar si la profundidad del árbol es como máximo se puede resolver en tiempo polinomial . Más específicamente, la dependencia de en este algoritmo se puede hacer lineal, por el siguiente método: calcule un árbol de búsqueda en profundidad primero y pruebe si la profundidad de este árbol es mayor que . Si es así, la profundidad del árbol del grafo es mayor que y el problema está resuelto. Si no, el árbol de búsqueda en profundidad primero poco profundo se puede utilizar para construir una descomposición de árbol con ancho acotado, y las técnicas de programación dinámica estándar para grafos de ancho de árbol acotado se pueden utilizar para calcular la profundidad en tiempo lineal. ^[20] ${\displaystyle f(d)n^{O(1)}}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle 2^{d}}$ ${\displaystyle d}$

También es posible calcular la profundidad del árbol con exactitud, para gráficos cuya profundidad de árbol puede ser grande, a tiempo para una constante ligeramente menor que 2. ^[21] ${\displaystyle O(c^{n})}$ ${\displaystyle c}$

Notas

1. Bodlaender y col. (1998); Rossman (2008); Nešetřil y Ossona de Méndez (2012), pág. 116.
2. Nešetřil & Ossona de Méndez (2012), Definición 6.1, p. 115.
3. Eppstein, David (15 de noviembre de 2012), Parámetros gráficos y camarillas en supergrafos.
4. Nešetřil y Ossona de Méndez (2012), Lema 6.1, p. 117.
5. Nešetřil & Ossona de Mendez (2012), Sección 6.5, "Coloraciones centradas", págs. 125-128.
6. Gruber y Holzer (2008), Teorema 5, Hunter (2011), Teorema principal.
7. Nešetřil & Ossona de Méndez (2012), Fórmula 6.2, p. 117.
8. Bodlaender y col. (1995); Nešetřil & Ossona de Méndez (2012), Corolario 6.1, p. 124.
9. Kawarabayashi y Rossman (2018)
10. Bodlaender y col. (1995); Nešetřil y Ossona de Méndez (2012), pág. 123.
11. Nešetřil y Ossona de Méndez (2012), Lema 6.2, p. 117.
12. Nešetřil & Ossona de Méndez (2012), Proposición 6.4, p. 122.
13. Nešetřil y Ossona de Méndez (2012), Lema 6.13, p. 137.
14. Nešetřil & Ossona de Mendez (2012), p. 138. La figura 6.6 en la p. 139 muestra los 14 subgrafos prohibidos para grafos con una profundidad de árbol de como máximo tres, acreditados a la tesis doctoral de 2007 de Zdeněk Dvořák .
15. Pothen (1988).
16. Dereniowski y Nadolski (2006).
17. Aspvall y Heggernes (1994).
18. Deogun y otros (1999).
19. Iyer, Ratliff y Vijayan (1988); Schäffer (1989).
20. Nešetřil & Ossona de Mendez (2012), p. 138. Bodlaender et al. (1998) presentaron anteriormente un algoritmo de tiempo lineal más complicado basado en la planaridad de los menores excluidos para la profundidad del árbol. Para algoritmos parametrizados mejorados, consulte Reidl et al. (2014).
21. Fomin, Giannopoulou y Pilipczuk (2013).

Referencias

• Aspvall, Bengt; Heggernes, Pinar (1994), "Búsqueda de árboles de eliminación de altura mínima para gráficos de intervalos en tiempo polinomial", BIT , 34 (4): 484–509, doi :10.1007/BF01934264, S2CID  16141974.
• Bodlaender, Hans L .; Deogun, Jitender S.; Jansen, Klaus; Kloks, tonelada; Kratsch, Dieter; Müller, Haiko; Tuza, Zsolt (1998), "Clasificaciones de gráficos" (PDF) , Revista SIAM de Matemáticas Discretas , 11 (1): 168–181, doi :10.1137/S0895480195282550
• Bodlaender, Hans L .; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton (1995), "Aproximación del ancho del árbol, el ancho de la ruta, el tamaño del frente y el árbol de eliminación más corto", Journal of Algorithms , 18 (2): 238–255, CiteSeerX  10.1.1.29.7198 , doi :10.1006/jagm.1995.1009.
• Deogun, Jitender S.; Kloks, Ton; Kratsch, Dieter; Müller, Haiko (1999), "Sobre el problema de clasificación de vértices para trapezoide, arco circular y otros gráficos", Discrete Applied Mathematics , 98 (1–2): 39–63, doi : 10.1016/S0166-218X(99)00179-1.
• Dereniowski, D.; Nadolski, A. (2006), "Clasificación de vértices de grafos cordales y árboles ponderados", Information Processing Letters , 98 (3): 96–100, doi :10.1016/j.ipl.2005.12.006.
• Fomin, Fedor V.; Giannopoulou, Archontia C.; Pilipczuk, Michał (2013), "Computing tree-depth faster than 2 ⁿ ", en Gutin, Gregory; Szeider, Stefan (eds.), Parameterized and Exact Computation: 8th International Symposium, IPEC 2013, Sophia Antipolis, Francia, 4-6 de septiembre de 2013, Documentos revisados ​​seleccionados , Lecture Notes in Computer Science, vol. 8246, págs. 137–149, arXiv : 1306.3857 , doi :10.1007/978-3-319-03898-8_13, ISBN 978-3-319-03897-1.
• Gruber, Hermann; Holzer, Markus (2008), "Autómatas finitos, conectividad de dígrafos y tamaño de expresiones regulares" (PDF) , Proc. 35th International Colloquium on Automata, Languages ​​and Programming , Apuntes de clase sobre informática, vol. 5126, Springer-Verlag, págs. 39–50, doi :10.1007/978-3-540-70583-3_4, ISBN 978-3-540-70582-6.
• Hunter, Paul (2011), "Búsqueda LIFO en dígrafos: un juego de búsqueda de rangos cíclicos", 18.º Simposio internacional sobre fundamentos de la teoría de la computación , Lecture Notes on Computer Science, vol. 6914, Springer-Verlag, págs. 217–228, arXiv : 1103.6019 , doi :10.1007/978-3-642-22953-4_19, ISBN 978-3-642-22952-7, Número de identificación del sujeto  14278138
• Iyer, Ananth V.; Ratliff, H. Donald; Vijayan, Gopalakrishnan (1988), "Clasificación óptima de nodos de árboles", Information Processing Letters , 28 (5): 225–229, doi :10.1016/0020-0190(88)90194-9.
• Kawarabayashi, Ken-ichi ; Rossman, Benjamin (2018), "Una aproximación polinomial de menor excluido de la profundidad del árbol", Actas del vigésimo noveno simposio anual ACM-SIAM sobre algoritmos discretos , SIAM, págs. 234–246, doi : 10.1137/1.9781611975031.17 , ISBN 978-1-61197-503-1.
• Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "Capítulo 6. Árboles de altura acotada y profundidad de árbol", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, págs. 115–144, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, Sr.  2920058.
• Pothen, Alex (1988), La complejidad de los árboles de eliminación óptimos , Informe técnico CS-88-13, Universidad Estatal de Pensilvania.
• Reidl, Felix; Rossmanith, Peter; Sánchez Villaamil, Fernando; Sikdar, Somnath (2014), "A faster parameterized algorithm for treedepth", en Esparza, Javier; Fraigniaud, Pierre; Husfeldt, Thore; et al. (eds.), Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhague, Dinamarca, 8-11 de julio de 2014, Actas, Parte I , Lecture Notes in Computer Science, vol. 8572, págs. 931-942, arXiv : 1401.7540 , doi :10.1007/978-3-662-43948-7_77, ISBN 978-3-662-43947-0, Número de identificación del sujeto  7235055.
• Rossman, Benjamin (2008), "Teoremas de preservación del homomorfismo", Journal of the ACM , 55 (3): Artículo 15, doi :10.1145/1379759.1379763, S2CID  306577.
• Schäffer, Alejandro A. (1989), "Ranking óptimo de nodos de árboles en tiempo lineal", Information Processing Letters , 33 (2): 91–96, doi :10.1016/0020-0190(89)90161-0.