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

Graphes : représentations, cours 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 ¹.
La matrice d'adjacence est un tableau carré de 0 et de 1 : la case (i, j) vaut 1 s'il existe une liaison de i vers j. Elle est symétrique si le graphe est non orienté.
La liste d'adjacence (ou le dictionnaire de listes) range, pour chaque sommet, la liste de ses voisins ³.
Matrice : test d'une arête immédiat mais mémoire en n². Listes : mémoire proportionnelle aux sommets + arêtes, idéale pour les graphes peu denses.
Dans un graphe pondéré, chaque arête porte un poids (distance, coût, capacité) ³ : on le met dans la matrice ou dans un dictionnaire de dictionnaires.

Pourquoi représenter un graphe ?

Un plan de métro, un réseau d'amis, une molécule : dans chaque cas, on a des objets et des liens entre eux. Les graphes sont l'outil mathématique qui modélise cela. Les molécules (atomes et liaisons), les réseaux sociaux et les réseaux de transport figurent parmi les exemples classiques ³. Les graphes servent aussi à la gestion du trafic ou aux systèmes de recommandation ³.

Dans ce cours, la question n'est pas « qu'est-ce qu'un graphe ? » au sens théorique, mais : comment le ranger dans la mémoire d'un programme ? Un ordinateur ne voit pas un dessin. Il lui faut des listes, des tableaux, des dictionnaires. Tu as déjà manipulé ces structures avec les listes chaînées, les piles, les files, les dictionnaires et les arbres. Un arbre est d'ailleurs un cas particulier de graphe : tu vas donc retrouver des idées familières.

À la fin du chapitre, tu sauras :

décrire un graphe par ses sommets et ses arêtes ou arcs ;
construire sa matrice d'adjacence et sa liste d'adjacence ;
les écrire en Python (liste de listes, dictionnaire) ;
passer d'une représentation à l'autre ;
choisir la représentation adaptée à un problème, en justifiant par la mémoire et le temps de réponse.

Graphe

Vocabulaire
- Sommet
- Arête / arc
- Poids
Matrice
- Carré n×n
- 0 ou 1
- Symétrique si non orienté
Listes
- Voisins
- Dictionnaire
- Peu de mémoire
Choix
- Densité
- Opération fréquente

Représenter un graphe

Vocabulaire : graphes orientés et non orientés

Un graphe exemple pour tout le chapitre

Nous utiliserons un petit graphe non orienté à 5 sommets numérotés de 0 à 4. Ses arêtes sont :

0 — 1
0 — 2
1 — 2
2 — 3
3 — 4

Le sommet 2 est relié à trois autres sommets, il a donc pour degré 3. Le sommet 4 n'a qu'un voisin (le 3), son degré est 1. Les sommets 0, 1, 2 forment un triangle, et la chaîne 2 — 3 — 4 y est accrochée.

La matrice d'adjacence

ExempleMatrice en Python

n = 5
aretes = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)]

M = [[0] * n for _ in range(n)]
for a, b in aretes:
    M[a][b] = 1
    M[b][a] = 1

Attention à la création : [[0] * n] * n est un piège, car les n lignes seraient la même liste. Modifier une case modifierait alors toute une colonne. La compréhension de liste ci-dessus crée n listes distinctes.

La liste d'adjacence et le dictionnaire

ExempleListes du graphe exemple

Pour le graphe à 5 sommets :

0 : [1, 2]
1 : [0, 2]
2 : [0, 1, 3]
3 : [2, 4]
4 : [3]

En Python, on utilise soit une liste de listes indexée par les numéros de sommets, soit un dictionnaire dont les clés sont les sommets :

# liste de listes
adj = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3]]

# dictionnaire (sommets nommés)
G = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B', 'D'],
    'D': ['C', 'E'],
    'E': ['D'],
}

MéthodeConstruire le dictionnaire depuis les arêtes

aretes = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D'), ('D', 'E')]

G = {}
for a, b in aretes:
    G.setdefault(a, []).append(b)
    G.setdefault(b, []).append(a)   # à supprimer si le graphe est orienté

setdefault crée la liste vide si la clé n'existe pas encore, puis on y ajoute le voisin. Dans un graphe orienté, on ne fait que la première ligne d'ajout, mais il faut penser à créer aussi une clé pour les sommets qui n'ont aucun successeur (sinon on perd ces sommets).

Lire les deux représentations : opérations de base

Voyons ce que coûte chaque question simple, selon la représentation. On note $n$ le nombre de sommets et $m$ le nombre d'arêtes (ou d'arcs).

ExempleLister les voisins d'un sommet

Avec la liste d'adjacence : adj[a], immédiat. Avec la matrice : il faut parcourir toute la ligne de a, soit $n$ cases, même si a n'a qu'un voisin.

def voisins_matrice(M, a):
    return [b for b in range(len(M)) if M[a][b] == 1]

ExempleCompter les arêtes

