Descomposición de árboles
En la teoría de grafos , una descomposición de á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 clique o árboles de unión ; juegan un papel importante en problemas como la inferencia probabilística , la satisfacción de restricciones , la optimización de consultas , [ cita requerida ] y la descomposición de matrices .
El concepto de descomposición de árboles fue introducido originalmente por Rudolf Halin ( 1976 ). Posteriormente fue redescubierta por Neil Robertson y Paul Seymour ( 1984 ) y desde entonces ha sido estudiada por muchos otros autores. [1]
Intuitivamente, una 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 en el gráfico dado son adyacentes solo cuando los subárboles correspondientes se cruzan. Así, G forma un subgrafo del grafo 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. Así, dado un gráfico G = ( V , E ), una descomposición en á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 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.
