Graphes : vocabulaire et représentations

Vue d'ensemble

Un graphe modélise des objets et des liens entre eux : des villes reliées par des routes, des pages web par des liens, des personnes par des amitiés, des tâches par des dépendances. C'est l'une des structures les plus puissantes de l'informatique, et le support de grands algorithmes de deuxième année (parcours, plus court chemin). Avant de les parcourir, il faut deux choses : le vocabulaire exact (sommet, arête, degré, chemin, cycle…) et la façon de représenter un graphe en machine. Cette fiche pose ce socle, code les deux représentations classiques — listes d'adjacence et matrice d'adjacence —, les décrypte ligne par ligne et compare leurs coûts.

Au programme (tronc commun, 1^re année — BO 2021) — Graphes : vocabulaire (sommets, arêtes, graphe orienté / non orienté, degré, chemin, cycle, connexité, graphe pondéré) ; représentation par matrice d'adjacence et par listes d'adjacence. Les parcours (BFS, DFS) et le plus court chemin (Dijkstra) font l'objet d'une autre fiche.

Prérequis

Manipuler une liste Python : parcours for, len, test x in liste (fiche « listes et chaînes »)
Manipuler un dictionnaire : clé → valeur, parcours for k in d (fiche « dictionnaires »)
Savoir lire un coût en $O (n)$ , $O (n^{2})$ (fiche « complexité temporelle »)

🎯 Accompagnement Majorant

Les graphes font peur, mais tout part d'un vocabulaire précis et de deux représentations. Confondre arête et arc, ou choisir la mauvaise représentation, coûte cher aux concours. Nos mentors alumni X · Centrale · Mines t'apprennent à dessiner, coder et raisonner sur un graphe jusqu'à ce que la structure devienne intuitive.

Trouver un mentor →

1. Le vocabulaire des graphes

Définition 1.1 — Graphe

Un graphe est la donnée d'un ensemble de sommets (ou nœuds) et d'un ensemble de liens entre ces sommets. On note traditionnellement $n$ le nombre de sommets et $m$ le nombre de liens. Deux cas :

Graphe non orienté : les liens sont des arêtes, symétriques. Une arête entre $u$ et $v$ se note ${u, v}$ : elle relie $u$ à $v$ et $v$ à $u$ .
Graphe orienté : les liens sont des arcs, à sens unique. Un arc de $u$ vers $v$ se note $(u, v)$ : il va de $u$ à $v$ , pas l'inverse.

Prenons un graphe non orienté à quatre sommets $A, B, C, D$ et quatre arêtes : ${A, B}$ , ${A, C}$ , ${B, C}$ , ${C, D}$ . Il nous servira de fil rouge dans toute la fiche.

Définition 1.2 — Voisins, degré

Deux sommets reliés par une arête sont voisins (ou adjacents). Le degré d'un sommet est son nombre de voisins (le nombre d'arêtes qui le touchent). Dans notre exemple, $C$ a pour voisins $A, B, D$ : son degré vaut 3. Dans un graphe orienté, on distingue le degré sortant (nombre d'arcs qui partent du sommet) et le degré entrant (nombre d'arcs qui arrivent).

Définition 1.3 — Chemin, cycle, connexité

Un chemin est une suite de sommets consécutivement reliés : $A - C - D$ est un chemin de $A$ à $D$ , de longueur 2 (on compte les arêtes). Un cycle est un chemin qui revient à son point de départ sans réemprunter une arête : $A - B - C - A$ est un cycle. Un graphe est connexe si l'on peut aller de n'importe quel sommet à n'importe quel autre par un chemin (le graphe est « d'un seul tenant »).

📝 Graphe pondéré. On peut attacher à chaque arête (ou arc) un poids : une distance, un coût, une durée. On parle alors de graphe pondéré. C'est indispensable pour les problèmes de plus court chemin (Dijkstra) — mais le poids ne change rien au vocabulaire ci-dessus.

⚠ Arête ≠ arc. Dans un graphe non orienté, l'arête

{A, B}

se parcourt dans les deux sens :

A

est voisin de

B

B

voisin de

A

. Dans un graphe orienté, l'arc

(A, B)

ne dit rien sur un éventuel arc

(B, A)

