User Tools

Site Tools

                                   Brouillon projet


Let be a simple graph of nodes. we define the laplacian matrice (also known as Kirchnoff matrice) by

observation 1-

is a symetric, positive matrice. Indeed where is an incidence matrice Hence is diagonalisable and has it eigen values positive . In fact is always an eigenvalue, associated to the eigenvector (it follows of the observation one).

One of the first application of this matrice has been the computation of the number of spanning trees, known as Kirchnoff Matrice-Tree theorem following and whose proved in appendix.

*Kirchnoff Matrice-Tree theorem The number of spanning trees is equal to any cofactor of the laplacian matrice. where is the matrice where line and row have been deleted..

Connectivity Number

In 1973, Miroslav Fiedler introduce in its article Algebraic Connectivity in Graph an interpretation of the second smallest eigen value of that we will denote in term of connectivity.

First is symetric, has its coefficients positives and admit as eigen value. As it is irreductible if is connected, by Perron-Frobenius theorem the greatest eigenvalue as multiplicity one. Otherwise if is not connected 0 as clearly an associated eigenspace of dimension greater than 2. Hence

The eigenvector associated with , often called Fielder vector can be use as a mesure of the connectivity of a given vertice.

Computation of $a(G)$

Courant theorem can be used to compute :


*M Fiedler, Algebraic Connectivity in Graph, Czechoslovak Mathematical Journal, 23 (98), 1973


/net/html/perso/melancon/Visual_Analytics_Course/data/pages/godin_thibault/brouillon_projet.txt · Last modified: 2013/12/13 16:20 by tgodin