Numérique et sciences informatiques (spécialité) · TerminaleBac

Graphes : représentations, exercices corrigés de Terminale NSI

Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur

L'essentiel

Un graphe se représente par une matrice d'adjacence (tableau de 0 et de 1) ou par des listes de voisins (dictionnaire).
Pour un graphe non orienté, la matrice est symétrique ; pour un graphe orienté, elle ne l'est en général pas.
Un graphe pondéré associe un nombre (le poids) à chaque arête ; la matrice contient alors les poids.
Le dessin d'un graphe n'est pas unique : on raisonne sur sa structure, pas sur sa figure.
Matrice : lecture rapide d'une arête mais beaucoup de place ; listes : économes quand il y a peu d'arêtes.

Comment utiliser ces exercices

Ces exercices portent sur les représentations d'un graphe : le dessin, la matrice d'adjacence et les listes de voisins. Ils sont classés du plus simple au plus délicat. Cherche d'abord seul, avec une feuille, puis ouvre les indices un par un, et seulement ensuite la correction.

Les exercices

Exercice 1 Construire une matrice d'adjacence

★☆☆Environ 6 min

Un graphe non orienté a pour sommets $A$ , $B$ , $C$ , $D$ (dans cet ordre) et pour arêtes $A-B$ , $A-C$ , $B-C$ et $C-D$ .

Écris sa matrice d'adjacence.
Combien de cases de cette matrice valent $1$ ?

Indice 1

Une arête $A-B$ donne un $1$ à deux endroits : ligne $A$ colonne $B$ , et ligne $B$ colonne $A$ .

Indice 2

Aucun sommet n'a d'arête vers lui-même : la diagonale est remplie de $0$ .

Voir la correction pas à pas

On prépare un tableau $4\times 4$ dont les lignes et colonnes sont ordonnées $A,B,C,D$ .
On place les $1$ pour $A-B$ : cases $(A,B)$ et $(B,A)$ . Pour $A-C$ : $(A,C)$ et $(C,A)$ . Pour $B-C$ : $(B,C)$ et $(C,B)$ . Pour $C-D$ : $(C,D)$ et $(D,C)$ .
On complète par des $0$ . La matrice est $\begin{pmatrix}0&1&1&0\\1&0&1&0\\1&1&0&1\\0&0&1&0\end{pmatrix}$ .
On compte les $1$ : $2$ par arête, donc $2\times 4 = 8$ .

La matrice est symétrique, comme toujours pour un graphe non orienté, et le nombre de $1$ vaut deux fois le nombre d'arêtes.

Exercice 2 Passer à des listes de voisins

★☆☆Environ 5 min

On reprend le graphe de l'exercice précédent (arêtes $A-B$ , $A-C$ , $B-C$ , $C-D$ ).

Écris-le sous forme de dictionnaire Python associant à chaque sommet la liste de ses voisins.
Quel est le nombre de voisins du sommet $C$ ?

Indice 1

Le dictionnaire commence par {"A": ["B", "C"], ...}.

Indice 2

Compte les arêtes qui touchent $C$ .

Voir la correction pas à pas

Voisins de $A$ : $B$ et $C$ .
Voisins de $B$ : $A$ et $C$ . Voisins de $C$ : $A$ , $B$ et $D$ . Voisins de $D$ : $C$ .
Le dictionnaire est {"A": ["B","C"], "B": ["A","C"], "C": ["A","B","D"], "D": ["C"]}.
Le sommet $C$ a $3$ voisins, c'est len(g["C"]).

Chaque arête apparaît deux fois dans ce dictionnaire, une fois dans la liste de chacune de ses extrémités.

Exercice 3 Lire une matrice : nombre d'arêtes

★☆☆Environ 7 min

Un graphe non orienté à cinq sommets numérotés de $0$ à $4$ a pour matrice d'adjacence

$M=\begin{pmatrix}0&1&1&0&0\\1&0&1&1&0\\1&1&0&0&1\\0&1&0&0&1\\0&0&1&1&0\end{pmatrix}$

Combien ce graphe a-t-il d'arêtes ?

Indice 1

Additionne les $1$ ligne par ligne : chaque ligne donne le nombre de voisins du sommet.

Indice 2

Chaque arête est comptée deux fois dans la matrice.

Voir la correction pas à pas

Les lignes contiennent respectivement $2$ , $3$ , $3$ , $2$ et $2$ cases à $1$ .
La somme des cases vaut $2+3+3+2+2=12$ .
Chaque arête étant comptée une fois par extrémité, on divise par $2$ : $12/2=6$ .