. Toujours vérifier, dans un énoncé, si le graphe est orienté ou non : la moitié des erreurs vient de là.

2. Représentation par listes d'adjacence

Première façon de mettre un graphe en machine : pour chaque sommet, on stocke la liste de ses voisins. En Python, c'est naturellement un dictionnaire qui associe à chaque sommet la liste de ses voisins.

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

print(g["C"])        # ['A', 'B', 'D'] : les voisins de C
print(len(g["C"]))   # 3 : le degre de C
print("D" in g["A"]) # False : il n'y a pas d'arete entre A et D

🔍 Décryptage ligne par ligne

g = { "A": ["B", "C"], ... }Un dictionnaire sommet → voisins. Chaque clé est un sommet, chaque valeur est la liste de ses voisins. L'arête

{A, B}

apparaît deux fois : "B" est dans g["A"] ET "A" est dans g["B"]. C'est ce qui traduit la symétrie du non orienté.

g["C"]Les voisins d'un sommet, directement. On lit la liste des voisins de C en une seule opération : ['A', 'B', 'D']. C'est le grand atout de cette représentation.

len(g["C"])Le degré. Le degré d'un sommet est le nombre de ses voisins, donc la longueur de sa liste : ici 3.

"D" in g["A"]Tester une arête. L'arête

{A, D}

existe si "D" figure dans la liste des voisins de A. Ici False. Ce test parcourt la liste : il coûte

O (de g A)

, le degré de

A

Écrivons les trois opérations de base comme des fonctions, puis déroulons-les sur le fil rouge.

def voisins(g, s):
    return g[s]                 # la liste des voisins de s

def degre(g, s):
    return len(g[s])            # nombre de voisins

def nb_aretes(g):
    total = 0
    for s in g:                 # on additionne tous les degres
        total = total + len(g[s])
    return total // 2           # chaque arete est comptee 2 fois

print(degre(g, "A"), degre(g, "B"), degre(g, "C"), degre(g, "D"))  # 2 2 3 1
print(nb_aretes(g))            # 4

🔍 Décryptage ligne par ligne

return g[s]Voisins. On renvoie telle quelle la liste stockée pour s — coût

O (1)

total = total + len(g[s])On somme les degrés. On parcourt tous les sommets et on ajoute la longueur de chaque liste de voisins : on obtient la somme des degrés.

return total // 2Le piège du double comptage. Chaque arête

{u, v}

est comptée une fois dans le degré de

u

et une fois dans celui de

v

. La somme des degrés vaut donc deux fois le nombre d'arêtes : on divise par 2. (C'est le lemme démontré au §4.)

Exécution de nb_aretes sur le graphe fil rouge
Sommet `s`	`g[s]`	`len(g[s])`	`total` après
A	['B', 'C']	2	2
B	['A', 'C']	2	4
C	['A', 'B', 'D']	3	7
D	['C']	1	8
résultat : `total // 2`			8 // 2 = 4 ✓

3. Représentation par matrice d'adjacence

Deuxième façon : on numérote les sommets $0, 1, \dots, n - 1$ et on stocke un tableau carré $n \times n$ de 0 et de 1. La case ligne $i$ , colonne $j$ vaut 1 s'il y a une arête entre le sommet $i$ et le sommet $j$ , 0 sinon. En Python, c'est une liste de listes.

Avec l'ordre $A, B, C, D$ numérotés $0, 1, 2, 3$ , notre graphe donne :

# ordre des sommets : A=0, B=1, C=2, D=3
M = [
    [0, 1, 1, 0],   # A relie a B et C
    [1, 0, 1, 0],   # B relie a A et C
    [1, 1, 0, 1],   # C relie a A, B et D
    [0, 0, 1, 0],   # D relie a C
]

print(M[0][1])   # 1 : il y a une arete entre A (0) et B (1)
print(M[0][3])   # 0 : pas d'arete entre A (0) et D (3)
print(sum(M[2])) # 3 : le degre de C = somme de sa ligne

🔍 Décryptage ligne par ligne

M = [[0, 1, 1, 0], ...]Une grille de 0 et 1. M[i] est la ligne du sommet

i

; M[i][j] vaut 1 si

i

j

sont reliés. La matrice est symétrique (M[i][j] == M[j][i]) car le graphe est non orienté.

