Descomposición en árbol

Un grafo con ocho vértices y su descomposición en un árbol con seis nodos. Cada arista del grafo conecta dos vértices que se enumeran juntos en algún nodo del árbol, y cada vértice del gráfico se enumera en los nodos de un subárbol contiguo del árbol. Cada nodo del árbol enumera como máximo tres vértices, por lo que la anchura de esta descomposición es dos.

En teoría de grafos, una descomposición en árbol es una correspondencia de un grafo hacia un árbol, que puede emplearse para definir la anchura del árbol (treewidth) del grafo y acelerar así la resolución de ciertos problemas computaciones en grafos.

Las descomposiciones en árbol juegan un papel importante en problemas como la inferencia probabilística, la satisfacción de restricciones, la optimización de consultas y la factorización de matrices.

El concepto de descomposición en árbol fue introducido originalmente por Rudolf Halin en 1976.[1]​ Posteriormente fue redescubierto por Neil Robertson y Paul Seymour en 1984,[2]​ y desde entonces ha sido estudiado por muchos otros autores.[3]​

Definición

Intuitivamente, una descomposición en árbol representa los vértices de un grafo G como subárboles de un árbol, de manera que los vértices del grafo dado son adyacentes si y solo si los subárboles correspondientes intersecan. Así, G forma un subgrafo del grafo de intersección de los subárboles. El grafo de intersección completo es un grafo cordal.

Cada subárbol asocia un vértice del grafo con un conjunto de nodos del árbol. Formalmente, se representa cada nodo del árbol como el conjunto de los vértices asociados a éste.

Así, dado un grafo G = (V, E), una descomposición en árbol de G es un par (X, T), donde X = {X₁, ..., X_n} es una familia de subconjuntos de V, y T es un árbol cuyos nodos son los subconjuntos X_i, de tal forma que se satisfacen las siguientes propiedades:[3]​

1. La unión de todos los conjuntos X_i es igual a V. Esto es, cada vértice del grafo está asociado con al menos un nodo del árbol.
2. Para cada arista (v, w) del grafo, hay un subconjunto X_i que contiene los vértices v y w. Esto es, los vértices son adyacentes en el grafo si y solo si los subárboles que los contienen comparten (al menos) un nodo.
3. Si X_i y X_j contienen ambos un vértice v, entonces todos los nodos X_k del árbol en el camino (único) entre X_i y X_j contienen v también. Esto es, los nodos asociados con el 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 X_i, X_j y X_k son nodos, y X_k está en el camino de X_i a X_j, entonces ${\displaystyle X_{i}\cap X_{j}\subseteq X_{k}}$.

La descomposición en árbol no es única dado un grafo G; por ejemplo, una descomposición trivial en árbol contiene todos los vértices del grafo en un solo nodo del árbol: su raíz.

Una descomposición en árbol en la que el árbol subyacente es un grafo camino se denomina una descomposición de camino, y el parámetro de anchura derivado de este tipo particular de descomposiciones en árbol es denominado anchura de camino (pathwidth).

Una descomposición de árbol (X, T = (I, F)) de anchura de árbol k es suave, si para todo ${\displaystyle i\in I:|X_{i}|=k+1}$, y para todo ${\displaystyle (i,j)\in F:|X_{i}\cap X_{j}|=k}$.[4]​

Anchura de árbol (treewidth)

La anchura de una descomposición en árbol es el tamaño del mayor conjunto X_i menos uno. La treewidth tw(G) de un grafo G es la mínima anchura entre todas las posibles descomposiciones de G. En esta definición, el tamaño del mayor conjunto se disminuye en uno para forzar que el treewidth de un árbol sea igual a uno. El treewidth se puede definir a partir de otras estructuras distintas a las descomposiciones en árbol, que incluyen los grafos de cuerdas y los paraísos.

El problema de determinar si un grafo G tiene un treewidth menor o igual que una variable k dada es un problema NP-completo. En cambio, cuando k es una constante fija, los grafos con treewidth k pueden ser reconocidos, y una descomposición en árbol de anchura k puede ser construida, en tiempo lineal. La dependencia de tiempo de este algoritmo respecto a k es exponencial.

Referencias

1. Halin, Rudolf (1976). «S-functions for graphs». Journal of Geometry 8 (1–2): 171-186. S2CID 120256194. doi:10.1007/BF01917434. .
2. Robertson, Neil; Seymour, Paul (1984). «Graph minors III: Planar tree-width». Journal of Combinatorial Theory 36 (1): 49-64. doi:10.1016/0095-8956(84)90013-3. .
3. Diestel, Reinhard (2005). Graph Theory (3ª edición). Springer. ISBN 3-540-26182-6. 
4. Bodlaender, Hans L. (1988). «Dynamic programming on graphs with bounded treewidth». En Lepistö, T.; Salomaa, A., eds. Automata, Languages and Programming. ICALP 1988. Lecture Notes in Computer Science, vol 317. Springer-Verlag. pp. 105-118. doi:10.1007/3-540-19488-6_110. hdl:1874/16258. 

• Datos: Q462095
• Multimedia: Tree decomposition / Q462095