Numérique et sciences informatiques (spécialité) · TerminaleBac
Graphes : représentations, fiche de révision de Terminale NSI
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
- Un graphe est un ensemble de sommets reliés par des arêtes (non orienté) ou des arcs (orienté).
- Son dessin n'est pas unique : seule la structure, qui est relié à qui, compte.
- Pour programmer, on le stocke par une matrice d'adjacence (tableau de 0 et de 1) ou par des listes de voisins (souvent un dictionnaire).
- Matrice : test d'une arête immédiat, mais tableau de n×n cases. Listes : plus économe quand il y a peu d'arêtes.
- Dans un graphe non orienté, la matrice est symétrique ; changer les étiquettes des sommets permute ses lignes et ses colonnes.
Ce qu'est un graphe
Un dessin n'est pas un graphe
C'est pour cela qu'un programme ne stocke pas un dessin : il stocke la structure, c'est-à-dire la liste des liaisons. Il existe deux grandes façons de le faire.
Exemple de référence
Matrice d'adjacence
Listes de voisins et dictionnaire
Choisir sa représentation
| Critère | Matrice d'adjacence | Dictionnaire de listes |
|---|---|---|
| Mémoire | cases, même si peu d'arêtes | proportionnelle aux sommets et aux arêtes |
| Tester une arête | accès direct M[i][j] |
parcours de la liste d'un sommet |
| Parcourir les voisins | balayer toute une ligne | lire directement la liste |
| Sommets nommés (chaînes) | il faut les numéroter | clés quelconques |
Questions flash
5 questions · correction immédiate · ton score reste sur ton appareil.
-
Chaque arête est notée deux fois, en
M[i][j]et enM[j][i], donc . Répondre 4 oublie la symétrie d'un graphe non orienté. -
Un arc a un sens : seule la case départ→arrivée est remplie. Remplir aussi la case symétrique, c'est traiter le graphe comme non orienté, ce qui est faux ici.
-
La représentation graphique d'un graphe n'est pas unique et les arêtes peuvent se couper.1 Ce qui définit le graphe, c'est sa structure, pas son dessin.
-
G[2]est la liste des voisins ;len(G[2])donne .len(G)compte les sommets (4), etsum(G[2])additionne les numéros des voisins, ce qui n'a pas de sens ici. -
La matrice dépend de l'étiquetage : échanger deux étiquettes échange à la fois les lignes et les colonnes correspondantes.3 Le graphe reste le même ; seule sa description change.
Les questions qu'on se pose
Matrice ou dictionnaire : que choisir au bac ?
Utilise ce que l'énoncé impose. Sinon, le dictionnaire de listes est souvent plus simple à parcourir et plus économe quand il y a peu d'arêtes ; la matrice est pratique pour tester vite l'existence d'une arête.
Que mettre dans la matrice d'un graphe pondéré ?
Chaque arête d'un graphe pondéré porte un poids3 : on place ce poids à la place du . Il faut alors une valeur qui signifie « pas d'arête », par exemple None, choisie pour ne pas être confondue avec un poids possible.
Pourquoi la matrice est-elle symétrique pour un graphe non orienté ?
Une arête relie et dans les deux sens : on remplit donc M[i][j] et M[j][i]. Pour un graphe orienté, cette symétrie n'est pas garantie.
Sources
- Document officiel eduscol : Graphes (structures de données), Éduscol. Consulté le 7 novembre 2026.
- Représentation graphique, Wikipédia. Consulté le 7 novembre 2026.
- Théorie des graphes, Wikipédia. Consulté le 7 novembre 2026.
Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.