Degré (théorie des graphes)

théorie des graphes

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 est noté .

Un graphe non orienté où on a indiqué le degré de chaque sommet sur ce sommet. Dans ce graphe, le degré maximal est et le degré minimal est .

Graphe orienté

modifier

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

Caractéristiques

modifier

Le degré maximal d'un graphe  , noté  , et le degré minimal de ce graphe, noté  , 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.

Bibliographie

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

Notes et références

modifier
  1. (en) Reinhard Diestel, Graph Theory [détail des éditions], p. 5.

Article connexe

modifier