Estudo de eficiência algorítmica para conectividade de Grafos via Teoria Espectral de Grafos (TEG)

Abstract

Seja G = G(V, E) um grafo simples com n vértices. Denotemos por A = A(G) a matriz de adjacência de G, D = D(G) a matriz diagonal dos graus dos vértices de G e L = L(G) = D − A a matriz laplaciana de G. O presente trabalho estuda e compara a eficiência computacional de algoritmos que analisam a conectividade de grafos a partir das matrizes A e L. [...]