ArithmétiqueObjet mathématique · Glossaire
degré d'un sommet d'un graphe
Dans la théorie des graphes, le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes, c'est-à-dire le nombre d'arêtes dont ce sommet est l'une des deux extrémités. Une boucle — arête reliant un sommet à lui-même — est comptée pour deux unités dans le calcul du degré, car elle contribue deux fois à l'incidence. La somme des degrés de tous les sommets d'un graphe est toujours égale au double du nombre d'arêtes : c'est le lemme des poignées de mains. Dans le cas des graphes orientés, où les arêtes sont remplacées par des arcs possédant une direction, on distingue le degré entrant (ou demi-degré intérieur), qui comptabilise les arcs dont le sommet est le nœud terminal, et le degré sortant (ou demi-degré extérieur), qui comptabilise les arcs dont le sommet est le nœud initial. Le degré total d'un sommet dans un graphe orienté est la somme de son degré entrant et de son degré sortant.
Sommaire
Ce que vous allez apprendre
- Compter correctement les arêtes incidentes à un sommet.
- Traiter une boucle comme deux incidences dans un graphe non orienté.
- Contrôler le calcul avec le lemme des poignées de mains.
- Séparer degré entrant et degré sortant dans un graphe orienté.
En clair
Imaginez des villes reliées par des routes. Pour une ville donnée, comptez toutes les routes qui y arrivent : ce total joue le rôle du degré. Un sommet isolé a donc un degré nul. Si une route part d'une ville et y revient, elle touche deux fois la même ville et compte pour deux.
Le degré décrit ainsi le nombre de connexions portées par un sommet. Dans un réseau orienté, comme des rues à sens unique, on sépare les connexions qui entrent de celles qui sortent.
Définition
Dans un graphe non orienté, une arête est incidente à un sommet lorsqu'elle possède ce sommet comme extrémité. Le degré d'un sommet est le nombre de ces incidences. Une arête reliant deux sommets distincts ajoute une unité au degré de chacun. Une boucle possède deux extrémités confondues au même sommet : elle ajoute donc deux unités à son degré. Un sommet sans arête incidente est isolé et son degré vaut 0.
Pour un graphe fini, notons V l'ensemble des sommets, E l'ensemble des arêtes et d(v) le degré d'un sommet v. Le symbole |E| désigne le nombre d'arêtes, et la somme parcourt tous les sommets de V. Chaque arête fournit exactement deux incidences, y compris lorsqu'il s'agit d'une boucle. Le lemme des poignées de mains s'écrit alors : .
Dans un graphe orienté, les liens sont des arcs. Le degré entrant, aussi appelé demi-degré intérieur, compte les arcs dont le sommet est le nœud terminal. Le degré sortant, ou demi-degré extérieur, compte ceux dont il est le nœud initial. Leur somme donne le degré total. Une boucle orientée contribue une unité au degré entrant et une unité au degré sortant.
De quoi c'est fait
Le calcul mobilise quatre éléments. Les sommets sont les objets reliés. Les arêtes joignent deux extrémités dans un graphe non orienté. Les arcs jouent ce rôle dans un graphe orienté, avec un nœud initial et un nœud terminal. Une boucle relie un sommet à lui-même.
Le degré dépend des incidences entre sommets et liens, pas de la longueur apparente des traits ni de leur position dans une représentation graphique. Dans un graphe non orienté, les extrémités suffisent à calculer chaque degré. Dans un graphe orienté, le sens de chaque arc est indispensable pour séparer entrées et sorties. Une couleur ou une courbure ne change rien, sauf si elle code explicitement une donnée supplémentaire.
Un exemple, pas à pas
Considérons un graphe dont le schéma rend visibles toutes les incidences à compter.
Donnée 1 : ses quatre sommets sont A, B, C et D.
Donnée 2 : ses cinq arêtes sont AB, AC, BC, CD et une boucle en C.
Donnée 1 : ses quatre sommets sont A, B, C et D.
Donnée 2 : ses cinq arêtes sont AB, AC, BC, CD et une boucle en C.
1. Au sommet A, les arêtes AB et AC donnent un degré de 2.
2. Au sommet B, les arêtes AB et BC donnent aussi un degré de 2.
3. Au sommet C, AC, BC et CD fournissent trois incidences. La boucle en fournit deux autres : le degré de C vaut donc 5.
4. Au sommet D, seule l'arête CD est incidente : son degré vaut 1.
Le contrôle additionne les quatre degrés : . La somme vaut bien deux fois les cinq arêtes. Si les mêmes liens deviennent les arcs A→B, A→C, B→C, C→D et C→C, alors C reçoit trois arcs et en émet deux ; son degré total entrant + sortant vaut 5. La boucle compte une fois dans chaque demi-degré.
En pratique
Dans un réseau non orienté, le degré repère immédiatement les sommets très connectés. Pour comparer leur degré, on compte leurs incidences ; si le sens des échanges importe, on utilise plutôt les degrés entrant et sortant.
Pour contrôler un graphe fini, on additionne tous les degrés. Un total impair signale forcément une erreur de comptage, puisque la somme doit valoir deux fois le nombre d'arêtes. Ce contrôle détecte notamment l'oubli du second compte d'une boucle.
Dans un réseau orienté, comparer entrées et sorties décrit des rôles différents. Un sommet qui reçoit trois arcs et n'en émet aucun n'a pas le même profil qu'un sommet qui en reçoit un et en émet deux, même si leur degré total vaut 3.
À ne pas confondre
Degré et nombre de voisins. Le degré compte des incidences, tandis que le nombre de voisins dépend de la convention adoptée pour une boucle. Dans l'exemple, C a trois voisins distincts autres que lui-même — A, B et D — mais son degré vaut 5 à cause de la boucle. Si l'on considère qu'une boucle rend aussi C voisin de lui-même, C a alors quatre voisins distincts.
Degré et nombre total d'arêtes. Le degré est local à un sommet ; le nombre d'arêtes décrit tout le graphe. Le graphe de l'exemple possède cinq arêtes, mais A est seulement de degré 2.
Degré et distance. Le degré compte les incidences en un sommet ; lorsque deux sommets sont reliés, leur distance est le minimum d'arêtes d'un chemin qui les relie. Dans l'exemple, A a un degré de 2, tandis que le chemin A–C–D donne une distance de 2 entre A et D.
Limites et pièges
Sommet isolé. L'absence totale d'arête incidente donne un degré égal à 0 ; il ne faut pas compter le sommet lui-même comme une connexion.
Boucle. Dans un graphe non orienté, une boucle touche deux fois son sommet et ajoute 2, non 1. Dans un graphe orienté, elle ajoute 1 au degré entrant et 1 au degré sortant.
Arêtes multiples. Si plusieurs arêtes relient les mêmes sommets, chacune compte séparément. Il faut compter les arêtes avec leur multiplicité, au lieu de ne retenir qu'une relation entre les deux sommets.
Orientation oubliée. Compter seulement le total masque le sens des arcs. Lorsque l'arrivée et le départ ont des rôles distincts, il faut conserver séparément le degré entrant et le degré sortant avant de les additionner.
Pour aller plus loin
Graphe orienté et non-orienté. Cette distinction précise quand séparer le degré entrant du degré sortant.
Sous-graphe. Cette notion montre pourquoi le degré d'un même sommet peut changer lorsque certaines arêtes sont retirées.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres