Árvores Geradoras e Grafos Matrogênicos

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 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 es- tudo sobre redes elétricas [5]. Várias provas diferentes, generalizações e também algumas aplicações são conhecidas. Por exemplo, Arthur Cayley – um matemático britânico, tentou contar o número de hidrocarbonetos saturados Cn H2n+2 contendo um determinado número de átomos de carbono. Em 1889, o mesmo autor, em [2], provou que o número de árvores geradoras de um grafo completo Kn é dado por nn−2. [...]