Degré (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Un graphe non orienté où on a indiqué le degré de chaque sommet sur ce sommet.

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 v est noté \deg(v).

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

Le degré maximal d'un graphe G, noté \Delta(G), et le degré minimal de ce graphe, noté \delta(G), sont respectivement le maximum et le minimum des degrés de ses sommets. Dans le graphe de la figure ci-contre, le degré maximal est 5 et le degré minimal est 0. Dans un graphe régulier, tous les sommets ont le même degré, et on peut donc parler du degré du graphe.

Notes et références[modifier | modifier le code]

  1. Diestel, Reinhard, Graph Theory (3rd ed.), Springer-Verlag, 2005, p.5 (ISBN 978-3-540-26183-4.)

Voir aussi[modifier | modifier le code]

Source[modifier | modifier le code]

Article connexe[modifier | modifier le code]