Matrice laplacienne

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 : $M_l = M_d - M_a$ où $M_d$ est la matrice des degrés de G et $M_a$ la matrice d'adjacence de G.

Plus formellement, soit un graphe non-orienté et non-réflexif G=(S,A) de 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 :

$(M_l)_{i,j}:=\left\{ \begin{matrix} \deg(s_i) = \sum_{k=1}^n p(s_i,s_k) & \mbox{si } i = j \\ - p(s_i,s_j) & \mbox{si } i \neq j \mbox{ et } (s_i,s_j) \in A \\ 0 & \mbox{sinon} \end{matrix} \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.

La matrice laplacienne d'un graphe est utilisée dans le cadre du partitionnement de graphe par les méthodes spectrales.

Propriétés

La matrice laplacienne d'un graphe pondéré par des poids positifs est semi-définie positive.