O teorema da Matriz-Árvore e aplicações

Abstract

O Teorema da Matriz-Árvore é um dos teoremas clássicos da Teoria Algébrica de Grafos. Este provê um método de contagem das árvores geradoras de um grafo conexo em termo dos autovalores ou determinantes de matrizes associadas a tais grafos. O teorema foi provado pela primeira vez em 1847, pelo físico alemão Gustav Kirchhof em seu estudo sobre redes elétricas, e demonstra uma relação entre árvores geradoras e matrizes. Várias provas diferentes, generalizações e também algumas aplicações são conhecidas, como a Fórmula de Cayley, que nos diz que o número de árvores geradoras de um grafo completo Kn é dado por nn−2. Nosso objetivo é entender o Teorema da Matriz-Árvore na visão da Teoria Espectral de Grafos, esta que estuda o espectro de algumas matrizes associadas a tais grafos a fim de obter propriedades sobre estes. Finalmente, aplicaremos o Teorema da Matriz-Árvore em algumas classes de grafos, em especial, a classe dos grafos matrogênicos.