\documentclass[a4paper, oneside, 10pt]{article}
\usepackage[utf8x]{inputenc}
\usepackage[english]{babel}
\date{\today}
\title{}
\author{}
\begin{document}
\begin{verbatim}
Brouillon projet
\end{verbatim}
\underline{Introduction}
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, \ldots, \lambda_n$. In fact $0$ is always an eigenvalue, associated to the eigenvector ${}^t(1,\ldots,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 \emph{Kirchnoff Matrice-Tree theorem} following and whose proved in appendix.
\underline{*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..
\underline{Connectivity Number}
In 1973, Miroslav Fiedler introduce in its article \emph{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 \emph{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 \emph{Fielder vector} can be use as a mesure of the connectivity of a given vertice.
\underline{Computation of \$a(G)\$}
\emph{Courant theorem} can be used to compute $a(G)$ :
\[a(G) = \text{min}_{||x||=1}~({}^txLx)
\]
\underline{Bibliographie}
*M Fiedler, \emph{Algebraic Connectivity in Graph}, Czechoslovak Mathematical Journal, 23 (98), 1973
\underline{Appendix}
\end{document}