# Visual Analytics Course

### Site Tools

godin_thibault:brouillon_projet

# Differences

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

 godin_thibault:brouillon_projet [2013/12/13 14:52]tgodin godin_thibault:brouillon_projet [2013/12/13 16:20] (current)tgodin Both sides previous revision Previous revision 2013/12/13 16:20 tgodin 2013/12/13 15:52 tgodin 2013/12/13 15:39 tgodin 2013/12/13 15:15 tgodin 2013/12/13 15:14 tgodin 2013/12/13 14:52 tgodin 2013/12/13 14:50 tgodin 2013/12/13 14:27 tgodin 2013/12/13 14:27 tgodin 2013/12/13 14:24 tgodin 2013/12/13 14:21 tgodin 2013/12/13 14:21 tgodin created Next revision Previous revision 2013/12/13 16:20 tgodin 2013/12/13 15:52 tgodin 2013/12/13 15:39 tgodin 2013/12/13 15:15 tgodin 2013/12/13 15:14 tgodin 2013/12/13 14:52 tgodin 2013/12/13 14:50 tgodin 2013/12/13 14:27 tgodin 2013/12/13 14:27 tgodin 2013/12/13 14:24 tgodin 2013/12/13 14:21 tgodin 2013/12/13 14:21 tgodin created Line 1: Line 1: ​Brouillon projet ​Brouillon projet + + + __Introduction__ Let $G=(V,E)$ be a simple graph of $n$ nodes. Let $G=(V,E)$ be a simple graph of $n$ nodes. Line 12: Line 15: \] \] - $L=D-A ~\text{where }~ A ~\text{is the adjacency matrice and }~ D ~\text{the degree matrice.}$ + observation 1- $L=D-A ~\text{where }~ A ~\text{is the adjacency matrice and }~ D ~\text{the degree matrice.}$ $L$ is a symetric, positive matrice. Indeed $L=U{}^tU$ where $U$ is an incidence matrice ​ $L$ is a symetric, positive matrice. Indeed $L=U{}^tU$ where $U$ is an incidence matrice ​ $u_{i,​j}:​=\left\{ $$u_{i,​j}:​=\left\{ \begin{matrix} \begin{matrix} - 1 & \mbox{if} v_i \mbox{ is the target of } e_j \\ + 1 & \mbox{if} ​~v_i \mbox{ is the target of } e_j \\ - -1 & \mbox{si } v_i \mbox{ is the source of } e_j \\ + -1 & \mbox{if }~ v_i \mbox{ is the source of } e_j \\ - 0 & \mbox{si } v_i \notin e_j + 0 & \mbox{if }~ v_i \notin e_j \end{matrix} \end{matrix} \right. \right.$$$ - Hence $L$ is diagonalisable ​ + 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. + + + __*Kirchnoff Matrice-Tree theorem__ The number of spanning trees is equal to any cofactor of the laplacian matrice. + $\forall (i,j) \in \{1;​n\}^2,​~N_t(G)=\text{Det}\tilde{L}_{i,​j}$ where $\tilde{L}_{i,​j} \in M_{n-1}(\bf{Z})~$ is the matrice $L$ where line $i$ and row $j$ 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 $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__ + *M Fiedler, //Algebraic Connectivity in Graph//, Czechoslovak Mathematical Journal, 23 (98), 1973 + __Appendix__ 