Profundidad del árbol

En teoría de grafos , la profundidad de árbol de un grafo no dirigido conectado${\displaystyle G}$es un invariante numérico de${\displaystyle G}$, la altura mínima de un árbol de Trémaux para un supergrafo de${\displaystyle G}$. Este invariante y sus parientes cercanos han recibido muchos nombres diferentes en la literatura, incluyendo 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, mientras que 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 .

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

El conjunto de pares ancestro-descendiente en${\displaystyle F}$forma un gráfico trivialmente perfecto y la altura de${\displaystyle F}$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${\displaystyle G}$, reflejando la definición de ancho de árbol como uno menos que el tamaño de la camarilla más grande en un supergrafo cordal de${\displaystyle G}$. ^{[ 3 ]}

Otra definición es la siguiente:

$${\displaystyle \operatorname {td} (G)={\begin{cases}1,&{\text{si }}|G|=1;\\1+\min _{v\in V}\operatorname {td} (Gv),&{\text{si }}G{\text{ está conectado y }}|G|>1;\\\max _{i}{\rm {td}}(G_{i}),&{\text{en otro caso}};\end{cases}}}$$

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

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 conexo 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${\displaystyle F}$es un bosque de altura${\displaystyle d}$con la propiedad de que cada borde de${\displaystyle G}$conecta a un antepasado y a un descendiente en${\displaystyle F}$, luego una coloración centrada de${\displaystyle G}$usando${\displaystyle d}$Los colores se pueden obtener coloreando cada vértice por su distancia desde la raíz de su árbol en${\displaystyle F}$. ^{[ 5 ]}

Finalmente, podemos definir esto en términos de un juego de piedras , o más precisamente como un juego de policías y ladrones . Consideremos el siguiente juego, jugado en un grafo 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 las aristas del grafo. El policía tiene un número ilimitado de piedras, pero quiere minimizar la cantidad que usa. El policía no puede mover una piedra una vez colocada en el grafo. El juego se desarrolla así: el ladrón coloca su piedra. El policía anuncia dónde quiere colocar una nueva piedra. El ladrón puede entonces mover su piedra a lo largo de las aristas, pero no a través de vértices ocupados. El juego termina cuando el policía coloca una piedra encima de la piedra del ladrón. La profundidad del árbol del grafo es el número mínimo de piedras que necesita el policía para garantizar la victoria. ^{[ 6 ]} Para un grafo estrella , dos guijarros son suficientes: la estrategia consiste en colocar un guijarro en el vértice central, obligando al ladrón a usar un brazo, y luego colocar el guijarro restante sobre el ladrón. Para un camino con${\displaystyle n}$vértices, el policía utiliza una estrategia de búsqueda binaria , que garantiza que como máximo${\displaystyle \lceil \log _ {2}(n+1)\rceil}$Se necesitan guijarros.

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

La profundidad de un sendero con árboles${\displaystyle n}$vértices es exactamente${\displaystyle \lceil \log _{2}(n+1)\rceil }$Un bosque${\displaystyle F}$La representación de este camino con esta profundidad se puede formar colocando el punto medio del camino como la raíz de${\displaystyle F}$y recursivamente dentro de los dos caminos más pequeños a cada lado de él. ^{[ 7 ]}

Cualquier${\displaystyle n}$-El bosque de vértices tiene profundidad de árbol${\displaystyle O(\log n)}$. 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${\displaystyle 2n/3}$vértices cada uno. Al particionar recursivamente cada uno de estos dos subbosques, se puede derivar fácilmente una cota superior logarítmica en la profundidad del árbol. La misma técnica, aplicada a una descomposición en árbol de un grafo, muestra que, si el ancho del árbol de un${\displaystyle n}$-grafo de vértices${\displaystyle G}$es${\displaystyle t}$, entonces la profundidad del árbol de${\displaystyle G}$es${\displaystyle O(t\log n)}$. ^{[ 8 ]} Dado que los grafos exteriores planares , los grafos serie-paralelo y los grafos de Halin tienen un ancho de árbol acotado, también tienen una profundidad de árbol como máximo logarítmica. Los grafos típicos con gran profundidad de árbol y pequeño ancho de árbol son los árboles binarios perfectos y los caminos. Precisamente, hay una constante${\displaystyle C}$con la siguiente propiedad: si un grafo tiene al menos una profundidad de árbol${\displaystyle Ck^{5}\log ^{2}k}$y ancho del árbol menor que${\displaystyle k}$entonces contiene un árbol binario perfecto con altura${\displaystyle k}$o un camino de longitud${\displaystyle 2^{k}}$como menor de edad. ^{[ 9 ]}

