Graphes au Bac NSI : dictionnaire d'adjacence, matrice, parcours et plus court chemin
Mis à jour le · AprenAI
Les graphes représentent 8 exercices sur les 136 des annales de Métropole (5,9 %), dans 7 sujets : un en 2021, trois en 2024, un en 2025 et trois en 2026. Le thème a pris de l'importance depuis 2024. On y attend de modéliser un réseau par un dictionnaire ou une matrice, de dérouler un parcours en largeur ou en profondeur et d'écrire un algorithme qui exploite le graphe.
- 27 sujets officiels
- 5,3 % des sujets
- 2021-2026 années
Que faut-il savoir sur les graphes en NSI ?
Un graphe est un ensemble de sommets reliés par des arêtes. Il modélise un réseau de routeurs, une carte routière, un réseau de sites Web ou les configurations d'un jeu. Un graphe est non orienté quand une arête relie deux sommets dans les deux sens, orienté quand elle a un sens, et pondéré (ou valué) quand chaque arête porte un nombre : une distance, un coût, un nombre de citations. Le degré d'un sommet est le nombre d'arêtes qui y arrivent.
Deux représentations reviennent dans tous les sujets. Le dictionnaire d'adjacence associe à chaque sommet la liste de ses voisins, par exemple 'R1' : ['R2', 'R3', 'R4', 'R6']. Pour un graphe pondéré, on utilise un dictionnaire de dictionnaires : domaine['E']['F'] donne la longueur de la piste entre E et F. La matrice d'adjacence est un tableau à deux dimensions où la case de la ligne i et de la colonne j vaut 1 s'il y a une arête entre les sommets i et j, et 0 sinon. Pour un graphe non orienté sans boucle, la diagonale est nulle et la matrice est symétrique.
Le choix entre les deux est une question de mémoire. Dans l'exercice du jeu Recto-Verso (Métropole France 1 2026), le graphe a 2⁹ = 512 sommets, chacun relié à 8 voisins au plus. Une matrice demanderait 512 × 512 = 2¹⁸ = 262 144 cases, alors que le dictionnaire stocke environ 8 × 512 = 4 096 voisins : le dictionnaire est bien plus économe quand le graphe est creux.
Le parcours en profondeur descend le plus loin possible avant de revenir en arrière : il s'écrit de façon récursive ou avec une pile. Le parcours en largeur explore les sommets par distance croissante depuis le départ et utilise une file. Dans un graphe non pondéré, il donne un plus court chemin en nombre d'arêtes, ce qui le rend adapté à la recherche du plus petit nombre de coups. Pour un graphe pondéré, la recherche d'un plus court chemin se fait par comparaison des longueurs des chemins possibles, par force brute, ou avec l'algorithme de Dijkstra.
Enfin, le théorème d'Euler apparaît en 2024 : un graphe connexe admet une chaîne eulérienne (un chemin qui emprunte chaque arête une seule fois) si et seulement si il a zéro ou exactement deux sommets de degré impair.
- Sommet et arête: Éléments d'un graphe : un sommet représente un objet, une arête relie deux sommets.
- Degré: Nombre d'arêtes incidentes à un sommet.
- Dictionnaire d'adjacence: Dictionnaire qui associe à chaque sommet la liste (ou le dictionnaire pondéré) de ses voisins.
- Matrice d'adjacence: Tableau à deux dimensions dont la case (i, j) vaut 1 s'il existe une arête entre i et j.
- Excentricité: Plus grande distance entre un sommet et tous les autres sommets du graphe, en nombre d'arêtes.
- Chaîne eulérienne: Chemin qui parcourt chaque arête une fois et une seule.
- Graphe connexe: Graphe où l'on peut aller de n'importe quel sommet à n'importe quel autre.
| Dictionnaire d'adjacence | Matrice d'adjacence | |
|---|---|---|
| Forme | {sommet : liste de voisins} | Tableau n × n de 0 et de 1 |
| Mémoire | Proportionnelle au nombre d'arêtes | n × n, même si le graphe est creux |
| Voisins d'un sommet | Lecture directe de la liste | Parcours d'une ligne |
| Degré d'un sommet | Longueur de la liste | Somme de la ligne |
Quels exercices de Bac sont tombés sur les graphes ?
Sur 8 exercices (répartition : 2021 : 1 ; 2024 : 3 ; 2025 : 1 ; 2026 : 3), le thème est absent de 2022 et de 2023, puis revient dans les sujets 2024 à 2026. Les parties valent de 1 à 6 points, 3,6 points en moyenne. Elles sont presque toujours couplées à un autre thème : réseaux et routage (2024, remplacement), programmation orientée objet (2024), bases de données (2025), binaire (2026).
- Modéliser et représenter un graphe (3): Écrire le dictionnaire d'adjacence ou la matrice d'un schéma, calculer des degrés, modéliser un jeu par un graphe. Exemples : « Métropole France 1 remplacement 2024, exercice 2 » (réseau de routeurs R1 à R9), « Métropole France 2 remplacement 2021, exercice 2 » (liaisons ferroviaires des Aventuriers du Rail) et « Métropole France 2 2026, exercice 2 » (taquin).
- Parcours en largeur et en profondeur (3): Reconnaître un parcours, donner l'ordre de visite, compléter son code. Exemples : « Métropole France 1 2026, exercice 2, partie B » (parcours en profondeur d'un graphe de 512 configurations), « Métropole France 2 2026, exercice 3 » (parcours en largeur et excentricité) et « Métropole France 1 2024, exercice 1 » (réseau de sites Web).
- Plus court chemin sur un graphe pondéré (2): Comparer les longueurs de chemins, écrire une recherche par force brute ou un algorithme glouton. Exemples : « Métropole France 2 2024, exercice 3, partie B » (domaine skiable) et « Métropole France 2 remplacement 2025, exercice 3 » (réseau routier Toulouse–Calais).
- Exercice 2 - Graphes · Métropole 1 remplacement 2024 · Modéliser et représenter un graphe
- Exercice 2 · Métropole 2 remplacement 2021 · Modéliser et représenter un graphe
- Exercice 2 - Partie B · Métropole 2026 (sujet 1) · Parcours en largeur et en profondeur
- Exercice 3 - Graphes · Métropole 2026 (sujet 2) · Parcours en largeur et en profondeur
- Exercice 3 - Partie B · Métropole 2024 (sujet 2) · Plus court chemin sur un graphe pondéré
- Exercice 3 - Graphes · Métropole 2 remplacement 2025 · Plus court chemin sur un graphe pondéré
Entraîne-toi : Graphes : modélisation et parcours (27 sujets officiels)
Tous les sujets de NSI sur « Graphes : modélisation et parcours » (2021-2026), avec le corrigé.
Comment résoudre un exercice de graphes en NSI ?
Exemple : « Métropole France 1 remplacement 2024, exercice 2 », sur un réseau de neuf routeurs R1 à R9 reliés par des fibres optiques. On demande un dictionnaire, une matrice, la fonction des degrés puis une chaîne eulérienne.
- Écrire le dictionnaire d'adjacence: Chaque sommet est une clé, sa valeur est la liste de ses voisins : R1 est relié à R2, R3, R4 et R6, R2 à R1, R3 et R5, et ainsi de suite jusqu'à R9 relié à R7 et R8.
- Construire la matrice: Les sommets sont ordonnés de R1 à R9. La case (i, j) vaut 1 si Ri et Rj sont reliés. Le graphe étant non orienté sans boucle, la diagonale vaut 0 et la matrice est symétrique : cela permet de vérifier son travail.
- Calculer les degrés: La fonction parcourt la matrice ligne par ligne, puis colonne par colonne, et ajoute chaque valeur à un compteur. Elle renvoie les degrés [4, 3, 4, 2, 4, 6, 4, 3, 2].
- Compter les degrés impairs: Seuls R2 et R8 ont un degré impair (3). Le graphe est connexe : d'après le théorème d'Euler, il admet une chaîne eulérienne, qui relie R2 à R8.
- Rédiger la conclusion: On répond « Oui », avec la justification complète : le graphe est connexe et possède exactement deux sommets de degré impair. La réponse « Oui » seule serait insuffisante.
À ne pas confondre
- Parcours en largeur ≠ Parcours en profondeur: La largeur explore par distance croissante avec une file. La profondeur va au bout d'une branche avant de revenir, de façon récursive ou avec une pile.
- Graphe orienté ≠ Graphe non orienté: Dans un graphe orienté, une arête a un sens et la matrice n'est pas forcément symétrique. Dans un graphe non orienté, elle l'est.
- Graphe pondéré ≠ Graphe non pondéré: Un graphe pondéré porte un nombre sur chaque arête (distance, coût). La longueur d'un chemin est alors la somme des poids.
- Chaîne eulérienne ≠ Plus court chemin: Une chaîne eulérienne parcourt toutes les arêtes une fois. Un plus court chemin relie deux sommets avec une longueur minimale.
- Liste d'arêtes ≠ Dictionnaire d'adjacence: La liste d'arêtes donne des paires de sommets. Le dictionnaire donne directement les voisins de chaque sommet.
Mode Bac : ce qui rapporte des points
- Théorème d'Euler: Un graphe connexe a une chaîne eulérienne s'il a 0 ou 2 sommets de degré impair. Citer les sommets impairs.
- Largeur contre profondeur: La largeur donne un plus court chemin en nombre d'arêtes dans un graphe non pondéré, avec une file.
- Choix de la représentation: Pour un graphe creux, le dictionnaire est plus économe que la matrice. Donner les deux chiffres si on peut (4 096 contre 262 144 dans l'exercice de 2026).
- Dictionnaire de dictionnaires: G[a][b] donne le poids de l'arête a-b. voisins(G, s) renvoie la liste des clés de G[s].
- Longueur d'un chemin: Somme des poids des arêtes successives, avec un précédent mis à jour à chaque tour.
Quelles erreurs éviter sur les graphes ?
Les corrigés de ce thème sont des réponses détaillées, sans barème par question.
- Oublier de justifier une chaîne eulérienne: Il faut préciser que le graphe est connexe et compter les sommets de degré impair, comme dans l'exercice des routeurs.
- Mauvais ordre de parcours: Dans le réseau routier de 2025, les sommets sont pris dans l'ordre alphabétique. Le parcours en profondeur depuis Calais donne Calais, Nantes, Bordeaux, Toulouse, Lyon, Marseille, Paris, Strasbourg, alors que le parcours en largeur donne Calais, Nantes, Paris, Strasbourg, Bordeaux, Lyon, Toulouse, Marseille.
- Choisir un chemin trop vite: Entre Toulouse et Calais, le chemin par Bordeaux et Nantes fait 250 + 340 + 550 = 1 140 km, celui par Lyon et Paris 1 170 km. Il faut calculer les longueurs de tous les chemins plausibles.
- Liaisons non directes: Dans le jeu Les Aventuriers du Rail, la liaison Luchon-Muret n'est pas directe : elle passe par Saint-Gaudens, donc elle ne peut pas être enregistrée.
- Oublier de marquer les sommets vus: Un parcours sans liste de sommets visités boucle indéfiniment dans un graphe avec cycles. Le code du parcours en profondeur de 2026 ajoute le sommet à la liste vus avant d'explorer ses voisins.
Comment réviser les graphes pour le Bac NSI ?
- Passer d'une représentation à l'autre: Partez d'un schéma et écrivez le dictionnaire, puis la matrice, puis revenez au dessin. Les sujets le demandent sans cesse.
- Dérouler les deux parcours à la main: Choisissez un graphe de 8 sommets et donnez l'ordre de visite en largeur et en profondeur, en prenant les voisins dans l'ordre alphabétique.
- Écrire les fonctions classiques: Degré d'un sommet, voisins, longueur d'un chemin, parcours récursif avec la liste des sommets vus, excentricité.
- Revoir les piles et les files: Le parcours en largeur repose sur une file, comme l'exercice de 2026 qui demande l'ordre d'insertion des sommets. Voir le thème des structures de données.
- Retenir un exemple de chaque cas: Un exemple de chaîne eulérienne, un exemple de plus court chemin pondéré, un exemple de parcours : les justifications sont plus simples quand on a déjà vu un cas.
Quelle est la différence entre un graphe et un arbre en NSI ?
Un arbre est un graphe particulier : connexe, sans cycle, avec une racine. Un graphe général peut contenir des cycles, et un sommet peut avoir un nombre quelconque de voisins.
Comment représenter un graphe en Python ?
Par un dictionnaire d'adjacence (sommet : liste de voisins), par un dictionnaire de dictionnaires pour les poids, ou par une matrice d'adjacence. Le dictionnaire est préférable pour un graphe creux.
Quand un graphe a-t-il une chaîne eulérienne ?
Quand il est connexe et qu'il a zéro ou deux sommets de degré impair. Avec deux, la chaîne relie ces deux sommets.
Quel parcours utiliser pour trouver le plus petit nombre de coups ?
Le parcours en largeur, car dans un graphe non pondéré il explore les sommets par distance croissante et trouve donc un plus court chemin en nombre d'arêtes.
Comment calculer le degré d'un sommet avec une matrice ?
En additionnant les valeurs de sa ligne, puisque chaque 1 représente une arête. La somme des degrés est égale au double du nombre d'arêtes.
Plus sur l'épreuve de NSI
- Piles, files, listes et dictionnaires · 66 sujets
- Programmation orientée objet · 46 sujets
- Arbres et arbres binaires de recherche · 50 sujets
- Bases de données et SQL · 83 sujets
- Binaire, entiers et opérateurs booléens · 16 sujets
- Architectures matérielles et systèmes d'exploitation · 32 sujets
- Réseaux : adressage IP et sous-réseaux · 39 sujets
- Protocoles de routage : RIP et OSPF · 51 sujets
- Sécurisation des communications : chiffrement et HTTPS · 9 sujets
- Récursivité · 24 sujets
- Modularité, API et paradigmes de programmation · 6 sujets
- Mise au point des programmes : bugs, assertions et tests · 13 sujets
- Programme comme donnée, calculabilité et décidabilité · 2 sujets
- Diviser pour régner · 8 sujets
- Programmation dynamique · 7 sujets
- Recherche textuelle et algorithme de Boyer-Moore · 3 sujets
- Coût des algorithmes, tris et recherche · 23 sujets