Matrice des degrés

En mathématiques, et en particulier en théorie des graphes, la matrice des degrés d'un graphe est la matrice diagonale, qui contient sur sa diagonale, le degré de chaque sommet. Si on lui soustrait la matrice d'adjacence, on obtient la matrice laplacienne d'un graphe. É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. Ainsi, pour un graphe non orienté, 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. Le degré du sommet 1 vaut 4 : en effet, le sommet 1 est connecté aux sommets 2 et 5, et il y a aussi la boucle. Ainsi, le sommet 1 est de degré 2+2 = 4. Le degré du sommet 2 vaut 3 : en effet, le sommet numéro 2 est connecté aux sommet 1, 3 et 5, d'où un degré de 3. vignette|Graphe de Petersen : graphe régulier où les sommets de degré 3. La matrice des degrés d'un graphe régulier de degré a une diagonale dont les coefficients valent tous .