O Problema da Árvore Geradora de Representação Mínima

Este trabalho apresenta o Problema da Árvore Geradora de Representação Mínima (AGRM) e algumas de suas características particulares. O AGRM visa minimizar a soma das rapresentações dos nós, onde a representação dum nó é a quantidade dos seus rótulos incidentes. Provamos que o MRSTP é NP-Difícil e propomos uma formulação matemática, uma heurística construtiva efetiva e um algoritmo baseado em GRASP para o problema. Além disso, o conceito da subárvore maximal monocromático é introduzido. Finalmente, comparamos e discutimos o desempenho dos métodos exatos e heurísticos propostos.