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.

[modifier] Définition

La matrice laplacienne d'un graphe non-orienté G est définie par : Ml = Md − Ma où Md est la matrice des degrés de G et Ma la matrice d'adjacence de G.

Plus formellement, soit un graphe non-orienté G=(S,A) de n sommets, pondéré par la fonction poids qui à tout arête (si,sj) associe son poids p(si,sj).

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.

[modifier] 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.

[modifier] Propriétés

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

Autres langues