Matrice laplacienne

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
 Ne doit pas être confondu avec Laplacien.
Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
Cet article ne cite pas suffisamment ses sources (septembre 2013).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références » (modifier l'article, comment ajouter mes sources ?).

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 :

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.

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

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