Ir al contenido

Descomposición en árbol

De Wikipedia, la enciclopedia libre
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

[editar]

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 = {X1, ..., Xn} es una familia de subconjuntos de V, y T es un árbol cuyos nodos son los subconjuntos Xi, de tal forma que se satisfacen las siguientes propiedades:[3]

  1. La unión de todos los conjuntos Xi 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 Xi 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 Xi y Xj contienen ambos un vértice v, entonces todos los nodos Xk del árbol en el camino (único) entre Xi y Xj 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 Xi, Xj y Xk son nodos, y Xk está en el camino de Xi a Xj, entonces .

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 , y para todo .[4]

Anchura de árbol (treewidth)

[editar]

La anchura de una descomposición en árbol es el tamaño del mayor conjunto Xi 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

[editar]
  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. a b 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.