Teoria espectral de grafos

e aplicações

Resumo

A teoria espectral de grafos se caracteriza pelo uso de técnicas de álgebra linear para tratar de problemas relacionados à teoria dos grafos. Como é notório, o estudo em teoria de grafos é justificado pelo fato de a área ser especialmente rica em aplicações, como o estudo de redes, seus grupos e fluxos. Em particular, foi escolhida para este trabalho uma das aplicações da teoria espectral de grafos em Física. São estudadas nesta área as matrizes de adjacência, seus autovalores e multiplicidades, que estão associadas à conexidade de grafos e à obtenção de invariantes, o conceito de energia de um grafo e seus limitantes, e a matriz Laplaciana. É dado destaque aos grafos circulantes, periódicos e regulares. A teoria possui importantes e recentes aplicações. Por exemplo, o maior autovalor da Laplaciana está relacionado ao primeiro potencial de ionização de alcanos. Já o segundo menor valor do Laplaciana informa uma medida de compacidade do grafo: um valor pequeno indica moléculas “alongadas”. Além disso, a determinação do número de árvores geradoras de um grafo foi resolvida por Kirchhoff que, estudando circuitos elétricos, provou o resultado que ficou conhecido como Teorema da matriz-árvore, que também envolve a matriz Laplaciana. Conforme andamento, exemplos de sistemas dinâmicos em grafos podem ser considerados, em uma clara analogia com o operador Laplaciano contínuo. Pode-se estudar também métricas para determinar boas “partições” de um grafo, e tais métricas estão associadas aos autovalores e autovetores das matrizes associadas. Métodos para encontrar autovalores e análise dos resultados com variação de dados são problemas interessantes de serem abordados nesse contexto. Como material de base, foi escolhida a apostila. As referências são destacadas no auxílio ao estudo da mencionada aplicação em Física. Dada uma malha de resistores, cada um com sua resistência, é interessante calcular a resistência equivalente do sistema para uma análise global do que acontece quando uma corrente elétrica passa por ele. Existem regras para calcular esse parâmetro, mas muitas vezes elas podem ser trabalhosas e limitadas. No entanto, o trabalho de calcular a resistência equivalente de uma rede (malha) extremamente complexa de resistores (algo que é simples experimentalmente, mas muito difícil analiticamente) foi apresentado de duas formas, umas delas reduzindo-se o problema a calcular a (pseudo)inversa de uma matriz e seus autovalores.