ArithmétiqueObjet mathématique · Glossaire
Noeud d'un graphe
Un noeud (ou sommet, ou vertex) d'un graphe est l'un des éléments fondamentaux du graphe. Un graphe est constitué d'un ensemble de noeuds et d'un ensemble éventuellement vide de liaisons entre eux : des arêtes dans un graphe non orienté, des arcs dans un graphe orienté. On mesure les liaisons incidentes à un noeud par son degré : on compte les arêtes dans un graphe non orienté ; dans un graphe orienté, on distingue le degré entrant et le degré sortant. Les noeuds sont les entités représentées dans le graphe, comme des villes dans un réseau routier ou des personnes dans un réseau social.
Sommaire
Ce que vous allez apprendre
- Identifier ce que représentent un nœud et une arête.
- Calculer le degré de chaque sommet dans un petit graphe.
- Distinguer degré entrant et degré sortant dans un graphe orienté.
- Traiter les sommets isolés, les boucles et les arêtes multiples.
En clair
Imaginez quatre villes marquées par les lettres A, B, C et D sur une carte. Chaque ville est un nœud, aussi appelé sommet. Une route directe entre deux villes devient une arête. Le dessin peut changer de forme sans changer le réseau : ce sont les villes et leurs liaisons qui comptent.
Pour une ville donnée, le nombre de routes qui la touchent est son degré. Si les liaisons ont un sens, comme des rues à sens unique, on compte séparément celles qui arrivent et celles qui partent.
Définition
Un nœud, ou sommet — parfois nommé vertex — est un élément de l’ensemble des sommets d’un graphe. Une arête relie deux sommets dans un graphe non orienté. Dans un graphe orienté, cette liaison est un arc muni d’un sommet de départ et d’un sommet d’arrivée. Les nœuds représentent les entités étudiées, par exemple des villes ou des personnes ; les arêtes représentent leurs relations.
Dans un graphe non orienté, le degré d’un sommet est le nombre d’arêtes qui lui sont incidentes, c’est-à-dire qui le touchent. Dans un graphe orienté, le degré entrant compte les arcs qui arrivent au sommet, tandis que le degré sortant compte ceux qui en partent. La position, la taille ou la couleur du point dessiné ne font pas partie de cette définition, sauf si le graphe leur attribue explicitement une information.
De quoi c'est fait
Un graphe réunit d’abord un ensemble de sommets, qui porte les entités. Il comprend ensuite un ensemble d’arêtes, ou d’arcs si les liaisons sont orientées. Chaque arête dépend de ses deux extrémités ; chaque arc dépend en plus de l’ordre départ-arrivée. L’incidence indique qu’une liaison touche un sommet. Elle permet de compter son degré.
Ces données suffisent à reconstruire les connexions et à calculer les degrés. En revanche, l’emplacement des points sur la page, la courbure des traits et leur longueur apparente ne définissent pas le graphe. Deux dessins très différents peuvent donc représenter exactement les mêmes sommets et les mêmes liaisons.
Un exemple, pas à pas
Quatre villes A, B, C et D forment un réseau routier non orienté.
Données : les routes sont A–B, A–C, B–C et C–D. Il y a donc quatre sommets et quatre arêtes.
Données : les routes sont A–B, A–C, B–C et C–D. Il y a donc quatre sommets et quatre arêtes.
1. Pour A, comptez les routes A–B et A–C : le degré de A vaut 2.
2. Pour B, comptez A–B et B–C : le degré de B vaut également 2.
3. Le sommet C touche A–C, B–C et C–D : son degré vaut 3. Le sommet D ne touche que C–D : son degré vaut 1.
Le contrôle consiste à additionner les degrés : 2 + 2 + 3 + 1 = 8. Chaque arête ayant deux extrémités, les quatre arêtes contribuent deux fois, soit 2 × 4 = 8. Les deux comptes coïncident.
En pratique
Dans un réseau routier, une ville devient un nœud et une route directe devient une arête. Ce modèle convient lorsque l’on étudie quelles villes sont reliées. Si la distance ou le temps de trajet compte aussi, il faut ajouter cette valeur aux liaisons.
Dans un réseau social, chaque personne peut être un nœud. Une relation mutuelle se représente par une arête non orientée ; un abonnement à sens unique demande plutôt un arc orienté. Le sens observable de la relation détermine le choix.
Pour repérer une entité très connectée, on examine son degré. Dans un réseau orienté, le seul degré total masque la différence entre recevoir et émettre des liaisons : les degrés entrant et sortant donnent alors l’information utile.
À ne pas confondre
Nœud et arête. Le nœud représente une entité ; l’arête représente une liaison entre deux nœuds. Dans le réseau des villes, C est un nœud, tandis que C–D est une arête.
Degré et nombre total d’arêtes. Le degré se calcule pour un sommet précis, alors que le nombre d’arêtes concerne tout le graphe. Dans l’exemple, C a un degré égal à 3, mais le graphe possède 4 arêtes.
Arête et arc. Une arête n’impose pas de sens ; un arc distingue un départ et une arrivée. Une route utilisable dans les deux sens appelle une arête, tandis qu’une liaison à sens unique appelle un arc.
Limites et pièges
Sommet isolé. Un nœud peut appartenir au graphe sans être relié à aucun autre : son degré vaut alors 0. Il ne faut pas l’effacer du seul fait qu’aucun trait ne le touche.
Boucle. Une arête peut, selon le type de graphe, partir d’un sommet et revenir au même sommet. Dans le calcul usuel du degré d’un graphe non orienté, cette boucle compte deux fois, car elle possède deux extrémités incidentes au même sommet.
Arêtes multiples. Certains graphes autorisent plusieurs arêtes entre les deux mêmes sommets. Le degré compte alors chaque arête avec sa multiplicité ; compter seulement les voisins donnerait un résultat trop petit. Il faut donc préciser le type de graphe étudié.
Orientation. Dans un graphe orienté, la somme des degrés entrant et sortant donne le degré total, mais elle ne remplace pas l’information directionnelle portée par les deux composantes. Il faut donc annoncer séparément les deux degrés ; une boucle orientée ajoute une unité à chacun.
Pour aller plus loin
Le glossaire Graphe orienté et non-orienté précise ce que le sens des liaisons change pour les sommets et leurs degrés.
La fiche Sous-graphe montre comment conserver une partie des sommets et des arêtes d’un graphe.
La fiche Graphe complet étudie le cas où chaque paire de sommets distincts est reliée.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres