## [Anchura de Árbol](/es/node/61224) Definición 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 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 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 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 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 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 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 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 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.