En sentido contrario, el ancho del árbol de un grafo es como máximo igual a su profundidad de árbol. Más precisamente, el ancho del árbol es como máximo igual al ancho del camino , que es como máximo uno menos que la profundidad del árbol. ^{[ 10 ]}

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

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

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

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

El ordenamiento cuasi-bien 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 de profundidad de árbol acotada. Los grafos con profundidad de árbol como máximo${\displaystyle d}$ellos mismos también tienen un conjunto finito de subgrafos inducidos prohibidos. ^{[ 14 ]}

Si${\displaystyle {\mathcal {F}}}$es una clase de grafos con degeneración acotada , los grafos en${\displaystyle {\mathcal {F}}}$tener profundidad de árbol limitada si y solo si existe un grafo de caminos que no puede aparecer como un subgrafo inducido de un grafo en${\displaystyle {\mathcal {F}}}$. ^{[ 12 ]}

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

En el lado positivo, la profundidad del árbol se puede calcular en tiempo polinomial en grafos de intervalos, ^{[ 17 ]} así como en grafos de permutación, trapecio, arco circular, permutación circular y grafos de cocomparabilidad de dimensión acotada. ^{[ 18 ]} Para árboles no dirigidos, la profundidad del árbol se puede calcular en tiempo lineal. ^{[ 19 ]}

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

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

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

• Aspvall, Bengt; Heggernes, Pinar (1994), "Finding Minimum Height Elimination Trees for Interval Graphs in Polynomial Time", 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), "Rankings 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 trapecios, arcos circulares y otros grafos", 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), "Cálculo de la profundidad de árboles más rápido que 2 ⁿ ", en Gutin, Gregory; Szeider, Stefan (eds.), Computación parametrizada y exacta: 8.º Simposio Internacional, IPEC 2013, Sophia Antipolis, Francia, 4-6 de septiembre de 2013, Artículos seleccionados revisados , Lecture Notes in Computer Science, vol.  8246, pp. 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 digrafos y tamaño de expresiones regulares" (PDF) , Actas del 35.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación , Lecture Notes on Computer Science, vol.  5126, Springer-Verlag, pp. 39–50 , doi : 10.1007/978-3-540-70583-3_4 , ISBN  978-3-540-70582-6.
• Hunter, Paul (2011), "LIFO-Search on Digraphs: A Searching Game for Cycle-Rank", 18th International Symposium on Fundamentals of Computation Theory , Lecture Notes on Computer Science, vol.  6914, Springer-Verlag, pp. 217–228 , arXiv : 1103.6019 , doi : 10.1007/978-3-642-22953-4_19 , ISBN  978-3-642-22952-7, S2CID 14278138 
• Iyer, Ananth V.; Ratliff, H. Donald; Vijayan, Gopalakrishnan (1988), "Clasificación óptima de nodos en á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 menores excluidos de la profundidad de árbol", Actas del vigésimo noveno simposio anual ACM-SIAM sobre algoritmos discretos , SIAM, pp. 234–246 , doi : 10.1137/1.9781611975031.17 , ISBN  978-1-61197-503-1.
• Nešetřil, Jaroslav ; Ossona de Méndez, 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, pp. 115–144 , doi : 10.1007/978-3-642-27875-4 , ISBN  978-3-642-27874-7, MR 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), "Un algoritmo parametrizado más rápido para la profundidad de á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-11 de julio de 2014, Actas, Parte I , Lecture Notes in Computer Science, vol.  8572, pp. 931-942 , arXiv : 1401.7540 , doi : 10.1007/978-3-662-43948-7_77 , ISBN  978-3-662-43947-0, S2CID 7235055 .
• Rossman, Benjamin (2008), "Teoremas de preservación de homomorfismos", 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", Information Processing Letters , 33 (2): 91–96 , doi : 10.1016/0020-0190(89)90161-0.