def nb_aretes_matrice(M):
    total = sum(sum(ligne) for ligne in M)
    return total // 2          # graphe non orienté

def nb_aretes_listes(adj):
    total = sum(len(v) for v in adj)
    return total // 2          # graphe non orienté

Dans les deux cas, on compte chaque arête deux fois, d'où la division par 2. Pour un graphe orienté, on ne divise pas : le total est déjà le nombre d'arcs.

Démonstration · Pourquoi la somme des degrés vaut 2m

Chaque arête relie deux sommets. En additionnant les degrés de tous les sommets, on compte, pour chaque arête, une unité à chacune de ses deux extrémités. Chaque arête contribue donc exactement 2 à la somme. On obtient $\sum_{s} \deg(s) = 2m$ . En particulier, cette somme est toujours paire : un graphe non orienté ne peut pas avoir un nombre impair de sommets de degré impair.

Passer d'une représentation à l'autre

MéthodeDe la matrice à la liste d'adjacence

Pour chaque ligne $i$ , on collecte les indices $j$ où la case vaut 1.

def matrice_vers_listes(M):
    n = len(M)
    return [[j for j in range(n) if M[i][j] == 1] for i in range(n)]

Temps : on lit les $n^2$ cases de la matrice.

MéthodeDe la liste d'adjacence à la matrice

def listes_vers_matrice(adj):
    n = len(adj)
    M = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in adj[i]:
            M[i][j] = 1
    return M

Temps : $n^2$ pour créer la matrice, plus la somme des longueurs des listes pour la remplir.

MéthodeDu dictionnaire à la matrice

Quand les sommets sont nommés, on commence par attribuer un indice à chaque nom :

def dict_vers_matrice(G):
    noms = sorted(G)                       # ordre choisi
    indice = {nom: k for k, nom in enumerate(noms)}
    n = len(noms)
    M = [[0] * n for _ in range(n)]
    for a in G:
        for b in G[a]:
            M[indice[a]][indice[b]] = 1
    return M, noms

On renvoie aussi noms, qui précise l'étiquetage, car la matrice seule n'a de sens qu'avec cette correspondance (voir la dépendance à l'étiquetage plus haut).

Choisir la bonne représentation

Aucune représentation n'est meilleure dans tous les cas. Le choix dépend de la densité du graphe, c'est-à-dire du nombre d'arêtes par rapport au maximum possible, et de l'opération la plus fréquente. Un graphe de réseau routier est peu dense : chaque carrefour est relié à quelques autres seulement, alors qu'il y a des milliers de carrefours. Un graphe où presque tous les sommets sont reliés entre eux est dense.

Matrice ou liste d'adjacence
Critère	Matrice d'adjacence	Liste / dictionnaire
Mémoire	n² cases	n + m éléments environ
Arête a–b existe ?	Un accès direct	Parcours de la liste de a
Voisins de a	Parcours d'une ligne de n cases	Liste déjà prête
Graphe adapté	Dense	Peu dense
Poids	Dans la case	Dictionnaire de dictionnaires

Matrice ou liste d'adjacence

EstimerCompte n sommets et m arêtes.
DensitéCompare m à n² : graphe dense ou non ?
OpérationTest d'arête ou parcours de voisins ?
DéciderDense ou tests : matrice. Sinon : listes.

Choisir sa représentation

Erreurs fréquentes et conseils pour le Bac

« À bien des égards, les graphes sont la principale modalité de données que nous recevons de la nature. » (Petar Veličković, 2023) ³

Pourquoi les graphes sont partout

Exercices corrigés

Exercice 1 Lire une matrice d'adjacence

★☆☆Environ 8 min

Un graphe non orienté a 4 sommets numérotés de 0 à 3. Sa matrice d'adjacence est :

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

Donne la liste d'adjacence de chaque sommet.
Quel est le degré de chaque sommet ?
Combien ce graphe compte-t-il d'arêtes ?

Indice 1

La ligne i de la matrice contient un 1 pour chaque voisin de i.

Indice 2

Chaque arête apparaît deux fois dans la matrice.

Voir la correction pas à pas

Ligne 0 : des 1 aux colonnes 1 et 2, donc voisins de 0 : [1, 2].
Ligne 1 : colonnes 0, 2, 3, donc [0, 2, 3]. Ligne 2 : colonnes 0, 1, 3, donc [0, 1, 3]. Ligne 3 : colonnes 1 et 2, donc [1, 2].
Degrés : 2, 3, 3, 2 (nombre de voisins de chaque sommet).
La somme des degrés vaut 2 + 3 + 3 + 2 = 10. Chaque arête étant comptée deux fois, il y a 10 / 2 = 5 arêtes.

Le graphe compte 5 arêtes. Le contrôle de symétrie de la matrice confirme qu'il s'agit bien d'un graphe non orienté.

Exercice 2 Compter les arcs d'un graphe orienté

★★☆Environ 10 min

