Descomposición en árbol

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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) y acelerar así la resolución de ciertos problemas computaciones en grafos.

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.

Cada subárbol asocia a 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:

  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.

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 camino en el grafo se denomina una descomposición de camino, y el parámetro de anchura derivado de este caso particular de descomposiciones en árbol es denominado anchura de camino (pathwidth).

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.