M[0][1]Tester une arête en $O (1)$ . On lit directement la case : y a-t-il une arête entre

A

(0) et

B

(1) ? La valeur 1 dit oui. Aucun parcours, contrairement aux listes d'adjacence.

M[0][3]Absence d'arête. La case vaut 0 : pas d'arête entre

A

D

. Cohérent avec le §2.

sum(M[2])Le degré par somme de ligne. Le degré du sommet

i

est le nombre de 1 sur sa ligne, donc sum(M[i]). Pour

C

(ligne 2) :

1 + 1 + 0 + 1 = 3

. Ce calcul coûte

O (n)

(on lit toute la ligne).

📝 La diagonale. M[i][i] vaut 0 tant qu'il n'y a pas de boucle (une arête d'un sommet vers lui-même). En orienté, la matrice n'est en général pas symétrique : M[i][j] = 1 signale l'arc

(i, j)

, et M[j][i] peut valoir 0.

4. Quelle représentation choisir ?

Les deux représentations décrivent le même graphe, mais n'ont pas les mêmes coûts. Le choix dépend de la densité du graphe (beaucoup d'arêtes, ou peu) et des opérations qu'on veut faire souvent.

Listes d'adjacence contre matrice d'adjacence ( $n$ sommets, $m$ arêtes)
Critère	Listes d'adjacence	Matrice d'adjacence
Mémoire	$O (n + m)$	$O (n^{2})$
Tester une arête $(u, v)$	$O (de g u)$	$O (1)$
Parcourir les voisins de $u$	$O (de g u)$	$O (n)$
Idéale pour…	graphe creux (peu d'arêtes)	graphe dense (beaucoup d'arêtes)

📐 Méthode — choisir sa représentation.

Le graphe est creux ( $m$ petit devant $n^{2}$ , comme un réseau routier) et on parcourt souvent les voisins : listes d'adjacence ( $O (n + m)$ mémoire).
Le graphe est dense ou on teste très souvent « telle arête existe-t-elle ? » : matrice d'adjacence (test en $O (1)$ ).
En cas de doute aux concours, les listes d'adjacence sont le choix par défaut : les vrais graphes sont presque toujours creux.

Terminons par un résultat qui relie degrés et arêtes, déjà croisé au §2 avec la division par 2.

Propriété 4.1 — Lemme des poignées de main ★ À savoir démontrer

Dans un graphe non orienté à $m$ arêtes, la somme des degrés de tous les sommets vaut $s \sum de g (s) = 2 m .$ En particulier, cette somme est toujours paire.

Démonstration

Comptons de deux façons le nombre de couples $(s, e)$ où $s$ est un sommet et $e$ une arête qui touche $s$ (on dit que $s$ est une extrémité de $e$ ).

Premier décompte, par sommet. Pour un sommet $s$ fixé, le nombre d'arêtes qui le touchent est, par définition, son degré $de g (s)$ . En sommant sur tous les sommets, le nombre de couples vaut $s \sum de g (s)$ .

Second décompte, par arête. Une arête ${u, v}$ a exactement deux extrémités, $u$ et $v$ . Elle fournit donc exactement 2 couples. En sommant sur les $m$ arêtes, le nombre de couples vaut $2 m$ .

Les deux décomptes comptent la même chose, donc $s \sum de g (s) = 2 m$ . Comme $2 m$ est pair, la somme des degrés est paire. $■$

💡 Vérification sur le fil rouge. Les degrés sont

2, 2, 3, 1

, de somme

8 = 2 \times 4

: on retrouve bien

2 m

avec

m = 4

arêtes. C'est exactement ce que calcule nb_aretes en divisant la somme des degrés par 2.

🎯 Accompagnement Majorant

Le « double comptage » est une technique de preuve qui revient partout en info comme en maths. Nos mentors alumni X · Centrale · Mines t'entraînent à ce type de raisonnement — celui qui fait la différence sur les questions de cours à l'oral.

Trouver un mentor →

5. Exercices d'application

Fais-les sur papier (dessine le graphe !) avant d'ouvrir le corrigé, puis passe au quiz en bas de fiche.

Exo 1Du dessin à la liste d'adjacenceFacile

