Matrice laplacienne

Un article de Wikipédia, l'encyclopédie libre.

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 : est la matrice des degrés de G et la matrice d'adjacence de G[1]. Formellement :

Intuition[modifier | modifier le code]

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 correspond à l'opérateur de diffusion sur le graphe. Si correspond à la densité de particules d'un gaz en chacun des sommets du graphe, il est facile de noter que 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éatoirement[réf. nécessaire].

Également, la matrice laplacienne peut être vue comme une forme quadratique caractérisant la régularité d'un vecteur au regard de la distance définie par le graphe. En effet, on a la formule suivante: .

Exemple[modifier | modifier le code]

Graphe non orienté Matrice des degrés Matrice d'adjacence Matrice laplacienne
6n-graf.svg

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.

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 On peut par exemple remarquer que si et seulement si le graphe contient au moins composantes connexes.

Variantes[modifier | modifier le code]

Graphe pondéré[modifier | modifier le code]

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 associe son poids . La matrice laplacienne de G vérifie :

Graphe orienté[modifier | modifier le code]

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

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

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