Largura de árvore: um parâmetro-chave na teoria dos grafos e suas aplicações
2025-01-14
Este artigo aprofunda a largura de árvore, um parâmetro crucial na teoria dos grafos. Definida usando decomposições em árvore, a largura de árvore caracteriza a estrutura do grafo e está intimamente relacionada à complexidade algorítmica. O artigo explora múltiplas definições equivalentes de largura de árvore, suas propriedades estruturais e métodos computacionais. Em seguida, detalha suas amplas aplicações em álgebra linear numérica esparsa, inferência bayesiana, teoria dos jogos, topologia de baixa dimensão, ciência de redes e geometria algébrica. O autor também discute avanços em parâmetros de largura relacionados e como a largura de árvore pode melhorar a eficiência de algoritmos de grafos.