Matrice laplacienne

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Ne doit pas être confondu avec Laplacien.

En théorie des graphes, une matrice laplacienne, ou matrice de Laplace, est une matrice représentant un graphe.

Définition[modifier | modifier le code]

La matrice laplacienne d'un graphe G non orienté et non réflexif est définie par : M_l = M_d - M_aM_d est la matrice des degrés de G et M_a la matrice d'adjacence de G[1]. Elle vérifie :

(M_l)_{i,j}:=\left\{
\begin{matrix}
\deg(s_i) & \mbox{si } i = j\\
-1 & \mbox{ si } i \neq j \mbox{ et si i et j sont reliés par une arête} \\
0 & \mbox{sinon}
\end{matrix}
\right.

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 :

(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.

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

Applications[modifier | modifier le code]

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[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  1. Laurent et Pierre Beauguitte, Opérations matricielles et analyse de graphe, automne 2011