Degré (théorie des graphes)

Pour les articles homonymes, voir Degré.

En mathématiques, et plus particulièrement en théorie des graphes, le degré (ou valence) d'un sommet d'un graphe est le nombre de liens (arêtes ou arcs) reliant ce sommet, avec les boucles comptées deux fois^[1]. Le degré d'un sommet ${\displaystyle s}$ est noté ${\displaystyle \deg(s)}$.

Dans le cas d'un graphe orienté, on parle aussi du degré entrant d'un sommet ${\displaystyle d^{-}(s)}$, c'est-à-dire le nombre d'arcs dirigés vers le sommet ${\displaystyle s}$, et du degré sortant de ce sommet ${\displaystyle d^{+}(s)}$, c'est-à-dire le nombre d'arcs sortant de ${\displaystyle s}$. On a ${\displaystyle \deg(s)=d^{+}(s)+d^{-}(s)}$ : le degré du sommet est la somme du degré sortant et du degré entrant.

Le degré maximal d'un graphe ${\displaystyle G}$, noté ${\displaystyle \Delta (G)}$, et le degré minimal de ce graphe, noté ${\displaystyle \delta (G)}$, sont respectivement le maximum et le minimum des degrés de ses sommets. Dans un graphe régulier, tous les sommets ont le même degré, et on peut donc parler du degré du graphe.

• Alain Bretto, Alain Faisant et François Hennecart, Elements of Graph Theory: From Basic Concepts to Modern Developments, European Mathematical Society Press, 2022 (ISBN 978-3-98547-017-4, lire en ligne)

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Degree (graph theory) » (voir la liste des auteurs).

• Matrice des degrés
• Problème de réalisation de graphe, qui consiste, étant donné une liste de degrés, à décider s'il existe un graphe réalisant cette liste.
• Algorithme de Havel-Lakimi, algorithme pour le problème précédent
• Lemme des poignées de main, qui lie les degrés et le nombre d'arêtes
• Graphe eulérien, et le théorème d'Euler où le degré des sommets permet de savoir un parcours eulérien, ou bien un cycle eulérien existe

• Portail des mathématiques
• Portail de l'informatique théorique