degré d'un sommet d'un graphe

Sur un plan de réseau, choisissez un point et comptez toutes les liaisons qui y arrivent. Ce total est le degré du sommet. Dans notre graphe, A touche trois arêtes : son degré vaut donc 3.

Une liaison qui part d'un sommet et revient au même sommet forme une boucle. Elle touche ce sommet par ses deux extrémités et ajoute donc 2, non 1, à son degré. Pour un réseau fléché, on compte séparément les flèches qui arrivent et celles qui partent.

Un graphe non orienté est formé de sommets et d'arêtes reliant des paires de sommets. Une arête est incidente à un sommet lorsque celui-ci en est une extrémité. Le degré d'un sommet v, noté deg(v), est le nombre d'incidences de ce sommet. Une arête ordinaire incidente à v contribue 1 ; une boucle sur v contribue 2, puisque ses deux extrémités coïncident avec v. Un sommet sans arête incidente est isolé et a pour degré 0.

Si V désigne l'ensemble des sommets et E l'ensemble des arêtes d'un graphe fini non orienté, chaque arête fournit exactement deux incidences. Le lemme des poignées de mains s'écrit ${\sum }_{v\in V}\mathrm{deg}(v)=2\mathrm{\mid }E\mathrm{\mid }\backslash sum\_\{v\backslash in\; V\}\; \backslash deg(v)=2|E|$. Cette identité reste valable avec des boucles si chacune compte deux fois. Elle implique notamment que le nombre de sommets de degré impair est pair.

Dans un graphe orienté, chaque arc possède un sommet initial et un sommet terminal. Le degré sortant compte les arcs issus du sommet ; le degré entrant compte ceux qui y aboutissent. Leur somme donne le degré total. Une boucle orientée ajoute 1 au degré entrant et 1 au degré sortant.

Le calcul mobilise quatre éléments. Le sommet étudié fixe le point où compter. Les arêtes donnent les liaisons. Leurs extrémités déterminent quelles arêtes sont incidentes au sommet. Enfin, une éventuelle boucle possède deux extrémités confondues et fournit deux incidences au même endroit.

Le degré dépend uniquement de ces incidences, pas de la position des sommets, de la longueur des traits ni de leurs croisements dans la représentation. Déplacer A sans changer ses arêtes conserve donc son degré. À l'inverse, ajouter ou retirer une arête incidente le modifie. Dans un graphe orienté, le sens des arcs devient une donnée nécessaire pour séparer les comptes entrant et sortant.

Considérons un graphe non orienté à quatre sommets A, B, C et D. Ses arêtes sont AB, AC, AD, BC et une boucle sur C. La représentation rend chaque incidence visible, y compris les deux extrémités de la boucle réunies en C.

Données.
Sommets : A, B, C et D.
Arêtes ordinaires : AB, AC, AD et BC.
Boucle : CC.
Nombre total d'arêtes : 5.

Étape 1. A est une extrémité de AB, AC et AD. Ces trois incidences donnent deg(A) = 3.

Étape 2. B touche AB et BC, donc deg(B) = 2. D ne touche que AD, donc deg(D) = 1.

Étape 3. C touche AC et BC, puis sa boucle compte deux fois. Ainsi, deg(C) = 1 + 1 + 2 = 4.

Contrôle. La somme des degrés vaut 3 + 2 + 4 + 1 = 10. Le graphe possède 5 arêtes et 2 × 5 = 10 : le lemme des poignées de mains confirme tous les comptes.

Pour repérer les points les plus connectés d'un réseau non orienté, on compare les degrés. Cette mesure locale convient lorsque chaque liaison compte de la même façon ; si les liaisons ont des poids, il faut plutôt additionner leurs poids.

Pour contrôler un dessin de graphe fini, on additionne tous les degrés et on compare le résultat au double du nombre d'arêtes. Un écart signale une arête oubliée, une boucle comptée une seule fois ou une incidence attribuée au mauvais sommet.

Pour un réseau orienté, le choix dépend de la question. Le degré entrant mesure les arcs reçus, le degré sortant les arcs émis, tandis que le degré total ignore cette distinction en additionnant les deux.

Degré d'un sommet et nombre de sommets du graphe. Le degré est local, alors que l'ordre du graphe compte tous ses sommets. Dans l'exemple, le graphe a quatre sommets, mais A a pour degré 3.

Degré et nombre de voisins. Sans boucle ni arêtes multiples, les deux nombres coïncident. Avec une boucle, ils diffèrent : la boucle ajoute 2 au degré de C, mais ne crée pas un nouveau sommet voisin.

Degré entrant et degré sortant. Dans un graphe orienté, le premier compte les arcs qui aboutissent au sommet et le second ceux qui en partent. Un sommet peut donc avoir trois arcs entrants et aucun arc sortant.

Une boucle compte deux fois dans un graphe non orienté. La compter comme une seule arête incidente fait échouer la somme des degrés. Il faut compter ses deux extrémités, même si elles coïncident.

Le degré 0 est permis. Un sommet isolé ne touche aucune arête. Il reste un sommet du graphe et contribue 0 à la somme des degrés ; il ne faut pas le supprimer du décompte des sommets.

Les arêtes multiples se comptent avec leur multiplicité. Dans un multigraphe, deux arêtes reliant les mêmes sommets ajoutent chacune 1 au degré de chaque extrémité. Dans un graphe simple, cette situation est interdite par définition.

Une boucle orientée intervient dans les deux comptes. Elle est à la fois issue de son sommet et dirigée vers lui. Elle ajoute donc 1 au degré sortant et 1 au degré entrant, soit 2 au degré total.

Le glossaire arête d'un graphe précise l'objet dont les extrémités fournissent les incidences comptées dans le degré.

La fiche Graphe orienté et non-orienté aide à choisir entre degré unique et comptes entrant et sortant.

L'article Balades dans le graphe divisoriel montre comment sommets et arêtes structurent un graphe construit à partir de relations arithmétiques.