User Tools

Site Tools


godin_thibault:brouillon_projet

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
godin_thibault:brouillon_projet [2013/12/13 15:15]
tgodin
godin_thibault:brouillon_projet [2013/12/13 16:20] (current)
tgodin
Line 26: Line 26:
 \right. \right.
 \] \]
-Hence $L$ is diagonalisable and has it eigen values positive. In fact $0$ is always an eigenvalue, associated to the eigenvector ${}^t(1,​...,​1)$ (it follows of the observation one).+Hence $L$ is diagonalisable and has it eigen values positive ​$\lambda_0, ..., \lambda_n$. In fact $0$ is always an eigenvalue, associated to the eigenvector ${}^t(1,​...,​1)$ (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. 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.
Line 39: Line 39:
 In 1973, Miroslav Fiedler introduce in its article //Algebraic Connectivity in Graph// an interpretation of the second smallest eigen value of $L$ that we will denote $a(G)$ in term of connectivity. In 1973, Miroslav Fiedler introduce in its article //Algebraic Connectivity in Graph// an interpretation of the second smallest eigen value of $L$ that we will denote $a(G)$ in term of connectivity.
  
 +First $(n-1)I-L$ is symetric, has its coefficients positives and admit $n-1~-\lambda_i$ as eigen value. As it is irreductible if $G$ is connected, by //​Perron-Frobenius theorem// the  greatest eigenvalue as multiplicity one. Otherwise if $G$ is not connected 0 as clearly an associated eigenspace of dimension greater than 2. Hence $a(G)\neq 0 \Leftrightarrow G~ \text{is connected}$
 +
 +The eigenvector associated with $a(G)$, 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 $a(G)$ : 
 +
 +\[a(G) = \text{min}_{||x||=1}~({}^txLx)
 +\]
  
 __Bibliographie__ __Bibliographie__
/net/html/perso/melancon/Visual_Analytics_Course/data/attic/godin_thibault/brouillon_projet.1386944152.txt.gz · Last modified: 2013/12/13 15:15 by tgodin