Matrice des degrés
En mathématiques, et en particulier en théorie des graphes, la matrice des degrés est une matrice qui contient des informations sur le degré de chaque sommet d'un graphe.
La matrice des degrés est une matrice diagonale. Elle est utilisée en conjonction avec la matrice d'adjacence pour construire la matrice laplacienne d'un graphe.
Définition
Étant donné un graphe contenant sommets, la matrice des degrés de est la matrice carrée définie par :
Le degré du sommet est le nombre de liens (arêtes ou arcs) aboutissant à ce sommet. Cela entraîne que chaque boucle compte pour 2 : en effet, chaque lien a deux extrémités et chacune de ces deux extrémités augmente le degré. De la même façon, les sommets isolés ont un degré égal à 0.
Dans le cas d'un graphe orienté, le degré d'un sommet est la somme de son degré entrant et de son degré sortant[1].
Exemple
Graphe étiqueté | Matrice des degrés |
---|---|
![]() |
On remarque que le degré du sommet 1 vaut 4 : 2 pour les deux sommets adjacents 2 et 5 et 2 pour la boucle qui part de 1 et y revient.
Propriétés
- La matrice des degrés d'un graphe régulier de degré a une diagonale dont les coefficients valent tous .