Conectividade algébrica
A conectividade algébrica de um grafo é o segundo menor autovalor da sua matriz Laplaciana associada.[1] Fiedler mostrou[2] 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[editar | editar código-fonte]
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.[3]
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[editar | editar código-fonte]
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. [4]
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.
Referências
- ↑ Weisstein, Eric W. Algebraic Connectivity. From MathWorld--A Wolfram Web Resource.
- ↑ Algebraic connectivity of graphs, by Miroslav Fiedler, Czechoslo- vak Mathematical Journal, Vol. 23 (1973), 298-305.
- ↑ 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.
- ↑ Synchronization and Connectivity of Discrete Complex Systems, Michael Holroyd, International Conference on Complex Systems, 2006.