Un graphe orienté a 5 sommets (0 à 4). On donne la liste des successeurs de chaque sommet :

0 : [1, 2]
1 : [2]
2 : [0, 3, 4]
3 : []
4 : [3, 1]

Combien d'arcs ce graphe possède-t-il ?
Quel est le degré entrant du sommet 3 ?
Écris la ligne 4 de la matrice d'adjacence.

Indice 1

Dans un graphe orienté, chaque arc n'apparaît qu'une fois dans les listes de successeurs.

Indice 2

Le degré entrant de 3 est le nombre de listes qui contiennent 3.

Voir la correction pas à pas

Nombre d'arcs : on additionne les longueurs des listes, 2 + 1 + 3 + 0 + 2 = 8.
Degré entrant de 3 : le sommet 3 apparaît dans la liste de 2 et dans celle de 4, soit 2 arcs entrants.
Ligne 4 : les successeurs de 4 sont 3 et 1. On met un 1 aux colonnes 1 et 3, d'où [0, 1, 0, 1, 0].

Le graphe compte 8 arcs. On ne divise pas par 2, puisqu'un arc n'a qu'un sens.

Exercice 3 Écrire une fonction de conversion

★★★Environ 15 min

On représente un graphe non orienté par un dictionnaire G dont les clés sont des sommets nommés et les valeurs des listes de voisins.

Écris une fonction degre(G, s) qui renvoie le degré du sommet s.
Écris une fonction est_coherent(G) qui renvoie True si, pour chaque b voisin de a, a figure aussi dans la liste de b.
Explique pourquoi un sommet isolé doit apparaître comme clé du dictionnaire.

Indice 1

Le degré est la longueur de la liste associée à la clé.

Indice 2

Parcours toutes les clés a, puis tous les voisins b de a, et teste a in G[b].

Voir la correction pas à pas

Question 1 : def degre(G, s): return len(G[s]).
Question 2 : on parcourt chaque couple (a, b) avec b dans G[a] ; si a not in G[b], on renvoie False ; à la fin de la double boucle, on renvoie True.
Version complète : def est_coherent(G): puis for a in G: puis for b in G[a]: puis if a not in G[b]: return False, enfin return True.
Question 3 : sans clé pour un sommet isolé, le sommet n'existe pas dans la structure ; le nombre de sommets, len(G), serait faux, et G[s] provoquerait une erreur.

Cette vérification de cohérence est utile après avoir construit un graphe à la main : elle détecte les arêtes inscrites une seule fois.

Les questions qu'on se pose

Faut-il retenir la matrice ou la liste d'adjacence pour le Bac ?

Les deux. Le programme attend que tu saches passer de l'une à l'autre et justifier un choix. Dans les sujets, on te donne souvent un graphe sous forme de dictionnaire de listes ou de matrice, et on te demande d'écrire une fonction qui le parcourt ou le convertit. Retiens aussi les ordres de grandeur de mémoire : $n^2$ pour la matrice, de l'ordre de $n + m$ pour les listes.

Comment savoir si un graphe est dense ou peu dense ?

Compare le nombre d'arêtes $m$ au maximum possible. Dans un graphe non orienté sans boucle, ce maximum vaut $n(n-1)/2$ . Si $m$ est proche de ce maximum, le graphe est dense ; s'il est de l'ordre de $n$ , il est peu dense. Les réseaux routiers ou sociaux sont en général peu denses.

Un arbre est-il un graphe ?

Oui. Un arbre est un graphe particulier, sans cycle et dont tous les sommets sont reliés entre eux. On peut donc le représenter avec une liste d'adjacence ou une matrice, même si, pour un arbre binaire, une structure dédiée (nœud avec fils gauche et fils droit) est souvent plus simple.

Que mettre dans la matrice pour un graphe pondéré ?

On y place le poids de l'arête à la place du 1. Comme 0 peut être un poids valide, on marque l'absence de liaison par une valeur spéciale, None ou float('inf') selon l'usage. Avec un dictionnaire, on écrit G['A']['B'] = poids.

Pourquoi un graphe non orienté est-il stocké avec chaque arête en double ?

Parce qu'une arête relie les deux sommets dans les deux sens. Pour pouvoir lire directement les voisins de n'importe quel sommet, on inscrit B chez A et A chez B. Le coût est un doublement du stockage, mais les parcours restent simples.

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, cours de Terminale NSI

L'essentiel

Pourquoi représenter un graphe ?

Vocabulaire : graphes orientés et non orientés

Un graphe exemple pour tout le chapitre

La matrice d'adjacence

La liste d'adjacence et le dictionnaire

Lire les deux représentations : opérations de base

Passer d'une représentation à l'autre

Choisir la bonne représentation

Erreurs fréquentes et conseils pour le Bac

Exercices corrigés

Exercice 1 Lire une matrice d'adjacence

Exercice 2 Compter les arcs d'un graphe orienté

Exercice 3 Écrire une fonction de conversion

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur