Árvores Geradoras e Grafos Matrogênicos

Robson Carlos de Moura Junior, Francisca Andrea Macedo França, Andre Ebling Brondani

Resumo


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. [...]


Texto completo:

PDF

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato