Recherche opérationnelle & graphes : 18 exercices corrigés

Degrés & lemme des poignées

CalculDifficulté 3/5

Soit le graphe non orienté de sommets $\{0,1,2,3,4\}$ et d'arêtes $01,02,12,23,34$ . Écrire sa matrice d'adjacence, donner les degrés, et vérifier le lemme des poignées.

Indices (3)

La matrice d'adjacence $A$ est symétrique : $A_{ij}=1$ si $i$ et $j$ sont reliés.

Le degré d'un sommet est la somme de sa ligne dans $A$ .

Lemme des poignées : $\sum_v\deg(v)=2\lvert E\rvert$ .

Correction détaillée

L'idée directrice

Un graphe est la structure de base de tout ce chapitre : des sommets reliés par des arêtes. Pour le manipuler par le calcul, il faut le représenter, et la représentation la plus directe est la matrice d'adjacence.

A_{ij}=\begin{cases}1&\text{s'il y a une arête entre }i\text{ et }j\\ 0&\text{sinon}\end{cases}

Le degré d'un sommet est son nombre de voisins. Et le lemme des poignées de main relie les deux : il dit que la somme des degrés vaut le double du nombre d'arêtes.

Étape 1 — la matrice d'adjacence

Sommets $\{0,1,2,3,4\}$ , arêtes $01$ , $02$ , $12$ , $23$ , $34$ .

Le graphe est non orienté, donc chaque arête $ij$ produit deux $1$ : en $(i,j)$ et en $(j,i)$ . La matrice est donc symétrique.

A=\begin{pmatrix}0&1&1&0&0\\1&0&1&0&0\\1&1&0&1&0\\0&0&1&0&1\\0&0&0&1&0\end{pmatrix}

Contrôles de forme, à faire systématiquement :

la matrice est symétrique ✓ (graphe non orienté) ;
la diagonale est nulle ✓ (aucune boucle : pas d'arête d'un sommet vers lui-même) ;
il y a $2\times5=10$ coefficients égaux à $1$ ✓ (deux par arête).

Étape 2 — les degrés

Le degré d'un sommet se lit sur sa ligne : c'est la somme des coefficients.

sommet	voisins	degré
$0$	$1,2$	$2$
$1$	$0,2$	$2$
$2$	$0,1,3$	$\mathbf{3}$
$3$	$2,4$	$2$
$4$	$3$	$\mathbf{1}$

Le sommet $2$ est le plus connecté (c'est un « carrefour »), le sommet $4$ est une feuille — il n'a qu'un seul voisin.

Étape 3 — le lemme des poignées de main

$\sum_{v}\deg(v)=2\,\lvert E\rvert$

Vérification :

2+2+3+2+1=\mathbf{10},\qquad 2\times5=\mathbf{10}.\qquad\checkmark

Pourquoi c'est vrai — et l'argument est joli : chaque arête a deux extrémités, donc elle contribue $1$ au degré de chacune, soit $2$ au total. En sommant sur toutes les arêtes, on compte donc chaque arête deux fois.

Le nom vient de l'interprétation : dans une réunion, la somme des nombres de mains serrées par chaque personne vaut le double du nombre de poignées de main échangées.

La conséquence à connaître : le nombre de sommets de degré IMPAIR est PAIR

Séparons la somme selon la parité des degrés :

\underbrace{\sum_{\deg\ \text{pair}}\deg(v)}_{\text{pair}}+\sum_{\deg\ \text{impair}}\deg(v)=\underbrace{2\lvert E\rvert}_{\text{pair}}.

La seconde somme est donc paire. Or c'est une somme de nombres impairs : elle n'est paire que s'il y en a un nombre pair.

\boxed{\text{Il y a toujours un nombre PAIR de sommets de degré impair.}}

Vérification ici : les degrés sont $2,2,3,2,1$ — deux impairs ( $3$ et $1$ ), donc un nombre pair ✓

Ce corollaire est loin d'être anecdotique : c'est lui qui décide de l'existence d'un parcours eulérien (exercice A4).

Contrôle par la matrice

On peut aussi lire les degrés matriciellement : le vecteur des degrés est $A\vec{\mathbf 1}$ , où $\vec{\mathbf 1}=(1,1,1,1,1)^{\mathsf T}$ .

A\vec{\mathbf 1}=\begin{pmatrix}0+1+1+0+0\\1+0+1+0+0\\1+1+0+1+0\\0+0+1+0+1\\0+0+0+1+0\end{pmatrix}=\begin{pmatrix}2\\2\\3\\2\\1\end{pmatrix}\ \checkmark

Et le nombre d'arêtes vaut $\tfrac12\vec{\mathbf 1}^{\mathsf T}A\vec{\mathbf 1}=\tfrac{10}{2}=5$ ✓

Autre propriété utile : le coefficient $(i,j)$ de $A^k$ compte le nombre de chemins de longueur exactement $k$ entre $i$ et $j$ . C'est ce qui fait de la matrice d'adjacence un outil de calcul, et pas seulement de rangement.

Réponse : la matrice est symétrique à diagonale nulle avec dix $1$ ; les degrés sont $(2,2,3,2,1)$ , de somme $10=2\times5$ — le lemme des poignées de main est vérifié.

Réponse. Degrés

(2,2,3,2,1)

,

\sum=10=2\lvert E\rvert

avec

\lvert E\rvert=5

. (Recoupement : somme des coefficients de

A

=10=2\lvert E\rvert

✓)

Faire cet exercice dans l'app →

Parcours BFS et DFS

CalculDifficulté 3/5

Sur le graphe précédent (arêtes $01,02,12,23,34$ ), donner l'ordre de visite par BFS puis par DFS depuis le sommet $0$ (voisins explorés par ordre croissant).

Indices (3)

BFS : file d'attente, on visite tous les voisins avant d'aller plus loin.

DFS : pile (ou récursion), on plonge le plus loin possible.

Voisins de $0$ : $\{1,2\}$ ; de $2$ : $\{0,1,3\}$ ; etc.

Correction détaillée

Les deux parcours

Explorer un graphe, c'est visiter tous ses sommets à partir d'un point de départ. Deux stratégies, qui diffèrent par une seule structure de données :

	structure	comportement
BFS (parcours en largeur)	FILE — premier entré, premier sorti	explore par couches : tous les voisins, puis les voisins des voisins
DFS (parcours en profondeur)	PILE — dernier entré, premier sorti	s'enfonce aussi loin que possible, puis revient en arrière

Le graphe : sommets $\{0,1,2,3,4\}$ , arêtes $01$ , $02$ , $12$ , $23$ , $34$ , avec les listes de voisins triées par ordre croissant :

0:\{1,2\},\quad 1:\{0,2\},\quad 2:\{0,1,3\},\quad 3:\{2,4\},\quad 4:\{3\}.

BFS, pas à pas

On part de $0$ . La file contient les sommets découverts mais pas encore traités.

étape	on traite	on découvre	file après	visités
1	$0$	$1$ , $2$	$[1,2]$	$0$
2	$1$	rien ( $0$ vu, $2$ déjà découvert)	$[2]$	$0,1$
3	$2$	$3$	$[3]$	$0,1,2$
4	$3$	$4$	$[4]$	$0,1,2,3$
5	$4$	rien	$[\,]$	$0,1,2,3,4$

\boxed{\text{BFS} : 0,\ 1,\ 2,\ 3,\ 4}

Le point à ne pas rater, étape 2 : on ne rajoute pas $2$ une seconde fois. Un sommet est marqué dès qu'il est découvert, pas quand il est traité — sinon il entrerait plusieurs fois dans la file.

DFS, pas à pas

On part de $0$ et on s'enfonce, en prenant toujours le plus petit voisin non visité.

on est en	voisins non visités	on va en
$0$	$1,2$	$\to1$
$1$	$2$ ( $0$ est vu)	$\to2$
$2$	$3$ ( $0,1$ vus)	$\to3$
$3$	$4$ ( $2$ vu)	$\to4$
$4$	aucun	retour arrière

\boxed{\text{DFS} : 0,\ 1,\ 2,\ 3,\ 4}

⚠️ Les deux ordres sont IDENTIQUES — ce qui ne veut pas dire que les parcours le sont

C'est le fait le plus instructif de l'exercice, et il faut savoir l'expliquer.

Sur ce graphe, BFS et DFS visitent les sommets dans le même ordre. Ce n'est pas une erreur, c'est une coïncidence de structure : le graphe est presque un chemin, il n'offre pas de « choix » qui ferait diverger les deux stratégies.

Mais les ARBRES d'exploration diffèrent, et c'est là qu'on voit la différence :

sommet	père en BFS	père en DFS
$1$	$0$	$0$
$\mathbf{2}$	$\mathbf{0}$	$\mathbf{1}$
$3$	$2$	$2$
$4$	$3$	$3$

Le sommet $2$ est atteint depuis $0$ en BFS, depuis $1$ en DFS. Conséquence sur les profondeurs :

sommet	profondeur BFS	profondeur DFS
$0$	$0$	$0$
$1$	$1$	$1$
$2$	$\mathbf{1}$	$\mathbf{2}$
$3$	$2$	$3$
$4$	$3$	$4$

Les profondeurs BFS sont les vraies distances en nombre d'arêtes ; les profondeurs DFS ne le sont pas.

Ce que chacun sert à faire

C'est la seule chose à retenir vraiment, parce qu'elle décide du choix en pratique.

BFS	DFS
plus courts chemins en nombre d'arêtes	détection de cycles
niveaux / couches (réseaux sociaux : « à 2 amis de distance »)	tri topologique (exercice A6)
propagation, diffusion	composantes fortement connexes
il visite $2$ à distance $1$ , ce qui est exact	il le voit à profondeur $2$ , ce qui n'est pas la distance

La propriété fondamentale du BFS : il découvre les sommets par distance croissante à la source. C'est ce qui en fait l'algorithme des plus courts chemins quand toutes les arêtes ont le même poids — et c'est exactement ce que généralise Dijkstra (exercice B1) pour des poids quelconques.

Complexité : les deux sont en $O(\lvert V\rvert+\lvert E\rvert)$ — chaque sommet est traité une fois, chaque arête examinée deux fois (une par extrémité).

Réponse : BFS et DFS donnent tous deux $0,1,2,3,4$ ; mais leurs arbres d'exploration diffèrent — en BFS le sommet $2$ a pour père $0$ (profondeur $1$ ), en DFS il a pour père $1$ (profondeur $2$ ).

Réponse. BFS

=

DFS

=(0,1,2,3,4)

. (Recoupement scipy breadth_first_order/depth_first_order :

[0,1,2,3,4]

pour les deux ✓)

Faire cet exercice dans l'app →

Composantes connexes

CalculDifficulté 3/5

Le graphe non orienté de sommets $\{0,1,2,3,4\}$ a pour arêtes $01,02,12,34$ . Combien a-t-il de composantes connexes ? Les décrire.

Indices (3)

Une composante connexe est un groupe maximal de sommets reliés entre eux.

Lancer un parcours depuis un sommet : il découvre toute sa composante.

Recommencer depuis un sommet non encore visité.

Correction détaillée

L'idée directrice

Une composante connexe est un « morceau » du graphe : un ensemble maximal de sommets reliés entre eux par des chemins. Deux sommets de composantes différentes ne peuvent jamais être joints.

La méthode est mécanique : on lance un parcours (BFS ou DFS, exercice A2) depuis un sommet non encore visité, ce qui découvre toute sa composante ; puis on recommence depuis un sommet resté non visité, et ainsi de suite jusqu'à épuisement.

Étape 1 — le graphe

Sommets $\{0,1,2,3,4\}$ , arêtes $01$ , $02$ , $12$ , $34$ .

Listes de voisins :

0:\{1,2\},\qquad 1:\{0,2\},\qquad 2:\{0,1\},\qquad 3:\{4\},\qquad 4:\{3\}.

⚠️ Comparer avec l'exercice A1 : le graphe est le même, à une arête près — l'arête $23$ a disparu. C'était précisément le pont entre les deux moitiés.

Étape 2 — dérouler l'algorithme

Premier parcours, depuis $0$ (le plus petit sommet non visité) :

on traite	on découvre
$0$	$1$ , $2$
$1$	rien de neuf
$2$	rien de neuf

Composante trouvée : $\{0,1,2\}$ . Le parcours s'arrête — il ne peut pas sortir.

Deuxième parcours, depuis $3$ (plus petit sommet non encore visité) :

on traite	on découvre
$3$	$4$
$4$	rien de neuf

Composante trouvée : $\{3,4\}$ .

Tous les sommets sont visités, l'algorithme s'arrête.

\boxed{2\text{ composantes connexes} : \{0,1,2\}\ \text{et}\ \{3,4\}}

Décrire les composantes

composante	sommets	arêtes	structure
$C_1$	$\{0,1,2\}$	$01$ , $02$ , $12$	triangle $K_3$ — complet
$C_2$	$\{3,4\}$	$34$	arête simple $K_2$

$C_1$ est un graphe complet : ses trois sommets sont deux à deux adjacents. $C_2$ est le plus petit graphe connexe non trivial.

Contrôles :

$3+2=5$ sommets ✓ — les composantes partitionnent l'ensemble des sommets ;
$3+1=4$ arêtes ✓ — toute arête est à l'intérieur d'une composante, jamais entre deux ;
il n'existe aucun chemin de $0$ à $3$ : c'est ce qui définit deux composantes distinctes.

Les bornes à connaître

Le nombre $c$ de composantes est encadré par des propriétés simples du graphe.

Un graphe à $n$ sommets et $m$ arêtes vérifie $c\ge n-m$ . Ici $5-4=1$ , et l'on a $c=2\ge1$ ✓ (chaque arête ne peut fusionner que deux composantes au plus, donc en partant de $n$ composantes isolées, $m$ arêtes en suppriment au plus $m$ .)

Deux conséquences immédiates :

affirmation	vraie ?
un graphe connexe ( $c=1$ ) a au moins $n-1$ arêtes	oui
un graphe à $n-1$ arêtes est connexe	non — c'est notre exemple ! $5$ sommets, $4$ arêtes, et pourtant $2$ composantes

Notre graphe est le contre-exemple : il a bien $n-1=4$ arêtes, mais une est « gaspillée » dans le triangle (qui n'a besoin que de $2$ arêtes pour être connexe) au lieu de servir de pont.

\text{connexe}\ \Longrightarrow\ m\ge n-1,\qquad\text{mais la réciproque est FAUSSE.}

Le cas d'égalité $m=n-1$ avec connexité caractérise les arbres — c'est l'objet de l'exercice E3.

Ce que ça sert à faire

La connexité n'est pas une curiosité théorique : c'est souvent la première question à poser sur un réseau.

domaine	ce que dit une composante
réseau informatique	des machines qui ne peuvent pas communiquer
réseau social	des groupes sans aucune relation commune
routier	des zones inaccessibles l'une depuis l'autre
résolution de systèmes	des blocs indépendants, traitables séparément

Et pour tous les algorithmes du chapitre, la question est préalable : chercher un plus court chemin de $0$ à $3$ (exercice B1) n'a pas de sens ici, il n'y en a aucun. Un algorithme de plus court chemin rendra $+\infty$ — ce qui est la bonne réponse, mais il faut savoir la lire.

Complexité : un seul parcours global, donc $O(n+m)$ — on ne visite chaque sommet et chaque arête qu'une fois, quel que soit le nombre de composantes.

Réponse : $2$ composantes connexes — $\{0,1,2\}$ , qui est un triangle, et $\{3,4\}$ , qui est une simple arête ; aucun chemin ne relie les deux.

Réponse.

2

composantes :

\{0,1,2\}

et

\{3,4\}

. (Recoupement scipy connected_components :

2

composantes, labels

[0,0,0,1,1]

✓)

Faire cet exercice dans l'app →

Ponts de Königsberg (Euler)

DémonstrationDifficulté 3/5

Le multigraphe des ponts de Königsberg a $4$ sommets de degrés $3,3,3,5$ . Peut-on faire une promenade empruntant chaque pont une seule fois ? Comparer avec un cycle $C_4$ .

Indices (3)

Critère d'Euler : un chemin eulérien existe ssi le graphe connexe a $0$ ou $2$ sommets de degré impair.

Compter les sommets de degré impair de Königsberg.

Un circuit fermé exige $0$ sommet impair.

Correction détaillée

Le problème historique

Königsberg, $1736$ : quatre quartiers reliés par sept ponts. Les habitants cherchaient une promenade empruntant chaque pont une fois et une seule. Euler a montré que c'était impossible — et sa démonstration a fondé la théorie des graphes.

Le point remarquable est que la réponse ne demande aucune recherche exhaustive : elle se lit sur les degrés, en une ligne.

Le théorème d'Euler

Pour un graphe connexe :

condition sur les degrés	ce qui existe
tous pairs	un cycle eulérien (on revient au point de départ)
exactement 2 impairs	un chemin eulérien (départ et arrivée = les deux sommets impairs)
plus de 2 impairs	rien — ni cycle, ni chemin

Rappel de l'exercice A1 : le nombre de sommets de degré impair est toujours pair. Les seuls cas possibles sont donc $0$ , $2$ , $4$ , $6$ … impairs.

Pourquoi la parité décide

L'argument est d'une simplicité totale, et il vaut mieux le comprendre que le retenir.

Considérons un sommet intermédiaire du parcours — un sommet qui n'est ni le départ ni l'arrivée. Chaque fois qu'on y entre par un pont, il faut en ressortir par un autre. Les ponts de ce sommet se regroupent donc par paires : son degré est nécessairement pair.

Restent le départ et l'arrivée. Au départ, on sort une fois de plus qu'on n'entre ; à l'arrivée, l'inverse. Ces deux sommets-là peuvent donc être de degré impair.

\boxed{\text{Au plus DEUX sommets peuvent être de degré impair, et ce sont les extrémités.}}

Si l'on veut un cycle (départ = arrivée), ce sommet-là redevient intermédiaire : tous les degrés doivent être pairs.

Application à Königsberg

Degrés : $3$ , $3$ , $3$ , $5$ .

\text{nombre de sommets de degré IMPAIR}=\mathbf{4}.

4>2\qquad\Longrightarrow\qquad \boxed{\text{IMPOSSIBLE — ni cycle ni chemin eulérien.}}

Contrôle par le lemme des poignées de main (exercice A1) : $3+3+3+5=14=2\times7$ , il y a donc bien sept ponts ✓ Et $4$ est bien un nombre pair de sommets impairs, comme le veut le corollaire ✓

La réponse est donc NON, et Euler l'a établie sans essayer un seul itinéraire — c'est ce qui fait la force de l'argument.

Comparaison avec le cycle $C_4$

Le cycle à quatre sommets $C_4$ : arêtes $01$ , $12$ , $23$ , $30$ .

sommet	voisins	degré
$0$	$1,3$	$2$
$1$	$0,2$	$2$
$2$	$1,3$	$2$
$3$	$2,0$	$2$

\text{nombre de degrés impairs}=\mathbf{0}\qquad\Longrightarrow\qquad \textbf{cycle eulérien}.

Et il est évident : le parcours $0\to1\to2\to3\to0$ emprunte les quatre arêtes, une fois chacune, et revient au départ ✓

Contrôle : $2+2+2+2=8=2\times4$ ✓

Le contraste est net : les deux graphes sont connexes, les deux ont un nombre pair de sommets impairs — mais l'un en a $4$ et l'autre $0$ . C'est ce seul décompte qui décide.

Un cas intermédiaire, pour compléter

Reprenons le graphe de l'exercice A1 (arêtes $01$ , $02$ , $12$ , $23$ , $34$ ), de degrés $2,2,3,2,1$ .

\text{impairs} : \text{les sommets }2\text{ et }4\ \Longrightarrow\ \mathbf{2}\ \text{impairs}.

Il existe donc un chemin eulérien, d'extrémités $2$ et $4$ . Vérifions en l'exhibant :

2\to0\to1\to2\to3\to4.

Arêtes empruntées : $20$ , $01$ , $12$ , $23$ , $34$ — les cinq, chacune une fois ✓ Et l'on part bien de $2$ pour arriver en $4$ , les deux sommets impairs ✓

⚠️ On ne peut pas revenir au départ : il n'y a pas de cycle eulérien, seulement un chemin.

⚠️ Ne pas confondre avec le circuit hamiltonien, qui passe par chaque SOMMET une fois — celui-là n'a aucun critère simple et est NP-difficile (exercice D6). Euler pour les arêtes : facile. Hamilton pour les sommets : difficile. La différence entre les deux problèmes est l'une des plus frappantes du chapitre.

Réponse : NON pour Königsberg — ses quatre sommets de degré impair ( $3,3,3,5$ ) interdisent tout parcours eulérien ; alors que $C_4$ , dont les quatre degrés valent $2$ , admet le cycle eulérien $0\to1\to2\to3\to0$ .

Réponse. Impossible à Königsberg (

4

sommets de degré impair

>2

) ;

C_4

admet un circuit eulérien (

0

impair). (Recoupement : critère d'Euler vérifié ✓)

Faire cet exercice dans l'app →

Graphe biparti & cycle impair

DémonstrationDifficulté 3/5

Montrer que le cycle $C_4$ est biparti (donc $2$ -coloriable) mais que le triangle $C_3$ ne l'est pas.

Indices (3)

Biparti $\iff$ $2$ -coloriable $\iff$ aucun cycle de longueur impaire.

Tenter une $2$ -coloration en alternant les couleurs le long du cycle.

Sur un cycle impair, l'alternance se contredit au bouclage.

Correction détaillée

La notion

Un graphe est biparti si l'on peut partager ses sommets en deux groupes tels que toute arête relie un groupe à l'autre — jamais deux sommets du même groupe.

C'est exactement une coloration à 2 couleurs : on peint un groupe en rouge, l'autre en bleu, et aucune arête ne joint deux sommets de même couleur.

\text{biparti}\quad\Longleftrightarrow\quad 2\text{-coloriable}\quad\Longleftrightarrow\quad \chi\le2.

$C_4$ est biparti

Le cycle $C_4$ : sommets $\{0,1,2,3\}$ , arêtes $01$ , $12$ , $23$ , $30$ .

La partition : $\ X=\{0,2\}$ et $Y=\{1,3\}$ .

Vérifions chaque arête — c'est le seul contrôle qui vaille :

arête	de	vers	traverse ?
$01$	$0\in X$	$1\in Y$	✓
$12$	$1\in Y$	$2\in X$	✓
$23$	$2\in X$	$3\in Y$	✓
$30$	$3\in Y$	$0\in X$	✓

Les quatre arêtes traversent $\Longrightarrow$ $C_4$ est biparti, donc $2$ -coloriable.

Contrôle de complétude : $X$ et $Y$ sont disjoints et leur réunion est l'ensemble des sommets ✓ Et aucune arête n'est interne : il n'y a ni $02$ ni $13$ dans la liste ✓

$C_3$ ne l'est PAS

Le triangle $C_3$ : sommets $\{0,1,2\}$ , arêtes $01$ , $12$ , $20$ .

Démonstration par l'absurde. Supposons une partition en deux groupes.

$0$ est dans un groupe, disons $X$ ;
l'arête $01$ force $1$ dans l'autre groupe, $Y$ ;
l'arête $12$ force $2$ dans le groupe de $0$ , donc $X$ ;
mais alors l'arête $20$ relie $2\in X$ à $0\in X$ : deux sommets du même groupe.

Contradiction $\Longrightarrow$ $C_3$ n'est pas biparti, et $\chi(C_3)=3$ .

C'est aussi ce qu'on voit en coloriant : $0$ rouge, $1$ bleu, $2$ doit différer des deux — il faut une troisième couleur.

Le critère général — c'est le résultat à retenir

Théorème. Un graphe est biparti si et seulement si il ne contient aucun cycle de longueur impaire.

Pourquoi. En parcourant un cycle, la couleur alterne à chaque arête : rouge, bleu, rouge, bleu… Après $k$ arêtes on a la couleur de départ si et seulement si $k$ est pair. Un cycle impair ramènerait donc au point de départ avec la mauvaise couleur — impossible.

graphe	cycles	biparti ?	$\chi$
$C_3$	longueur $\mathbf{3}$ , impaire	non	$3$
$C_4$	longueur $4$ , paire	oui	$2$
$C_5$	longueur $\mathbf{5}$ , impaire	non	$3$
$C_6$	longueur $6$ , paire	oui	$2$
arbre (au moins une arête)	aucun cycle	toujours oui	$2$

Règle générale des cycles : $\chi(C_n)=2$ si $n$ est pair, $3$ si $n$ est impair. On la retrouvera à l'exercice D4.

Les arbres sont bipartis par vacuité — sans cycle, il n'y a pas de cycle impair. On les colorie par la parité de la profondeur.

Comment le TESTER en pratique

L'algorithme est un simple BFS (exercice A2) qui colorie au passage :

colorier le sommet de départ en rouge ;
à chaque découverte, colorier le nouveau sommet de la couleur opposée à son père ;
si l'on rencontre une arête entre deux sommets déjà coloriés de la même couleur : le graphe n'est pas biparti, et cette arête ferme un cycle impair.

Sur $C_3$ : $0$ rouge, $1$ bleu (via $01$ ), $2$ rouge (via $12$ ). Puis l'arête $20$ relie deux sommets rouges $\Longrightarrow$ détection ✓

Sur $C_4$ : $0$ rouge, $1$ bleu, $2$ rouge, $3$ bleu. L'arête $30$ relie bleu et rouge $\Longrightarrow$ aucun conflit ✓

Coût : $O(n+m)$ , celui d'un parcours — c'est-à-dire très peu.

Ce que ça sert à faire

La bipartition n'est pas qu'un exercice de coloriage : c'est la structure de tous les problèmes d'appariement.

situation	groupe $X$	groupe $Y$
affectation de tâches	agents	tâches
emplois du temps	cours	créneaux
mariages stables	candidats	postes
recommandation	utilisateurs	produits

Et c'est décisif algorithmiquement : le couplage maximal, qui reste polynomial en général mais exige l'algorithme « des fleurs » d'Edmonds, devient simple sur un graphe biparti (exercice C3), par réduction au flot maximal.

⚠️ La différence avec la coloration générale est frappante : tester si $\chi\le2$ coûte $O(n+m)$ , alors que tester si $\chi\le3$ est NP-complet (exercice D6). Une seule couleur de plus fait basculer le problème.

Réponse : $C_4$ est biparti, avec $X=\{0,2\}$ et $Y=\{1,3\}$ — ses quatre arêtes traversent ; $C_3$ ne l'est pas, car son cycle de longueur $3$ est impair, et $\chi(C_3)=3$ .

Réponse.

C_4

biparti (

\{0,2\}\mid\{1,3\}

) ;

C_3

non (cycle impair). (Recoupement : parcours de coloration — succès sur

C_4

, conflit sur

C_3

✓)

Faire cet exercice dans l'app →

Tri topologique d'un DAG

CalculDifficulté 3/5

Pour le graphe orienté d'arcs $0\to2$ , $1\to2$ , $2\to3$ , $2\to4$ , donner un tri topologique. Que se passe-t-il si on ajoute l'arc $3\to1$ ?

Indices (3)

Algorithme de Kahn : retirer un sommet de degré entrant nul, recommencer.

Degrés entrants : $0\!:\!0$ , $1\!:\!0$ , $2\!:\!2$ , $3\!:\!1$ , $4\!:\!1$ .

Un cycle empêche tout sommet d'avoir un degré entrant nul à un moment.

Correction détaillée

L'idée directrice

Un tri topologique ordonne les sommets d'un graphe orienté de sorte que chaque arc aille de gauche à droite : si $u\to v$ , alors $u$ apparaît avant $v$ .

C'est l'ordre dans lequel exécuter des tâches qui dépendent les unes des autres.

\boxed{\text{Un tri topologique existe si et seulement si le graphe est un DAG — sans circuit.}}

DAG = Directed Acyclic Graph, graphe orienté acyclique.

Étape 1 — les degrés entrants

Arcs : $0\to2$ , $1\to2$ , $2\to3$ , $2\to4$ .

Le degré entrant d'un sommet est son nombre de prédécesseurs — c'est-à-dire le nombre de conditions à remplir avant de pouvoir le traiter.

sommet	prédécesseurs	degré entrant
$0$	aucun	$\mathbf{0}$
$1$	aucun	$\mathbf{0}$
$2$	$0$ , $1$	$2$
$3$	$2$	$1$
$4$	$2$	$1$

Les sommets de degré entrant $0$ sont ceux qu'on peut traiter immédiatement : ici $0$ et $1$ .

Étape 2 — l'algorithme de Kahn

Le principe : on retire un sommet sans prédécesseur, on met à jour les degrés entrants, et on recommence.

étape	disponibles	on sort	on décrémente	sortie
1	$\{0,1\}$	$0$	$\deg^-(2):2\to1$	$0$
2	$\{1\}$	$1$	$\deg^-(2):1\to\mathbf{0}$	$0,1$
3	$\{2\}$	$2$	$\deg^-(3):1\to0$ , $\deg^-(4):1\to0$	$0,1,2$
4	$\{3,4\}$	$3$	—	$0,1,2,3$
5	$\{4\}$	$4$	—	$0,1,2,3,4$

\boxed{\text{tri topologique} : 0,\ 1,\ 2,\ 3,\ 4}

Vérification — chaque arc doit aller de gauche à droite :

arc	position source	position cible	OK ?
$0\to2$	$1^{\text{re}}$	$3^{\text{e}}$	✓
$1\to2$	$2^{\text{e}}$	$3^{\text{e}}$	✓
$2\to3$	$3^{\text{e}}$	$4^{\text{e}}$	✓
$2\to4$	$3^{\text{e}}$	$5^{\text{e}}$	✓

⚠️ Le tri n'est pas unique : $1,0,2,4,3$ convient aussi. À l'étape 1, on avait le choix entre $0$ et $1$ ; à l'étape 4, entre $3$ et $4$ . Un DAG admet en général plusieurs tris, tous également valides.

Étape 3 — ce qui se passe avec l'arc $3\to1$

On ajoute $3\to1$ . Le degré entrant de $1$ passe de $0$ à $1$ .

sommet	degré entrant
$0$	$\mathbf{0}$
$1$	$1$ (à cause de $3\to1$ )
$2$	$2$
$3$	$1$
$4$	$1$

Déroulons Kahn :

étape	disponibles	on sort	résultat
1	$\{0\}$	$0$	$\deg^-(2):2\to1$
2	$\{\,\}$	—	BLOCAGE

Aucun sommet de degré entrant nul, et il reste $4$ sommets non sortis.

\boxed{\text{Il n'existe AUCUN tri topologique.}}

La raison : le graphe contient un circuit,

1\to2\to3\to1.

Vérification : les arcs $1\to2$ , $2\to3$ et $3\to1$ sont bien tous présents ✓

Un circuit rend l'ordre impossible : $1$ devrait précéder $2$ , qui devrait précéder $3$ , qui devrait précéder $1$ . Il faudrait que $1$ soit avant lui-même.

Le blocage est un DÉTECTEUR de circuit

C'est la propriété la plus utile de l'algorithme, et il faut la savoir :

Si Kahn sort moins de $n$ sommets, le graphe contient un circuit — et les sommets restants sont exactement ceux qui y participent ou en dépendent.

L'algorithme ne fait donc pas que trier : il certifie l'acyclicité. C'est le test de circuit le plus employé en pratique, et il coûte $O(n+m)$ .

⚠️ Le blocage n'est pas un échec de l'algorithme, c'est sa réponse. Un programme qui « plante » sur un cycle est mal écrit ; le bon comportement est de rendre « pas de tri, voici le circuit ».

Ce que ça sert à faire

Le tri topologique est partout où il y a des dépendances.

domaine	sommets	arcs	ce qu'un circuit signifie
compilation	modules	« A importe B »	dépendance circulaire — refusée
gestion de projet	tâches	« A avant B »	planning impossible (exercice E4)
tableur	cellules	« A2 utilise B7 »	référence circulaire
build system	fichiers	dépendances	cible impossible à construire
cours	modules	prérequis	cursus impossible

Le message « référence circulaire » d'un tableur, c'est exactement ce blocage de Kahn.

⚠️ Et l'ordre importe pour la suite du chapitre : la méthode PERT (exercice E4) commence par un tri topologique, parce que calculer une date au plus tôt suppose que toutes les tâches amont soient déjà datées.

Réponse : $0,1,2,3,4$ est un tri topologique valide (il en existe d'autres) ; avec l'arc $3\to1$ , l'algorithme se bloque après le seul sommet $0$ — le circuit $1\to2\to3\to1$ rend tout tri impossible.

Réponse. Tri valide

0,1,2,3,4

; avec

3\to1

le cycle

1\to2\to3\to1

rend tout tri impossible. (Recoupement : Kahn renvoie

5

sommets sans arc

3\to1

, échoue avec ✓)

Faire cet exercice dans l'app →

Algorithme de Dijkstra

CalculDifficulté 3/5

Graphe orienté pondéré : $0\to1\,(4)$ , $0\to2\,(1)$ , $2\to1\,(2)$ , $1\to3\,(1)$ , $2\to3\,(5)$ , $3\to4\,(3)$ . Calculer les distances depuis $0$ et le plus court chemin vers $4$ .

Indices (3)

Dijkstra fixe à chaque étape le sommet non traité de plus petite distance, puis relâche ses arcs.

Initialiser $d_0=0$ , les autres $=+\infty$ .

Relâcher $u\to v$ : si $d_u+w<d_v$ , mettre à jour $d_v$ et le prédécesseur.

Correction détaillée

L'idée directrice

L'algorithme de Dijkstra calcule les plus courts chemins depuis une source, dans un graphe à poids positifs ou nuls.

Son principe est celui d'une tache d'huile : on connaît d'abord la distance au sommet le plus proche, puis au suivant, et ainsi de suite par distance croissante. À chaque tour, on fige définitivement le sommet non traité de plus petite distance provisoire.

\boxed{\text{on extrait toujours le sommet de distance provisoire MINIMALE, et sa valeur devient définitive.}}

⚠️ Cette garantie repose entièrement sur la positivité des poids — c'est ce que montrera l'exercice B6.

Le graphe

0\to1\ (4),\quad 0\to2\ (1),\quad 2\to1\ (2),\quad 1\to3\ (1),\quad 2\to3\ (5),\quad 3\to4\ (3).

Départ : sommet $0$ . Distances initiales : $d(0)=0$ et $d(v)=+\infty$ ailleurs.

Le déroulé, tour par tour

tour	on extrait	$d$ figée	on relâche	mises à jour
1	$\mathbf{0}$	$0$	$0\to1\,(4)$ : $\infty\to4$	$d(1)=4$ , père $=0$
			$0\to2\,(1)$ : $\infty\to1$	$d(2)=1$ , père $=0$
2	$\mathbf{2}$	$1$	$2\to1\,(2)$ : $1+2=3<4$ ✓	$d(1)=\mathbf{3}$ , père $=\mathbf{2}$
			$2\to3\,(5)$ : $1+5=6<\infty$	$d(3)=6$ , père $=2$
3	$\mathbf{1}$	$3$	$1\to3\,(1)$ : $3+1=4<6$ ✓	$d(3)=\mathbf{4}$ , père $=\mathbf{1}$
4	$\mathbf{3}$	$4$	$3\to4\,(3)$ : $4+3=7$	$d(4)=7$ , père $=3$
5	$\mathbf{4}$	$7$	—	fini

Ordre d'extraction : $0,\ 2,\ 1,\ 3,\ 4$ — par distance croissante $0,1,3,4,7$ , comme le veut l'algorithme.

\boxed{d(0)=0,\quad d(1)=3,\quad d(2)=1,\quad d(3)=4,\quad d(4)=7}

Les deux relâchements qui comptent

Le mot relâcher désigne le test $d(u)+w<d(v)$ , qui améliore une estimation. Deux d'entre eux ont vraiment changé le résultat, et il faut les avoir vus :

Tour 2 — le sommet $1$ . On avait $d(1)=4$ par l'arc direct $0\to1$ . Le détour $0\to2\to1$ coûte $1+2=3<4$ : le détour est plus court que la ligne directe. C'est précisément ce que l'algorithme est fait pour découvrir.

Tour 3 — le sommet $3$ . On avait $d(3)=6$ via $2\to3$ . Le chemin $\dots\to1\to3$ coûte $3+1=4<6$ : nouvelle amélioration.

Sans ces deux relâchements, on aurait conclu $d(4)=6+3=9$ au lieu de $7$ .

Le chemin optimal

On remonte les pères depuis $4$ :

4\ \xleftarrow{\text{père}}\ 3\ \xleftarrow{}\ 1\ \xleftarrow{}\ 2\ \xleftarrow{}\ 0.

\boxed{0\to2\to1\to3\to4}

Vérification par les poids :

1+2+1+3=\mathbf{7}=d(4).\ \checkmark

Comparaison avec l'alternative $0\to1\to3\to4$ : $\ 4+1+3=8>7$ . Et $0\to2\to3\to4$ : $\ 1+5+3=9>7$ . Le chemin trouvé est bien le meilleur des trois.

Pourquoi ça marche, et à quel prix

L'invariant : quand on extrait un sommet $u$ de distance provisoire minimale, cette valeur est définitive.

Preuve en une phrase : tout autre chemin vers $u$ passerait par un sommet encore non extrait, donc de distance $\ge d(u)$ ; comme les poids sont $\ge0$ , ce chemin ne peut qu'être plus long.

C'est ici, et uniquement ici, que la positivité sert — et c'est ce qui tombe en défaut à l'exercice B6.

	complexité
avec tas binaire	$O\big((n+m)\log n\big)$
avec tableau simple	$O(n^2)$

Pour un graphe peu dense ( $m\ll n^2$ ), le tas gagne largement ; pour un graphe dense, le tableau suffit.

Réponse : $d=(0,3,1,4,7)$ ; le plus court chemin vers $4$ est $0\to2\to1\to3\to4$ , de longueur $7$ — et il passe par deux détours, chacun découvert par un relâchement.

Réponse. Distances

(0,3,1,4,7)

; chemin

0\to2\to1\to3\to4

de coût

7

. (Recoupement scipy dijkstra :

[0,3,1,4,7]

✓)

Faire cet exercice dans l'app →

Bellman-Ford & poids négatifs

CalculDifficulté 3/5

Graphe orienté $0\to1\,(4)$ , $0\to2\,(2)$ , $1\to2\,(-3)$ , $2\to3\,(2)$ . Calculer les plus courtes distances depuis $0$ par Bellman-Ford et commenter le rôle de l'arc négatif.

Indices (3)

Dijkstra est exclu : il y a un poids négatif.

Bellman-Ford relâche toutes les arêtes $\lvert V\rvert-1=3$ fois.

Comparer le chemin $0\to2$ direct et $0\to1\to2$ .

Correction détaillée

Pourquoi un autre algorithme

Dijkstra exige des poids positifs ou nuls. Dès qu'un arc est négatif, il peut se tromper (exercice B6). Bellman–Ford n'a pas cette limite : il accepte les poids négatifs, au prix d'une méthode plus lente mais plus robuste.

Son principe est brutal et sûr : au lieu de choisir soigneusement quel sommet traiter, on relâche TOUS les arcs, $n-1$ fois de suite.

\text{pour }k=1\dots n-1 : \quad\text{pour chaque arc }(u,v,w) : \quad d(v)\leftarrow\min\big(d(v),\ d(u)+w\big).

Le graphe

0\to1\ (4),\qquad 0\to2\ (2),\qquad 1\to2\ (\mathbf{-3}),\qquad 2\to3\ (2).

L'arc $1\to2$ a un poids négatif : c'est lui qui rend Dijkstra inutilisable.

Le déroulé

Initialisation : $d(0)=0$ , tout le reste à $+\infty$ . Il y a $n=4$ sommets, donc $n-1=3$ passes.

après	$d(0)$	$d(1)$	$d(2)$	$d(3)$
init	$0$	$\infty$	$\infty$	$\infty$
passe 1	$0$	$4$	$\mathbf{1}$	$\mathbf{3}$
passe 2	$0$	$4$	$1$	$3$
passe 3	$0$	$4$	$1$	$3$

\boxed{d(0)=0,\quad d(1)=4,\quad d(2)=1,\quad d(3)=3}

Détail de la passe 1, en traitant les arcs dans l'ordre donné :

$0\to1\,(4)$ : $d(1)=0+4=4$ ;
$0\to2\,(2)$ : $d(2)=0+2=2$ ;
$1\to2\,(-3)$ : $4+(-3)=1<2$ ✓ $\Rightarrow d(2)=\mathbf{1}$ ;
$2\to3\,(2)$ : $1+2=3$ $\Rightarrow d(3)=3$ .

Ici tout converge dès la première passe, parce que l'ordre des arcs suit le sens du graphe. Avec un ordre défavorable, il aurait fallu les trois passes — c'est pourquoi l'algorithme les fait toutes.

Le rôle de l'arc négatif

C'est le cœur de l'exercice.

Vers le sommet $2$ , il y a deux chemins :

chemin	coût
$0\to2$ (direct)	$2$
$0\to1\to2$ (détour)	$4+(-3)=\mathbf{1}$

Le détour est MOINS cher que la route directe — c'est exactement ce que permet un poids négatif, et c'est ce qui ruine l'intuition géométrique. On ne peut plus se dire « s'éloigner coûte », puisqu'un arc peut rapporter.

Et l'effet se propage : $d(3)$ passe de $2+2=4$ à $1+2=\mathbf{3}$ . Un seul arc négatif améliore toute une branche en aval.

Pourquoi $n-1$ passes suffisent

Un plus court chemin sans circuit a au plus $n-1$ arcs (il ne repasse par aucun sommet, donc en visite au plus $n$ ).

Or chaque passe garantit au moins un arc de plus dans les chemins correctement calculés : après la passe $k$ , tous les plus courts chemins d'au plus $k$ arcs sont exacts.

Après $n-1$ passes, tous les plus courts chemins sont donc trouvés.

⚠️ Et une $n$ -ième passe sert de test. Si elle améliore encore quelque chose, c'est qu'il existe un chemin de $n$ arcs ou plus qui gagne — donc qu'il repasse par un sommet, donc qu'il y a un circuit de poids négatif. C'est l'objet de l'exercice B5.

Ici, la passe supplémentaire n'améliore rien : pas de circuit négatif ✓

Bellman–Ford contre Dijkstra

	Dijkstra	Bellman–Ford
poids négatifs	non	oui
circuits négatifs	—	les détecte
complexité	$O\big((n+m)\log n\big)$	$O(n\,m)$
stratégie	choisir le meilleur sommet	relâcher tout, plusieurs fois
parallélisable	difficilement	facilement (les relâchements d'une même passe sont indépendants)

Bellman–Ford est nettement plus lent — quadratique au lieu de quasi-linéaire — mais il ne demande aucune hypothèse et il détecte les circuits négatifs. On l'emploie exactement quand Dijkstra ne s'applique pas.

Application réelle : le protocole de routage RIP en réseau est un Bellman–Ford distribué, chaque routeur relâchant les arcs qu'il connaît.

Réponse : $d=(0,4,1,3)$ ; l'arc négatif $1\to2\,(-3)$ rend le détour $0\to1\to2$ moins cher ( $1$ ) que la route directe ( $2$ ), et cette amélioration se propage jusqu'à $3$ .

Réponse. Distances

(0,4,1,3)

; le chemin

0\to1\to2

(

=1

) bat

0\to2

(

=2

) grâce à l'arc

-3

. (Recoupement scipy bellman_ford :

[0,4,1,3]

✓)

Faire cet exercice dans l'app →

Floyd-Warshall (toutes paires)

CalculDifficulté 3/5

Sur le graphe de l'exercice B1, on veut les plus courtes distances entre toutes les paires. Quel algorithme et quelle est la distance de $2$ à $4$ ?

Indices (3)

Floyd-Warshall calcule toutes les paires en $O(\lvert V\rvert^3)$ par programmation dynamique sur les sommets intermédiaires.

Pour $d(2,4)$ : chercher le meilleur trajet de $2$ à $4$ .

Les arcs utiles : $2\to1\,(2)$ , $1\to3\,(1)$ , $3\to4\,(3)$ .

Correction détaillée

La question posée

Dijkstra et Bellman–Ford calculent les distances depuis une source. Si l'on veut toutes les paires $(i,j)$ , on pourrait relancer Dijkstra $n$ fois — mais il existe mieux : Floyd–Warshall, qui traite le problème d'un bloc.

\boxed{\text{Floyd–Warshall : toutes les paires, }O(n^3)\text{, en trois boucles imbriquées.}}

Le principe

L'algorithme repose sur une idée de programmation dynamique remarquablement simple :

$D_k[i][j]$ = plus courte distance de $i$ à $j$ en n'utilisant comme sommets intermédiaires que $0,1,\dots,k$ .

La récurrence s'écrit alors : pour aller de $i$ à $j$ en s'autorisant le sommet $k$ , ou bien on ne passe pas par $k$ , ou bien on y passe :

D_k[i][j]=\min\Big(\underbrace{D_{k-1}[i][j]}_{\text{sans }k},\ \underbrace{D_{k-1}[i][k]+D_{k-1}[k][j]}_{\text{en passant par }k}\Big).

D'où le code, qui tient en trois lignes :

\textbf{pour }k,\ \textbf{pour }i,\ \textbf{pour }j:\qquad D[i][j]\leftarrow\min\big(D[i][j],\ D[i][k]+D[k][j]\big).

⚠️ L'ordre des boucles n'est pas négociable : $k$ à l'EXTÉRIEUR. Mettre $k$ à l'intérieur casse la récurrence — on utiliserait des valeurs pas encore calculées pour le bon ensemble de sommets intermédiaires.

Le résultat sur le graphe de B1

0\to1\,(4),\ 0\to2\,(1),\ 2\to1\,(2),\ 1\to3\,(1),\ 2\to3\,(5),\ 3\to4\,(3).

Matrice finale des distances (ligne = départ, colonne = arrivée) :

de \ vers	$0$	$1$	$2$	$3$	$4$
$\mathbf{0}$	$0$	$3$	$1$	$4$	$7$
$\mathbf{1}$	$\infty$	$0$	$\infty$	$1$	$4$
$\mathbf{2}$	$\infty$	$2$	$0$	$3$	$\mathbf{6}$
$\mathbf{3}$	$\infty$	$\infty$	$\infty$	$0$	$3$
$\mathbf{4}$	$\infty$	$\infty$	$\infty$	$\infty$	$0$

\boxed{d(2,4)=6}

Vérification à la main : de $2$ à $4$ , les chemins possibles sont

chemin	coût
$2\to1\to3\to4$	$2+1+3=\mathbf{6}$
$2\to3\to4$	$5+3=8$

Le minimum est bien $6$ ✓

Lire la matrice

Trois observations, toutes instructives :

(a) La première ligne est le résultat de Dijkstra de l'exercice B1 : $(0,3,1,4,7)$ ✓ Floyd–Warshall contient donc ce calcul, et les $n-1$ autres.

(b) Beaucoup de $\infty$ , et c'est normal. Le graphe est orienté : de $1$ , on ne peut jamais revenir vers $0$ ni vers $2$ , car aucun arc ne remonte. La matrice n'est donc pas symétrique — elle le serait sur un graphe non orienté.

(c) La diagonale est nulle : $d(i,i)=0$ , on ne bouge pas. (Une valeur négative sur la diagonale signalerait un circuit de poids négatif — c'est le test de détection de Floyd–Warshall, à rapprocher de l'exercice B5.)

Quel algorithme choisir

situation	algorithme	coût
une source, poids $\ge0$	Dijkstra	$O\big((n+m)\log n\big)$
une source, poids quelconques	Bellman–Ford	$O(nm)$
toutes les paires, graphe dense	Floyd–Warshall	$O(n^3)$
toutes les paires, graphe creux, poids $\ge0$	$n\times$ Dijkstra	$O\big(n(n+m)\log n\big)$

Le point de bascule. Sur un graphe dense ( $m\approx n^2$ ), $n$ Dijkstra coûtent $O(n^3\log n)$ — donc plus que Floyd–Warshall. Sur un graphe creux ( $m\approx n$ ), ils coûtent $O(n^2\log n)$ — donc moins.

Ici : $n=5$ , $m=6$ , graphe creux. Cinq Dijkstra seraient plus rapides — mais Floyd–Warshall tient en trois lignes de code et accepte les poids négatifs, ce que Dijkstra ne fait pas. À cette taille, la simplicité l'emporte.

Sa vraie force : Floyd–Warshall se transpose à d'autres « min-plus », comme la fermeture transitive (existe-t-il un chemin ?) en remplaçant $\min$ par « ou » et $+$ par « et ».

Réponse : Floyd–Warshall, en $O(n^3)$ ; la distance de $2$ à $4$ vaut $\mathbf6$ , par le chemin $2\to1\to3\to4$ ( $2+1+3$ ), meilleur que $2\to3\to4$ qui coûte $8$ .

Réponse. Floyd-Warshall (

O(\lvert V\rvert^3)

, toutes paires) ;

d(2,4)=6

via

2\to1\to3\to4

. (Recoupement scipy floyd_warshall :

d(2,4)=6

, ligne

0=[0,3,1,4,7]

✓)

Faire cet exercice dans l'app →

Reconstruction du chemin

ApplicationDifficulté 3/5

On a exécuté Dijkstra depuis $0$ sur le graphe de B1 et stocké les prédécesseurs. Comment reconstruire le chemin optimal vers $4$ ?

Indices (3)

Le tableau des prédécesseurs donne, pour chaque sommet, par où on l'a atteint au mieux.

Partir de la destination et remonter de prédécesseur en prédécesseur.

Inverser la liste obtenue.

Correction détaillée

Le problème

Dijkstra rend les distances. Mais en pratique on veut le chemin : quel itinéraire suivre ? Le stocker en entier pour chaque sommet coûterait $O(n^2)$ en mémoire.

La solution tient en un seul tableau : pour chaque sommet $v$ , on retient son prédécesseur sur le plus court chemin depuis la source — un seul numéro par sommet, donc $O(n)$ en mémoire.

Le tableau des prédécesseurs

Sur le graphe de l'exercice B1, Dijkstra a produit :

sommet $v$	$d(v)$	père $(v)$	posé au tour
$0$	$0$	aucun (source)	—
$1$	$3$	$\mathbf{2}$	tour 2
$2$	$1$	$0$	tour 1
$3$	$4$	$\mathbf{1}$	tour 3
$4$	$7$	$3$	tour 4

Le père se met à jour EN MÊME TEMPS que la distance. Quand le relâchement $d(u)+w<d(v)$ réussit, on écrit à la fois $d(v)\leftarrow d(u)+w$ et père $(v)\leftarrow u$ .

⚠️ Noter que père $(1)$ vaut $2$ et non $0$ : au tour 2, le détour $0\to2\to1$ a battu l'arc direct. Le père enregistre le dernier vainqueur, pas le premier venu.

La reconstruction

On part de la cible et on remonte les pères jusqu'à la source, puis on retourne la liste.

étape	sommet courant	son père	chemin accumulé
1	$4$	$3$	$[4]$
2	$3$	$1$	$[4,3]$
3	$1$	$2$	$[4,3,1]$
4	$2$	$0$	$[4,3,1,2]$
5	$0$	aucun	$[4,3,1,2,0]$ — stop

On retourne :

\boxed{0\to2\to1\to3\to4}

Vérification par les poids : $1+2+1+3=7=d(4)$ ✓

L'algorithme en pseudo-code :

\texttt{ch}\leftarrow[t]\ ;\quad\textbf{tant que}\ \text{père}(\texttt{ch}[-1])\ \text{existe} : \texttt{ch}.\text{ajouter}(\text{père}(\texttt{ch}[-1]))\ ;\quad\textbf{renverser}(\texttt{ch}).

Les trois contrôles à faire

(a) La somme des poids doit valoir la distance. C'est le contrôle décisif : $1+2+1+3=7=d(4)$ ✓ S'il échoue, le tableau des pères est incohérent avec les distances.

(b) Chaque arc du chemin doit exister. $0\to2$ ✓, $2\to1$ ✓, $1\to3$ ✓, $3\to4$ ✓ — les quatre sont dans la liste des arcs.

(c) On doit atteindre la source. Si la remontée boucle ou s'arrête ailleurs, il y a une erreur.

⚠️ Le cas où il n'y a pas de chemin : si $d(t)=+\infty$ , la cible n'a pas de père, et la reconstruction doit rendre « aucun chemin » — pas une liste vide qu'on lirait comme un chemin de longueur nulle. C'est le cas de $1\to0$ dans la matrice de l'exercice B3.

Ce que la structure des pères représente

L'ensemble des arcs $\big(\text{père}(v),v\big)$ forme un arbre couvrant enraciné à la source, appelé arbre des plus courts chemins :

0\to2,\qquad 2\to1,\qquad 1\to3,\qquad 3\to4.

Quatre arcs pour cinq sommets — c'est bien $n-1$ , comme tout arbre (exercice E3).

Propriété remarquable : ce seul arbre contient les plus courts chemins vers tous les sommets à la fois. Pour aller en $3$ , on lit $0\to2\to1\to3$ ; pour aller en $1$ , $0\to2\to1$ . Un seul tableau de $n$ entiers encode donc $n$ itinéraires.

C'est ce qui rend les GPS possibles : on ne stocke pas un chemin par destination, mais un père par carrefour.

⚠️ Ne pas confondre avec l'arbre couvrant MINIMAL des exercices E1–E2 : celui-là minimise le poids total, celui-ci minimise chaque distance à la source. Ce sont deux arbres différents, obtenus par des algorithmes différents.

Réponse : on remonte les pères depuis la cible — $4\to3\to1\to2\to0$ — puis on retourne, ce qui donne $0\to2\to1\to3\to4$ ; le contrôle est que la somme des poids, $1+2+1+3=7$ , égale $d(4)$ .

Réponse. Chemin

0\to2\to1\to3\to4

obtenu en remontant les prédécesseurs. (Recoupement scipy (return_predecessors) :

[0,2,1,3,4]

✓)

Faire cet exercice dans l'app →

Détection d'un cycle négatif

DémonstrationDifficulté 3/5

Soit le graphe orienté $0\to1\,(1)$ , $1\to2\,(1)$ , $2\to1\,(-3)$ . Que vaut le plus court chemin de $0$ vers $2$ ? Qu'en dit Bellman-Ford ?

Indices (3)

Repérer le cycle entre $1$ et $2$ et calculer son poids total.

Si on peut tourner indéfiniment en diminuant le coût, la notion de plus court chemin s'effondre.

Bellman-Ford détecte une amélioration au $\lvert V\rvert$ -ième tour.

Correction détaillée

Le graphe et le piège

0\to1\ (1),\qquad 1\to2\ (1),\qquad 2\to1\ (\mathbf{-3}).

Question : que vaut le plus court chemin de $0$ vers $2$ ?

Réflexe naturel : $0\to1\to2$ coûte $1+1=2$ . Mais ce n'est pas la réponse, et il faut regarder ce que le graphe permet de faire.

Le circuit, et ce qu'il coûte

Repérons le circuit :

1\to2\to1,\qquad\text{de poids}\qquad 1+(-3)=\boxed{-2}.

Ce circuit fait GAGNER $2$ à chaque tour. On peut donc l'emprunter autant de fois qu'on veut :

chemin	coût
$0\to1\to2$	$1+1=2$
$0\to1\to2\to1\to2$	$2+(-3)+1=0$
$0\to1\to2\to1\to2\to1\to2$	$0-3+1=-2$
… $k$ tours de plus	$2-2k$

\lim_{k\to\infty}(2-2k)=-\infty.

\boxed{\text{Il n'existe AUCUN plus court chemin de }0\text{ vers }2 : \text{la borne inférieure est }-\infty.}

⚠️ Ce n'est pas « la réponse est $-\infty$ » au sens d'une valeur : c'est qu'il n'y a pas de minimum. Quel que soit le chemin proposé, on peut en exhiber un strictement plus court.

Ce qu'en dit Bellman–Ford

L'algorithme fait $n-1=2$ passes, puis une passe supplémentaire de contrôle.

après	$d(0)$	$d(1)$	$d(2)$
init	$0$	$\infty$	$\infty$
passe 1	$0$	$\mathbf{-1}$	$2$
passe 2	$0$	$\mathbf{-3}$	$\mathbf{0}$
passe 3 (test)	$0$	$\mathbf{-5}$	$\mathbf{-2}$

(arcs traités dans l'ordre $0\to1$ , $1\to2$ , $2\to1$ ; dès la première passe, le retour $2\to1$ fait déjà descendre $d(1)$ à $-1$ .)

La passe de contrôle AMÉLIORE encore des distances. C'est exactement le signal :

\boxed{\text{Si la }n\text{-ième passe améliore quelque chose, il y a un circuit de poids négatif.}}

Pourquoi c'est un critère sûr. Un plus court chemin sans circuit a au plus $n-1$ arcs (exercice B2). Après $n-1$ passes, tous les chemins sans circuit sont donc exacts. Une amélioration supplémentaire ne peut venir que d'un chemin avec circuit — donc d'un circuit qui fait baisser le coût, donc négatif.

Bellman–Ford ne rend pas un résultat faux : il rend un diagnostic. C'est un comportement bien plus utile qu'une valeur arbitraire.

Ce qui a du sens malgré tout

Le circuit négatif ne rend pas tout impossible — il faut savoir ce qui survit.

question	réponse
plus court chemin de $0$ à $2$	n'existe pas ( $-\infty$ )
plus court chemin élémentaire (sans répéter de sommet)	existe : $0\to1\to2$ , de coût $2$
existe-t-il un chemin de $0$ à $2$ ?	oui — la connexité est intacte

⚠️ Mais chercher le plus court chemin ÉLÉMENTAIRE en présence de poids négatifs est NP-difficile. Le problème « facile » devient donc « très dur » dès qu'on impose la non-répétition. C'est l'une des bascules les plus nettes du chapitre, à rapprocher de l'exercice D6.

C'est pourquoi les algorithmes de plus court chemin exigent l'absence de circuit négatif : sans cette hypothèse, le problème change de nature.

Où ça arrive en vrai

Un circuit négatif n'est pas une curiosité d'exercice.

domaine	ce que serait un circuit négatif
arbitrage de devises	une suite de conversions qui crée de l'argent
comptabilité	une chaîne d'écritures qui se solde par un gain
ordonnancement	des contraintes de dates contradictoires
flots à coût minimal	un cycle qu'il faut annuler pour optimiser

L'arbitrage est l'exemple le plus parlant. En posant $w=-\log(\text{taux})$ , un circuit de poids négatif correspond à un produit de taux $>1$ : convertir euro → dollar → yen → euro rapporterait plus qu'on n'a mis. Détecter un tel circuit par Bellman–Ford est un algorithme réellement employé en finance — et les marchés efficients les font disparaître en quelques millisecondes.

Cas particulier : un circuit de poids exactement nul ne pose aucun problème. Ce n'est pas la présence d'un circuit qui gêne, c'est son signe.

Réponse : le circuit $1\to2\to1$ pèse $-2$ , donc on peut descendre aussi bas qu'on veut — il n'y a pas de plus court chemin de $0$ à $2$ ; Bellman–Ford le détecte parce que sa $n$ -ième passe améliore encore les distances.

Réponse. Cycle

1\to2\to1

de poids

-2<0

: pas de plus court chemin (

-\infty

), détecté par Bellman-Ford. (Recoupement scipy : NegativeCycleError levée ✓)

Faire cet exercice dans l'app →

Pourquoi Dijkstra échoue en négatif

DémonstrationDifficulté 3/5

Expliquer pourquoi l'algorithme de Dijkstra peut donner un résultat faux sur un graphe à arcs de poids négatif.

Indices (3)

Dijkstra « fixe » définitivement un sommet dès qu'il a la plus petite distance provisoire.

Cette décision suppose qu'aucun chemin futur ne pourra faire mieux.

Un arc négatif viole cette hypothèse.

Correction détaillée

Ce qu'il faut expliquer

Pourquoi Dijkstra peut-il rendre un résultat faux sur un graphe à arcs négatifs ?

La réponse tient à l'invariant qui fonde l'algorithme (exercice B1) :

quand on extrait le sommet de distance provisoire minimale, cette distance est définitive.

Cet invariant repose entièrement sur une hypothèse : s'éloigner coûte. Un arc négatif la détruit.

L'argument, et l'endroit exact où il casse

Preuve de l'invariant, quand les poids sont $\ge0$ . Soit $u$ le sommet extrait, de distance provisoire $d(u)$ minimale. Tout autre chemin vers $u$ devrait passer par un sommet $x$ encore non extrait, donc de distance $d(x)\ge d(u)$ . Ce chemin coûterait donc

d(x)+\underbrace{(\text{reste du chemin})}_{\ge0}\ \ge\ d(x)\ \ge\ d(u).

Il ne peut pas faire mieux. $\blacksquare$

L'étape marquée $\ge0$ est la seule qui utilise l'hypothèse — et c'est celle qui tombe. Avec des arcs négatifs, le reste du chemin peut être négatif, et un détour par un sommet plus lointain peut finir moins cher.

Le contre-exemple, en chiffres

Reprenons le graphe de l'exercice B2 :

0\to1\ (4),\qquad 0\to2\ (2),\qquad 1\to2\ (\mathbf{-3}),\qquad 2\to3\ (2).

Déroulons Dijkstra :

tour	on extrait	$d$ figée	on relâche
1	$0$	$0$	$d(1)=4$ , $d(2)=2$
2	$\mathbf{2}$	$\mathbf{2}$ — FIGÉE	$d(3)=2+2=\mathbf{4}$
3	$1$	$4$	$1\to2$ : $4-3=1<2$ … mais $2$ est déjà extrait
4	$3$	$4$	—

Le résultat de Dijkstra : $d(3)=4$ .

La vérité, par Bellman–Ford (exercice B2) : $d(3)=\mathbf{3}$ , par le chemin $0\to1\to2\to3$ de coût $4-3+2=3$ .

\boxed{\text{Dijkstra se trompe sur le sommet }3 : \text{il rend }4\text{ au lieu de }3.}

Le mécanisme précis de l'erreur

Au tour 2, Dijkstra extrait le sommet $2$ avec $d(2)=2$ et fige cette valeur. Il en déduit aussitôt $d(3)=4$ .

Au tour 3, il découvre que $2$ était en fait à distance $1$ (via le détour par $1$ ). Mais il est trop tard :

le sommet $2$ est déjà extrait, donc l'algorithme ne le retraite pas ;
ses successeurs — ici $3$ — ne sont donc jamais recalculés ;
l'erreur de $1$ sur $d(2)$ se propage en une erreur de $1$ sur $d(3)$ .

⚠️ Le sommet $2$ lui-même finit avec la bonne valeur dans certaines implémentations (celles qui écrivent $d(2)=1$ même après extraction). C'est trompeur : la valeur affichée est juste, mais elle n'a pas été propagée. L'erreur ne se voit que sur le sommet $3$ , en aval.

Leçon de méthode : vérifier un algorithme sur la seule valeur qu'on regarde ne suffit pas. Ici $d(2)$ est correct et $d(3)$ ne l'est pas.

Ce qu'il ne faut PAS essayer

Deux « réparations » viennent naturellement à l'esprit. Les deux échouent, et savoir pourquoi vaut mieux que de les essayer.

(a) « Ajouter une constante à tous les poids pour les rendre positifs. » Cela change le problème : un chemin de $k$ arcs voit son coût augmenter de $k\times C$ . Les chemins longs sont donc pénalisés davantage que les courts, et le plus court chemin peut changer.

Sur notre exemple avec $C=3$ : $0\to2\to3$ coûterait $5+5=10$ , et $0\to1\to2\to3$ coûterait $7+0+5=12$ . On conclurait au premier, alors que le vrai optimum est le second.

(b) « Autoriser la réextraction d'un sommet déjà figé. » L'algorithme devient correct (en l'absence de circuit négatif)… mais sa complexité explose — il peut extraire un sommet un nombre exponentiel de fois. On a alors réinventé, en moins bien, ce que Bellman–Ford fait proprement.

La seule bonne réponse est de changer d'algorithme.

poids	algorithme
tous $\ge0$	Dijkstra, $O\big((n+m)\log n\big)$
quelconques, sans circuit négatif	Bellman–Ford, $O(nm)$
graphe acyclique, poids quelconques	tri topologique + relâchement, $O(n+m)$

La troisième ligne est utile : sur un DAG (exercice A6), les poids négatifs ne posent aucun problème, et l'on est même plus rapide que Dijkstra.

Réponse : Dijkstra fige la distance d'un sommet à son extraction, ce qui n'est justifié que si les poids sont $\ge0$ ; sur $0\to1\,(4)$ , $0\to2\,(2)$ , $1\to2\,(-3)$ , $2\to3\,(2)$ , il fige $d(2)=2$ trop tôt et rend $d(3)=4$ au lieu de $3$ .

Réponse. L'hypothèse gloutonne « un sommet fixé ne s'améliore plus » tombe avec un arc négatif

\Rightarrow

utiliser Bellman-Ford. (Recoupement : cf. B2, où le détour négatif bat l'arc direct ✓)

Faire cet exercice dans l'app →

Arbre couvrant minimal (Kruskal)

CalculDifficulté 3/5

Graphe non orienté pondéré, arêtes (poids) : $01\,(2)$ , $03\,(6)$ , $12\,(3)$ , $13\,(8)$ , $14\,(5)$ , $24\,(7)$ , $34\,(9)$ . Trouver l'arbre couvrant minimal par Kruskal.

Indices (3)

Trier les arêtes par poids croissant.

Ajouter chaque arête si elle ne crée pas de cycle (union-find).

S'arrêter à $\lvert V\rvert-1=4$ arêtes.

Correction détaillée

L'idée directrice

Un arbre couvrant minimal (ACM) est un sous-graphe qui relie tous les sommets avec le poids total le plus petit possible, et sans cycle.

C'est le problème du câblage : relier $n$ villes par des routes, au coût minimal.

L'algorithme de Kruskal procède par arêtes, dans l'ordre croissant des poids :

on trie les arêtes par poids croissant, et on prend chacune sauf si elle crée un cycle.

C'est un algorithme glouton — il ne revient jamais sur ses choix — et, fait remarquable, il donne l'optimum exact.

Étape 1 — trier les arêtes

Arêtes et poids : $01\,(2)$ , $03\,(6)$ , $12\,(3)$ , $13\,(8)$ , $14\,(5)$ , $24\,(7)$ , $34\,(9)$ .

Triées par poids croissant :

01\,(2),\quad 12\,(3),\quad 14\,(5),\quad 03\,(6),\quad 24\,(7),\quad 13\,(8),\quad 34\,(9).

Étape 2 — parcourir et décider

arête	poids	crée un cycle ?	décision	composantes après
$01$	$2$	non	PRISE	$\{0,1\}$ , $\{2\}$ , $\{3\}$ , $\{4\}$
$12$	$3$	non	PRISE	$\{0,1,2\}$ , $\{3\}$ , $\{4\}$
$14$	$5$	non	PRISE	$\{0,1,2,4\}$ , $\{3\}$
$03$	$6$	non	PRISE	$\{0,1,2,3,4\}$ — tout relié
$24$	$7$	oui ( $2$ et $4$ déjà reliés)	rejetée	—
$13$	$8$	oui	rejetée	—
$34$	$9$	oui	rejetée	—

\boxed{\text{ACM} = \{01,\ 12,\ 14,\ 03\},\qquad \text{poids} = 2+3+5+6 = \mathbf{16}}

Contrôles :

$4$ arêtes pour $5$ sommets, soit $n-1$ ✓ (exercice E3) ;
une seule composante à la fin ✓ ;
on s'arrête dès qu'on a $n-1$ arêtes : les trois dernières n'ont même pas besoin d'être examinées.

Le test « crée un cycle ? »

C'est l'opération critique de l'algorithme, et sa mise en œuvre décide de la complexité.

Une arête $uv$ crée un cycle si et seulement si $u$ et $v$ sont déjà dans la même composante.

Vérifions sur $24\,(7)$ : après les trois premières arêtes, la composante contient $\{0,1,2,4\}$ . Les sommets $2$ et $4$ y sont tous deux $\Longrightarrow$ il existe déjà un chemin entre eux ( $2\to1\to4$ ), donc l'arête $24$ fermerait un cycle ✓

La structure adaptée est l'union–find (union par rang, compression de chemin), qui répond en temps quasi constant :

O(m\log m)\ \text{pour le tri}\ +\ O(m\,\alpha(n))\ \text{pour les tests}\ \approx\ O(m\log m).

Le tri domine — c'est lui qui fixe la complexité.

Pourquoi le glouton donne l'OPTIMUM

C'est le point qui mérite explication : un algorithme glouton donne rarement l'optimum, ici toujours.

Propriété de la coupe. Soit une partition des sommets en deux groupes. L'arête de poids minimal qui les traverse appartient à un ACM.

Démonstration par échange : si un ACM ne la contenait pas, lui ajouter $e$ créerait un cycle, qui traverse la partition une seconde fois par une arête $e'$ , de poids $\ge$ . En remplaçant $e'$ par $e$ , on obtient encore un arbre couvrant, de poids $\le$ . Donc $e$ est dans un ACM.

Kruskal ne fait rien d'autre qu'appliquer cette propriété à répétition : chaque arête prise est la plus légère qui relie deux composantes encore séparées.

⚠️ Cette propriété est propre aux arbres couvrants. Le même raisonnement glouton sur le voyageur de commerce (exercice D2) ou le sac à dos (D1) échoue — c'est ce qui sépare les problèmes faciles des problèmes NP-difficiles.

Réponse : ACM $=\{01,12,14,03\}$ , de poids $\mathbf{16}$ ; les arêtes $24$ , $13$ et $34$ sont rejetées car elles fermeraient un cycle.

Réponse. ACM de poids

16

(arêtes

01,12,14,03

). (Recoupement : Prim donne

16

, et scipy minimum_spanning_tree somme

16

✓)

Faire cet exercice dans l'app →

Prim vs Kruskal

DémonstrationDifficulté 3/5

Sur le graphe de E1, exécuter Prim depuis le sommet $0$ et vérifier qu'on retrouve le même poids qu'avec Kruskal.

Indices (3)

Prim fait croître un arbre depuis un sommet de départ.

À chaque étape, ajouter l'arête la moins chère sortant de l'arbre courant.

Continuer jusqu'à couvrir tous les sommets.

Correction détaillée

L'autre stratégie

Kruskal (exercice E1) raisonne par arêtes, en partant du graphe entier. Prim raisonne par sommets, en partant d'un seul et en faisant grossir un arbre :

on part d'un sommet, et à chaque tour on ajoute l'arête la plus légère qui sort de l'arbre déjà construit.

C'est la même idée gloutonne, appliquée à une frontière qui avance — très proche de Dijkstra dans sa mécanique (un tas, une extraction du minimum), mais avec un critère différent.

Le déroulé depuis le sommet $0$

Arêtes : $01\,(2)$ , $03\,(6)$ , $12\,(3)$ , $13\,(8)$ , $14\,(5)$ , $24\,(7)$ , $34\,(9)$ .

tour	arbre courant	arêtes sortantes (poids)	la plus légère	on ajoute
1	$\{0\}$	$01\,(2)$ , $03\,(6)$	$\mathbf{01\,(2)}$	sommet $1$
2	$\{0,1\}$	$03\,(6)$ , $12\,(3)$ , $13\,(8)$ , $14\,(5)$	$\mathbf{12\,(3)}$	sommet $2$
3	$\{0,1,2\}$	$03\,(6)$ , $13\,(8)$ , $14\,(5)$ , $24\,(7)$	$\mathbf{14\,(5)}$	sommet $4$
4	$\{0,1,2,4\}$	$03\,(6)$ , $13\,(8)$ , $34\,(9)$	$\mathbf{03\,(6)}$	sommet $3$
5	$\{0,1,2,3,4\}$	—	—	fini

\boxed{\text{ACM} = \{01,\ 12,\ 14,\ 03\},\qquad \text{poids} = 2+3+5+6 = \mathbf{16}}

⚠️ À chaque tour, on ne regarde QUE les arêtes qui sortent de l'arbre. Au tour 3, l'arête $12\,(3)$ n'est plus candidate : ses deux extrémités sont dans l'arbre. La prendre créerait un cycle.

La comparaison avec Kruskal

	Kruskal	Prim
poids total	$\mathbf{16}$	$\mathbf{16}$
arêtes	$01,12,14,03$	$01,12,14,03$
ordre d'ajout	$2,3,5,6$ (poids croissant global)	$2,3,5,6$

Même poids ET mêmes arêtes ✓

L'ordre coïncide ici, mais ce n'est pas une règle : Kruskal prend les arêtes par poids croissant dans tout le graphe, Prim par poids croissant au bord de son arbre. Sur un autre graphe, les ordres diffèrent — et les arbres aussi, si plusieurs ACM existent.

Quand les arbres peuvent-ils différer ? Uniquement si le graphe a plusieurs ACM, ce qui suppose des poids égaux. Ici les sept poids sont deux à deux distincts :

2,3,5,6,7,8,9\quad\text{tous distincts}\ \Longrightarrow\ \textbf{l'ACM est UNIQUE.}

C'est un théorème : si tous les poids sont distincts, l'arbre couvrant minimal est unique. Les deux algorithmes devaient donc trouver le même — leur accord n'est pas une chance, c'est une conséquence.

Lequel choisir en pratique

	Kruskal	Prim (avec tas)	Prim (avec tableau)
complexité	$O(m\log m)$	$O\big(m\log n\big)$	$O(n^2)$
adapté aux graphes	creux	creux	denses
structure	union–find	tas de priorité	tableau
se parallélise	plutôt bien	mal	mal

Le critère est la densité. Sur un graphe creux ( $m\approx n$ ), Kruskal est simple et rapide. Sur un graphe dense ( $m\approx n^2$ ), Prim avec tableau tourne en $O(n^2)$ alors que le seul tri de Kruskal coûterait $O(n^2\log n)$ .

Prim ressemble beaucoup à Dijkstra (exercice B1) : même boucle, même tas, même extraction du minimum. La seule différence tient au critère — Dijkstra compare $d(u)+w$ (distance depuis la source), Prim compare $w$ seul (coût de raccordement). Un caractère de code, deux problèmes différents.

Réponse : Prim depuis $0$ ajoute $01\,(2)$ , $12\,(3)$ , $14\,(5)$ , $03\,(6)$ — soit le même arbre que Kruskal, de poids $\mathbf{16}$ ; c'était garanti, les sept poids étant distincts, l'ACM est unique.

Réponse. Prim depuis

0

: poids

16

, comme Kruskal. (Recoupement : prim=kruskal

=16

✓)

Faire cet exercice dans l'app →

Arbre couvrant : nombre d'arêtes

DémonstrationDifficulté 3/5

Pourquoi un arbre couvrant d'un graphe à $n=5$ sommets a-t-il exactement $4$ arêtes ? Que signifierait une cinquième arête ?

Indices (3)

Un arbre est connexe et sans cycle.

Un graphe connexe à $n$ sommets a au moins $n-1$ arêtes.

Ajouter une arête à un arbre crée un cycle.

Correction détaillée

Ce qu'il faut démontrer

Pourquoi un arbre couvrant d'un graphe à $n=5$ sommets a-t-il exactement $4$ arêtes ?

La réponse est un théorème de structure, et il tient à la définition même d'un arbre : un graphe connexe et sans cycle.

\boxed{\text{arbre à }n\text{ sommets}\ \Longleftrightarrow\ n-1\ \text{arêtes, connexe}\ \Longleftrightarrow\ n-1\ \text{arêtes, sans cycle}}

Deux des trois propriétés — connexité, acyclicité, $n-1$ arêtes — impliquent toujours la troisième. C'est ce qui rend les arbres si commodes.

La démonstration, par construction

Construisons l'arbre en ajoutant les sommets un par un.

Départ : $1$ sommet, $0$ arête.

À chaque étape, on rattache un nouveau sommet à l'arbre déjà construit. Il faut exactement une arête :

moins d'une (c'est-à-dire zéro) : le sommet resterait isolé, le graphe ne serait plus connexe ;
plus d'une : le nouveau sommet aurait deux voisins déjà reliés entre eux — cela fermerait un cycle.

Après $n-1$ étapes, on a $n$ sommets et $n-1$ arêtes. $\blacksquare$

Pour $n=5$ : $4$ arêtes ✓ — c'est exactement le compte trouvé aux exercices E1 et E2.

Ce que signifierait une CINQUIÈME arête

Ajoutons une arête à un arbre à $5$ sommets et $4$ arêtes. Ses deux extrémités sont déjà reliées (l'arbre est connexe), donc il existe déjà un chemin entre elles.

\text{nouveau chemin}+\text{ancien chemin}\ =\ \textbf{CYCLE.}

\boxed{\text{Toute arête ajoutée à un arbre crée EXACTEMENT un cycle.}}

Sur l'exercice E1 : l'ACM est $\{01,12,14,03\}$ . Ajoutons $24$ :

ancien chemin de $2$ à $4$ : $2\to1\to4$ ;
avec la nouvelle arête : le cycle $2\to1\to4\to2$ ✓

C'est exactement la raison pour laquelle Kruskal l'a rejetée. Le test « crée un cycle ? » et le compte « $n-1$ arêtes » sont les deux faces du même fait.

Et symétriquement : retirer une arête d'un arbre le déconnecte toujours en deux morceaux, puisqu'aucun chemin de secours n'existe. Un arbre est donc minimalement connexe — on ne peut rien enlever — et maximalement acyclique — on ne peut rien ajouter.

Le tableau des cas

Pour un graphe à $n$ sommets et $m$ arêtes :

$m$	conséquence
$m<n-1$	jamais connexe — au moins $n-m$ composantes
$m=n-1$	arbre si et seulement si connexe (ou, ce qui revient au même, sans cycle)
$m>n-1$	au moins un cycle, quelle que soit la disposition

⚠️ Le cas $m=n-1$ ne suffit pas à conclure. Le graphe de l'exercice A3 a $5$ sommets et $4$ arêtes — donc $m=n-1$ — et pourtant deux composantes : le triangle $\{0,1,2\}$ gaspille une arête dans un cycle, et il en manque une pour rejoindre $\{3,4\}$ .

Le compte d'arêtes est nécessaire, jamais suffisant. Il faut toujours lui adjoindre la connexité ou l'acyclicité.

Le nombre $m-n+1$ s'appelle le nombre cyclomatique : c'est le nombre de cycles indépendants. Pour un arbre il vaut $0$ ; pour le graphe de l'exercice A1 ( $5$ sommets, $5$ arêtes) il vaut $1$ — il y a bien exactement un cycle, le triangle $0\to1\to2\to0$ .

Ce que ça sert à faire

Ce compte est un contrôle immédiat de tout résultat du chapitre.

situation	contrôle
ACM (E1, E2)	doit avoir exactement $n-1$ arêtes
arbre des plus courts chemins (B4)	pareil
parcours BFS/DFS (A2)	son arbre a $n-1$ arêtes
structure de données (arbre binaire)	$n$ nœuds, $n-1$ liens

Un résultat qui n'a pas $n-1$ arêtes est faux, sans qu'on ait besoin de vérifier autre chose : trop peu et le graphe est déconnecté, trop et il y a un cycle. C'est le contrôle le moins cher et le plus efficace de tout le lot E.

Conséquence pratique en câblage : relier $n$ bâtiments coûte au minimum $n-1$ liaisons. Une $n$ -ième liaison n'améliore pas la connexité — elle apporte de la redondance, ce qui est un autre objectif (tolérance aux pannes) et se paie en plus.

Réponse : $n-1=4$ arêtes, parce que chaque nouveau sommet demande exactement une arête pour être rattaché sans créer de cycle ; une cinquième arête relierait deux sommets déjà connectés et créerait donc exactement un cycle.

Réponse.

n-1=4

arêtes (connexe + sans cycle) ; une

5^\text{e}

arête créerait un cycle. (Recoupement : Kruskal s'arrête à

4

arêtes ✓)

Faire cet exercice dans l'app →

Ordonnancement PERT — durée du projet

ApplicationDifficulté 3/5

Un projet a $5$ tâches $A,B,C,D,E$ de durées $3,2,4,1,2$ , avec les dépendances $A\to C$ , $B\to C$ , $C\to D$ , $C\to E$ . Quelle est la durée minimale du projet et le chemin critique ?

Indices (3)

Les dépendances forment un DAG ; on calcule les dates de début au plus tôt.

Date au plus tôt d'une tâche $=\max$ des dates de fin de ses prédécesseurs.

La durée du projet est le plus long chemin.

Correction détaillée

La méthode PERT

Un projet est un ensemble de tâches avec des dépendances. La question est : combien de temps au minimum ?

La réponse n'est ni la somme des durées (les tâches indépendantes se font en parallèle) ni la plus longue tâche : c'est la longueur du chemin critique, le plus long chemin de dépendances.

\boxed{\text{durée minimale}=\text{longueur du plus LONG chemin dans le graphe de dépendances.}}

⚠️ C'est un plus LONG chemin, pas un plus court — l'inverse des exercices du lot B. Le problème serait NP-difficile en général, mais il est facile sur un DAG (exercice A6) : il suffit de parcourir les tâches dans l'ordre topologique.

Les données

tâche	durée	dépend de
$A$	$3$	—
$B$	$2$	—
$C$	$4$	$A$ , $B$
$D$	$1$	$C$
$E$	$2$	$C$

Le graphe : $A\to C$ , $B\to C$ , $C\to D$ , $C\to E$ .

Tri topologique (exercice A6) : $A,B,C,D,E$ — chaque tâche apparaît après toutes celles dont elle dépend ✓ C'est dans cet ordre qu'on va calculer.

Étape 1 — les dates au plus tôt

La date de début au plus tôt d'une tâche est la plus tardive des fins de ses prédécesseurs — il faut que tous soient finis :

\text{début}(t)=\max_{p\ \to\ t}\big(\text{début}(p)+\text{durée}(p)\big),\qquad\text{et }0\text{ s'il n'y a pas de prédécesseur.}

tâche	calcul	début	fin
$A$	aucun prédécesseur	$0$	$0+3=3$
$B$	aucun prédécesseur	$0$	$0+2=2$
$C$	$\max(\text{fin}A,\text{fin}B)=\max(3,2)$	$\mathbf{3}$	$3+4=7$
$D$	fin $\,C$	$7$	$7+1=8$
$E$	fin $\,C$	$7$	$7+2=\mathbf{9}$

\boxed{\text{DURÉE MINIMALE}=\max(\text{fins})=\mathbf{9}}

⚠️ Le $\max$ de la ligne $C$ est le cœur du calcul. $C$ ne peut pas démarrer à $2$ (fin de $B$ ) : elle doit attendre $A$ , qui finit à $3$ . C'est la tâche la plus lente qui commande — pas la moyenne, pas la somme.

Étape 2 — le chemin critique

Énumérons les quatre chemins complets et leurs durées :

chemin	durées	total
$A\to C\to D$	$3+4+1$	$8$
$\mathbf{A\to C\to E}$	$3+4+2$	$\mathbf{9}$ ← CRITIQUE
$B\to C\to D$	$2+4+1$	$7$
$B\to C\to E$	$2+4+2$	$8$

\boxed{\text{chemin critique} : A\to C\to E,\ \text{de durée }9}

Le maximum, $9$ , coïncide bien avec la durée trouvée à l'étape 1 ✓ — c'est le contrôle qui valide le calcul, par une voie entièrement différente.

Ce que « critique » signifie

Une tâche est critique quand tout retard sur elle retarde tout le projet.

Vérifions sur $A$ (critique) : si $A$ prend $4$ au lieu de $3$ , alors $C$ démarre à $4$ , finit à $8$ , $E$ finit à $10$ . Le projet passe de $9$ à $10$ — le retard se répercute intégralement.

Vérifions sur $B$ (non critique) : si $B$ prend $3$ au lieu de $2$ , elle finit à $3$ . Mais $C$ démarrait déjà à $3$ à cause de $A$ : rien ne change, le projet reste à $9$ .

\boxed{B\ \text{dispose d'une MARGE}\ :\ \text{elle peut glisser sans conséquence.}}

C'est exactement ce que l'exercice E5 va chiffrer.

Le contraste est frappant : les deux tâches sont des prédécesseurs de $C$ , mais l'une commande le projet et l'autre non. Ce n'est ni la durée ni la position qui décide, c'est l'appartenance au chemin le plus long.

Pourquoi c'est facile ici, et difficile ailleurs

Chercher un plus long chemin est NP-difficile dans un graphe général — c'est essentiellement le problème du chemin hamiltonien.

Mais sur un DAG, c'est linéaire : sans circuit, on peut trier les sommets topologiquement, et chaque date se calcule une fois pour toutes à partir de celles déjà connues. Coût : $O(n+m)$ .

⚠️ D'où l'importance du tri topologique de l'exercice A6 : il n'est pas décoratif, il est ce qui rend PERT calculable. Et si le graphe de dépendances contenait un circuit — « $A$ avant $B$ , $B$ avant $C$ , $C$ avant $A$ » —, il n'y aurait aucun planning possible, et le blocage de Kahn le dirait.

La méthode PERT (Program Evaluation and Review Technique) a été mise au point en 1958 pour le programme de missiles Polaris ; la méthode jumelle CPM (Critical Path Method) l'a été à la même époque (1957) chez DuPont. Toutes deux sont, mathématiquement, ce calcul de plus long chemin sur un DAG.

Réponse : la durée minimale est $\mathbf{9}$ , et le chemin critique est $A\to C\to E$ ( $3+4+2$ ) ; $C$ ne peut démarrer qu'à la date $3$ , imposée par $A$ et non par $B$ .

Réponse. Durée minimale

9

, chemin critique

A\to C\to E

. (Recoupement : dates au plus tôt

[0,0,3,7,7]

, durée projet

9

✓)

Faire cet exercice dans l'app →

Marges et tâches critiques

CalculDifficulté 3/5

Pour le projet de E4 (durée $9$ ), calculer la marge de chaque tâche et identifier les tâches critiques.

Indices (3)

Calculer les dates de début au plus tard (rétro-planning depuis la fin $9$ ).

Marge $=$ date au plus tard $-$ date au plus tôt.

Une tâche est critique si sa marge est nulle.

Correction détaillée

La notion de marge

La marge d'une tâche est le retard qu'elle peut prendre sans retarder le projet. Elle se calcule en confrontant deux dates :

date	définition	sens du calcul
au plus tôt $\text{tôt}(t)$	le plus tôt où $t$ peut commencer	en avant, depuis le début
au plus tard $\text{tard}(t)$	le plus tard où $t$ peut commencer sans retarder le projet	en arrière, depuis la fin

\boxed{\text{marge}(t)=\text{tard}(t)-\text{tôt}(t)}

Une tâche de marge nulle est critique : elle n'a aucune souplesse.

Étape 1 — les dates au plus tôt (rappel de E4)

tâche	durée	tôt	fin au plus tôt
$A$	$3$	$0$	$3$
$B$	$2$	$0$	$2$
$C$	$4$	$3$	$7$
$D$	$1$	$7$	$8$
$E$	$2$	$7$	$9$

Durée du projet : $T=9$ .

Étape 2 — les dates au plus tard, EN REMONTANT

On part de la fin et on remonte. La formule est :

\text{tard}(t)=\min_{t\ \to\ s}\big(\text{tard}(s)\big)-\text{durée}(t),

et pour une tâche sans successeur, $\text{tard}(t)=T-\text{durée}(t)$ .

⚠️ Attention à la formule : on prend le min des dates de début des successeurs, puis on retranche sa propre durée. L'erreur classique est de retrancher la durée du successeur — ce qui donne un résultat faux.

tâche	successeurs	calcul	tard
$E$	aucun	$9-2$	$\mathbf{7}$
$D$	aucun	$9-1$	$\mathbf{8}$
$C$	$D$ , $E$	$\min(8,7)-4=7-4$	$\mathbf{3}$
$B$	$C$	$3-2$	$\mathbf{1}$
$A$	$C$	$3-3$	$\mathbf{0}$

Le $\min$ sur la ligne $C$ compte : $C$ doit finir avant que le premier de ses successeurs ne démarre, donc avant $7$ (date de $E$ ), et non avant $8$ .

Étape 3 — les marges

tâche	tôt	tard	marge	statut
$A$	$0$	$0$	$\mathbf{0}$	CRITIQUE
$B$	$0$	$1$	$1$	souple
$C$	$3$	$3$	$\mathbf{0}$	CRITIQUE
$D$	$7$	$8$	$1$	souple
$E$	$7$	$7$	$\mathbf{0}$	CRITIQUE

\boxed{\text{tâches critiques} : A,\ C,\ E}

Contrôle décisif : ces trois tâches sont exactement le chemin critique $A\to C\to E$ trouvé à l'exercice E4 ✓ Les deux méthodes — énumérer les chemins, ou calculer les marges — doivent toujours désigner les mêmes tâches. C'est ce qui valide le calcul.

Vérifier les marges une par une

$B$ , marge $1$ . Si $B$ prend $3$ au lieu de $2$ , elle finit à $3$ — et $C$ démarrait déjà à $3$ à cause de $A$ . Le projet reste à $\mathbf9$ ✓ Mais si $B$ prenait $4$ (retard de $2>1$ ), elle finirait à $4$ , $C$ démarrerait à $4$ , et le projet passerait à $10$ . La marge est bien de $1$ , pas plus.

$D$ , marge $1$ . $D$ finit à $8$ alors que le projet dure $9$ : elle a une unité de battement. Si $D$ prenait $2$ au lieu de $1$ , elle finirait à $9$ — juste à temps.

$A$ , marge $0$ . Tout retard sur $A$ décale $C$ , donc $E$ , donc le projet ✓ (vérifié à l'exercice E4 : $A$ à $4$ donne un projet à $10$ ).

Ces trois vérifications sont la meilleure façon de s'assurer qu'on n'a pas confondu les dates. Une marge qui ne « résiste » pas au test est mal calculée.

Ce que les marges apportent en pratique

Le chemin critique est ce qu'un chef de projet surveille en priorité : c'est la seule chaîne où un jour perdu est un jour perdu pour tout le monde.

marge	ce que ça permet
$0$	rien — surveiller de près
$>0$	absorber un aléa, décaler le démarrage, lisser les ressources

Deux usages concrets de la marge :

lissage des ressources. Si $B$ et $A$ demandent la même équipe, on peut décaler $B$ de $1$ sans coût. Cela libère la date $0$ , sans supprimer le chevauchement (il glisse sur $[1,3]$ ) : pour séparer $A$ et $B$ , il faudrait décaler $B$ de $3$ , au-delà de sa marge.
absorption des aléas. Une tâche de marge $2$ tolère deux jours de retard imprévu ; une tâche critique, aucun.

⚠️ Le chemin critique BOUGE dès qu'on modifie le projet. Si l'on accélère $E$ de $2$ à $1$ , alors $A\to C\to E$ ne dure plus que $8$ , et $A\to C\to D$ (qui durait $8$ ) devient critique à égalité. Les marges sont donc à recalculer après chaque changement — c'est le sujet de l'exercice E6.

Il existe aussi une marge libre — le retard possible sans décaler la tâche suivante — toujours $\le$ à la marge totale calculée ici. Sur ce projet, $B$ a une marge totale de $1$ et une marge libre de $1$ également, puisque son unique successeur $C$ démarre à $3$ .

Réponse : marges $A=0$ , $B=1$ , $C=0$ , $D=1$ , $E=0$ ; les tâches critiques sont $A$ , $C$ et $E$ — exactement le chemin critique de l'exercice E4.

Réponse. Marges

(0,1,0,1,0)

; tâches critiques

A,C,E

. (Recoupement : pert_tard donne marges

[0,1,0,1,0]

✓)

Faire cet exercice dans l'app →

Piloter le délai d'un projet

DémonstrationDifficulté 3/5

Dans le projet de E4-E5, le chef de projet veut raccourcir la durée totale. Sur quelles tâches doit-il agir, et qu'apporte une accélération de $B$ ou de $D$ ?

Indices (3)

Seules les tâches du chemin critique fixent la durée totale.

Accélérer une tâche à marge non nulle ne fait que consommer cette marge.

Le chemin critique est $A\to C\to E$ ; $B$ et $D$ ont une marge de $1$ .

Correction détaillée

La question, et la réponse en une ligne

Le chef de projet veut raccourcir la durée totale. Sur quelles tâches agir ?

\boxed{\text{UNIQUEMENT sur les tâches CRITIQUES : }A,\ C,\ E.}

Accélérer une tâche non critique ne sert à RIEN — elle ne fait qu'augmenter sa marge, déjà positive. C'est le résultat le plus contre-intuitif de la gestion de projet, et le plus utile.

La vérification, tâche par tâche

On accélère chaque tâche d'une unité et l'on recalcule la durée du projet (initialement $9$ ) :

on accélère	marge	nouvelle durée	gain
$\mathbf{A}$ ( $3\to2$ )	$0$	$\mathbf{8}$	$\mathbf{-1}$ ✓
$\mathbf{C}$ ( $4\to3$ )	$0$	$\mathbf{8}$	$\mathbf{-1}$ ✓
$\mathbf{E}$ ( $2\to1$ )	$0$	$\mathbf{8}$	$\mathbf{-1}$ ✓
$B$ ( $2\to1$ )	$1$	$9$	$\mathbf{0}$ ✗
$D$ ( $1\to0$ )	$1$	$9$	$\mathbf{0}$ ✗

Le tableau est sans appel : les trois tâches critiques rapportent chacune une unité, les deux autres rien du tout.

Pourquoi accélérer $B$ ne sert à rien

$B$ dure $2$ et finit à la date $2$ . Mais $C$ ne démarre qu'à $3$ , parce qu'elle attend $A$ .

\text{Accélérer }B\text{ de }2\text{ à }1\ \Longrightarrow\ B\text{ finit à }1\ \Longrightarrow\ C\text{ démarre TOUJOURS à }3.

$B$ attendait déjà. La faire finir plus tôt ne fait qu'allonger son attente : sa marge passe de $1$ à $2$ .

Le chemin $B\to C\to E$ passe de $8$ à $7$ — mais comme $A\to C\to E$ reste à $9$ , c'est ce dernier qui commande.

\text{durée}=\max(\text{tous les chemins})\ :\ \text{diminuer un chemin NON maximal ne change pas le max.}

Pourquoi accélérer $D$ ne sert à rien non plus

$D$ commence à $7$ et finit à $8$ . Le projet, lui, dure $9$ — c'est $E$ qui le termine.

Même en rendant $D$ instantanée ( $1\to0$ ), elle finirait à $7$ et le projet durerait toujours $\mathbf9$ , imposé par $E$ .

\text{Il faudrait accélérer }E,\text{ pas }D.

Cas particulier instructif : $D$ et $E$ démarrent toutes deux à $7$ et sont en parallèle. C'est la plus longue des deux qui compte, donc $E$ ( $2$ ) et non $D$ ( $1$ ). Réduire la plus courte de deux branches parallèles est toujours sans effet.

⚠️ Le piège : le chemin critique BOUGE

Accélérer une tâche critique fonctionne — mais pas indéfiniment.

Accélérons $E$ de $2$ à $1$ . Le projet passe à $8$ . Recalculons les chemins :

chemin	avant	après
$A\to C\to D$	$8$	$\mathbf{8}$
$A\to C\to E$	$\mathbf{9}$	$\mathbf{8}$
$B\to C\to D$	$7$	$7$
$B\to C\to E$	$8$	$7$

Il y a maintenant DEUX chemins critiques, tous deux à $8$ : $A\to C\to D$ et $A\to C\to E$ .

Conséquence : accélérer $E$ une seconde fois ne rapporterait plus rien — il faudrait accélérer $D$ aussi, ou bien $A$ ou $C$ , qui sont sur les deux chemins.

\boxed{\text{Après chaque accélération, RECALCULER le chemin critique.}}

C'est l'erreur classique du pilotage de projet : on optimise une fois, on croit pouvoir continuer sur la même tâche, et le gain s'arrête sans qu'on comprenne pourquoi.

La stratégie complète, et son coût

La marche à suivre, à chaque itération :

calculer le chemin critique ;
parmi ses tâches, accélérer la moins chère ;
recalculer — le chemin critique a pu changer ;
recommencer tant que le gain vaut son prix.

Le meilleur candidat ici est $C$ , et pour une raison structurelle : elle est sur les quatre chemins. L'accélérer bénéficie donc à tous en même temps, alors qu'accélérer $E$ ne sert que deux chemins sur quatre.

tâche critique	sur combien de chemins	robustesse du gain
$A$	$2$ ( $A\to C\to D$ , $A\to C\to E$ )	moyenne
$\mathbf{C}$	$\mathbf{4}$ — tous	la meilleure
$E$	$2$	moyenne

C'est le problème du crashing en gestion de projet : chaque accélération a un coût, et l'on cherche le meilleur rapport gain de durée / coût. Formalisé, c'est un programme linéaire — ce qui referme la boucle avec le chapitre Optimisation.

Réponse : agir sur $A$ , $C$ ou $E$ — chacune fait passer le projet de $9$ à $8$ ; accélérer $B$ ou $D$ ne change RIEN, car elles disposent déjà d'une marge de $1$ . Et après toute accélération, il faut recalculer : dès que $E$ passe à $1$ , le chemin $A\to C\to D$ devient critique à son tour.

Réponse. Agir sur

A,C,E

(critiques) ; accélérer

B

ou

D

est sans effet sur le délai. (Recoupement : marges

1

pour

B,D

— pur battement ✓)

Faire cet exercice dans l'app →

Exercices corrigés — Recherche opérationnelle & graphes

Les 18 exercices

Degrés & lemme des poignées

Parcours BFS et DFS

Composantes connexes

Ponts de Königsberg (Euler)

Graphe biparti & cycle impair

Tri topologique d'un DAG

Algorithme de Dijkstra

Bellman-Ford & poids négatifs

Floyd-Warshall (toutes paires)

Reconstruction du chemin

Détection d'un cycle négatif

Pourquoi Dijkstra échoue en négatif

Arbre couvrant minimal (Kruskal)

Prim vs Kruskal

Arbre couvrant : nombre d'arêtes

Ordonnancement PERT — durée du projet

Marges et tâches critiques

Piloter le délai d'un projet

S'entraîner davantage sur recherche opérationnelle & graphes

tâche	durée	tôt	fin au plus tôt
$A$	$3$	$0$	$3$
$B$	$2$	$0$	$2$
$C$	$4$	$3$	$7$
$D$	$1$	$7$	$8$
$E$	$2$	$7$	$9$

tâche	durée	tôt	fin au plus tôt
$A$	$3$	$0$	$3$
$B$	$2$	$0$	$2$
$C$	$4$	$3$	$7$
$D$	$1$	$7$	$8$
$E$	$2$	$7$	$9$

tâche	durée	tôt	fin au plus tôt
$A$	$3$	$0$	$3$
$B$	$2$	$0$	$2$
$C$	$4$	$3$	$7$
$D$	$1$	$7$	$8$
$E$	$2$	$7$	$9$