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 14:27] tgodin |
godin_thibault:brouillon_projet [2013/12/13 16:20] (current) tgodin |
||
---|---|---|---|

Line 2: | Line 2: | ||

- | Laplacian Matrice | + | __Introduction__ |

- | $L=D-A ~\text{where~}~ A ~\text{is the adjacency matrice and~}~ D ~\text{the degree matrice.}$ | + | |

+ | Let $G=(V,E)$ be a simple graph of $n$ nodes. | ||

+ | we define the laplacian matrice (also known as Kirchnoff matrice) $L=(l_{i,j})_{(i,j) \in \{1;n^2\}}$ by | ||

+ | \[l_{i,j}:=\left\{ | ||

+ | \begin{matrix} | ||

+ | -1 & \mbox{if }~ v_i~ \mbox{is adjacent to}~ v_j \\ | ||

+ | | ||

+ | \text{deg}(v_i) & \mbox{if }~ i=j\\ | ||

+ | \end{matrix} | ||

+ | \right. | ||

+ | \] | ||

+ | | ||

+ | 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 | ||

+ | \[u_{i,j}:=\left\{ | ||

+ | \begin{matrix} | ||

+ | 1 & \mbox{if} ~v_i \mbox{ is the target of } e_j \\ | ||

+ | -1 & \mbox{if }~ v_i \mbox{ is the source of } e_j \\ | ||

+ | 0 & \mbox{if }~ v_i \notin e_j | ||

+ | \end{matrix} | ||

+ | \right. | ||

+ | \] | ||

+ | 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__ |

/net/html/perso/melancon/Visual_Analytics_Course/data/attic/godin_thibault/brouillon_projet.1386941252.txt.gz · Last modified: 2013/12/13 14:27 by tgodin