Les Graphs
(Graphes)
Une leçon complète, simplifiée, en français
Définitions • BFS • Bipartiteness • Directed graphs • DAGs
Chapitre 3 — Algorithmique des graphs
D'après les notes de cours de Kevin Wayne (Kleinberg & Tardos)
Table des matières
Chapitre 1
Définitions de base
et applications
Chapitre 2 Graph
connectivity et
graph traversal
(BFS)
Chapitre 3 Tester
si un graph est
bipartite
Chapitre 4
Connectivity dans
les directed graphs
Chapitre 5 DAGs
et topological
ordering
Annexe A Petit
lexique (Français !”
English)
Comment lire cette leçon ?
Chaque chapitre commence par les idées intuitives, puis donne les définitions formelles, des
illustrations dessinées, et enfin les algorithmes. Les termes techniques restent en anglais (node,
edge, BFS, DAG, etc.) car tu les retrouveras tels quels dans tous les livres et les cours
d'informatique.
Chapitre 1 — Définitions de base
1.1 Qu'est-ce qu'un graph ?
Un graph (en français : un graphe) est simplement un ensemble de points reliés entre eux par des
lignes. Les points s'appellent des nodes (ou vertices, sommets) et les lignes s'appellent des edges
(arêtes ou liens).
Imagine une carte des amitiés sur Facebook : chaque personne est un node, et chaque amitié entre
deux personnes est un edge. Imagine une carte routière : chaque ville est un node, chaque route est
un edge. Imagine Internet : chaque ordinateur est un node, chaque câble est un edge. Le graph est
l'outil mathématique qui modélise toutes ces situations en une seule structure.
Notation officielle
On écrit G = (V, E) où V est l'ensemble des nodes (Vertices) et E est l'ensemble des edges. On
note souvent n = |V| (le nombre de nodes) et m = |E| (le nombre de edges). Ces deux nombres
reviendront partout dans l'analyse des algorithmes.
Exemple visuel
1 2 4
3 5
8 6
Un graph G avec V = {1,…,8} et 11 edges. Ici n = 8 et m = 11.
1.2 Pourquoi c'est partout dans la vraie vie ?
Le graph est une des structures les plus puissantes de l'informatique parce que des milliers de
problèmes se ramènent à un problème de graphs. Voici quelques exemples classiques :
• Communication : nodes = téléphones / ordinateurs, edges = câbles ou liens sans-fil.
• Circuit électronique : nodes = portes logiques (gates), registers, processors ; edges = fils.
• Mécanique : nodes = articulations (joints) ; edges = ressorts, poutres, barres.
• Finance : nodes = banques ou monnaies ; edges = transactions.
• Transport : nodes = intersections ou aéroports ; edges = routes, lignes aériennes.
• Internet : nodes = réseaux ; edges = connexions.
• Jeux : nodes = positions sur l'échiquier ; edges = coups légaux.
• Réseaux sociaux : nodes = personnes ; edges = amitiés ou films communs (cf. Kevin Bacon).
• Réseaux de neurones biologiques : nodes = neurones ; edges = synapses.
• Biologie moléculaire : nodes = protéines ; edges = interactions protéine-protéine.
• Chimie : nodes = atomes ; edges = liaisons (bonds).
Étude célèbre : Framingham Heart Study
Christakis et Fowler ont modélisé 2 200 personnes comme un grand graph (amis, familles,
conjoints). Ils ont montré que l'obésité se « propage » sur le graph comme une épidémie. Sans le
langage des graphs, ce résultat aurait été impossible à formuler.
1.3 Undirected vs Directed graphs
Il existe deux grandes familles de graphs : les undirected graphs (graphes non orientés) et les
directed graphs (graphes orientés).
Dans un undirected graph, un edge entre u et v est symétrique : si u est lié à v, alors v est lié à u
(comme une amitié sur Facebook). Dans un directed graph, un edge a un sens : il part de u et arrive
à v (comme un follow sur Twitter, ou un hyperlien d'une page web vers une autre).
u v u v
Undirected edge {u,v} Directed edge (u, v) : de u vers v
1.4 Comment représenter un
graph dans un programme ?
Pour stocker un graph en mémoire, deux structures
classiques : adjacency matrix et adjacency list. Le
choix dépend de la densité du graph (m petit ou m
grand).
Adjacency matrix
On crée une matrice n × n appelée A. La case A[u]
[v] vaut 1 s'il existe un edge entre u et v, sinon 0.
Pour un undirected graph, la matrice est symétrique
(A[u][v] = A[v][u]).
• Espace utilisé : 9‚†ë"’r6†VRVFvRW7B7Fö0ké
deux fois.
• Tester si (u, v) est un edge : 9‚ƒ’–ç7FçFî•.
• Lister tous les edges : 9‚†ë"’–Â`aut tout balayer.
• Bon choix si le graph est dense (m proche de
n²).
1 2 3 4 5 6 7 8
1 0 1 1 0 0 0 0 0
2 1 0 1 1 1 0 0 0
3 1 1 0 0 1 0 1 1
4 0 1 0 0 1 0 0 0
5 0 1 1 1 0 1 0 0
6 0 0 0 0 1 0 0 0
7 0 0 1 0 0 0 0 1
8 0 0 1 0 0 0 1 0
Adjacency matrix du graph précédent (les 1 sont coloriés).
Adjacency list
À chaque node u, on associe une liste contenant tous
ses voisins (neighbors). On parle aussi du degree(u) =
nombre de voisins de u.
• Espace utilisé : 9‚†Ò²â’r&VV6÷WÇW26ö×7B
si le graph est sparse.
• Tester si (u, v) est un edge : O(degree(u)) — il faut
parcourir la liste.
• Lister tous les edges : 9‚†Ò²â’r÷F–ÖÂà
• Choix par défaut dans la majorité des algorithmes
(BFS, DFS, etc.).
1 3 2
2 1 3 4 5
3 2 1 5 7 8
4 2 5
5 2 3 4 6
6 5
7 3 8
8 3 7
Adjacency lists du même graph : chaque node pointe vers ses voisins.
1.5 Vocabulaire essentiel : path, cycle, connected,
tree
Path (chemin)
Un path est une suite de nodes v •, v ‚, …, v – où chaque paire consécutive (vb, vb Š •) est
reliée par un edge. Si tous les nodes du path sont distincts, on dit que le path est
simple.
Connected (connexe)
Un undirected graph est connected si pour toute paire de nodes u, v il existe au moins un path qui
les relie. Sinon, le graph est composé de plusieurs morceaux séparés appelés connected
components (composantes connexes).
Cycle
Un cycle est un path qui revient à son point de départ : v • = v – et k "e 2. Si tous les nodes intermédiaires
sont distincts, le cycle est simple.
1 2
3 5
Un cycle simple C = 1 !’ 2 !’ 4 !’ 5 !’ 3 !’ 1 (en orange).
Tree (arbre)
Un tree est un undirected graph qui est connected et qui ne contient aucun cycle. C'est l'une des
structures les plus importantes de l'informatique : arbres généalogiques, arbres de fichiers, arbres
binaires, arbres syntaxiques, etc.
Théorème (les trois propriétés magiques d'un tree)
Soit G un undirected graph à n nodes. Si deux des trois propriétés suivantes sont vraies, alors la
troisième l'est aussi : (1) G est connected ; (2) G ne contient pas de cycle ; (3) G a exactement n "
1 edges. Autrement dit : un tree à n nodes a TOUJOURS exactement n " 1 edges.
2 3
4 5 6 7
Un rooted tree (arbre enraciné). 1 est la root. 2 est le parent de 4 et 5. 4 et 5 sont les children (enfants) de 2.
Rooted tree (arbre enraciné)
Quand on choisit un node spécial appelé root et qu'on oriente toutes les edges vers le bas, on
obtient un rooted tree. C'est le modèle naturel de toute hiérarchie : système de fichiers, arbre
généalogique, structure des composants d'une interface graphique (GUI), arbres phylogénétiques en
biologie.
Chapitre 2 — BFS et la connectivité
2.1 Les questions de base
Quand on dispose d'un graph, deux questions reviennent sans cesse :
• s-t connectivity : étant donnés deux nodes s et t, existe-t-il un path entre eux ?
• s-t shortest path : si oui, quelle est la longueur du plus court path ?
Ces questions ont des applications partout : Friendster / Facebook (es-tu lié à cette personne ?),
labyrinthes (peut-on sortir ?), Kevin Bacon number (combien de films te séparent de Kevin Bacon ?),
réseaux de communication (combien de sauts entre deux machines ?), GPS, etc.
2.2 BFS — Breadth-First Search
BFS (parcours en largeur) est l'algorithme de base pour répondre à ces questions. L'intuition est très
simple : on part de s, on explore d'abord tous ses voisins immédiats, puis tous les voisins des
voisins, et ainsi de suite, couche par couche (layer by layer).
Image mentale
Imagine que tu jettes un caillou dans une mare au point s. Une onde circulaire se propage. La
couche L € ne contient que s. La couche L • contient les nodes touchés au premier instant. La
couche L ‚ contient les nouveaux nodes touchés à l'instant suivant. Etc.
Algorithme BFS
BFS(s):
L[0] = { s }
i = 0
tant que L[i] n'est pas vide:
L[i+1] = ensemble vide
pour chaque node u dans L[i]:
pour chaque voisin v de u:
si v n'a encore jamais été visité:
ajouter v à L[i+1]
marquer v comme visité
parent[v] = u
i = i + 1
Le théorème fondamental de BFS
Théorème
Pour chaque i, la couche L[i] contient EXACTEMENT tous les nodes situés à distance i de s (où
la distance est le nombre minimum d'edges d'un path). Donc s'il existe un path de s à t, le
numéro de la couche dans laquelle apparaît t est la distance la plus courte entre s et t.
d
h
e
s b
f
i
L € (s) L• L‚ Lƒ
BFS construit les layers L €, L •,
L ‚, … en s'éloignant de s.
Propriété cruciale
du BFS tree
Quand on construit
BFS, on garde aussi un
BFS tree (arbre BFS) en
mémorisant pour
chaque node v son
parent (le node qui l'a
découvert). Ce tree a
une propriété très utile :
Property
Soit T le BFS tree obtenu et soit (x, y) un edge quelconque du graph G. Alors les niveaux (layers)
de x et y diffèrent d'AU PLUS 1. Autrement dit, BFS ne « saute » jamais une couche : il n'existe
jamais d'edge qui relie L ‚ à L … par exemple.
2.3 Complexité (running time) de BFS
La beauté de BFS, c'est sa rapidité. En représentation par adjacency lists, BFS s'exécute en temps
O(m + n) — c'est-à-dire linéaire en la taille du graph. C'est optimal : il faut bien au moins lire toutes
les edges et tous les nodes pour répondre.
Pourquoi O(m + n) et pas O(n²) ?
Quand on traite un node u, on parcourt ses degree(u) edges sortantes. La somme totale de tous
les degree(u) sur tous les nodes vaut exactement 2m (chaque edge est compté deux fois, une
pour chaque extrémité). Donc le total du temps passé sur les edges est 2m. À cela on ajoute
O(n) pour l'initialisation. Total : O(m + n).
2.4 Connected components
Une connected component est un sous-ensemble maximal de nodes tous reliés entre eux. Pour la
trouver à partir de s, il suffit de lancer BFS depuis s et de récupérer tous les nodes visités.
a d
s c
b e
Connected component de s = {s, a, b, c, d, e}. {x, y} forment une autre composante.
2.5 Application : flood fill
Tu connais l'outil « pot de peinture » dans MS Paint ou Photoshop : tu cliques sur une zone, et toute
la zone connexe de la même couleur change de couleur. C'est exactement BFS sur un graph :
• Node = pixel.
• Edge = deux pixels voisins de la même couleur.
• Blob = connected component de pixels.
• Algorithme : BFS depuis le pixel cliqué et on repeint chaque node visité.
!’
Avant (vert) !’ après (bleu) un flood fill sur la zone connexe.
Chapitre 3 — Bipartite graphs
3.1 C'est quoi un graph bipartite ?
Un graph G est dit bipartite si on peut colorier ses nodes en deux couleurs (par exemple bleu et
blanc) de telle sorte que CHAQUE edge ait une extrémité bleue et une extrémité blanche. Aucune
edge ne doit relier deux nodes de la même couleur.
C'est exactement la situation où l'on a deux familles d'objets et où les liens vont uniquement d'une
famille vers l'autre :
• Stable matching : étudiants en médecine (bleu) !” hôpitaux (blanc).
• Scheduling (planification) : machines (bleu) !” tâches/jobs (blanc).
• Recommandation : utilisateurs (bleu) !” films (blanc).
• Affectation : employés (bleu) !” projets (blanc).
a d
b e
c f
Un bipartite graph : tous les edges traversent du côté bleu vers le côté blanc.
3.2 Le seul obstacle : les odd-length cycles
Lemme clé
Si G contient un cycle de longueur impaire (odd-length cycle), alors G n'est PAS bipartite.
Pourquoi ? Parce que le long d'un cycle, les couleurs doivent alterner bleu / blanc / bleu / blanc /
… Si la longueur est impaire, on retombe sur la même couleur que celle de départ, ce qui est
impossible.
1
5 2
4 3
Un 5-cycle (longueur impaire) : impossible de 2-colorier ses nodes !’ pas bipartite.
3.3 L'algorithme : tester avec BFS
Bonne nouvelle : on peut tester si un graph est bipartite en temps O(m + n) en utilisant simplement
BFS. L'idée : on lance BFS depuis n'importe quel node s, ce qui produit des layers L €, L •, L ‚, …. On
colorie ensuite :
• blanc tous les nodes des layers IMPAIRS,
• bleu tous les nodes des layers PAIRS.
Lemme (avec preuve intuitive)
Pendant le BFS, deux situations exclusives sont possibles : (i) AUCUN edge ne relie deux nodes
du même layer !’ la coloration paire/impaire fonctionne, donc G est bipartite. (ii) Il EXISTE un edge
(x, y) dans le même layer L_j !’ on peut alors remonter au plus proche ancêtre commun z et
construire un odd-length cycle, donc G n'est pas bipartite.
Cas (i) : bipartite Cas (ii) : pas bipartite
s a c s a
b d b
À gauche :
aucune edge
dans un même
layer. À droite :
edge rouge
entre a et b
dans le même
layer !Ò odd-length
cycle s-a-b-s.
3.4 Théorème final
Corollaire (la caractérisation parfaite)
Un graph G est bipartite SI ET SEULEMENT SI il ne contient aucun cycle de longueur impaire.
C'est tout. Pas plus compliqué que ça.
Chapitre 4 — Directed graphs
4.1 Quand les edges ont un sens
Un directed graph (souvent abrégé digraph) est un graph où chaque edge a une direction : on note
(u, v) pour dire que l'edge part de u et arrive en v. C'est différent de (v, u). On dit que l'edge leaves u
(sort de u) et enters v (entre dans v).
A D
Un petit directed graph : chaque edge porte une flèche.
4.2 Exemples (le sens est crucial)
• World Wide Web : nodes = pages web ; edges = hyperliens (!’). PageRank de Google exploite
massivement la structure de ce digraph.
• Réseau routier : nodes = intersections ; edges = rues (parfois en sens unique).
• Web alimentaire (food web) : nodes = espèces ; edges = de la proie vers le prédateur.
• WordNet : nodes = synsets (groupes de synonymes) ; edges = hypernymes (chien !’ animal).
• Scheduling : nodes = tâches ; edges = précédences (A doit finir avant B).
• Transactions financières : nodes = banques ; edges = paiements.
• Téléphonie : nodes = personnes ; edges = appels passés.
• Maladies infectieuses : nodes = personnes ; edges = transmissions.
• Citations scientifiques : nodes = articles ; edges = citations.
• Inheritance OOP : nodes = classes ; edges = « hérite de ».
• Control flow : nodes = blocs de code ; edges = jumps.
4.3 Reachability et BFS sur un digraph
Le problème de directed reachability est : étant donné un node s, trouver tous les nodes accessibles
depuis s en suivant le sens des edges. Bonne nouvelle : BFS s'adapte SANS rien changer aux
digraphs. On suit simplement les edges sortantes de chaque node.
Application classique : un web crawler. On part d'une page s, on visite tous les liens sortants, puis
tous les liens des pages atteintes, etc. C'est exactement BFS sur le web graph.
4.4 Strong connectivity (forte connexité)
Pour les undirected graphs, « connected » suffisait. Pour les digraphs, on doit être plus précis car le
sens compte.
Définitions
Deux nodes u et v sont dits mutually reachable s'il existe un path orienté de u vers v ET un path
orienté de v vers u. Un digraph est strongly connected si CHAQUE paire de nodes est mutually
reachable.
Un digraph strongly connected : depuis chaque node on peut atteindre tous les autres en suivant les flèches.
4.5 Algorithme : tester la strong connectivity
Lemme utile
Soit s un node quelconque. G est strongly connected SI ET SEULEMENT SI : (a) tous les nodes
sont reachable depuis s, ET (b) s est reachable depuis tous les nodes. La preuve est immédiate
par concaténation de paths.
Cela donne un algorithme simple en O(m + n) :
IsStronglyConnected(G):
s = n'importe quel node de G
marquer = BFS(s, G) # depuis s sur G
si tous les nodes pas atteints: retourner faux
G_reverse = G avec toutes les flèches inversées
marquer = BFS(s, G_reverse) # depuis s sur G inversé
si tous les nodes pas atteints: retourner faux
retourner vrai
4.6 Strong components
Si un digraph n'est pas strongly connected, on peut quand même le découper en strong
components : chaque strong component est un sous-ensemble maximal de nodes tous mutually
reachable entre eux.
Théorème de Tarjan (1972)
On peut trouver TOUS les strong components d'un digraph en temps O(m + n) — c'est-à-dire en
un seul passage. L'algorithme classique de Tarjan utilise DFS (Depth-First Search) et une pile.
C'est l'un des algorithmes les plus élégants de l'algorithmique classique.
d
g
c
h
f
Un digraph découpé en 3 strong components (rouge, vert, bleu). Les edges entre components ne forment jamais de cycle.
Chapitre 5 — DAGs et topological
ordering
5.1 Qu'est-ce qu'un DAG ?
Définition
Un DAG = Directed Acyclic Graph = digraph qui ne contient AUCUN directed cycle. Autrement
dit, on ne peut jamais partir d'un node, suivre les flèches, et revenir au point de départ.
Les DAGs sont partout en informatique car ils modélisent toutes les situations de dépendance : «
pour faire X, je dois d'abord faire Y ». S'il y avait un cycle, on aurait une contradiction (X dépend de Y
qui dépend de X).
v2 v3
v1 v4 v7
v6 v5
Un DAG : aucune flèche ne « revient en arrière ».
5.2 Topological ordering
Définition
Un topological order d'un digraph G = (V, E) est une numérotation (un alignement) des nodes v •,
v ‚, …, v ™ telle que pour CHAQUE edge (vb, v,|) on ait i < j. Visuellement : si on aligne tous les nodes
sur une ligne dans cet ordre, alors TOUTES les flèches pointent vers la droite.
v1 v2 v3 v4 v5 v6 v7
U
n
to
p
ol
o
gi
c
al
o
rd
er
:
to
u
sl
e
s
n
o
d
e
s
s
o
nt
a
lig
n
é
s
et
t
o
ut
e
sl
e
s
fl
è
c
h
e
s
vo
nt
v
er
sl
a
dr
oi
te
.
5.3 Applications concrètes
• Course prerequisites : pour s'inscrire à Algo II, il faut Algo I, qui requiert Maths discrètes. On veut
un ordre dans lequel suivre les cours.
• Compilation : un module M2 qui importe M1 doit être compilé après M1.
• Pipeline de calcul : la sortie de la tâche T1 alimente l'entrée de T2 !’ T1 d'abord.
• Gestion de projet : ordonnancer des tâches avec des contraintes de précédence.
• Make / npm scripts / build systems : ordonner les recompilations.
• Tableurs Excel : ordonner le recalcul des cellules en suivant les dépendances de formules.
5.4 Les deux théorèmes fondamentaux
Théorème 1 : si on a un topological order, alors c'est un DAG
Preuve par contradiction : suppose qu'il existe un cycle C. Soit vb le node du cycle avec le PLUS
PETIT indice. Le node juste avant vb dans le cycle, appelons-le v,|, donne un edge (v,|, vb). Mais notre
topological order impose j < i (car (v,|, vb) est un edge), alors qu'on a choisi vb comme le PLUS PETIT
indice donc i "d j. Contradiction. Donc pas de cycle.
Théorème 2 : tout DAG admet un topological order
C'est le sens inverse, et c'est lui qui donne l'algorithme. La preuve repose sur deux lemmes :
Lemme A : tout DAG a au moins un node sans edge entrant
Sinon, on pourrait remonter sans fin en arrière le long des edges entrantes. Comme le nombre
de nodes est fini, on revisiterait forcément un node — ce qui formerait un cycle, contradiction
avec le fait que G est un DAG.
Lemme B (récurrence)
On choisit ce node v sans edge entrante, on le place EN PREMIER dans le topological order, on
l'enlève du graph, on recommence. À chaque étape, le sous-graph reste un DAG (on ne crée
jamais de cycle en supprimant un node). Au bout de n étapes, on a un topological order valide.
5.5 L'algorithme efficace
Le lemme A donne un algorithme naïf : trouver un node sans edge entrant, l'enlever, répéter. Pour
atteindre la complexité O(m + n), on maintient deux structures :
• count[w] = nombre actuel de edges entrantes vers w (on l'appelle aussi in-degree).
• S = ensemble des nodes dont count vaut déjà 0 (candidats à placer ensuite).
TopologicalSort(G):
pour chaque node w: count[w] = nombre d'edges entrantes
S = { tous les w avec count[w] == 0 }
ordre = liste vide
tant que S n'est pas vide:
prendre un v dans S, le retirer de S
ajouter v à la fin de ordre
pour chaque edge (v, w) sortant de v:
count[w] = count[w] - 1
si count[w] == 0:
ajouter w à S
retourner ordre
Complexité
Initialisation = O(m + n) (on lit toutes les edges une fois). Chaque edge n'est traitée qu'une seule
fois pendant la boucle. Chaque node n'entre et ne sort de S qu'une fois. Total : O(m + n). C'est
optimal.
5.6 Récapitulatif visuel : qu'est-ce qu'on a construit ?
v1 v2 v3
v6 v7
v5 v4
Un DAG. Un topological order valide est : v6, v1, v2, v3, v5, v4, v7.
Annexe A — Petit lexique
Comme tous les manuels et toutes les bibliothèques de code utilisent le vocabulaire anglais, voici les
correspondances des termes que tu retrouveras partout.
graph graphe Structure (V, E) avec nodes et edges.
node / vertex sommet / nœud Un point du graph.
edge / arc arête / arc Un lien entre deux nodes.
undirected graph graphe non orienté Edges sans flèche.
directed graph / digraph graphe orienté Edges avec flèche.
adjacency matrix matrice d'adjacence Tableau n×n.
adjacency list liste d'adjacence Liste des voisins par node.
degree(u) degré de u Nombre de voisins de u.
in-degree / out-degree degré entrant / sortant Pour digraphs.
path chemin Suite de nodes reliés par des edges.
simple path chemin simple Path sans node répété.
cycle cycle Path qui revient au point de départ.
connected connexe Tout le monde se rejoint.
connected component composante connexe Morceau connexe maximal.
tree arbre Connexe + sans cycle.
rooted tree arbre enraciné Arbre avec une root.
root / parent / child racine / parent / enfant Vocabulaire de tree.
BFS parcours en largeur Breadth-First Search.
DFS parcours en profondeur Depth-First Search.
layer couche Niveau dans BFS.
bipartite biparti 2-coloriable.
odd-length cycle cycle de longueur impaire Le seul obstacle à bipartite.
reachable accessible Atteignable via un path.
mutually reachable mutuellement accessible Path dans les deux sens.
strongly connected fortement connexe Tous mutually reachable.
strong component composante fortement Maximal mutually reachable.
connexe
DAG graphe orienté sans cycle Directed Acyclic Graph.
topological order tri topologique Linéarisation respectant les flèches.
precedence constraint contrainte de précédence X avant Y.
running time / complexity temps d'exécution / O(m+n), O(n²)…
complexité
À retenir
Trois algorithmes fondamentaux à connaître par cœur : (1) BFS pour tout ce qui est plus court
chemin et connectivité, (2) BFS modifié pour tester la bipartiteness, (3) tri topologique pour les
DAGs. Tous tournent en O(m + n) — autant dire que c'est gratuit.