Matrice des degrés

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

Étant donné un graphe G = (V, E) contenant n sommets, la matrice des degrés D de G est la matrice carrée n \times n définie par : d_{i,j}:=\left\{
\begin{matrix} 
\deg(v_i) & \mbox{si}\ i = j \\
0 & \mbox{sinon}
\end{matrix}
\right.

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[modifier | modifier le code]

Graphe étiqueté Matrice des degrés
6n-graph2.svg \begin{pmatrix}
4 & 0 & 0 & 0 & 0 & 0\\
0 & 3 & 0 & 0 & 0 & 0\\
0 & 0 & 2 & 0 & 0 & 0\\
0 & 0 & 0 & 3 & 0 & 0\\
0 & 0 & 0 & 0 & 3 & 0\\
0 & 0 & 0 & 0 & 0 & 1\\
\end{pmatrix}

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[modifier | modifier le code]

  • La matrice des degrés d'un graphe régulier de degré k a une diagonale dont les coefficients valent tous k.

Références[modifier | modifier le code]

  1. Krishnaiyan Thulasiraman, Graph Theory, page 218