Profundidad del árbol

Invariante numérica de gráficos.

En teoría de grafos , la profundidad del árbol de un gráfico no dirigido conectado es una invariante numérica de , la altura mínima de un árbol de Trémaux para un supergrafo de . Esta invariante y sus parientes cercanos han recibido muchos nombres diferentes en la literatura, incluido el número de clasificación de vértices, el número cromático ordenado y la altura mínima del árbol de eliminación; también está estrechamente relacionado con el rango cíclico de los gráficos dirigidos y la altura de las estrellas de los lenguajes regulares . ^[1] Intuitivamente, mientras que el ancho del árbol de un gráfico mide qué tan lejos está de ser un árbol , este parámetro mide qué tan lejos está un gráfico 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 conecta un par de nodos que tienen una relación ancestro-descendiente entre sí . ^[2] Si está conectado, este bosque debe ser un solo árbol; No es necesario que sea un subgrafo 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 de ancestros-descendientes forma un gráfico trivialmente perfecto , y la altura de es el tamaño de la camarilla más grande en este gráfico. 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 una 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 se puede definir mediante una forma de coloración de gráficos . Una coloración centrada de un gráfico 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 gráfico dado. Si es un bosque de altura con la propiedad de que cada borde de conecta a un antepasado y un descendiente en , entonces se puede obtener una coloración centrada usando colores 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, podemos definirlo 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 sobre un gráfico no dirigido. Hay dos jugadores, un ladrón y un policía. El ladrón tiene una piedra que puede mover a lo largo de los bordes del gráfico dado. La policía tiene una cantidad ilimitada de piedras, pero quiere minimizar la cantidad de piedras que usa. El policía no puede mover una piedra después de haberla colocado en el gráfico. El juego se desarrolla de la siguiente manera. El ladrón coloca su piedra. Luego, el policía anuncia dónde quiere colocar un nuevo guijarro policial. El ladrón puede entonces mover su piedra a lo largo de los bordes, pero no a través de los vértices ocupados. El juego termina cuando el policía coloca una piedra encima del ladrón. La profundidad del árbol del gráfico dado es la cantidad mínima de piedras que necesita el policía para garantizar una victoria. ^[6] Para un gráfico estelar , dos piedras son suficientes: la estrategia es colocar una piedra en el vértice central, obligando al ladrón a levantar 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 como máximo se necesitan guijarros. ${\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 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 gráfico completo es igual a su número de vértices. Porque, 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 gráfico bipartito completo es . Porque los nodos que se colocan en las hojas del bosque deben tener al menos ancestros en . Se puede construir un bosque que logre este límite formando un camino para el lado más pequeño de la bipartición, formando cada vértice en el lado más grande de la bipartición una hoja 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 un camino con vértices es exactamente . Se puede formar un bosque que represente este camino con esta profundidad colocando el punto medio del camino como la raíz y recurriendo dentro de los dos caminos más pequeños a cada lado del mismo. ^[7] ${\displaystyle n}$ ${\displaystyle \lceil \log _{2}(n+1)\rceil }$ ${\displaystyle F}$ ${\displaystyle F}$

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

Cualquier bosque de vértice tiene 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 puede dividirse 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 del árbol. La misma técnica, aplicada a la descomposición en árbol de un gráfico, muestra que, si el ancho del árbol de un gráfico de vértices es , entonces la profundidad del árbol es . ^[8] Dado que los gráficos planos externos , los gráficos en serie-paralelos y los gráficos de Halin tienen un ancho de árbol limitado, todos también tienen como máximo una profundidad de árbol logarítmica. Los gráficos típicos con una gran profundidad de árbol y un ancho de árbol pequeño son los árboles binarios perfectos y los caminos. Precisamente, hay una constante con la siguiente propiedad: si un gráfico tiene al menos una profundidad de árbol y un ancho de árbol menor, entonces contiene un árbol binario perfecto con 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 la profundidad del árbol. Más precisamente, el ancho del árbol es como máximo el ancho de la ruta , que es como máximo uno menos que la profundidad del árbol. ^[10]

Graficar menores

Un gráfico menor de un gráfico es otro gráfico formado a partir de un subgrafo de mediante la contracción de algunos de sus bordes. La profundidad del árbol es monótona en menores: cada menor de un gráfico tiene una profundidad de árbol como máximo igual a la profundidad del árbol de sí mismo. ^[11] Así, según el teorema de Robertson-Seymour , para cada conjunto fijo de gráficos 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 gráficos cerrada bajo la toma de gráficos menores, entonces los gráficos tienen profundidad de árbol si y solo si no incluyen todos los gráficos de ruta . ^[12] Más precisamente, existe una constante tal que cada gráfico 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 cuadrícula, ${\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 con gráficos menores, la profundidad del árbol tiene estrechas conexiones con la teoría de los subgrafos inducidos de un gráfico. Dentro de la clase de gráficos que tienen una profundidad de árbol como máximo (para cualquier entero fijo ), la relación de ser un subgrafo inducido forma un cuasi-ordenamiento . ^[13] La idea básica de la prueba de que esta relación es un cuasi-ordenamiento es utilizar la inducción en ; Los bosques de altura pueden interpretarse como secuencias de bosques de altura (formados 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 bien cuasi ordenadas. . ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d-1}$ ${\displaystyle d}$

El cuasiordenamiento correcto implica que cualquier propiedad de los gráficos 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 gráficos de profundidad de árbol limitada. Los gráficos con 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 limitada si y solo si hay un gráfico de ruta que no puede ocurrir como un subgrafo 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 gráficos bipartitos (Bodlaender et al. 1998), así como para gráficos cordales . ^[dieciséis]

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, trapezoide, arco circular, permutación circular y gráficos de cocomparabilidad de dimensión limitada. ^[18] Para árboles no dirigidos, la profundidad del árbol se puede calcular en tiempo lineal. ^[19]

Bodlaender et al. (1995) dan 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 en gráficos menores, es manejable con parámetros fijos : existe un algoritmo para calcular la profundidad del árbol que se ejecuta en el tiempo , donde es la profundidad del gráfico 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 polinómico . Más específicamente, la dependencia en este algoritmo se puede hacer lineal mediante el siguiente método: calcular un primer árbol de búsqueda en profundidad y probar si la profundidad de este árbol es mayor que . Si es así, la profundidad del árbol del gráfico es mayor y el problema está resuelto. De lo contrario, el primer árbol de búsqueda de poca profundidad se puede usar para construir una descomposición de árbol con ancho acotado, y se pueden usar técnicas de programación dinámica estándar para gráficos de ancho de árbol acotado 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 exactamente, para gráficos cuya profundidad del árbol puede ser grande, en el 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 y Ossona de Méndez (2012), pág. 138. Figura 6.6 en la pág. 139 muestra los 14 subgrafos prohibidos para gráficos de profundidad de árbol como máximo tres, acreditados al Ph.D. tesis 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 y Ossona de Méndez (2012), pág. 138. Bodlaender et al. proporcionaron anteriormente un algoritmo de tiempo lineal más complicado basado en la planaridad de los menores excluidos para la profundidad del árbol. (1998). Para algoritmos parametrizados mejorados, consulte Reidl et al. (2014).
21. Fomin, Giannopoulou y Pilipczuk (2013).

Referencias

• Aspvall, Bengt; Heggernes, Pinar (1994), "Encontrar árboles de eliminación de altura mínima para gráficos de intervalos en tiempo polinómico", 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, tonelada; Kratsch, Dieter; Müller, Haiko (1999), "Sobre el problema de clasificación de vértices para gráficos trapezoidales, de arco circular y otros", Matemáticas Aplicadas Discretas , 98 (1–2): 39–63, doi : 10.1016/S0166-218X(99)00179 -1.
• Dereniowski, D.; Nadolski, A. (2006), "Clasificaciones de vértices de gráficos cordales y árboles ponderados", Cartas de procesamiento de información , 98 (3): 96–100, doi :10.1016/j.ipl.2005.12.006.
• Fomin, Fedor V.; Giannopoulou, Archontia C.; Pilipczuk, Michał (2013), "Cálculo de la profundidad del árbol más rápido que 2 ⁿ ", en Gutin, Gregory; Szeider, Stefan (eds.), Computación exacta y parametrizada: octavo simposio internacional, IPEC 2013, Sophia Antipolis, Francia, 4 al 6 de septiembre de 2013, artículos seleccionados revisados , Lecture Notes in Computer Science, vol. 8246, págs. 137–149, arXiv : 1306.3857 , doi : 10.1007/978-3-319-03898-8_13.
• Gruber, Hermann; Holzer, Markus (2008), "Autómatas finitos, conectividad de dígrafos y tamaño de expresión regular" (PDF) , Proc. 35º Coloquio Internacional sobre Autómatas, Lenguajes y Programación , Apuntes de conferencias sobre informática, vol. 5126, Springer-Verlag, págs. 39–50, doi :10.1007/978-3-540-70583-3_4.
• Hunter, Paul (2011), "LIFO-Search on Digraphs: A Searching Game for Cycle-Rank", 18º Simposio internacional sobre fundamentos de la teoría de la computación , Apuntes de conferencias sobre informática, vol. 6914, Springer-Verlag, págs. 217–228, arXiv : 1103.6019 , doi : 10.1007/978-3-642-22953-4_19, S2CID  14278138
• Iyer, Ananth V.; Ratliff, H. Donald; Vijayan, Gopalakrishnan (1988), "Clasificación óptima de nodos de árboles", Cartas de procesamiento de información , 28 (5): 225–229, doi :10.1016/0020-0190(88)90194-9.
• Kawarabayashi, Ken-ichi ; Rossman, Benjamin (2018), "Una aproximación polinómica menor excluida 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.
• Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2012), "Capítulo 6. Árboles de altura acotada y profundidad de árbol", Escasa: gráficos, estructuras y algoritmos , Algoritmos y combinatoria, vol. 28, Heidelberg: Springer, págs. 115-144, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, señor  2920058.
• Pothen, Alex (1988), La complejidad de los árboles de eliminación óptima , Tech. Informe CS-88-13, Universidad Estatal de Pensilvania.
• Reidl, Félix; Rossmanith, Peter; Sánchez Villaamil, Fernando; Sikdar, Somnath (2014), "Un algoritmo parametrizado más rápido para la profundidad del árbol", en Esparza, Javier; Fraigniaud, Pierre; Husfeldt, Thore; et al. (eds.), Autómatas, lenguajes y programación: 41.° Coloquio internacional, ICALP 2014, Copenhague, Dinamarca, 8 al 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, S2CID  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), "Clasificación óptima de nodos de árboles en tiempo lineal", Cartas de procesamiento de información , 33 (2): 91–96, doi :10.1016/0020-0190(89)90161-0.