Visual Analytics Course

Site Tools

godin_thibault:brouillon_projet

This is an old revision of the document!

                                   Brouillon projet

Introduction

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.

Bibliographie

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

Appendix