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 non-orienté
G est définie par :
M l = M d - M a où
M d est la matrice des degrés de
G et
M a 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 (s i ,s j ) associe son poids p (s i ,s j ).
La matrice laplacienne de G vérifie :
| (M l ) i,j : = { n | | n deg(s i ) = | n
Σ
k = 1 | p (s i ,s k ) |
| {si } i = j | | n- p (s i ,s j ) | {si } i ≠ j { et } (s i ,s j ) ∈ A | | n0 | {sinon} n |
| n n |
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.
Voir aussi
<table style"float:left; margin:0 2em 0.5em 0; border:1px solid black;font-size:90%; text-align:center" cellspacing="0" cellpadding="2">
| Matrice mathématique |
| par forme |
| carrée • triangulaire • diagonale • tridiagonale élémentaire • échelonnée • creuse • aléatoire circulante • de Hankel • de Toeplitz • de Vandermonde |
| transformée | en relation |
| transposée • adjointe inverse • Comatrice | équivalente • semblable congruente |
| par propriété |
| inversible • diagonalisable • trigonalisable symétrique • antisymétrique • hermitienne • normale orthogonale • unitaire • symplectique • de Hadamard définie positive • à diagonale dominante • nilpotente |
| par famille | associée |
| identité de De Casteljau de Cartan de Hilbert de Mueller de Pauli • de Dirac | de permutation • de passage compagnon • de Sylvester d'adjacence • laplacienne hessienne • jacobienne génératrice • de contrôle de corrélation • de Gram de variance-covariance d'inertie • de Jones des gains • stochastique |
| particulière |
| CKM |
| résultats |
| décompositions : LU • QR • polaire valeurs singulières | Trigonalisation Réduction de Jordan facteurs invariants |
| Voir aussi |
| théorie des matrices • Algèbre linéaire |