Problemas de Árvores Geradoras em Grafos com Ênfase no Número de Folhas

Dado um grafo não orientado G = (V,E) e um inteiro l, o problema da árvore geradora com restrição no número de folhas consiste em encontrar uma árvore geradora T = (V,E'), com pelo menos l folhas. A versão de otimização desse problema busca encontrar uma árvore geradora de custo mínimo para G, que contenha pelo menos l folhas. Um outro problema muito próximo ao que acabamos de descrever é aquele de encontrar uma árvore geradora de G com um número máximo de folhas. Formulações, desigualdades válidas e algoritmos de solução para esses dois problemas são os temas principais investigados nesse trabalho.
Entre as principais contribuições alcançadas, destacamos a introdução de uma nova família de desigualdades válidas para a formulação clássica baseada em grafos não orientados.
Ainda, como contribuições do trabalho, chamamos a atenção para o desenvolvimento de um algoritmo exato do tipo branch-and-cut baseado em uma nova formulação proposta para os problemas apresentados acima. Esse algoritmo se mostrou capaz de resolver à otimalidade as maiores instâncias propostas até o problema,
apresentado performance comparável à de outras formulações existentes na literatura. Adicionalmente, sugerimos um conjunto de instâncias difíceis para o problema da árvore geradora de custo mínimo com limite inferior do número de folhas. Finalmente, desenvolvemos um algoritmo do tipo relax-and-cut, que contém, como parte integrante, uma heurística Lagrangeana que se mostrou eficaz na construção de soluções viáveis de boa qualidade para o problema.