Sur cette page
Un exemple concret
Quatre villes A, B, C et D sont reliées par les routes A–B, A–C, B–C et C–D. Le graphe a 4 sommets et 4 arêtes. C a pour voisins A, B et D, donc son degré vaut 3. Le chemin A, C, D relie A à D en deux arêtes, et A, B, C, A forme un cycle.
Le piège à éviter
Ne confonds pas graphe et arbre : un arbre est un cas particulier de graphe, connexe et sans cycle. Dans un graphe orienté, un arc de A vers B ne permet pas d'aller de B vers A.
Pour aller plus loin
On représente un graphe de deux façons principales. La matrice d'adjacence est un tableau carré de n lignes et n colonnes, où la case de la ligne i et de la colonne j vaut 1 s'il existe une arête de i vers j, et 0 sinon ; pour un graphe pondéré, on y place le poids. La liste d'adjacence associe à chaque sommet la liste de ses voisins ; en Python, on utilise un dictionnaire dont les clés sont les sommets. La matrice occupe une place proportionnelle à n², la liste une place proportionnelle au nombre d'arêtes, ce qui est plus économe pour un graphe peu relié.
Deux parcours sont au programme. Le parcours en largeur part d'un sommet, visite tous ses voisins, puis les voisins de ces voisins, à l'aide d'une file : il donne les plus courts chemins en nombre d'arêtes. Le parcours en profondeur s'enfonce le plus loin possible avant de revenir en arrière, à l'aide d'une pile ou d'une fonction récursive ; il permet par exemple de détecter un cycle. Dans les deux cas, on marque les sommets déjà visités pour ne pas tourner en rond. Propriété utile : dans un graphe non orienté, la somme des degrés est égale au double du nombre d'arêtes, puisque chaque arête est comptée une fois à chacune de ses extrémités.
Les graphes font partie des structures de données de la spécialité NSI de Terminale. Ils interviennent aussi dans le thème des réseaux : le protocole de routage RIP compte le nombre de sauts entre routeurs, tandis qu'OSPF cherche des chemins de coût minimal dans un graphe pondéré.
Ne pas confondre
- Arbre : Un arbre est un graphe connexe sans cycle, souvent muni d'une racine ; un graphe quelconque peut contenir des cycles et plusieurs composantes séparées.
- Graphe orienté : Dans un graphe non orienté, une arête se parcourt dans les deux sens ; dans un graphe orienté, chaque arc n'a qu'un sens de parcours.
Dans ta copie
Pour trouver le chemin comportant le moins d'arêtes entre deux sommets, j'utilise un parcours en largeur. Je place le sommet de départ dans une file et je le marque comme visité. Tant que la file n'est pas vide, je défile un sommet, puis j'enfile chacun de ses voisins non encore visités en notant leur distance, égale à celle du sommet défilé plus un. Comme les sommets sont traités par distance croissante, la première fois que j'atteins le sommet d'arrivée, la distance notée est la plus courte possible.
À retenir
- Un graphe est formé de sommets reliés par des arêtes, éventuellement orientées ou pondérées.
- On le représente par une matrice d'adjacence ou par une liste d'adjacence.
- Le parcours en largeur utilise une file et le parcours en profondeur une pile.
- La somme des degrés d'un graphe non orienté vaut le double du nombre d'arêtes.
Teste-toi
NSI · question corrigée
Quelle structure de données utilise-t-on pour un parcours en largeur d'un graphe ?
Voir la réponse
Réponse B. Le parcours en largeur traite les sommets dans leur ordre de découverte, premier découvert, premier traité : c'est le fonctionnement d'une file.
NSI · question corrigée
Un graphe non orienté a 5 sommets de degrés 1, 2, 2, 3 et 4. Combien d'arêtes possède-t-il ?
Voir la réponse
Réponse D. La somme des degrés vaut 1 + 2 + 2 + 3 + 4 = 12 ; chaque arête compte deux fois, donc il y a 12 / 2 = 6 arêtes.
Questions fréquentes
Faut-il choisir une matrice ou une liste d'adjacence ?
La matrice permet de savoir instantanément si deux sommets sont reliés, mais elle prend beaucoup de place. La liste est plus économe et plus pratique pour parcourir les voisins : c'est souvent le meilleur choix pour un graphe avec peu d'arêtes.
Pourquoi marquer les sommets visités pendant un parcours ?
Parce qu'un graphe peut contenir des cycles. Sans marquage, le parcours repasserait indéfiniment par les mêmes sommets et ne se terminerait jamais.
Notions liées
Pour réviser tout le chapitre, va sur la page NSI, ou retrouve toutes les définitions dans le lexique du bac. Dans l'application, les quiz reprennent ces notions sur le programme de ta série.