Medida numérica de cuánto se parece un grafo no dirigido a un árbol, definida como el mínimo, entre todas las descomposiciones en árbol, del tamaño máximo de las 'bolsas' menos uno; una anchura de árbol pequeña significa que el grafo puede organizarse por pequeños conjuntos de vértices solapados dispuestos en forma de árbol.

Principio

Organizar el grafo mediante un árbol de bolsas de vértices solapados y usar el tamaño de bolsa más grande como métrica de coste; minimizar ese máximo captura el menor tamaño de interacciones locales necesario para reconstruir la estructura global.

Demostración

Un árbol o bosque tiene anchura de árbol 1 (las bolsas contienen como máximo dos vértices); un camino simple tiene anchura 1, un ciclo tiene anchura 2, y el grafo completo en n vértices tiene anchura n−1; muchos algoritmos de programación dinámica tienen tiempo exponencial en la anchura de árbol pero polinomial en el tamaño del grafo.

Aplicación incorrecta

Confundir grado máximo, arboricidad o pathwidth con anchura de árbol y suponer que un grado máximo pequeño implica anchura de árbol pequeña, o aplicar algoritmos que dependen de la anchura de árbol sin construir una descomposición en árbol válida y de anchura acotada.

Consecuencia

Si un grafo tiene anchura de árbol acotada, muchos problemas en general difíciles (coloreo, variantes hamiltonianas, satisfacción de restricciones) admiten soluciones parametrizadas o en tiempo polinomial cuando se parametrizan por la anchura de árbol; la teoría estructural de grafos proporciona teoremas de descomposición y menores relacionados con la anchura de árbol.

Inversión

La perspectiva inversa son los grafos de gran anchura de árbol (expanders, menores densos) que resisten la descomposición en pequeñas bolsas y muestran fuerte conectividad global; una anchura elevada dificulta la programación dinámica local pero denota riqueza combinatoria.

Límite

Definida para grafos no dirigidos mediante descomposiciones en árbol; existen extensiones para grafos dirigidos e hipergráfos que requieren formulaciones diferentes; la anchura de árbol es invariante por menores, pero no mide la sparsity en todos los sentidos y difiere de invariantes relacionados como pathwidth o tree-depth.

Tensión semántica

Tensión con pathwidth, tree-depth y medidas de densidad: pathwidth restringe más la forma de la descomposición, tree-depth mide una complejidad tipo altura, y densidad/arboricidad caracterizan la distribución de aristas; cada invariante enfatiza aspectos estructurales distintos.

Síntesis

La anchura de árbol resume la complejidad global de un grafo en el tamaño de piezas locales solapadas organizadas como un árbol: encuentre una descomposición en árbol que minimice la bolsa máxima; un valor pequeño indica que muchos problemas globales se reducen a razonamiento local en estructura arbórea.