A conectividade algébrica de um grafo é o segundo menor autovalor da sua matriz Laplaciana associada.Weisstein, Eric W. Algebraic Connectivity. From MathWorld--A Wolfram Web Resource. Fiedler mostrouAlgebraic connectivity of graphs, by Miroslav Fiedler, Czechoslo- vak Mathematical Journal, Vol. 23 (1973), 298-305. que um grafo é conexo se, e somente se, o seu segundo menor autovalor Laplaciano é positivo. Denotamos a conectividade algébrica por a(G).
Relação com outros Parâmetros Se o número de vértices de um grafo conexo é n e D é o diâmetro, a conectividade algébrica é limitada inferiormente por 4/nD.Bojan Mohar, The Laplacian Spectrum of Graphs, in Graph Theory, Combinatorics, and Applications, Vol. 2, Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk, Wiley, 1991, pp. 871–898.
As conectividades algébrica, de vértices e de arestas, respectivamente a(G), κ(G) e λ(G), estão relacionadas de acordo com o resultado abaixo, provado por Fiedler.
Teorema
Se G não é um grafo completo então a(G) ≤ κ(G) ≤ λ(G).
Ao contrário da conectividade tradicional, a conectividade algébrica é dependente do número de vértices, bem como a maneira pela qual os vértices estão ligados. Nos grafos aleatórios, a conectividade algébrica diminui com o número de vértices, e aumenta com o grau médio. Synchronization and Connectivity of Discrete Complex Systems, Michael Holroyd, International Conference on Complex Systems, 2006.
A conectividade algébrica também se relaciona com outras propriedades de conectividade, tais como o número isoperimétrico, que é limitado inferiormente por metade da conectividade algébrica.
Ver também
Categoria:Combinatória Categoria:Teoria dos grafos Categoria:Conectividade de grafos