Matrice laplacienne

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 : Ml = MdMaMd est la matrice des degrés de G et Ma 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 (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.

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.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Matrice laplacienne de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • 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 : Ml = Md − Ma où Md est la matrice… …   Wikipédia en Français

  • Laplacienne — 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 : Ml = Md − Ma où …   Wikipédia en Français

  • Matrice (algèbre) — Matrice (mathématiques) Pour les articles homonymes, voir Matrice. En mathématiques, les matrices servent à interpréter en termes calculatoire …   Wikipédia en Français

  • Matrice (mathematiques) — Matrice (mathématiques) Pour les articles homonymes, voir Matrice. En mathématiques, les matrices servent à interpréter en termes calculatoire …   Wikipédia en Français

  • Matrice carrée — Matrice (mathématiques) Pour les articles homonymes, voir Matrice. En mathématiques, les matrices servent à interpréter en termes calculatoire …   Wikipédia en Français

  • Matrice Diagonalisable — En algèbre linéaire, une matrice carrée M d ordre n ( ) à coefficients dans un corps commutatif K, est dite diagonalisable si elle est semblable à une matrice diagonale, c est à dire s il existe une matrice inversible P et une matrice diagonale D …   Wikipédia en Français

  • Matrice Définie Positive — En algèbre linéaire, la notion de matrice définie positive est analogue à celle de nombre réel strictement positif. On introduit tout d abord les notations suivantes ; si a est une matrice à éléments réels ou complexes : aT désigne la… …   Wikipédia en Français

  • Matrice Inversible — En mathématiques et plus particulièrement en algèbre linéaire, une matrice carrée A d ordre n est dite inversible ou régulière ou encore non singulière, s il existe une matrice B d ordre n telle que AB = BA = In, ( AB = In suffit d aprés le… …   Wikipédia en Français

  • Matrice Nilpotente — Une matrice nilpotente est une matrice dont il existe une puissance égale à la matrice nulle. Elle correspond à la notion d endomorphisme nilpotent. Cette notion joue un rôle important dans le monde des matrices. En effet, pour un maniement plus… …   Wikipédia en Français

  • Matrice definie positive — Matrice définie positive En algèbre linéaire, la notion de matrice définie positive est analogue à celle de nombre réel strictement positif. On introduit tout d abord les notations suivantes ; si a est une matrice à éléments réels ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”