En la teoría de grafos , el árbol de profundidad de un conectado grafo no dirigido G es un numérico invariante de G , la altura mínima de un árbol Tremaux para un supergraph de G . Este invariante y sus parientes cercanos han recibido muchos nombres diferentes en la literatura, incluido el número de clasificación del vértice, 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, donde elEl parámetro de ancho de gráfico de treewidth mide qué tan lejos está un gráfico de ser un árbol , este parámetro mide qué tan lejos está un gráfico de ser una estrella .
Definiciones
El árbol de profundidad de un gráfico de G puede ser definida como la altura mínima de un bosque F con la propiedad de que cada borde de G conecta un par de nodos que tienen una relación ancestro-descendiente entre sí en F . [2] Si G está conectado, este bosque debe ser un solo árbol; no tiene que ser un subgrafo de G , pero si lo es, se trata de un árbol de Tremaux de G .
El conjunto de pares ancestro-descendiente en F forma un gráfico trivialmente perfecto , y la altura de F es el tamaño de la camarilla más grande en este gráfico. Por lo tanto, el árbol de profundidad, alternativamente, se puede definir como el tamaño de la más grande clique en un supergraph trivialmente perfecta de G , lo que refleja la definición de treewidth como uno menos que el tamaño de la más grande clique en un cordal supergraph de G . [3]
Otra definición es la siguiente:
donde V es el conjunto de vértices de G y elson los componentes conectados de G . [4] Esta definición refleja la definición de rango de ciclo de gráficos dirigidos, que utiliza una fuerte conectividad y componentes fuertemente conectados en lugar de la conectividad no dirigida y los componentes conectados.
La profundidad del árbol también se puede definir utilizando una forma de coloración gráfica . 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 F es un bosque de altura d con la propiedad de que cada borde de G conecta un ancestro y un descendiente en el árbol, entonces se puede obtener una coloración centrada de G usando d colores coloreando cada vértice por su distancia desde la raíz de su árbol en F . [5]
Finalmente, se puede definir esto 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 gráfico 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 gráfico dado. La 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 haberlo colocado en el gráfico. El juego procede de la siguiente manera. El ladrón coloca su guijarro. La policía luego anuncia dónde quiere colocar una nueva piedra de policía. El ladrón puede entonces 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 encima del guijarro del ladrón. La profundidad del árbol del gráfico dado es el número mínimo de guijarros que necesita el policía para garantizar una victoria. [6] Para un gráfico de estrella , dos guijarros son suficientes: la estrategia es colocar un guijarro en el vértice central, obligando al ladrón a inclinarse sobre un brazo, y luego colocar el guijarro restante sobre el ladrón. Por un camino convértices, la policía utiliza una estrategia de búsqueda binaria , que garantiza que como máximo se necesitan guijarros.
Ejemplos de
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 F posible para el que cada par de vértices está en una relación ancestro-descendiente es una ruta única. De manera similar, la profundidad del árbol de un gráfico bipartito completo K x , y es min ( x , y ) + 1. Porque, los nodos que se colocan en las hojas del bosque F deben tener al menos min ( x , y ) ancestros. en F . Se puede construir un bosque que logre este límite mínimo ( x , y ) + 1 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 F conectada al vértice inferior de esta camino.
La profundidad del árbol de una ruta con n vértices es exactamente. Se puede formar un bosque F que represente este camino con esta profundidad colocando el punto medio del camino como la raíz de F y recurriendo a los dos caminos más pequeños a cada lado del mismo. [7]
Profundidad de los árboles y relación con el ancho del árbol
Cualquier bosque de n- vértices tiene una profundidad de árbol 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 un máximo de 2 n / 3 vértices cada uno. Al dividir recursivamente cada uno de estos dos subbosques, podemos derivar fácilmente un límite superior logarítmico en la profundidad del árbol. La misma técnica, aplicada a la descomposición de un árbol de un gráfico, muestra que, si el ancho del árbol de un gráfico de n -vértices G es t , entonces la profundidad del árbol de G es O ( t log n ). [8] Dado que los gráficos planos exteriores , los gráficos en serie-paralelo y los gráficos de Halin tienen un ancho de árbol limitado, todos ellos también tienen una profundidad de árbol logarítmica como máximo. Los gráficos 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 C con la siguiente propiedad: si un gráfico tiene una profundidad de árbol al menosy el ancho del árbol es menor que k, entonces contiene un árbol binario perfecto con altura k o una ruta de longitudcomo menor. [9]
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 menor de un gráfico G es otro gráfico formado a partir de un subgráfico de G al contraer algunos de sus bordes. La profundidad del árbol es monótona en los menores: cada menor de un gráfico G tiene una profundidad de árbol como máximo igual a la profundidad del árbol de G en sí. [11] Así, según el teorema de Robertson-Seymour , para cada d fijo, el conjunto de gráficos con una profundidad de árbol como máximo d tiene un conjunto finito de menores prohibidos .
Si C es una clase de gráficos cerrados tomando gráficos menores, entonces los gráficos en C tienen profundidad de árbolsi y solo si C no incluye todos los gráficos de ruta . [12] Más precisamente, hay una constante c tal que cada gráfico de treedepth al menoscontiene uno de los siguientes menores (cada uno de treedepth al menos k ): [9]
- la red,
- el árbol binario completo de altura k ,
- el camino del orden .
Subgrafos inducidos
Además de comportarse bien en gráficos menores, la profundidad del árbol tiene estrechas conexiones con la teoría de los subgráficos inducidos de un gráfico. Dentro de la clase de gráficos que tienen una profundidad de árbol como máximo d (para cualquier entero fijo d ), la relación de ser un subgrafo inducido forma un cuasi-ordenamiento bien . [13] La idea básica de la prueba de que esta relación es un cuasi ordenamiento bien es usar la inducción en d ; los bosques de altura d pueden interpretarse como secuencias de bosques de altura d - 1 (formados al eliminar las raíces de los árboles en el bosque de altura d ) y el lema de Higman se puede utilizar junto con la hipótesis de inducción para demostrar que estas secuencias son bien cuasi ordenado.
El buen cuasi-ordenamiento implica que cualquier propiedad de los gráficos que sea monótona con respecto a los subgráficos inducidos tiene un número finito de subgrafos inducidos prohibidos y, por lo tanto, puede probarse en tiempo polinómico en gráficos de profundidad de árbol limitada. Los gráficos con profundidad de árbol como máximo d también tienen un conjunto finito de subgrafos inducidos prohibidos. [14]
Si C es una clase de gráficos con acotada degeneración , los gráficos de C tienen acotada árbol profundidad si y sólo si hay un gráfico de ruta que no pueden ocurrir como un subgrafo inducido de un gráfico en C . [12]
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 gráficos bipartitos ( Bodlaender et al. 1998 ), así como para los 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 acotada. [18] Para árboles no dirigidos, la profundidad del árbol se puede calcular en tiempo lineal. [19]
Bodlaender y col. (1995) dan un algoritmo de aproximación para la profundidad del árbol con una razó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.
Debido a que la profundidad del árbol es monótona en los gráficos menores, es manejable con parámetros fijos : hay un algoritmo para calcular la profundidad del árbol que se ejecuta en el tiempo., donde d es la profundidad del gráfico dado yn es su número de vértices. Por lo tanto, para cada valor fijo de d , el problema de probar si la profundidad del árbol es como máximo d puede resolverse en tiempo polinomial . Más específicamente, la dependencia de n en este algoritmo se puede hacer lineal, mediante el siguiente método: calcule un primer árbol de búsqueda de profundidad y pruebe si la profundidad de este árbol es mayor que 2 d . Si es así, la profundidad del árbol de la gráfica es mayor que dy 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 limitado, y se pueden usar técnicas de programación dinámica estándar para gráficos de ancho de árbol limitado para calcular la profundidad en tiempo lineal. [20]
También es posible calcular la profundidad del árbol exactamente, para gráficos cuya profundidad del árbol puede ser grande, en el tiempo O ( c n ) para una constante c ligeramente menor que 2. [21]
Notas
- ^ Bodlaender y col. (1998) ; Rossman (2008) ; Nešetřil y Ossona de Mendez (2012) , p. 116.
- ^ Nešetřil y Ossona de Mendez (2012) , Definición 6.1, p. 115.
- ^ Eppstein, David (15 de noviembre de 2012), parámetros de gráfico y camarillas en supergráficos.
- ^ Nešetřil y Ossona de Mendez (2012) , Lema 6.1, p. 117.
- ^ Nešetřil y Ossona de Mendez (2012) , Sección 6.5, "Colorantes centrados", págs. 125-128.
- ^ Gruber y Holzer (2008) , Teorema 5, Hunter (2011) , Teorema principal.
- ^ Nešetřil y Ossona de Mendez (2012) , Fórmula 6.2, p. 117.
- ^ Bodlaender y col. (1995) ; Nešetřil y Ossona de Mendez (2012) , Corolario 6.1, p. 124.
- ↑ a b Kawarabayashi y Rossman (2018)
- ^ Bodlaender y col. (1995) ; Nešetřil y Ossona de Mendez (2012) , p. 123.
- ^ Nešetřil y Ossona de Mendez (2012) , Lema 6.2, p. 117.
- ↑ a b Nešetřil y Ossona de Mendez (2012) , Proposición 6.4, p. 122.
- ↑ Nešetřil y Ossona de Mendez (2012) , Lema 6.13, p. 137.
- ^ Nešetřil y Ossona de Mendez (2012) , p. 138. Figura 6.6 en la p. 139 muestra los 14 subgrafos prohibidos para gráficos de profundidad de árbol como máximo tres, acreditados al Ph.D. de 2007. tesis de Zdeněk Dvořák .
- ^ Pothen (1988) .
- ^ Dereniowski y Nadolski (2006) .
- ^ Aspvall y Heggernes (1994) .
- ^ Deogun y col. (1999) .
- ^ Iyer, Ratliff y Vijayan (1988) ; Schäffer (1989) .
- ^ Nešetřil y Ossona de Mendez (2012) , p. 138. Un algoritmo de tiempo lineal más complicado basado en la planaridad de los menores excluidos para la profundidad del árbol fue presentado anteriormente por Bodlaender et al. (1998) . Para obtener algoritmos parametrizados mejorados, consulte Reidl et al. (2014) .
- ^ Fomin, Giannopoulou y Pilipczuk (2013) .
Referencias
- Aspvall, Bengt; Heggernes, Pinar (1994), "Encontrar árboles de eliminación de altura mínima para gráficos de intervalo en tiempo polinomial", BIT , 34 (4): 484–509, doi : 10.1007 / BF01934264.
- Bodlaender, Hans L .; Deogun, Jitender S .; Jansen, Klaus; Kloks, Ton; Kratsch, Dieter; Müller, Haiko; Tuza, Zsolt (1998), "Rankings of graphs" (PDF) , SIAM Journal on Discrete Mathematics , 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, del ancho de la ruta, del tamaño del frente y del á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 trapezoides, arcos circulares y otros gráficos", Matemáticas aplicadas discretas , 98 : 39–63, doi : 10.1016 / S0166-218X (99) 00179-1.
- Dereniowski, D .; Nadolski, A. (2006), "Ranking de vértices de gráficos cordales y árboles ponderados", Information Processing Letters , 98 : 96–100, doi : 10.1016 / j.ipl.2005.12.006.
- Fomin, Fedor V .; Giannopoulou, Archontia C .; Pilipczuk, Michał (2013), "Calcular la profundidad del árbol más rápido que 2 n ", en Gutin, Gregory; Szeider, Stefan (eds.), Parameterized and Exact Computation: 8th International Symposium, IPEC 2013, Sophia Antipolis, Francia, 4-6 de septiembre de 2013, Revised Selected Papers , Lecture Notes in Computer Science, 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 , Lecture Notes on Computer Science, 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 , Lecture Notes on Computer Science, 6914 , Springer-Verlag, págs. 217-228, arXiv : 1103.6019 , doi : 10.1007 / 978-3-642-22953-4_19
- Iyer, Ananth V .; Ratliff, H. Donald; Vijayan, Gopalakrishnan (1988), "Clasificación óptima de los nodos de los árboles", Information Processing Letters , 28 : 225–229, doi : 10.1016 / 0020-0190 (88) 90194-9.
- Kawarabayashi, Ken-ichi ; Rossman, Benjamin (2018), "A Polynomial Excluded-Minor Approximation of Treedepth", 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 limitada y profundidad de los árboles", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, 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 óptima , Tech. Informe 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 del árbol", en Esparza, Javier; Fraigniaud, Pierre; Husfeldt, Thore; et al. (eds.), Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhague, Dinamarca, 8 al 11 de julio de 2014, Actas, Parte I , Lecture Notes in Computer Science, 8572 , págs. 931–942, arXiv : 1401.7540 , doi : 10.1007 / 978-3-662-43948-7_77.
- Rossman, Benjamin (2008), "Teoremas de preservación del homomorfismo", Journal of the ACM , 55 (3): Artículo 15, doi : 10.1145 / 1379759.1379763.
- Schäffer, Alejandro A. (1989), "Clasificación de nodos óptima de árboles en tiempo lineal", Information Processing Letters , 33 : 91–96, doi : 10.1016 / 0020-0190 (89) 90161-0 , hdl : 10338.dmlcz / 140723.