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.

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.

Dictionnaire d'adjacenceMatrice d'adjacence
Forme{sommet : liste de voisins}Tableau n × n de 0 et de 1
MémoireProportionnelle au nombre d'arêtesn × n, même si le graphe est creux
Voisins d'un sommetLecture directe de la listeParcours d'une ligne
Degré d'un sommetLongueur de la listeSomme 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).

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.

  1. É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.
  2. 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.
  3. 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].
  4. 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.
  5. 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

Mode Bac : ce qui rapporte des points

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.

Comment réviser les graphes pour le Bac NSI ?

  1. 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.
  2. 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.
  3. Écrire les fonctions classiques: Degré d'un sommet, voisins, longueur d'un chemin, parcours récursif avec la liste des sommets vus, excentricité.
  4. 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.
  5. 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