En teoría de grafos , un k -árbol parcial es un tipo de grafo, definido como un subgrafo de un k -árbol o como un grafo con un ancho de árbol de k como máximo . [1] Muchos problemas combinatorios NP-duros en grafos se pueden resolver en tiempo polinomial cuando se restringen a los k -árboles parciales, para valores acotados de k .
Para cualquier constante fija k , los k -árboles parciales están cerrados bajo la operación de menores de grafos , y por lo tanto, por el teorema de Robertson-Seymour , esta familia puede ser caracterizada en términos de un conjunto finito de menores prohibidos . Los 1-árboles parciales son exactamente los bosques , y su único menor prohibido es un triángulo. Para los 2-árboles parciales el único menor prohibido es el grafo completo en cuatro vértices. Sin embargo, el número de menores prohibidos aumenta para valores mayores de k . Para los 3-árboles parciales hay cuatro menores prohibidos: el grafo completo en cinco vértices, el grafo octaédrico con seis vértices, el grafo de Wagner de ocho vértices y el prisma pentagonal con diez vértices. [2]
Muchos problemas algorítmicos que son NP-completos para gráficos arbitrarios se pueden resolver de manera eficiente para árboles k parciales mediante programación dinámica , utilizando las descomposiciones de árboles de estos gráficos. [3]
Si una familia de grafos tiene un ancho de árbol acotado , entonces es una subfamilia de los k -árboles parciales, donde k es el límite del ancho del árbol. Las familias de grafos con esta propiedad incluyen los grafos de cactus , los pseudobosques , los grafos serie-paralelos , los grafos planos exteriores , los grafos de Halin y las redes apolíneas . [2] Por ejemplo, los grafos serie-paralelos son una subfamilia de los 2-árboles parciales, y más fuertemente un grafo es un 2-árbol parcial si y solo si cada uno de sus componentes biconectados es serie-paralelo.
Los gráficos de flujo de control que surgen en la compilación de programas estructurados también tienen un ancho de árbol limitado, lo que permite que ciertas tareas como la asignación de registros se realicen de manera eficiente en ellos. [4]