Trace:

godin_thibault:brouillon_projet

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

Both sides previous revision Previous revision Next revision | Previous revision | ||

godin_thibault:brouillon_projet [2013/12/13 15:39] tgodin |
godin_thibault:brouillon_projet [2013/12/13 16:20] (current) tgodin |
||
---|---|---|---|

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}$ | + | 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.1386945598.txt.gz · Last modified: 2013/12/13 15:39 by tgodin