Árvores Geradoras e Grafos Matrogênicos

O Teorema da Matriz-Arvore é um dos teoremas clássicos da Teoria Algébrica de Grafos. Este prove um método de contagem das árvores geradoras de um grafo conexo em termos 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 Kirchhoff 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. Por exemplo, Artur Cayley - um matemático britânico, tentou contar o número de hidrocarbonetos saturados $C_{n}H_{2n+2}$ contendo um determinado número de átomos de carbono. Propomos neste trabalho, apresentar um estudo da quantidade de árvores geradoras em algumas subclasses de grafos matrogênicos utilizando o Teorema da Matriz-Árvore.