Matrice laplacienne

Modèle:À sourcer Modèle:Confusion En théorie des graphes, une matrice laplacienne, ou matrice de Laplace, est une matrice représentant un graphe.

Définition

La matrice laplacienne d'un graphe G non orienté et non réflexif est définie par : $L=D-A$ où $D$ est la matrice des degrés de G et $A$ la matrice d'adjacence de G. Formellement :

$L_{i,j}:=\{\begin{array}{cc}\mathrm{deg}(s_i)& \text{si }i=j\\ -x& \text{ si }i\ne j\text{ avec }x\text{ le nombre d'ar}\hat{\text{e}}\text{tes reliant directement }i\stackrel{`}{\text{ a }}j\\ 0& \text{sinon}\end{array}$

Intuition

Modèle:Pertinence section A la différence de la matrice d'adjacence d'un graphe, la matrice laplacienne a une interprétation algébrique ce qui rend son analyse spectrale fructueuse.

Plus précisément la matrice $D^{-1}A$ correspond à l'opérateur de diffusion sur le graphe. Si $x\in {ℝ}^n$ correspond à la densité de particules d'un gaz en chacun des $n$ sommets du graphe, il est facile de noter que $D^{-1}Ax$ correspond à la densité après une itération de la diffusion au cours de laquelle chaque particule se déplace de son sommet à un voisin choisi aléatoirementModèle:Référence nécessaire.

Également, la matrice laplacienne peut être vue comme une forme quadratique caractérisant la régularité d'un vecteur $x\in {ℝ}^n$ au regard de la distance définie par le graphe. En effet, on a la formule suivante: $x^{T}Lx=\sum _{(u,v)\in E}(x(u)-x(v){)}^2$.

Exemple

Graphe non orienté	Matrice des degrés	Matrice d'adjacence	Matrice laplacienne
	$\left(\begin{array}{cccccc}2& 0& 0& 0& 0& 0\\ 0& 3& 0& 0& 0& 0\\ 0& 0& 2& 0& 0& 0\\ 0& 0& 0& 3& 0& 0\\ 0& 0& 0& 0& 3& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right)$	$\left(\begin{array}{cccccc}0& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 1\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0\end{array}\right)$	$\left(\begin{array}{cccccc}2& -1& 0& 0& -1& 0\\ -1& 3& -1& 0& -1& 0\\ 0& -1& 2& -1& 0& 0\\ 0& 0& -1& 3& -1& -1\\ -1& -1& 0& -1& 3& 0\\ 0& 0& 0& -1& 0& 1\end{array}\right)$

Applications

La matrice laplacienne est utilisée par le théorème de Kirchhoff pour calculer le nombre d'arbres couvrants d'un graphe.

Le spectre de la matrice laplacienne est étudiée en théorie spectrale des graphes. Cette étude permet entre autres de définir des méthodes spectrales pour le partitionnement de graphe.

Si les valeurs propres sont triées $0\le {\lambda }_1\le ...\le {\lambda }_n$On peut par exemple remarquer que ${\lambda }_r=0$ si et seulement si le graphe contient au moins $r$ composantes connexes.

Variantes

Graphe pondéré

Plus généralement, soit un graphe non orienté et non réflexif G = (S, A) à n sommets, pondéré par la fonction poids qui à toute arête $(s_i,s_j)$ associe son poids $p(s_i,s_j)$. La matrice laplacienne de G vérifie :

$(L{)}_{i,j}:=\{\begin{array}{cc}\mathrm{deg}(s_i)=\sum _{k=1}^{n}p(s_i,s_k)& \text{si }i=j\\ -p(s_i,s_j)& \text{si }i\ne j\text{ et }(s_i,s_j)\in A\\ 0& \text{sinon}\end{array}$

Graphe orienté

Ces définitions peuvent se généraliser aux graphes orientés ; dans ce cas, la matrice laplacienne n'est plus symétrique.

Matrice Laplacienne normalisée

Dans le cas de certains problèmes notamment l'embedding de graphe, il est préférable de garder les valeurs propres dans l'intervalle $[0,2]$ (les valeurs propres de la matrice laplacienne peuvent prendre des valeurs beaucoup plus grandes). On utilise alors une matrice laplacienne normalisée, définie par $\overline{L}=D^{-1/2}L{D}^{-1/2}=I-D^{-1/2}A{D}^{-1/2}$ (pour éviter les divisions par 0, on pose que, lorsque $\mathrm{deg}(s_i)=0$, alors $(D^{-1/2}{)}_{i,i}=0$). On a alors

${\overline{L}}_{i,j}:=\{\begin{array}{cc}1& \text{si }i=j\\ -\frac{x}{\sqrt{\mathrm{deg}(s_i)\mathrm{deg}(s_j)}}& \text{ si }i\ne j\text{ avec }x\text{ le nombre d'ar}\hat{\text{e}}\text{tes reliant directement }i\stackrel{`}{\text{ a }}j\\ 0& \text{sinon}\end{array}$

La plus petite valeur propre de cette matrice est toujours 0, et la multiplicité de cette valeur propre est égale au nombre de composantes connexes du graphe. Par ailleurs, toutes les valeurs propres sont inférieures ou égales à 2, et la plus grande valeur propre est égale à 2 si et seulement si une des composantes connexes du graphe est bipartite.