AlgèbreObjet mathématique · Glossaire
matrice de Laplace
Soit G un graphe non orienté. La matrice de Laplace de G, notée L, est définie par L = D − A, où D est la matrice des degrés de G (matrice diagonale dont l'élément est le degré du sommet i, c'est-à-dire le nombre d'arêtes qui lui sont incidentes) et A est la matrice d'adjacence de G. La matrice de Laplace est symétrique semi-définie positive : toutes ses valeurs propres sont positives ou nulles. Sa plus petite valeur propre est toujours 0 (le vecteur constant étant dans son noyau) ; la multiplicité de cette valeur propre est égale au nombre de composantes connexes du graphe. La deuxième plus petite valeur propre, appelée valeur algébrique de connectivité ou valeur propre de Fiedler, mesure la connectivité du graphe et joue un rôle central en partitionnement de graphes et en analyse spectrale.
Sommaire
Ce que vous allez apprendre
- Construire L à partir des matrices des degrés et d’adjacence.
- Vérifier le calcul sur la chaîne 1—2—3.
- Interpréter la multiplicité de 0 et la deuxième valeur propre.
En clair
Imaginez trois sommets alignés, reliés comme une chaîne : 1—2—3. Pour chacun, on compte ses voisins, puis on inscrit aussi quelles paires sont reliées. La matrice de Laplace rassemble ces deux informations en soustrayant la matrice des connexions à celle des degrés.
Ses valeurs propres transforment ensuite le dessin en indices de structure. Le nombre de valeurs propres nulles révèle le nombre de morceaux connexes ; la deuxième plus petite renseigne sur la solidité de la connexion.
Définition
Pour un graphe simple non orienté nommé G, la matrice de Laplace, ou matrice laplacienne, est une matrice carrée notée L. On note D la matrice diagonale des degrés : son terme diagonal di,i est le nombre d’arêtes incidentes au sommet i. On note A la matrice d’adjacence, qui indique quelles paires de sommets sont reliées. Ces données donnent .
Comme le graphe est non orienté, L est symétrique. Elle est aussi semi-définie positive : chacune de ses valeurs propres est positive ou nulle. Le vecteur dont toutes les coordonnées sont égales appartient au noyau de L, donc 0 est toujours une valeur propre. Sa multiplicité est exactement le nombre de composantes connexes du graphe.
Pour un graphe ayant au moins deux sommets, en rangeant les valeurs propres dans l’ordre croissant, la deuxième, notée ici λ2, est la connectivité algébrique, aussi appelée valeur propre de Fiedler. Elle mesure la connectivité du graphe et intervient dans son partitionnement et son analyse spectrale.
De quoi c'est fait
La construction repose sur quatre éléments. Le graphe non orienté G fournit les sommets et les arêtes. La matrice d’adjacence A enregistre les connexions entre sommets. La matrice diagonale D place le degré de chaque sommet sur sa diagonale. Enfin, la soustraction produit la matrice L.
Les arêtes déterminent donc à la fois A et les degrés inscrits dans D. Chaque ligne de L associe le degré d’un sommet aux connexions de ce même sommet. Ces données suffisent à construire L, puis à étudier son noyau et ses valeurs propres. Le nom des sommets change seulement l’ordre des lignes et des colonnes ; ce sont les connexions qui portent la structure.
Un exemple, pas à pas
Prenons la chaîne non orientée 1—2—3. Les données sont les trois sommets 1, 2 et 3, ainsi que les deux arêtes 1—2 et 2—3. Les degrés valent respectivement 1, 2 et 1. La figure rend visibles ces connexions et les trois matrices correspondantes.
1. On inscrit les degrés sur la diagonale :
2. On code les deux arêtes :
3. On soustrait terme à terme :
4. On calcule les valeurs propres de L : 0, 1 et 3.
.
2. On code les deux arêtes :
.
3. On soustrait terme à terme :
.
4. On calcule les valeurs propres de L : 0, 1 et 3.
Il n’y a qu’une valeur propre nulle : le graphe possède donc une seule composante connexe. La deuxième plus petite valeur propre vaut 1, qui est sa connectivité algébrique. Pour contrôler la construction, la somme des nombres de chaque ligne de L doit être nulle ; c’est bien le cas ici.
En pratique
Pour compter les composantes connexes, on construit L puis on détermine la multiplicité de sa valeur propre 0. Le résultat donne directement le nombre de morceaux connexes du graphe.
Pour apprécier la connectivité, on ordonne les valeurs propres et on lit la deuxième plus petite. Cette valeur de Fiedler est préférable au seul comptage des composantes lorsqu’on veut mesurer la connexion plutôt que constater une séparation.
Pour partitionner un graphe, l’analyse spectrale de L apporte une information que la seule matrice d’adjacence ne donne pas directement : elle organise les connexions à travers les valeurs propres.
À ne pas confondre
Matrice d’adjacence. La matrice A code les arêtes, tandis que la matrice de Laplace combine cette information avec les degrés par L = D − A. Pour la chaîne 1—2—3, A a une diagonale nulle, alors que L porte 1, 2 et 1 sur sa diagonale.
Matrice des degrés. La matrice D est diagonale et ne conserve que le nombre d’arêtes incidentes à chaque sommet. Deux sommets de même degré y ont la même valeur diagonale ; L conserve aussi, hors diagonale, la trace de leurs connexions.
Limites et pièges
Plusieurs composantes. Si le graphe a au moins deux composantes connexes, 0 apparaît au moins deux fois dans le spectre. La deuxième valeur propre vaut alors 0 : elle ne doit pas être interprétée comme une connectivité positive entre des morceaux séparés.
Lecture du zéro. Une valeur propre nulle n’indique pas à elle seule que le graphe est déconnecté, puisque 0 est toujours présent. Il faut compter sa multiplicité : une seule occurrence correspond à une composante connexe, deux occurrences à deux composantes, et ainsi de suite.
Ordre des valeurs propres. La valeur de Fiedler est la deuxième plus petite, et non la deuxième valeur rencontrée dans un calcul non trié. Il faut d’abord ranger toutes les valeurs propres par ordre croissant, en répétant chacune selon sa multiplicité.
Pour aller plus loin
matrice d'adjacence — Revenir au codage des arêtes permet de voir précisément l’information soustraite à la matrice des degrés.
degré d'un sommet d'un graphe — Approfondir le degré éclaire la diagonale de D et, par conséquent, celle de la matrice de Laplace.
valeur propre — Cette notion donne les outils pour lire le noyau, la multiplicité de 0 et la valeur de Fiedler.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres