Teoria das Árvores
Contexto
Após a solução de Euler para as Pontes de Königsberg, a Teoria dos Grafos permaneceu em grande parte adormecida por mais de cem anos, pois era visto como solução a uma charada do que uma ferramenta matemática ampla.
Problema
Essa percepção mudou em 1847, quando o físico alemão Gustav Kirchhoff enfrentou o desafio de analisar como a corrente elétrica se distribuía em circuitos complexos.
Os métodos de cálculo da época eram confusos e inadequados para redes elétricas intricadas com múltiplos caminhos e malhas (ciclos), e ele precisava de um método sistemático para garantir que suas equações pudessem ser resolvidas.
Note
Nesse problema, as malhas (ciclos) eram um problema, pois se você escolher os ciclos de forma aleatória para escrever suas equações, é muito provável que você crie equações redundantes (uma equação que é apenas uma combinação das outras), e seu sistema de equações não terá solução.
Solução
Inspirado pela abordagem de Euler, Kirchhoff representou os circuitos como grafos, onde os pontos de junção se tornaram os vértices e os componentes (como resistores) se tornaram as arestas.
O verdadeiro desafio era como aplicar sua “Lei das Malhas” sem gerar equações redundantes, o que tornaria o sistema insolúvel.
A sua grande inovação, que deu origem à Teoria das Árvores, foi o método para selecionar um conjunto de malhas independentes.
O processo funciona assim:
- Primeiro, ele simplificou o grafo do circuito em uma “árvore geradora” (spanning tree): um esqueleto do circuito que conecta todos os vértices sem formar nenhum ciclo.
- Em seguida, ele observou as arestas que foram deixadas de fora da árvore. Ao reintroduzir cada uma dessas arestas, uma de cada vez, na árvore geradora, cada aresta criava exatamente um ciclo único e fundamental.
- Ao aplicar a Lei das Malhas a esse conjunto de “ciclos fundamentais”, Kirchhoff garantiu um sistema de equações perfeito (sem redundâncias) para encontrar todas as correntes do circuito.