Numérique et sciences informatiques · Terminale · Structures de données · 1.º Período

Graphes

Modélisation de relations à l'aide de graphes orientés et non orientés. Représentation par matrices d'adjacence et listes de successeurs.

En bref:Les graphes représentent l'outil de modélisation le plus polyvalent du programme de NSI. Ils permettent de formaliser des relations complexes entre des objets, qu'il s'agisse de réseaux sociaux, de cartes routières ou de liaisons internet. Les élèves découvrent les notions de sommets, d'arcs (ou arêtes), de pondération et d'orientation, tout en apprenant à traduire ces schémas en structures de données informatiques comme les matrices d'adjacence ou les listes de listes.

• Programmes Officiels
• BOEN spécial n°8 du 25 juillet 2019 - Structures de données
• Compétence : Modéliser des situations sous forme de graphes

À propos de ce thème

Les graphes représentent l'outil de modélisation le plus polyvalent du programme de NSI. Ils permettent de formaliser des relations complexes entre des objets, qu'il s'agisse de réseaux sociaux, de cartes routières ou de liaisons internet. Les élèves découvrent les notions de sommets, d'arcs (ou arêtes), de pondération et d'orientation, tout en apprenant à traduire ces schémas en structures de données informatiques comme les matrices d'adjacence ou les listes de listes.

Ce chapitre est crucial car il introduit la pensée systémique. Les élèves apprennent que la manière dont on représente un problème influence directement la complexité de sa résolution. Les graphes offrent un terrain idéal pour l'apprentissage par le projet et la collaboration, car ils sont visuels et connectés à des problématiques concrètes du quotidien. Les élèves saisissent mieux les concepts de chemins et de connectivité en travaillant sur des cas réels comme le routage de paquets ou les suggestions d'amis en ligne.

Questions clés

1. Comment représenter un graphe en mémoire ?
2. Quelle est la différence entre un graphe orienté et non orienté ?
3. Qu'est-ce qu'un chemin dans un graphe ?

Attention à ces idées reçues

Idée reçue courante

Penser qu'un graphe est forcément planaire (sans croisement d'arêtes).

Ce qu'il faut enseigner à la place

Un graphe est une structure abstraite ; la position des sommets n'importe pas, seules les connexions comptent. Faire redessiner le même graphe de plusieurs façons différentes aide à briser cette illusion visuelle.

Idée reçue courante

Confondre successeurs et prédécesseurs dans un graphe orienté.

Ce qu'il faut enseigner à la place

Dans un graphe orienté, le sens de la flèche est crucial. Utiliser des exemples de relations asymétriques (A suit B sur Twitter) permet de clarifier cette notion par la discussion.

Idées d'apprentissage actif

Galerie marchande

Modéliser le monde

Plusieurs situations sont affichées (réseau de bus, amitiés Facebook, dépendances logicielles). Les élèves circulent et doivent dessiner le graphe correspondant en précisant s'il est orienté ou pondéré.

50 min·Petits groupes

Résolution de problèmes en collaboration

Matrice vs Liste

Les groupes reçoivent un graphe dense et un graphe creux. Ils doivent essayer de les représenter avec une matrice d'adjacence et une liste de successeurs, puis débattre de la méthode la plus efficace en mémoire.

45 min·Petits groupes

Jeu de simulation

Le voyageur de commerce

Sur un grand graphe au sol, les élèves doivent trouver le chemin le plus court entre deux points. Ils découvrent par l'expérience la difficulté de l'optimisation dans les graphes complexes.

40 min·Classe entière

Questions fréquentes

Quelle est la différence entre un graphe orienté et non orienté ?

Dans un graphe non orienté, les relations sont symétriques (si A est lié à B, B est lié à A). Dans un graphe orienté, les liens ont un sens, représenté par des flèches. C'est la différence entre une amitié mutuelle et un abonnement sur un réseau social.

Pourquoi utiliser une liste d'adjacence plutôt qu'une matrice ?

La matrice d'adjacence est simple mais consomme beaucoup de mémoire si le graphe a peu de liaisons (graphe creux). La liste d'adjacence est plus efficace car elle ne stocke que les connexions existantes, ce qui est le cas de la plupart des réseaux réels.

Qu'est-ce qu'un chemin dans un graphe ?

Un chemin est une suite de sommets reliés par des arêtes ou des arcs. En NSI, on s'intéresse souvent à trouver le chemin le plus court ou à vérifier si deux sommets sont connectés.

Comment modéliser des situations réelles avec des graphes en classe ?

L'approche la plus efficace consiste à partir de données réelles : plans de métro, réseaux de neurones simplifiés ou graphes de pages web. En demandant aux élèves de construire eux-mêmes ces modèles en petits groupes, ils apprennent à identifier les entités (sommets) et les relations (arêtes), ce qui renforce leur capacité d'abstraction.