En la teoría de grafos , la descomposición de un árbol es un mapeo de un gráfico en un árbol que se puede usar para definir el ancho del árbol del gráfico y acelerar la resolución de ciertos problemas computacionales en el gráfico.
Las descomposiciones de árboles también se denominan árboles de unión , árboles de camarilla o árboles de unión ; juegan un papel importante en problemas como inferencia probabilística , satisfacción de restricciones , optimización de consultas , [ cita requerida ] y descomposición de matrices .
El concepto de descomposición de árboles fue introducido originalmente por Rudolf Halin ( 1976 ). Posteriormente fue redescubierto por Neil Robertson y Paul Seymour ( 1984 ) y desde entonces ha sido estudiado por muchos otros autores. [1]
Definición
Intuitivamente, la descomposición de un árbol representa los vértices de un gráfico G dado como subárboles de un árbol, de tal manera que los vértices en el gráfico dado son adyacentes solo cuando los subárboles correspondientes se cruzan. Por tanto, G forma un subgrafo del gráfico de intersección de los subárboles. El gráfico de intersección completo es un gráfico cordal .
Cada subárbol asocia un vértice de gráfico con un conjunto de nodos de árbol. Para definir esto formalmente, representamos cada nodo del árbol como el conjunto de vértices asociados con él. Por lo tanto, dado un gráfico G = ( V , E ), la descomposición de un árbol es un par ( X , T ), donde X = { X 1 , ..., X n } es una familia de subconjuntos (a veces llamados bolsas ) de V , y T es un árbol cuyos nodos son los subconjuntos X i , satisfaciendo las siguientes propiedades: [2]
- La unión de todos los conjuntos X i es igual a V . Es decir, cada vértice del gráfico está asociado con al menos un nodo de árbol.
- Para cada borde ( v , w ) en la gráfica, hay un subconjunto X i que contiene tanto v como w . Es decir, los vértices son adyacentes en el gráfico solo cuando los subárboles correspondientes tienen un nodo en común.
- Si X i y X j contienen ambos un vértice v , entonces todos los nodos X k del árbol en la ruta (única) entre X i y X j también contienen v . Es decir, los nodos asociados con vértice v forman un subconjunto conectado de T . Esto también se conoce como coherencia o propiedad de intersección en ejecución . Se puede afirmar de manera equivalente que si, y son nodos, y está en el camino de a , luego .
La descomposición en árbol de un gráfico está lejos de ser única; por ejemplo, una descomposición de árbol trivial contiene todos los vértices del gráfico en su único nodo raíz.
Una descomposición de árbol en la que el árbol subyacente es un gráfico de ruta se denomina descomposición de ruta, y el parámetro de ancho derivado de estos tipos especiales de descomposición de árboles se conoce como ancho de ruta .
Una descomposición de árbol ( X , T = ( I , F )) de ancho de árbol k es suave , si para todosy para todos . [3]
El número mínimo de árboles en la descomposición de un árbol es el número de árboles de G.
Ancho de árbol
El ancho de la descomposición de un árbol es el tamaño de su conjunto más grande X i menos uno. El treewidth tw ( G ) de un gráfico G es la anchura mínima entre todos los posibles descomposición en árbol de G . En esta definición, el tamaño del conjunto más grande se reduce en uno para hacer que el ancho de un árbol sea igual a uno. El ancho de árbol también puede definirse a partir de otras estructuras distintas de las descomposiciones de árboles, incluidos gráficos de cuerdas , zarzas y paraísos .
Es NP-completo determinar si un gráfico G dado tiene un ancho de árbol como máximo para una variable k dada . [4] Sin embargo, cuando k es cualquier constante fija, las gráficas con ancho de árbol k pueden ser reconocidas, y una descomposición de árbol de ancho k puede construirse para ellas, en tiempo lineal. [3] La dependencia del tiempo de este algoritmo en k es exponencial.
Programación dinámica
A principios de la década de 1970, se observó que una gran clase de problemas de optimización combinatoria definidos en gráficos podían resolverse eficientemente mediante programación dinámica no serial siempre que el gráfico tuviera una dimensión acotada , [5] un parámetro relacionado con el ancho del árbol. Posteriormente, varios autores observaron de forma independiente, a finales de la década de 1980, [6] que muchos problemas algorítmicos que son NP-completos para gráficos arbitrarios pueden resolverse de manera eficiente mediante programación dinámica para gráficos de ancho de árbol acotado, utilizando las descomposiciones de árbol de estos gráficos. .
Como ejemplo, considere el problema de encontrar el conjunto independiente máximo en una gráfica de ancho de árbol k . Para resolver este problema, primero elija uno de los nodos de la descomposición del árbol para que sea la raíz, arbitrariamente. Para un nodo X i de la descomposición del árbol, sea D i la unión de los conjuntos X j que descienden de X i . Para un conjunto independiente S ⊂ X i , deja A ( S , i ) denota el tamaño de la más grande subconjunto independiente I de D i tal que I ∩ X i = S . De manera similar, para un par adyacente de nodos X i y X j , con X i más lejos de la raíz del árbol que X j , y un conjunto independiente S ⊂ X i ∩ X j , sea B ( S , i , j ) el tamaño de la más grande subconjunto independiente I de D i tal que I ∩ X i ∩ X j = S . Podemos calcular estos valores A y B mediante un recorrido ascendente del árbol:
donde la suma en el cálculo de está sobre los hijos del nodo .
En cada nodo o borde, hay como máximo 2 k conjuntos S para los cuales necesitamos calcular estos valores, por lo que si k es una constante, entonces todo el cálculo toma un tiempo constante por borde o nodo. El tamaño del conjunto independiente máximo es el valor más grande almacenado en el nodo raíz, y el conjunto independiente máximo en sí mismo se puede encontrar (como es estándar en los algoritmos de programación dinámica) retrocediendo a través de estos valores almacenados a partir de este valor más grande. Por lo tanto, en las gráficas de ancho de árbol acotado, el problema del conjunto independiente máximo puede resolverse en tiempo lineal. Se aplican algoritmos similares a muchos otros problemas de gráficos.
Este enfoque de programación dinámica se utiliza en el aprendizaje automático a través del algoritmo del árbol de unión para la propagación de creencias en gráficos de ancho de árbol limitado. También juega un papel clave en los algoritmos para calcular el ancho del árbol y construir descomposiciones del árbol: típicamente, dichos algoritmos tienen un primer paso que se aproxima al ancho del árbol, construyendo una descomposición del árbol con este ancho aproximado, y luego un segundo paso que realiza la programación dinámica en el descomposición aproximada del árbol para calcular el valor exacto del ancho del árbol. [3]
Ver también
- Zarzas y paraísos : dos tipos de estructuras que se pueden utilizar como alternativa a la descomposición de árboles para definir el ancho de árbol de un gráfico.
- Descomposición de ramas : una estructura estrechamente relacionada cuyo ancho está dentro de un factor constante de ancho de árbol.
- Método de descomposición : la descomposición de árboles se utiliza en el método de descomposición para resolver el problema de satisfacción de restricciones.
Notas
- ^ Diestel (2005) págs . 354–355
- ^ Diestel (2005) sección 12.3
- ↑ a b c Bodlaender (1996) .
- ^ Arnborg, Corneil y Proskurowski (1987) .
- ^ Bertelé y Brioschi (1972) .
- ^ Arnborg y Proskurowski (1989) ; Bern, Lawler y Wong (1987) ; Bodlaender (1988) .
Referencias
- Arnborg, S .; Corneil, D .; Proskurowski, A. (1987), "Complejidad de encontrar incrustaciones en un árbol k ", SIAM Journal on Matrix Analysis and Applications , 8 (2): 277-284, doi : 10.1137 / 0608024.
- Arnborg, S .; Proskurowski, A. (1989), "Algoritmos de tiempo lineal para problemas NP difíciles restringidos a árboles k parciales", Matemáticas aplicadas discretas , 23 (1): 11-24, doi : 10.1016 / 0166-218X (89) 90031- 0.
- Berna, MW; Lawler, EL ; Wong, AL (1987), "Cálculo en tiempo lineal de subgráficos óptimos de gráficos descomponibles", Journal of Algorithms , 8 (2): 216-235, doi : 10.1016 / 0196-6774 (87) 90039-3.
- Bertelé, Umberto; Brioschi, Francesco (1972), Programación dinámica no serial , Academic Press, ISBN 0-12-093450-7.
- Bodlaender, Hans L. (1988), "Programación dinámica en gráficos con ancho de árbol acotado", Proc. XV Coloquio Internacional sobre Autómatas, Lenguajes y Programación , Lecture Notes in Computer Science, 317 , Springer-Verlag, págs. 105-118, doi : 10.1007 / 3-540-19488-6_110.
- Bodlaender, Hans L. (1996), "Un algoritmo de tiempo lineal para encontrar descomposiciones de árboles de pequeño ancho de árbol", SIAM Journal on Computing , 25 (6): 1305-1317, CiteSeerX 10.1.1.113.4539 , doi : 10.1137 / S0097539793251219.
- Diestel, Reinhard (2005), Graph Theory (3.a ed.), Springer , ISBN 3-540-26182-6.
- Halin, Rudolf (1976), " Funciones S para gráficos", Journal of Geometry , 8 : 171–186, doi : 10.1007 / BF01917434.
- Robertson, Neil ; Seymour, Paul D. (1984), "Graph minors III: Planar tree-width", Journal of Combinatorial Theory, Serie B , 36 (1): 49–64, doi : 10.1016 / 0095-8956 (84) 90013-3.