Un graphe non orienté a pour sommets $1, 2, 3$ et pour arêtes ${1, 2}$ , ${2, 3}$ , ${1, 3}$ . Donne sa représentation par listes d'adjacence (un dictionnaire Python), puis le degré de chaque sommet.

Voir la correction détaillée

Chaque sommet est relié aux deux autres : c'est un triangle. Chaque arête doit apparaître dans les deux listes concernées.

g = {
    1: [2, 3],
    2: [1, 3],
    3: [1, 2],
}

Degrés : len(g[1]) = len(g[2]) = len(g[3]) = 2. Somme des degrés

= 6 = 2 \times 3

: cohérent, il y a bien 3 arêtes.

Exo 2Compter les voisins communsIntermédiaire

Écris voisins_communs(g, u, v) qui renvoie la liste des sommets voisins à la fois de u et de v (représentation par listes d'adjacence). Teste sur le graphe fil rouge avec u = "A", v = "B".

Voir la correction détaillée

Un sommet x est voisin commun s'il est dans g[u] ET dans g[v].

def voisins_communs(g, u, v):
    communs = []
    for x in g[u]:
        if x in g[v]:
            communs.append(x)
    return communs

print(voisins_communs(g, "A", "B"))   # ['C']

Voisins de A : ['B', 'C'] ; voisins de B : ['A', 'C']. Le seul commun est C → ['C']. (

A

B

forment un triangle avec

C

Exo 3De la matrice à la liste d'adjacenceDifficile

On dispose d'une matrice d'adjacence M (liste de listes $n \times n$ , 0/1) et de la liste noms des sommets dans l'ordre des indices. Écris matrice_vers_listes(M, noms) qui renvoie le dictionnaire de listes d'adjacence correspondant.

Voir la correction détaillée

Pour chaque sommet i, on parcourt sa ligne M[i] ; dès que M[i][j] == 1, le sommet noms[j] est un voisin de noms[i].

def matrice_vers_listes(M, noms):
    n = len(M)
    g = {}
    for i in range(n):
        g[noms[i]] = []
        for j in range(n):
            if M[i][j] == 1:
                g[noms[i]].append(noms[j])
    return g

M = [[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]]
print(matrice_vers_listes(M, ["A","B","C","D"]))
# {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B', 'D'], 'D': ['C']}

On retombe exactement sur le dictionnaire g du §2. Deux boucles imbriquées sur

n

: la conversion coûte

O (n^{2})

— le prix à payer pour lire toute la matrice.

Récap final — Ce qu'il faut absolument retenir

À la veille d'une khôlle ou d'un DS, parcours cette checklist : tu dois pouvoir répondre « oui, sans hésiter » à chaque question.

Sais-tu distinguer graphe orienté (arcs, $(u, v)$ ) et non orienté (arêtes, ${u, v}$ ) ?
Sais-tu définir voisins, degré (et degrés entrant / sortant en orienté), chemin, cycle, connexité ?
Sais-tu représenter un graphe par listes d'adjacence (dictionnaire sommet → voisins) ?
Sais-tu représenter un graphe par matrice d'adjacence et lire un degré comme une somme de ligne ?
Sais-tu que les listes coûtent $O (n + m)$ en mémoire et la matrice $O (n^{2})$ ?
Sais-tu que tester une arête est $O (1)$ en matrice mais $O (de g u)$ en listes ?
Sais-tu pourquoi nb_aretes divise la somme des degrés par 2 ?
Sais-tu énoncer et démontrer le lemme des poignées de main ( $\sum de g = 2 m$ ) ?

À savoir refaire

Lemme des poignées de main — double comptage des couples (sommet, arête incidente) : $\sum_{s} de g (s) = 2 m$ .

Vue d'ensemble

Prérequis

1. Le vocabulaire des graphes

2. Représentation par listes d'adjacence

3. Représentation par matrice d'adjacence

4. Quelle représentation choisir ?

5. Exercices d'application

Récap final — Ce qu'il faut absolument retenir

À savoir refaire

Débloque la fiche complète

Quiz — Graphes

Fiches associées

Recherche par dichotomie

Variables, types et affectations

Conditions et booléens

Boucles for et while

Fonctions : paramètres et valeurs de retour

Listes et chaînes de caractères

Tu veux aller plus loin sur ce chapitre ?