On peut vérifier en listant les arêtes : $0-1$ , $0-2$ , $1-2$ , $1-3$ , $2-4$ , $3-4$ . Cela fait bien six arêtes.

Exercice 4 Un graphe orienté

★★☆Environ 9 min

Un graphe orienté a pour sommets $0,1,2,3$ et pour arcs $0\to1$ , $0\to2$ , $1\to2$ , $2\to0$ , $2\to3$ , $3\to1$ .

Écris sa matrice d'adjacence (la case de la ligne $i$ , colonne $j$ vaut $1$ si l'arc $i\to j$ existe).
Cette matrice est-elle symétrique ?
Combien d'arcs partent du sommet $2$ ?

Indice 1

Un arc $0\to1$ ne donne qu'un seul $1$ : ligne $0$ , colonne $1$ .

Indice 2

Le nombre d'arcs qui partent du sommet $2$ se lit sur la ligne $2$ .

Voir la correction pas à pas

Ligne $0$ : arcs vers $1$ et $2$ , soit $(0,1,1,0)$ . Ligne $1$ : arc vers $2$ , soit $(0,0,1,0)$ .
Ligne $2$ : arcs vers $0$ et $3$ , soit $(1,0,0,1)$ . Ligne $3$ : arc vers $1$ , soit $(0,1,0,0)$ .
Pas de symétrie : la case $(0,1)$ vaut $1$ mais la case $(1,0)$ vaut $0$ .
Sur la ligne $2$ , il y a deux $1$ : deux arcs partent du sommet $2$ .

Dans un graphe orienté, la ligne d'un sommet décrit les arcs qui en partent et la colonne ceux qui y arrivent. C'est pourquoi la matrice n'est plus symétrique.

Exercice 5 Du code à la structure du graphe

★★☆Environ 8 min

Un programme définit le graphe suivant :

g = {"A": ["B", "D"],
     "B": ["A", "C", "D"],
     "C": ["B"],
     "D": ["A", "B"]}

def nb_aretes(g):
    return sum(len(v) for v in g.values()) // 2

Que renvoie nb_aretes(g) ?
Pourquoi divise-t-on par $2$ ? Pourquoi serait-ce faux pour un graphe orienté ?

Indice 1

Calcule d'abord len de chaque liste.

Indice 2

Pense à la manière dont une arête apparaît dans le dictionnaire.

Voir la correction pas à pas

Les longueurs des listes sont $2$ , $3$ , $1$ et $2$ ; leur somme vaut $8$ .
Chaque arête non orientée est écrite deux fois (dans la liste de chaque extrémité), donc $8//2=4$ .
Les arêtes sont $A-B$ , $A-D$ , $B-C$ , $B-D$ : on en compte bien quatre.
Dans un graphe orienté, un arc $u\to v$ n'est écrit qu'une fois, dans la liste de $u$ : il ne faut alors pas diviser.

Avant d'utiliser une formule de comptage, demande-toi toujours si le graphe est orienté ou non.

Exercice 6 Matrice de poids et coût d'un chemin

★★☆Environ 10 min

Un graphe pondéré non orienté a pour sommets $A,B,C,D$ et pour arêtes pondérées : $A-B$ de poids $4$ , $A-C$ de poids $2$ , $B-C$ de poids $1$ , $B-D$ de poids $5$ , $C-D$ de poids $7$ .

Écris la matrice des poids, en mettant $0$ quand il n'y a pas d'arête.
Quel est le coût total du chemin $A\to C\to B\to D$ ?
Ce chemin est-il plus court que le chemin direct $A\to B\to D$ ?

Indice 1

Dans un graphe pondéré, le poids d'une arête peut représenter une distance ou un coût ³. On le place dans la matrice à la place du $1$ .

Indice 2

Le coût d'un chemin est la somme des poids de ses arêtes.

Voir la correction pas à pas

La matrice des poids, dans l'ordre $A,B,C,D$ , est $\begin{pmatrix}0&4&2&0\\4&0&1&5\\2&1&0&7\\0&5&7&0\end{pmatrix}$ .
Le chemin $A\to C\to B\to D$ utilise les arêtes de poids $2$ , $1$ et $5$ : coût $2+1+5=8$ .
Le chemin $A\to B\to D$ coûte $4+5=9$ .
Comme $8<9$ , le chemin qui passe par $C$ est plus économique, bien qu'il compte plus d'arêtes.

Le nombre d'arêtes d'un chemin ne dit rien de son coût : il faut additionner les poids.

Exercice 7 Choisir la représentation : coût mémoire

★★★Environ 10 min

Un graphe non orienté a $100$ sommets et $150$ arêtes.

Combien de cases contient sa matrice d'adjacence ?
Combien de sommets au total apparaissent dans l'ensemble de ses listes de voisins ?
Quelle représentation choisir pour ce graphe, et pourquoi ?

Indice 1

La matrice a une ligne et une colonne par sommet.

Indice 2

Chaque arête est écrite deux fois dans les listes de voisins.

Voir la correction pas à pas

La matrice est carrée de côté $100$ : $100\times100=10\,000$ cases.
Chaque arête figure dans la liste de chacune de ses deux extrémités : $2\times150=300$ entrées au total.
$300$ est bien inférieur à $10\,000$ : presque toutes les cases de la matrice contiendraient un $0$ .
On choisit donc les listes de voisins, plus économes quand il y a peu d'arêtes. La matrice garde l'avantage de répondre immédiatement à la question « ces deux sommets sont-ils reliés ? ».

Le choix dépend de la densité du graphe et de l'usage : peu d'arêtes, on préfère les listes ; test fréquent d'une arête précise, la matrice est pratique.

Exercice 8 Nombre maximal d'arêtes

★★★Environ 10 min

On considère des graphes non orientés à $5$ sommets, sans arête reliant un sommet à lui-même et sans arête multiple.

Combien d'arêtes au maximum un tel graphe peut-il avoir ?
Quel serait le nombre maximal d'arcs pour un graphe orienté de $5$ sommets, sans boucle et avec au plus un arc de $u$ vers $v$ ?
Comment le voit-on sur la matrice d'adjacence ?

Indice 1

Une arête relie deux sommets distincts : compte les paires de sommets.

Indice 2

Dans un graphe orienté, l'arc $u\to v$ et l'arc $v\to u$ sont deux arcs différents.

Voir la correction pas à pas

Le nombre de paires de sommets distincts parmi $5$ est $\dfrac{5\times4}{2}=10$ .
Pour un graphe orienté, chaque sommet peut émettre un arc vers chacun des $4$ autres : $5\times4=20$ arcs au maximum.
Sur la matrice, la diagonale reste à $0$ (pas de boucle). Il reste $25-5=20$ cases utilisables, dont la moitié suffit au cas non orienté, par symétrie : $10$ arêtes.

Un graphe qui atteint ce maximum est dit complet. La matrice d'un graphe complet non orienté ne contient que des $1$ hors de la diagonale.

Les questions qu'on se pose

Deux matrices différentes peuvent-elles représenter le même graphe ?

Oui. La matrice dépend de l'ordre dans lequel on étiquette les sommets ³. Si tu échanges l'étiquette de deux sommets, deux lignes et deux colonnes de la matrice sont échangées, mais le graphe reste le même. De même, plusieurs dessins peuvent représenter un seul graphe ¹. Pour comparer deux représentations, fixe d'abord l'ordre des sommets.

Au bac, faut-il préférer la matrice ou les listes de voisins ?

Le sujet l'indique en général : on te demande de lire ou d'écrire l'une ou l'autre. Quand tu as le choix, retiens la règle de l'exercice sur le coût mémoire : peu d'arêtes, les listes de voisins (un dictionnaire Python) ; test fréquent de la présence d'une arête, la matrice. Dans tous les cas, précise l'ordre des sommets et si le graphe est orienté ou non.

Comment vérifier rapidement une matrice d'adjacence que je viens d'écrire ?

Trois contrôles. Pour un graphe non orienté, la matrice doit être symétrique. La diagonale doit être nulle s'il n'y a pas de boucle. La somme de toutes les cases doit valoir deux fois le nombre d'arêtes (le nombre d'arcs pour un graphe orienté).

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.

Signaler une erreur sur cette page

Graphes : représentations, exercices corrigés de Terminale NSI

L'essentiel

Comment utiliser ces exercices

Les exercices

Exercice 1 Construire une matrice d'adjacence

Exercice 2 Passer à des listes de voisins

Exercice 3 Lire une matrice : nombre d'arêtes

Exercice 4 Un graphe orienté

Exercice 5 Du code à la structure du graphe

Exercice 6 Matrice de poids et coût d'un chemin

Exercice 7 Choisir la représentation : coût mémoire

Exercice 8 Nombre maximal d'arêtes

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur