Descomposición del árbol

En la teoría de grafos, la descomposición de árboles es un mapeo de un gráfico en un árbol que se puede usar para determinar el ancho del árbol de un gráfico y acelerar la solución de ciertos problemas computacionales en los gráficos.

En el campo del aprendizaje automático, una descomposición de árbol también se denomina árbol de unión , árbol de camarilla o árbol de adyacencia . La descomposición de árboles juega un papel importante en problemas como la inferencia probabilística , la búsqueda de valores válidos , la optimización de consultas de DBMS y la descomposición de matrices .

El concepto de descomposición de árboles fue propuesto originalmente por Halin [1] . Más tarde fue redescubierto por Robertson y Seymour [2] y desde entonces el concepto ha sido estudiado por muchos otros autores [3] .

Definición

Intuitivamente, la descomposición en árbol representa los vértices de un gráfico G dado como subárboles de un árbol de tal manera que los vértices del gráfico son adyacentes solo cuando los subárboles correspondientes se cruzan. Entonces G forma un subgrafo del grafo de intersección del subárbol . El gráfico de intersección completo es un gráfico cordal .

Cada subárbol vincula un vértice de gráfico a un conjunto de nodos de árbol. Para definir esto formalmente, representaremos cada nodo del árbol como un conjunto de vértices asociados a él. Entonces para un gráfico dado G = ( V , E ) la descomposición del árbol es un par ( X , T ), donde X = { X 1 , ..., X n } es una familia de subconjuntos del conjunto V , y T es un árbol cuyos nodos son subconjuntos X i que cumplen las siguientes propiedades: [4]

La unión de todos los conjuntos X i es igual a V . Así, cualquier vértice del grafo está conectado al menos a un nodo del árbol.
Para cualquier borde ( v , w ) del gráfico, hay un subconjunto X i que contiene tanto v como w . Por lo tanto, los vértices son adyacentes en un gráfico solo si corresponden a subárboles que tienen un nodo común.
Si X i y X j contienen v , entonces todos los nodos X k del árbol en el camino (único) entre X i y X j también contienen v . Es decir , los nodos asociados con el vértice v forman un subconjunto conexo en T. Esta propiedad se puede formular de manera equivalente: si , y son nodos, y van de camino a , entonces . $X_{yo}$ $X_{j}$ $X_{k}$ $X_{k}$ $X_{yo}$ $X_{j}$ ${\displaystyle X_{i}\cap X_{j}\subseteq X_{k))$

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 el nodo raíz.

Una descomposición de árbol en la que el árbol es un camino se llama descomposición de camino, y el ancho de árbol de este tipo especial de descomposición de árbol se conoce como ancho de camino .

Una descomposición de árbol ( X , T = ( I , F )) con ancho de árbol k es uniforme si para todos y para todos [5] . $i\in I:|X_{i}|=k+1$ $(i,j)\in F:|X_{i}\cap X_{j}|=k$

Ancho de madera

El ancho de la descomposición de un árbol es el tamaño de su conjunto más grande X i sin unidad. El ancho del árbol tw( G ) de G es el ancho mínimo entre todas las descomposiciones posibles de G . En esta definición, el tamaño del conjunto más grande se reduce en uno para hacer que el ancho arbóreo del árbol sea igual a uno. El ancho del árbol se puede determinar a partir de estructuras distintas de la descomposición del árbol. Esto incluye recuentos de cuerdas , zarzas y puertos .

Determinar si el ancho del árbol de un gráfico dado G no excede k es un problema NP-completo [6] . Sin embargo, si k es una constante fija, se puede reconocer un gráfico con ancho de árbol k y se puede construir una descomposición de árbol de ancho k en tiempo lineal [5] . El tiempo de ejecución de este algoritmo depende exponencialmente de k .

Programación dinámica

A principios de la década de 1970, se notó que los problemas de una gran clase de problemas de optimización combinatoria en gráficos se pueden resolver de manera eficiente utilizando programación dinámica no serial , si el gráfico tiene una dimensión acotada [7] , un parámetro relacionado con el ancho del árbol. Más tarde, algunos autores descubrieron de forma independiente a fines de la década de 1980 [8] que muchos problemas algorítmicos NP-completos para grafos arbitrarios se pueden resolver de manera eficiente usando programación dinámica para grafos de ancho de árbol limitado usando la descomposición de árbol de estos gráficos.

Como ejemplo, imagine el problema de encontrar el conjunto independiente más grande en un gráfico con un ancho de árbol k . Para resolver este problema, primero elegimos un nodo de descomposición de árbol como raíz (arbitrariamente). Para un nodo de descomposición en árbol X i , sea D i la unión de los conjuntos X j heredados de X i . Para un conjunto independiente S ⊂ X i , sea A ( S , i ) el tamaño del subconjunto independiente más grande 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 que X j y un conjunto independiente S ⊂ X i ∩ X j , sea B ( S , i , j ) el tamaño del mayor subconjunto independiente I en D i tal que I ∩ X i ∩ X j = S . Podemos calcular estos valores A y B recorriendo el árbol de abajo hacia arriba:

