En la teoría de grafos , un árbol k parcial es un tipo de gráfico, definido como un subgráfico de un árbol k o como un gráfico con un ancho de árbol como máximo k . Muchos problemas combinatorios NP-duros en gráficos se pueden resolver en tiempo polinomial cuando se restringen a los árboles k parciales, para valores acotados de k .
Graficar menores
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/7/73/Partial_3-tree_forbidden_minors.svg/220px-Partial_3-tree_forbidden_minors.svg.png)
Para cualquier constante fija k , los k -árboles parciales se cierran bajo la operación de grafos menores , y por lo tanto, por el teorema de Robertson-Seymour , esta familia se puede caracterizar en términos de un conjunto finito de menores prohibidos . Los árboles 1 parciales son exactamente los bosques , y su único menor prohibido es un triángulo. Para los 2 árboles parciales, el menor único prohibido es el gráfico completo en cuatro vértices. Sin embargo, el número de menores prohibidos aumenta para valores mayores de k . Para tres árboles parciales hay cuatro menores prohibidos: el gráfico completo en cinco vértices, el gráfico octaédrico con seis vértices, el gráfico de Wagner de ocho vértices y el prisma pentagonal con diez vértices. [1]
Programación dinámica
Muchos problemas algorítmicos NP-completos para gráficos arbitrarios pueden resolverse eficientemente para árboles k parciales mediante programación dinámica , utilizando las descomposiciones de árboles de estos gráficos. [2]
Familias relacionadas de gráficos
Si una familia de gráficos tiene un ancho de árbol limitado , entonces es una subfamilia de los árboles k parciales, donde k es el límite del ancho del árbol. Las familias de gráficas con esta propiedad incluyen gráficas de cactus , pseudoforestas , gráficas de series paralelas , gráficas de planos exteriores , gráficas de Halin y redes apolíneas . [1] Por ejemplo, los gráficos en serie-paralelos son una subfamilia de los 2 árboles parciales, y más fuertemente un gráfico es un 2-árbol parcial si y solo si cada uno de sus componentes biconectados es en 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 acotado, lo que permite que ciertas tareas, como la asignación de registros, se realicen de manera eficiente en ellos. [3]
Notas
Referencias
- Arnborg, S .; Proskurowski, A. (1989), "Algoritmos de tiempo lineal para problemas NP difíciles restringidos a árboles k parciales", Matemáticas aplicadas discretas , 23 (1): 11-24, doi : 10.1016 / 0166-218X (89) 90031- 0.
- Berna, MW; Lawler, EL ; Wong, AL (1987), "Cálculo en tiempo lineal de subgráficos óptimos de gráficos descomponibles", Journal of Algorithms , 8 (2): 216-235, doi : 10.1016 / 0196-6774 (87) 90039-3.
- Bodlaender, Hans L. (1988), "Programación dinámica en gráficos con ancho de árbol acotado", Proc. XV Coloquio Internacional sobre Autómatas, Lenguajes y Programación , Lecture Notes in Computer Science, 317 , Springer-Verlag, pp. 105-118, doi : 10.1007 / 3-540-19488-6_110 , ISBN 978-3-540-19488-0.
- Bodlaender, Hans L. (1998), "Un k -arboretum parcial de gráficos con ancho de árbol acotado", Ciencias de la computación teóricas , 209 (1–2): 1–45, doi : 10.1016 / S0304-3975 (97) 00228-4 , hdl : 1874/18312.
- Thorup, Mikkel (1998), "Todos los programas estructurados tienen un ancho de árbol pequeño y una buena asignación de registros", Information and Computation , 142 (2): 159-181, doi : 10.1006 / inco.1997.2697.