A(S,i)=|S|+\sum _{j}\left(B(S\cap X_{j},j,i)-|S\cap X_{j}|\right)

B(S,i,j)=\max _{S'\subset X_{i} \atop S=S'\cap X_{j}}A(S',i)

Donde la suma en la fórmula para se toma sobre los descendientes del nodo . ${\ estilo de visualización A (S, i)}$ $X_{yo}$

En cada nodo o arista, hay como máximo 2k conjuntos S para los que se deben calcular estos valores, de modo que en el caso de que k sea una constante, todos los cálculos toman un tiempo constante por arista o nodo. El tamaño del conjunto independiente más grande es el valor más grande almacenado en el nodo raíz, y el propio conjunto independiente más grande se puede encontrar (como es estándar en la programación dinámica) rastreando estos valores almacenados, comenzando con el valor más grande. Por lo tanto, en gráficos de ancho de árbol acotado, el problema de encontrar el conjunto independiente más grande se puede resolver en tiempo lineal. Algoritmos similares son aplicables a muchos otros problemas de gráficos.

Este enfoque de programación dinámica se aplica en el campo del aprendizaje automático utilizando el algoritmo de árbol de articulación para propagar la confianza en gráficos de ancho de árbol limitado. El enfoque también juega un papel clave en los algoritmos para calcular el ancho del árbol y construir una descomposición del árbol. Por lo general, estos algoritmos tienen un primer paso que aproxima el ancho del árbol y construye una descomposición del árbol con este ancho aproximado, y el segundo paso usa programación dinámica en la descomposición del árbol resultante para calcular el valor exacto del ancho del árbol [5] .

Véase también

Blackberry y Harbour , dos tipos de estructuras que se pueden usar como alternativa a la descomposición del árbol para determinar el ancho del árbol de un gráfico
Descomposición de gráfico de rama , una estructura estrechamente relacionada cuyo ancho está relacionado linealmente con el ancho del árbol
Método de descomposición .

Notas

↑ Halin, 1976 .
↑ Robertson, Seymour, 1984 .
↑ Diestel, 2005 , pág. 354–355.
↑ Diestel, 2005 , pág. sección 12.3.
↑ 1 2 3 Bodlaender, 1996 .
↑ Arnborg, Corneil, Proskurowski, 1987 .
↑ Bertelé, Brioschi, 1972 .
↑ Arnborg, Proskurowski, 1989 ; Berna, Lawler, Wong, 1987 ; Bodlaender, 1988 .

Literatura

S. Arnborg, D. Corneil, A. Proskurowski. Complejidad de encontrar incrustaciones en un árbol k // SIAM Journal on Matrix Analysis and Applications. - 1987. - T. 8 , núm. 2 . — S. 277–284 . -doi : 10.1137/ 0608024 . .
S. Arnborg, A. Proskurowski. Algoritmos de tiempo lineal para problemas NP-difíciles restringidos a árboles k parciales // Matemática aplicada discreta. - 1989. - T. 23 , núm. 1 . — P. 11–24 . - doi : 10.1016/0166-218X(89)90031-0 . .
MW Berna, EL Lawler, AL Wong. Cálculo en tiempo lineal de subgrafos óptimos de gráficos descomponibles // Journal of Algorithms. - 1987. - T. 8 , núm. 2 . — S. 216–235 . - doi : 10.1016/0196-6774(87)90039-3 . .
Umberto Bertele, Francesco Brioschi. Programación dinámica no serial. - Prensa académica, 1972. - ISBN 0-12-093450-7 . .
Hans L. Bodlaender. proc. XV Coloquio Internacional de Autómatas, Lenguajes y Programación. - Springer-Verlag, 1988. - T. 317. - S. 105-118. — (Apuntes de clase en informática). -doi : 10.1007/ 3-540-19488-6_110 . .
Hans L. Bodlaender. Un algoritmo de tiempo lineal para encontrar descomposiciones de árbol de ancho de árbol pequeño // SIAM Journal on Computing. - 1996. - T. 25 , núm. 6 _ - S. 1305-1317 . -doi : 10.1137/ S0097539793251219 . .
Reinhard Diestel. Teoría de grafos. — 3er. - Springer , 2005. - ISBN 3-540-26182-6 . .
Rodolfo Halin. S -funciones para grafos // Journal of Geometry. - 1976. - T. 8 . — S. 171–186 . -doi : 10.1007/ BF01917434 . .
Neil Robertson, Paul D. Seymour. Graph minors III: Planar tree-with // Journal of Combinatorial Theory, Serie B. - 1984. - V. 36 , no. 1 . — págs. 49–64 . - doi : 10.1016/0095-8956(84)90013-3 . .