Modèles et Algorithmes pour les Graphes (MAG)

Équipe pédagogique :

Achour Mostefaoui <[email protected]> : CM et TD (G2 Info, G1 Miage)

César Viho <[email protected]> : TD (G3 Info, G2 Miage)

Olivier Dameron <[email protected]> : TD (G4 Info)

Myriam Bontonou <[email protected]> : TD (G1 Info)

Université de Rennes et INRIA Rennes Bretagne-Atlantique

Contenu du cours

1. Généralités sur les graphes : exemples de graphes comme modèles de

situations concrètes, et questions associées pour découvrir quelques notions
(chemins, PCC, fermeture transitive, descendance, clique, CFC, arbres, etc.).
2. Représentation des graphes, structures de données associées : plusieurs
représentations (matrice d’adjacence, liste des prédécesseurs, liste des
successeurs), équivalence et passage de l’une à l’autre.
3. Notions de complexité des algorithmes (ordre de grandeur des fonctions).
4. Parcours en profondeur Depth-first search (DFS) et en largeur Breadth-first
search (BFS). Directed Acyclic Graph (DAG).
5. L’arbre couvrant de poids minimal (ACM) (Minimum spanning tree) : algorithme
de Prim et algorithme de Kruskal.
6. Le problème du flot maximum dans les réseaux de transport.
7. Les problèmes du plus court/long chemin (PCC/PLC) :
algorithme de Dijkstra. Binary heap (tas binaire) ;
algorithme de Bellman-Ford. Découverte des circuits négatifs ;
PCC/PLC dans un DAG (ordre topologique).
Programmation dynamique. Algorithmes pour ordonnancer les tâches.
8. Chemins, flots et programmes linéaires dans les graphes.
t
2/186 2/186
Bibliographie

Ce cours est fondé essentiellement sur les références suivantes.

Algorithms, S. Dasgupta, C. H. Papadimitriou, et U. V. Vazirani, McGraw-Hill
2006 (the undergraduate Algorithms course at Berkeley and U.C. San Diego)
Graphes et algorithmes, Michel Gondran et Michel Minoux, Eyrolles, 1995
Introduction à l’algorithmique, T. Cormen, C. Leiserson, R. Rivest, DUNOD,
1994.

3/186 3/186
Généralités, notions de base, exemples d’applications

4/186 4/186
Définitions formelles et notations : graphe, graphe orienté et non orienté

Un graphe est un doublet G = (V , E ), où V = {v1 , v2 , . . . , vn } est l’ensemble des

sommets/noeuds et E est un ensemble de couples (u , v ) ∈ V × V . Si tous les
couples (u , v ) ∈ E sont symétriques, le graphe est dit non orienté. Sinon, le graphe
est orienté. Un couple symétrique / non ordonné est dit une arête. Un couple non
symétrique / ordonné est dit un arc.

F IGURE 1 – Un graphe non orienté F IGURE 2 – Un graphe orienté.

5/186 5/186
Exemples de graphes
Obtention d’un diplôme Master d’informatique (Exam. décembre 2008)

Pour obtenir un Master d’informatique, il est nécessaire d’avoir passé un certain

nombre de modules. Chaque module demande un certain nombre de prérequis. Un
master simplifié pourrait se composer (prérequis entre parenthèses) de :
Système (Programmation) ;
MAG (Programmation, Math Discrètes) ;
Sécurité réseau (Système, Initiation réseau) ;
Initiation réseau (Programmation, MAG) ;
Systèmes répartis (MAG, Système, Initiation réseau).

1. Modéliser les prérequis à l’aide d’un graphe.

2. Quel est le nombre minimum de semestres pour obtenir ce master ? On suppose
bien sur que vous passez tous les examens avec succès, que chaque module
dure un semestre et est enseigné chaque semestre. Le nombre de modules
suivis par un étudiant pendant un semestre n’est pas limité et il n’y a pas de
problème d’emploi du temps. Indiquer l’algorithme utilisé et justifiez votre choix.
3. Un étudiant décide d’étudier un module dès qu’il a obtenu les modules
prérequis. Quel est le nombre maximum de modules qu’il devra suivre
simultanément en appliquant cette stratégie ? Quel algorithme permet de le
calculer ? Justifiez votre choix.
6/186 6/186
Obtention d’un diplôme Master d’informatique : suite 1

1. Modéliser les prérequis à l’aide d’un graphe.

Modélisation à l’aide d’un graphe : les sommets correspondent aux modules, les arcs
- aux prérequis.

7/186 7/186
Obtention d’un diplôme Master d’informatique : suite 2

1. Quel est le nombre minimum de semestres pour obtenir ce master ?

2. Quel est le nombre maximum de modules qu’il devra suivre simultanément ?

Les modules sont ordonnancés de gauche à droite sur l’axe horizontal.

8/186 8/186
Obtention d’un diplôme Master d’informatique : suite 3

1. Quel est le nombre minimum de semestres pour obtenir ce master ?

2. Quel est le nombre maximum de modules qu’il devra suivre simultanément

Au moins 4 semestres sont nécessaires pour obtenir ce master. Cela peut se

calculer par un algorithme du plus long chemin dans un graphe sans circuit.
Un étudiant peut suivre maximum deux modules par semestre. Nous allons
étudier l’algorithme adéquat qui permet de calculer ce nombre.

9/186 9/186
Exemple de graphes : suite
Construction d’un pavillon
La construction d’un pavillon demande la réalisation d’un certain nombre de tâches.
La liste des tâches à effectuer, leur durée et les contraintes d’antériorités à respecter
sont données dans le table ci-dessus. Le travail commençant à la date 0, on cherche
un planning des opérations qui permet de minimiser la durée totale.
Code tâche libellé durée antériorité
(semaines)
A Travaux de maçonnerie 7 -
B Charpente de la toiture 3 A
C Toiture 1 B
D Installation électrique 8 A
E Façade 2 D,C
F Fenêtres 1 D,C
G Aménagement du jardin 1 D,C
H Travaux de plafonnage 3 F
J Mise en peinture 2 H
K Emménagement 1 E,G,J

F IGURE 3 – Liste des tâches, durée et contraintes.

Devoir maison : Illustrer la construction de ce pavillon par un graphe adéquat.

10/186 10/186
Définitions formelles et notations : chemins, circuit, chaîne, cycle

Un chemin P dans un graphe orienté G est une suite d’arcs dont les extrémités
droites/gauches coïncident de la façon suivante :
P = ((u0 , u1 ), (u1 , u2 ), (u2 , u3 ), . . . , (uk −1 , uk )). La longueur du P est le nombre
d’arcs (ici k ).
Si u0 = uk , le chemin est appelé circuit.
Un chemin élémentaire est défini par une suite de sommets sans répétition (sauf
pour le premier et le dernier sommet).
Si le graphe est non orienté, on utilise chaîne et cycle à la place de chemin et
circuit.
Un graphe sans cycle/circuit est appelé acyclique / sans circuit.
Un graphe non orienté tel que chaque couple de sommets est connecté par une
chaîne est dit connexe.
Un graphe orienté tel que chaque couple de sommets (u , v ) est connecté par un
chemin dans les deux sens (c.-à-d. de u à v et de v à u) est dit fortement
connexe. On dit aussi que les sommets u et v sont mutuellement accessibles.
Un graphe, non orienté, connexe et acyclique est dit arbre.

11/186 11/186
Vocabulaire

Soit le graphe orienté G = (V , E ).

Pour un arc (x , y ) ∈ E, x est l’origine et y est l’extrémité de l’arc.
On dit aussi que y est successeur de x, ou que x est prédécesseur de y .
Γ+ (x ) = {y ∈ V | (x , y ) ∈ E } est l’ensemble des successeurs de x.
Γ−1 (x ) = {z ∈ V |(z , x ) ∈ E } est l’ensemble des prédécesseurs de x.
d + (x ) est le degré sortant du sommet x, c’est-à-dire le nombre d’arcs sortant
de x.
d − (x ) est degré entrant du sommet x, c’est-à-dire le nombre d’arcs dirigés vers
le sommet x.
d (x ) = d + (x ) + d − (x ) est le degré de x.
Un chemin P allant de x à y , dont on ne précise pas les sommets intermédiaires,
sera noté : P = x ; y . y est alors un descendant de x et x un ascendant de y .
Dans le cas d’un graphe non-orienté le degré d’un sommet est le nombre de liens
(arêtes ou arcs) reliant ce sommet, avec les boucles comptées deux fois.

12/186 12/186
Vocabulaire : Illustration pour le problème "Obtention d’un diplôme"

Γ+ (PROG) = {MAG, InR , Sys} : l’ensemble des successeurs de PROG,

d + (PROG) = 3.
Γ− (PROG) = 0/ , d − (PROG) = 0 : PROG est un sommet source.
Γ−1 (SysRep) = {InR , MAG, Sys} : l’ensemble des prédécesseurs de SysRep.
d − (SysRep) = 3
Γ+ (SysRep) = 0,/ d + (SysRep) = 0 : SysRep est un sommet target/puits

d + (MAG) = 2, d − (MAG) = 2 : MAG est un sommet intermédiaire.

13/186 13/186
Vocabulaire

Soit le graphe G = (V , E ) où |V | = n et |E | = m. On dit parfois que G est d’ordre n.

Deux sommets sont indépendants s’ils ne sont pas connectés, c’est-à-dire pas
adjacents.
Il existe 2 cas extrêmes pour l’ensemble de ses arêtes : soit le graphe n’a
aucune arête : on parle alors de stable. Soit toutes les arêtes possibles pouvant
relier les sommets 2 à 2 sont présentes : le graphe est dit alors complet.
On dit aussi qu’ensemble de sommets est indépendant (ou stable) s’il n’y a pas
deux de ses sommets adjacents.
Une clique est un sous-graphe complet.
Un stable est un sous-graphe sans arête.
Pour un graphe général, il est souvent intéressant de rechercher de tels sous-graphes.

14/186 14/186
Exemple de graphes : (clique, stable)

Planning d’examen

Les cinq étudiants : Dupont, Dupond, Durand, Duval et Duduche doivent passer
certaines épreuves parmi les suivants : Français, Anglais, Dessin, Couture,
Mécanique et Solfège. L’examen se déroulant par écrit, on désire que tous les
étudiants qui doivent subir une même épreuve le fassent simultanément. Chaque
étudiant ne peut se présenter qu’à une épreuve au plus chaque jour. Ci-dessous la
liste des épreuves que doit passer chaque étudiant : Dupont : Français, Anglais,
Mécanique ; Dupond : Dessin, Couture ; Durand : Anglais, Solfège ; Duval : Dessin,
Couture, Mécanique ; Duduche : Dessin, Solfège.
1. Quel est le nombre maximum d’épreuves que l’on peut organiser le même jour ?
2. Quel est le nombre minimum de jours nécessaires à l’organisation de toutes les
épreuves ?

15/186 15/186
Planning d’examen : solution

On construit le graphe G = (V , E ) tel que V = {F , A, D , C , M , S } (un sommet par

épreuve) et une arête relie deux solmmets si et seulement si un même candidat doit
subir les épreuves correspondants.
1. Le nombre maximum d’épreuves que l’on peut organiser le même jour est donné
alors par le cardinal du stable maximum {F , S , C }, donc 3.
2. Pour trouver le nombre minimum de jours nécessaires à l’organisation de toutes
les épreuves on peut appliquer l’algorithme suivant : tant qu’il y un graphe
non-vide, on trouve le stable max et on enlève du graphe ; sur le graphe ainsi
réduit on applique la même stratégie. La réponse est trois jours dans le cas
consideré ; le 1e jour on organise {F , S , C }, le 2e jour on organise {A, D }, le
dernier jour on organise {M },

16/186 16/186
Exemple des graphes : les 7 ponts de Königsberg

La ville de Königsberg sur le Pregel et ses 7 ponts. Déterminer s’il existe ou non une
promenade dans les rues de Königsberg permettant, à partir d’un point de départ au
choix, de passer une et une seule fois par chaque pont, et de revenir à son point de
départ. Ce problème (résolu par Leonhard Euler en 1736) est considéré comme
l’origine de la théorie des graphes.

17/186 17/186
Vocabulaire et modélisation

On appelle chaîne eulérienne (resp. cycle eulérien) une chaîne (resp. un cycle)
qui emprunte une fois et une seule chaque arête du graphe.
Théorème d’Euler : Un graphe connexe a une chaîne eulérienne si et
seulement si tous ses sommets ont un degré pair ou tous ses sommets ont un
degré pair sauf deux sommets.
On peut démontrer que :
si le graphe n’a pas de sommet impair, alors il a un cycle eulérien.
un graphe ayant plus de deux sommets impairs ne possède pas de chaîne
eulérienne (donc non pour le graphe de la ville de Königsberg).
si le graphe a deux sommets impairs, ce sont les extrémités de la chaîne eulérienne.

18/186 18/186
Les 7 ponts de Königsberg : Modélisation et solution

F IGURE 5 – Représentation des ponts de

F IGURE 4 – Les 7 ponts de Königsberg Königsberg sous forme d’un graphe non-orineté.

L’analyse des degrés des sommets du graphe de la figure (5) montre que
d (A) = 3, d (B ) = 3, d (C ) = 5, d (D ) = 3.
Ce graphe a plus de deux sommets impairs et ne possède donc pas de cycle eulérien
d’après le théorème d’Euler.

19/186 19/186
Exemples de graphes : suite

Modéliser l’accessibilité au centre-ville de l’Utopia (examen 2011/12)

Un ingénieur du service technique de la ville Utopia propose, pour la zone centrale, le

plan sens unique représenté à la figure (6). Avant d’adopter le plan, il convient
d’examiner s’il autorise la circulation des automobiles, c’est à dire s’il permet d’aller
de n’importe quel point à n’importe quel autre.
1. Enumérer les algorithmes vus en cours pouvant résoudre ce problème. Donner
la complexité de ces algorithmes pour un graphe quelconque G = (V , E ).
2. Appliquer l’algorithme de votre choix sur le graphe de la figure. Le calcul à
chaque itération sera clairement indiqué.
3. Vous constaterez facilement que le plan n’est pas acceptable. Quelles sont les
zones où les sommets sont mutuellement accessibles ? Quelle est la
dénomination de ces zones dans la terminologie spécifique pour l’algorithme en
considération ?
4. Trouver le nombre minimum de rues tel que l’inversion du sens de circulation
dans chacune de ces rues rend ce plan acceptable. Combien de solutions avez
vous trouvées ? Quelles sont ces solutions ?

20/186 20/186
Modéliser l’accessibilité au centre-ville de l’Utopia

1 2 3 4

5 6 7 8 9

10 11 12 13 14 15

F IGURE 6 – Le plan de sens unique du centre-ville.

21/186 21/186
Modéliser l’accessibilité au centre-ville de l’Utopia : solution

1 2 3 4

5 6 7 8 9

10 11 12 13 14 15

F IGURE 7 – Les sommets jaunes et verts ne sont pas joignables à partir des sommets rouges.
Les trois zones coloriées en rouge, jaune et vert sont des Composantes Fortements Connexes
(CFC)

22/186 22/186
Modéliser l’accessibilité au centre-ville de l’Utopia

1 2 3 4

5 6 7 8 9

10 11 12 13 14 15

F IGURE 8 – Le plan devient acceptable si on inverse au moins un arc (par exemple si l’arc
(14, 15) devient (15, 14)).

23/186 23/186
Graphe de de Bruijn : à voir en TD

Un graphe de de Bruijn est un graphe

orienté qui permet de représenter les
chevauchements de longueur n − 1
entre tous les mots de longueur n sur
un alphabet donné.
Le graphe de de Bruijn B (k , n) d’ordre
n sur un alphabet A à k lettres est
construit comme suit. Les sommets de
B (k , n) sont étiquetés par les k n mots
de longueur n sur A. Si u et v sont
deux sommets, il y a un arc de u à v
s’il existe deux lettres a et b, et un mot
x, tels que u = ax et v = xb. La
présence d’un arc signifie donc un
chevauchement maximal entre deux
mots de même longueur.
Le graphe B (2, 3) ci-contre est
construit sur un alphabet binaire
A={0, 1} pour des mots de longueur
n = 3.

24/186 24/186
Réseaux : une application importante pour les graphes

Soit G = (X , U , C ) un graphe connexe orienté (réseau). A ∀ arc u on affecte une

valeur (capacité) cu qui est une borne supérieure du flot sur l’arc.
Soit deux sommets particuliers s ∈ X (source) et t ∈ X (puits). Considérons le
graphe G0 = (X , U 0 ) où U 0 = U ∪ {t , s}. L’arc (t , s) est appelé l’arc de retour du
flot (numéroté 0). Notons n = |X | et m = |U |.

F IGURE 9 – Un réseau G = (X , U , C ). Chaque arc u ∈ U est muni d’une capacité cu .

On cherche dans G un flot de s à t compatible avec la capacité des arcs et qui soit de
valeur maximale.

25/186 25/186
Définition d’une coupe et de sa capacité
Soit le réseau G = (X , U , C ). Une coupe séparant s et t (notée s − t) est une
partition (L, R ) de X , telle que s ∈ L et t ∈ R = L̄ = X \ L.
La capacité C (L, R ) de la coupe s − t est définie par C (L, R ) = ∑ ce où
e∈ω+ (L)
ω+ (L) représente le sous-ensemble d’arcs qui ont leurs extrémités initiales dans
L et leurs extrémités terminales dans L̄ = R.
Lemme : La valeur maximale d’un flot de s à t compatible avec cu n’excède
jamais la capacité d’une coupe séparant s et t.

F IGURE 10 – Une coupe s − t définie par la partition L = {s, a, b} and R = {c , d , e, t }. Chaque

flot s ; t doit passer de L à R et traverser ainsi la coupe s ; t. Donc, la valeur d’un flot ne peut
jamais dépasser la valeur de la capacité C (L, R ) qui vaut 7. Ainsi, chaque flot s ; t de valeur 7,
est maximal (certificat d’optimalité).

26/186 26/186
Exemple de graphes : Le problème de mariage (couplage)

Soit G = (V , E ) un graphe. Rappel :

Un couplage ou appariement M (en anglais matching) est un ensemble d’arêtes
deux à deux non adjacentes.
Une couverture C est un ensemble de sommets tel que chaque arête est
incidente avec au moins un sommet de C.
Soit un graphe biparti G(U ∪ V , E ). L’ensemble des arêtes représente les couples
compatibles. Il s’agit de trouver le couplage maximum (un couplage contenant le plus
grand nombre possible d’arêtes) en satisfaisant les contraintes des couples
compatibles.

F IGURE 11 – Il s’agit de marier ces personnes en satisfaisant les contraintes des couples
compatibles. On peut voir ici (par énumération) qu’on ne peut marier que trois couples.

Montrer que ce problème se réduit au problème du flot maximum.

27/186 27/186
Le problème du flot maximum : un grand classique du domaine
Soit R = (X , U , C ) un graphe connexe orienté (réseau). A ∀ arc u on affecte une
valeur (capacité) cu qui est une borne supérieure du flux sur l’arc.
Soit deux sommets particuliers s ∈ X (source) et t ∈ X (puits). Considérons le
graphe G0 = (X , U 0 ) où U 0 = U ∪ {t , s}.
la loi de conservation du flot doit être satisfaite pour chaque sommet.
Ci-dessous le problème de mariage modélisé comme un problème du flot
maximum. Les capacités sont fixées à 1 partout.

28/186 28/186
Le problème du flot maximum : solution

Dans le graphe de la figure ci-dessous à gauche on cherche le nombre

maximum de chemins sommet-disjoints (donc ils ne se croisent pas) de s à t.
La solution est donnée sur la figure à droite. On trouve trois chemins
sommet-disjoints de s à t. Cette valeur correspond à la valeur du couplage
maximum.

29/186 29/186
Représentations des graphes : listes de successeurs

Soit le graphe G = (V , E ) où |V | = n et |E | = m. G peut être représenté en mémoire

soit par des listes d’adjacence, soit par une matrice d’adjacence.
Un graphe et sa représentation par des listes de successeurs.

30/186 30/186
Représentations des graphes : matrice d’adjacence

Soit le graphe G = (V , E ) où |V | = n et |E | = m. G peut être représenté en mémoire

soit par des listes d’adjacence, soit par une matrice d’adjacence.
La matrice d’adjacence d’un graphe G = (V , E ) où |V | = n, est une matrice
carrée de taille n et définie par :

1 si (u , v ) ∈ E
A(u , v ) =
0 sinon

31/186 31/186
Représentations des graphes : matrice d’incidence sommet/arc

Soit le graphe G = (V , E ) où |V | = n et |E | = m.
La matrice d’incidence sommet/arc d’un graphe orienté est une matrice
A = [ai ,j ] i = 1, 2, . . . , |V | et j = 1, 2, . . . , |E | telle que :

 +1 si l’arc uj est sortant pour le sommet i
ai ,j = −1 si l’arc uj est entrant pour le sommet i
0 sinon


u1 u2 u3 u4 u5
s +1 +1 0 0 0
A= t 0 0 0 −1 −1
a −1 0 +1 +1 0
b 0 −1 −1 0 +1

Remarque : les valeurs en bleu sont les poids (longueurs) des arcs.

32/186 32/186
 Complexité des algorithmes :
Ordre de grandeur des fonctions

33/186 33/186
Analyse des algorithmes

But : Etre capable de comparer les algorithmes et pouvoir affirmer :

Sur toute machine, et quel que soit le langage de programmation, l’algorithme A1 est
meilleur que l’algorithme A2 pour les données de grande taille.

Critères d’évaluation des algorithmes

Validité : s’effectue à la base de la notion "invariant de boucle". Cet aspect sera

vu en détail dans la 2e partie du cours.
Complexité temporelle : définir les notions de "taille de l’entrée" et de "temps
d’exécution".
Complexité spatiale : définir la notion de "place mémoire".
Simplicité et clarté : tenir compte du temps humain à implanter le code.
Précision : pour un algorithme numérique.
Stabilité : pour un algorithme de tri par exemple.
Conclusion : Savoir faire des compromis et prendre en compte le contexte dans
lequel le programme sera développé et utilisé.

34/186 34/186
Tri-Insertion

Algorithm 1 Insertion-sort(A = [a1 , a2 , . . . , an ])

Require: An array A = [a1 , a2 , . . . , an ] of n numbers.

Ensure: An array A = [a10 , a20 , . . . , an0 ] s.t. a10 ≤ a20 ≤ . . . an0 and [a10 , a20 , . . . , an0 ] is a
permutation of [a1 , a2 , . . . , an ].
1: for j = 2 to n do
2: clef ← A[j ]
3: i ← j −1
4: while i > 0 and A[i ] > clef do
5: A[i + 1] ← A[i ]
6: i ← i −1
7: end while
8: A[i + 1] ← clef
9: end for

35/186 35/186
Analyse de complexité de Tri-Insertion

On cherche une mesure du temps d’exécution T (n) qui doit être la plus
indépendante possible de l’implémentation et de la machine.
Associons une constante ci à chaque exécution de la i-ème ligne.
Soit tj le # de fois que le test de la ligne 4 est exécuté pour cette valeur de j.

Tri-Insertion(A(n)) coût # fois

1: for j = 2 to n do 1: c1 n
2: clef ← A[j ] 2: c2 n−1
3: i ← j −1 3: c3 n−1
4: while i > 0 and Ai > clef do 4: c4 ∑nj=2 tj
5: A[i + 1] ← A[i ] 5: c5 ∑nj=2 (tj − 1)
6: i ← i −1 6: c6 ∑nj=2 (tj − 1)
7: end while 7: 0
8: A[i + 1] ← clef 8: c8 n−1
9: end for 9: 0

n n
T (n) = c1 n + (c2 + c3 + c8 )(n − 1) + c4 ∑ tj + (c5 + c6 ) ∑ (tj − 1) (1)
j =2 j =2

36/186 36/186
Influence de la nature de données sur le temps d’exécution

On différencie 3 cas possibles

le meilleur des cas (best case).
C’est celui où le tableau est déjà trié. Dans ce cas tj = 1 pour j = 2, 3, . . . , n et

T (n) = c1 n + (c2 + c3 + c4 + c8 )(n − 1) = an + b (fonction linéaire) (2)

le pire des cas (worst case) ; C’est celui où le tableau est trié dans l’ordre
décroissant. Dans ce cas tj = j pour j = 2, 3, . . . , n et on obtient :
n n
T (n) = c1 n + (c2 + c3 + c8 )(n − 1) + c4 ∑ tj + (c5 + c6 ) ∑ (tj − 1)
j =2 j =2

n(n + 1) (3)
= ( c1 + c2 + c3 + c8 )n − (c2 + c3 + c8 ) + c4 ( − 1)
2
n (n − 1 )
+ (c5 + c6 )
2
= an2 + bn + c (fonction quadratique) (4)

le cas moyen (average case). Dans ce cas en moyenne tj = j /2 et on obtient

aussi une fonction quadratique.

37/186 37/186
Analyse de complexité de Tri-Insertion

On a fait les hypothèses simplificatrices suivantes :

on a ignoré le coût réel de chaque ligne en considérant un coût abstrait ci ;
même ce coût abstrait était après simplifié pour donner le temps d’exécution
comme une fonction linéaire/quadratique ;
dernière simplification : on ne considère que le 1er terme des polynômes. On
s’intéresse donc au comportement asymptotique des algorithmes (pour n
suffisamment grand).
Remarques : Pour chaque algorithme on peut mettre en évidence une ou plusieurs
opérations qui sont fondamentales au sens où le temps d’exécution est proportionnel
au nombre de ces opérations. Il est alors possible de comparer les algorithmes selon
cette mesure simplifiée.
Exemples pour opérations fondamentales : comparaisons, additions, multiplications,
lectures ; accès à la mémoire secondaire, etc.

38/186 38/186
Ordre de grandeur des fonctions : définitions principales

Notion O Soient deux fonctions f , g : N → R+ . On dit que f (n) = O (g (n)) ssi

∃c > 0, ∃n0 tq ∀n > n0 , f (n) ≤ cg (n).
Prononcer : f est en grand O de g (f égale grand O de g ; f est d’ordre au plus de g)
Notion Ω Soient f , g : N → R+ . On dit que f (n) = Ω(g (n)) ssi ∃c > 0, ∃n0 tq
∀n > n0 , cg (n) ≤ f (n).
Prononcer : f est en grand Ω de g (f égale grand Ω de g ; f est d’ordre au moins de g)
Notion Θ Soient f , g : N → R+ . On dit que f (n) = Θ(g (n)) ssi ∃c1 > 0, ∃c2 > 0, ∃n0 tq
∀n > n0 , c1 g (n) ≤ f (n) ≤ c2 g (n).
Prononcer : f est en grand Θ de g (f égale grand Θ de g ; f est de même ordre que g)
Notion o Soient f , g : N → R+ . On dit que f (n) = o(g (n)) ssi ∀c > 0, ∃n0 tq
∀n > n0 , 0 ≤ f (n) < cg (n). On dit que f est négligeable par rapport à g.
Notion ω Soient f , g : N → R+ . On dit que f (n) = ω(g (n)) ssi ∀c > 0, ∃n0 tq
∀n > n0 , cg (n) < f (n). On dit que g est une borne inférieure stricte de f .

39/186 39/186
Propriétés principales liées à l’ordre de grandeur des fonctions

Transitivité
f (n) = Θ(g (n)) et g (n) = Θ(h(n)) =⇒ f (n) = Θ(h(n))
f (n) = O (g (n)) et g (n) = O (h(n)) =⇒ f (n) = O (h(n))
f (n) = Ω(g (n)) et g (n) = Ω(h(n)) =⇒ f (n) = Ω(h(n))
f (n) = o(g (n)) et g (n) = o(h(n)) =⇒ f (n) = o(h(n))
f (n) = ω(g (n)) et g (n) = ω(h(n)) =⇒ f (n) = ω(h(n))
Reflexivité
f (n) = O (f (n)), f (n) = Θ(f (n)), f (n) = Ω(f (n))
Symétrie
f (n) = Θ(g (n)) ssi g (n) = Θ(f (n))
Symétrie transposée
f (n) = O (g (n)) ssi g (n) = Ω(f (n))
f (n) = o(g (n)) ssi g (n) = ω(f (n))
Analogie entre le comportement asymptotique des fonctions f et g et la
comparaison de 2 nombres réels a et b.
f (n) = O (g (n)) ' a ≤ b
f (n) = Ω(g (n)) ' a ≥ b
f (n) = Θ(g (n)) ' a = b : On dit que f et g sont asymptotiquement équivalents
f (n) = o(g (n)) ' a < b : On dit que f est négligeable devant g
f (n) = ω(g (n)) ' a > b

40/186 40/186
Propriétés principales liées à l’ordre de grandeur des fonctions

Classement de quelques fonctions

√
Θ(1) < Θ(log n) < Θ( n) < Θ(n) < Θ(n log n) < Θ(na ) < Θ(c n ) < Θ(n!) < Θ(nn )
où a > 1 et c > 1.

41/186 41/186
Critères pour classer les fonctions : Soit f , g , : N → R+ .

Lemme 1
f (n )
a) lim = a 6= 0 ⇒ f = Θ(g ) et g = Θ(f )
n→∞ g (n)
f (n )
b) lim = 0 ⇒ f = o(g ) ⇒ f = O (g ) et f 6= Θ(g )
n→∞ g (n)
f (n )
c) lim = ∞ ⇒ g = o(f ) ⇒ g = O (f ) et g 6= Θ(f )
n→∞ g (n)
Remarque : Le Lemme 1 est un critère suffisant. Les réciproques de a), b), c) sont
f (n)
fausses. Si la limite lim n’existe pas, il faut revenir aux définitions.
n→∞ g (n)

n si n est impair
Exemple 1 : Soit f (n) = et g (n) = 2n, ∀n
2n si n est pair
f (n ) g (n)
alors lim @, mais f = Θ(g ) puisque 2 ≤ f (n) ≤ g (n).
n→∞ g (n)
f (n)
Lemme 2 : Si lim n’est pas déterminée ( 00 ou ∞ ∞ ) on peut appliquer la règle de
n→∞ g (n)
0
f (n ) f (n ) 0
f (n)
l’Hôpital : lim 0 ∃ on a lim = lim 0 .
n→∞ g (n) n→∞ g (n) n→∞ g (n)
2
n 2n 2
Exemple 2 : n2 = o(en ) car lim n = lim n = lim n = 0.
n→∞ e n→∞ e n→∞ e
42/186 42/186
 Exploration des graphes :
Parcours en profondeur et parcours en largeur

43/186 43/186
Exploration des graphes

L’exploration d’un graphe (c.-à-d. la visite de tous les sommets joignables à partir
d’un sommet de départ) est une opération fréquente et importante.
elle ressemble à l’exploration d’un labyrinthe
pour explorer un labyrinthe il faut :
une craie : pour noter les carrefours/couloirs déjà visités
un fil : pour pouvoir retourner sur ses pas (backtrack)

44/186 44/186
Les structures Pile (Stack) et File (Queue)

F IGURE 12 – Le fonctionnement LIFO (Last F IGURE 13 – Le fonctionnement FIFO (First In

In First Out) : Une pile P et ses opérateurs First Out) : Une file F et ses opérateurs

45/186 45/186
Parcours en profondeur (Depth-first Search (DFS)) : 1e version itérative

Algorithm 2 DFS(G,s) (utilise une pile P et suit la stratégie LIFO (Last In First Out )).

Require: G=(V,E), start vertex s.

Ensure: v.visited = true for all vertices v ∈ V reachable from s.
1: Initialisation : ∀v ∈ V : v.visited ← false ; clock ← 1 ; previsit(s) ; P ← [s] ;
2: u ← P .head () ( u reçoit le sommet de la pile P )
3: while (u 6= nil ) do
4: if (∃(u , v ) ∈ E | v .visited = false ) then
5: { previsit(v) ; P.put(v) } { v est inséré dans P }
6: else
7: { postvisit(u) ; delete(u,P) } { le sommet u est supprimé de P }
8: end if
9: u ← P .head () { u reçoit le sommet de la pile P }
10: end while

where :
previsit(v)={v.visited ← true ; v.in ← clock ; clock ← clock+1}
postvisit(v)={v.out ← clock ; clock← clock+1}

46/186 46/186
Analyse de l’algorithme (2)

L’algorithme (2) est appliqué sur le graphe G de la Fig. (15) à partir du sommet S. Les
valeurs v .in (v .out) seront indiquées en haut à gauche(droite) du sommet v (une fois
calculées).

F IGURE 14 – L’état de la pile P après les

premiers quatre coups d’horloge (clock). La F IGURE 15 – Le graphe G après les premiers
pile contient les quatre sommets S , A, B , C quatre coups d’horloge. Les valeurs v .in
qui sont empilés l’un après l’autre sur la pile. correspondent au moment de la
La tête de la pile correspond au sommet de visite/découverte du sommet v .
la pile (C à l’occurence).

47/186 47/186
Analyse de l’algorithme (2) : suite

L’algorithme (2) est appliqué sur le graphe G de la Fig. (17) à partir du sommet S.

F IGURE 16 – L’état de la pile P après les F IGURE 17 – Le graphe G après les premiers
premiers cinq coups d’horloge (clock). La cinq coups d’horloge. C .out = 5 : c’est le
pile contient les trois sommets S , A, B. Le moment quand le sommet C a été dépilé de la
sommet B est actuellement la tête de la pile. pile.

48/186 48/186
Analyse de l’algorithme (2) : suite

L’algorithme (2) est appliqué sur le graphe G de la Fig. (19) à partir du sommet S.

F IGURE 19 – Le graphe G après les premiers six

F IGURE 18 – L’état de la pile P après les
coups d’horloge. Les valeurs v .in correspondent
premiers six coups d’horloge. La pile
au moment de la visite/découverte du sommet
contient les deux sommets S , A. Le sommet
v . Les valeurs v .out indiquent le moment de
A est actuellement la tête de la pile.
l’enlèvement du sommet v de la pile.

49/186 49/186
Analyse de l’algorithme (2) : suite

L’algorithme (2) est appliqué sur le graphe G de la Fig. (21) à partir du sommet S. .

F IGURE 21 – Le graphe G après les sept coups

F IGURE 20 – L’état de la pile P après sept d’horloge. Les valeurs v .in correspondent au
coups d’horloge (clock). La pile ne contient moment de la visite/découverte du sommet v .
que le sommet S qui est la tête de la pile. Les valeurs v .out indiquent le moment de
l’enlèvement du sommet v de la pile.

50/186 50/186
Analyse de l’algorithme (2) : suite

L’algorithme (2) est appliqué sur le graphe G de la Fig. (23) à partir du sommet S.

F IGURE 22 – L’état de la pile P après les

premiers huit coups d’horloge. La pile ne F IGURE 23 – Le graphe G après les premiers
contient que les sommets S , D. Le sommet huits coups d’horloge.
D est la tête de la pile.

51/186 51/186
Analyse de l’algorithme (2) : suite

L’algorithme (2) est appliqué sur le graphe G de la Fig. (25) à partir du sommet S. .

F IGURE 24 – L’état de la pile P après les F IGURE 25 – Le graphe G après les premiers
premiers neuf coups d’horloge. La pile neuf coups d’horloge. Tous les sommets ont été
contient les sommets S , D , E. Le sommet E visités. Les valeurs v .in correspondent au
est la tête de la pile. moment de la visite/découverte du sommet v .

52/186 52/186
Analyse de l’algorithme (2) : suite

L’algorithme (2) est appliqué sur le graphe G de la Fig. (26) à partir du sommet S.

F IGURE 27 – L’arbre de l’appel DFS (G, S ).

F IGURE 26 – Tous les sommets ont éte visités. Le graphe G a été parcouru en profondeur
La pile P est vide. d’abbord. Les lignes pointillées indiquent
des testes/vérifications éffectuées dans le
code.

53/186 53/186
Parcours en largeur d’abord (Breadth First Search (BFS))

Algorithm 3 BFS(G,s) (utilise une file F et suit la stratégie FIFO (First In First Out) ).

Require: G=(V,E), start vertex s.

Ensure: Breadth First Search (BFS) of the graph G
1: Initialisation : ∀v ∈ V : v.visited ← false ; clock← 1 ; previsit(s) ; F ← [s] ;
2: u ← P .head () (u reçoit le sommet de la file F )
3: while (u 6= nil ) do
4: if (∃(u , v ) ∈ E | v .visited = false) then
5: { previsit(v) ; F.put(v) } {v est inséré dans F }
6: else
7: { postvisit(u) ; delete(u,F) } {le sommet u est supprimé de F }
8: end if
9: u ← F .head () {u reçoit le sommet de la file F }
10: end while

where :
previsit(v)={v.visited ← true ; v.in ← clock ; clock ← clock+1}
postvisit(v)={v.out ← clock ; clock← clock+1}

54/186 54/186
Analyse de l’algorithme BFS(G,S)

L’algorithme (3) est appliqué sur le graphe G de la Fig. (29) à partir du sommet S. Les
valeurs v .in (v .out) seront indiquées en haut à gauche(droite) du sommet v (dès
qu’elles soient calculées).

F IGURE 28 – L’état de la file F après les

premiers cinq coups d’horloge. La file F IGURE 29 – Le graphe G après les premiers
contient le sommet S et les quatre sommets cinq coups d’horloge. Les valeurs v .in
qui lui sont adjacents A, C , D , E. La tête de correspondent au moment de la
la file n’a pas bougé et pointe sur le sommet visite/découverte du sommet v .
S.

55/186 55/186
Analyse de l’algorithme BFS(G,S) : suite

L’algorithme (3) est appliqué sur le graphe G de la Fig. (31) à partir du sommet S..

F IGURE 31 – Le graphe G après les premiers six

F IGURE 30 – L’état de la file F après les
coups d’horloge. Les valeurs v .in correspondent
premiers six coups d’horloge. Le sommet S
au moment de la visite/découverte du sommet
a été enlevé et la tête de la file pointe sur le
v . Les valeurs v .out indiquent le moment de
sommet A.
l’enlèvement du sommet v de la file.

56/186 56/186
Analyse de l’algorithme BFS(G,S) : suite

L’algorithme (3) est appliqué sur le graphe G de la Fig. (33) à partir du sommet S..

F IGURE 33 – Le graphe G après les premiers

F IGURE 32 – L’état de la file F après les
sept coups d’horloge. Les valeurs v .in
premiers sept coups d’horloge. La tête de la
correspondent au moment de la
file pointe sur le sommet A. Le sommet B
visite/découverte du sommet v . Les valeurs
qui lui est adjacent est ajouté(enfilé) dans la
v .out indiquent le moment de l’enlèvement du
file F .
sommet v de la file.

57/186 57/186
Analyse de l’algorithme BFS(G,S) : suite

L’algorithme (3) est appliqué sur le graphe G de la Fig. (35) à partir du sommet S..

F IGURE 35 – Le graphe G après les huit coups

F IGURE 34 – L’état de la file F après les huit d’horloge. Les valeurs v .in correspondent au
coups d’horloge. Après l’enlèvement de A, moment de la visite/découverte du sommet v .
la tête de la file pointe sur le sommet C. Les valeurs v .out indiquent le moment de
l’enlèvement du sommet v de la file.

58/186 58/186
Analyse de l’algorithme BFS(G,S) : fin

L’algorithme (2) est appliqué sur le graphe G de la Fig. (36) à partir du sommet S.

F IGURE 37 – L’arbre de l’appel BFS (G, S ).

F IGURE 36 – Tous les sommets ont éte visités. Le graphe G a été parcouru en largeur
La file F est vide. d’abbord. Les lignes pointillées indiquent
des testes/vérifications éffectuées dans le
code.

59/186 59/186
Parcours en profondeur d’abord :
version récursive

60/186 60/186
Exploration de la descendance d’un sommet donné v

Algorithm 4 Explore(G,v).

Require: G=(V,E), start vertex v∈ V.

Ensure: u.visited = true for all vertices u reachable from v.
1: v.visited ← true
2: previsit(v)
3: for all each edge (v,u)∈E do
4: if not u.visited then Explore(G,u)
5: end for
6: postvisit(v)

Les procédures « previsit(v) » et « postvisit(v) » contiennent des opérations

optionnelles à effectuer lors de la première visite du sommet v , et après l’avoir
complètement explorer. Ces procédures peuvent être extrêmement utiles.

61/186 61/186
Explore(G,v) : validation formelle

Proposition : Explore(G,v) visite chaque sommet joignable à partir de v.

Preuve : Supposons que le sommet u est joignable à partir de v, mais n’a pas
été visité par Explore(G,v). Notons P le chemin allant de v à u. Considérons le
dernier sommet z visité par Explore(G,v) sur ce chemin et soit w le sommet qui
suit immédiatement z sur P.

D’après la définition d’Explore(G,v), w devrait être aussi visité ; contradiction.

62/186 62/186
Parcours en profondeur d’abord : l’algorithme complet

Puisque le graphe G peut avoir plusieurs composantes distinctes, plusieurs

appels d’Explore(G,.) à partir de différents sommets de départ sont
éventuellement nécessaires.

Algorithm 5 DFS(G) : algorithme depth-first search.

Require: G=(V,E).
Ensure: v.visited = true for all vertices v∈ V.
1: for all v∈V do
2: v.visited ← false
3: end for
4: for all v∈V do
5: if not v.visited then Explore(G,v)
6: end for

Analyse de complexité :
∀v ∈ V Explore(G,v) est appelée une seule fois (grâce à l’étiquette v.visited).
Chaque arête (u,v)∈ E est examiné exactement deux fois : la première fois lors
d’Explore(G,u) et une deuxième fois lors d’Explore(G,v).
Sous l’hypothèse que previsit et postvisit prennent un temps constant, DFS(G)
nécessite un temps Θ(|V | + |E |) (linéaire).

63/186 63/186
Forêt couvrante associée à un parcours en profondeur d’abord

En général, DFS(G) engendre une foret qui contient plusieurs arbres de

parcours, une pour chaque composante connexe du graphe.

Lors du parcours, chaque sommet v est muni de deux étiquettes (v.in, v.out). On
utilise aussi les notations (pre(v), post(v)) 1 . v.in indique le moment de la
première visite du sommet v. v.out indique le moment quand la procédure DFS a
définitivement quitté le sommet v (il a été donc complètement exploré).

1. Dans la terminologie de ce cours la numérotation (pre, post) est une autre dénomination de la
numérotation (in, out) (c.-à-d. pre(u)=u.in et post(u)=u.out)
64/186 64/186
Calcul la numérotation (in, out) ((pre, post))

Les valeurs in/out peuvent être calculées dans les procédures previsit et
postvisit.
On utilise pour ce faire le compteur « clock » initialisé à 1 et défini comme suit.
previsit(v)={v.in ← clock ; clock ← clock+1}
postvisit(v)={v.out ← clock ; clock ← clock+1}
Proposition : Pour chaque couple de sommet u et v, les intervalles [u.in,u.out] et
[v.in,v.out] sont soit complètement disjoints, soit l’un est entièrement inclus dans
l’autre.
Preuve : L’intervalle [u.in, u.out] indique le temps durant lequel le sommet u est
présent dans la pile. La stratégie LIFO explique alors la propriété ci-dessus.

65/186 65/186
Parcours en profondeur dans les graphes orientés

DFS(G) s’applique d’une façon similaire dans les graphes orientés. En raison de
l’orientation des arcs, les arbres de parcours engendrés sont plus complexes
(appelés aussi arborescences).

F IGURE 38 – Un graphe G.
F IGURE 39 – L’arborescence de l’appel
DFS (G, A).

66/186 66/186
Parcours en profondeur dans les graphes orientés : classification des arcs

Les arcs u → v tels que Explore(G,u) appelle Explore(G,v) sont nommés

arcs couvrants (« tree edges »). Les arcs couvrants constituent une forêt
couvrante d’arborescences de parcours en profondeur.
Les arcs en pointillé peuvent être de trois types différents.
Les arcs en avant (« forward edges ») sont les arcs (u,v) qui relient un sommet u à un
descendant v.
Les arcs retour (« back edges ») sont les arcs (u,v) reliant un sommet u à un ancêtre
v. Les boucles sont considérées comme des arcs retour.
Les arcs croisés (« cross edges ») sont tous les autres arcs. Ce sont des arcs pour
lesquels il n’existe pas de chemin entre leurs extrémités dans la forêt. Ils peuvent
relier deux sommets d’une même arborescence, tant que l’un des sommets n’est pas
ancêtre de l’autre ; ils peuvent aussi relier deux sommets appartenant à des
arborescences différentes.
67/186 67/186
Relations entre le type d’arc et la numérotation [pre, post] ([in, out])

Dans une forêt DFS, le sommet u est un ancêtre du sommet v ssi u est visité le
premier et v est visité lors de l’appel explore(u) (c.-à-d. pre(u) < pre(v) <
post(v) < post(u)).
Dans une forêt DFS, le sommet u est un descendant du sommet v ssi v est visité
le premier et u est visité lors de l’appel explore(v) (c.-à-d. pre(v) < pre(u) <
post(u) < post(v)).
On peut alors donner la classification suivante pour l’arc (u,v) :
pre(u) < pre(v) < post(v) < post(u) ssi l’arc (u,v) est de type arc
couvrant/arc en avant.
pre(v) < pre(u) < post(u) < post(v) ssi l’arc (u,v) est de type arc retour.
les intervalles [pre(v), post(v)] et [pre(u), post(u)] sont disjoints ssi l’arc
(u,v) est de type arc croisé.

68/186 68/186
Application de DFS : tri topologique (linéaire)

Le parcours en profondeur peut être utilisé pour effectuer un tri topologique (ou tri
linéaire) d’un graphe orienté sans circuit. Le tri topologique d’un DAG (graphe orienté
acyclique) G = (V , E ) consiste à ordonner linéairement tous ses sommets de telle
sorte que si G contient l’arc (u,v) alors, u apparaisse avant v .

F IGURE 40 – Gauche : Un graphe G = (V , E ). Les sommets représentent un ensemble de

tâches, les arcs visualisent leurs relations d’antériorités. Il n’est pas évident de trouver l’ordre
exécution de ces tâches ? Droite : le même graphe est trié topologiquement (linéarisé) par
l’ordonnancement des sommets v ∈ V . Ainsi, un ordre d’exécution des tâches est explicité.

69/186 69/186
Application de DFS : linéarisation d’un DAG (Directed Acyclic Graph)

Les propositions suivantes sont utilisées pour effectuer un tri topologique.

Proposition : Un graphe orienté G contient un circuit, ssi la forêt engendrée
pars le parcours DFS(G) contient un arc retour.
Preuve :
Evident si le parcours DFS(G) contient un arc retour.
Supposons maintenant que G contient un circuit C : v0 → v1 → v2 → . . . → vk → v0 .
Soit vi le premier sommet du C qui a été visité durant le parcours DFS. Tous les
autres sommets de C sont des descendants de vi dans l’arbre de parcours et alors
vi −1 → vi est un arc retour (si i = 0 alors vk → v0 ).

70/186 70/186
Application de DFS : linéarisation d’un DAG (suite)

Proposition : La numérotation post d’un DAG obtenue lors d’un parcours DFS
satisfait l’inégalité post (u ) > post (v ) pour chaque arc (u, v).
Preuve : Les seuls arcs (u , v ) pour lesquels post (u ) < post (v ) dans l’arbre DFS
sont les arcs retour. Or, il n’y pas de tels arcs dans un DAG.

Algorithm 6 Premier algorithme pour linéariser un DAG.

Require: G=(V,E), DAG

Ensure: List vertices in linear order.
1: Perform a DFS search and obtain the number post (v ) for any vertex v ∈ V .
2: List vertices in order of decreasing post (v ) values.

71/186 71/186
Linéarisation d’un DAG par l’algorithme 6

F IGURE 42 – La numérotation
F IGURE 41 – Un graphe G = (V , E ). [pre, post ] obtenue avec un parcours
DFS (G, A).

F IGURE 43 – Le graphe G est trié topologiquement (linéarisé) par l’ordonnancement des

sommets v ∈ V dans l’ordre décroissant de leur numérotation post (v ).

72/186 72/186
Composantes fortement connexes (CFC)

73/186 73/186
Modéliser l’accessibilité au centre-ville de l’Utopia

1 2 3 4

5 6 7 8 9

10 11 12 13 14 15

F IGURE 44 – Le plan de sens uniques du centre-ville.

Comment détecter si ce plan est acceptable ?

74/186 74/186
Modéliser l’accessibilité au centre-ville de l’Utopia : solution

1 2 3 4

5 6 7 8 9

10 11 12 13 14 15

F IGURE 45 – Les sommets jaunes et verts ne sont pas joignables à partir des sommets rouges.
Les trois zones coloriées en rouge, jaune et vert sont des Composantes Fortements Connexes
(CFC)

Le plan donc n’est pas acceptable puisque le graphe associé contient trois CFC.

75/186 75/186
Application de DFS : Composantes fortement connexes (CFC)

Soit le graphe orienté G = (V , E ). G est dit fortement connexe, si pour chaque

couple de sommets (u , v ), il existe un chemin de u à v , noté (u ; v ), et un
chemin de v à u, noté (v ; u).
Cette définition définit une relation binaire dans V .

uRv ≡ (u ∈ Γ∗v ) ∧ (v ∈ Γ∗u ) (5)

où Γ∗v indique la descendance du sommet v .

C’est une relation d’équivalence dont les classes s’appellent composantes
fortement connexes (c.f.c.).
Elle partitionne V en ensembles disjoints (appelés C.F.C.).

76/186 76/186
Application de DFS : Composantes fortement connexes (suite)

La détection des c.f.c. se fait facilement grâce aux propriétés du parcours DFS.
Propriété 1 : La procédure explore(G,u) ne se termine que si tous les sommets
accessibles à partir de u soient visités/explorés (c.-à-d. après avoir exploré toute
la descendance Γ∗u du sommet u).
Ainsi, si la procédure explore(G, v ) est exécutée à partir d’un sommet v
appartenant à une c.f.c. puits (une c.f.c. sans arcs sortants), alors elle visiterait
exactement cette c.f.c. La dernière pourrait être alors enlevée du graphe G, et le
0
processus continuerait sur le graphe résultant G .
Illustrer cette propriété avec les deux meta-sommets {D} et {G,H,I,K,J,L} du
graphe de la figure (46).

77/186 77/186
Application de DFS : Composantes fortement connexes (suite)

F IGURE 46 – a) Un graphe orienté G et ses C.F.C. b) Son graphe réduit G̃

F IGURE 47 – Ce
meta-graphe a deux F IGURE 48 – On enlève F IGURE 49 – On enlève
sommets-puits (en gris). On l’unique sommet-puits. l’unique sommet-puits.
peut les enlever.
La connaissance des sommets-puits permet de les enlever un par un et de découvrir
ainsi toutes les C.F.C. du graphe. Pour se faire, on peut utiliser le deuxième
algorithme de tri topologique.
78/186 78/186
Application de DFS : Composantes fortement connexes (suite)

Comment détecter une c.f.c. puits ?

Trouver une c.f.c. puits est difficile, mais trouver une c.f.c. source (sans arcs
entrants) est facile en raison de l’observation suivante.
Propriété 2 : Le sommet v avec la plus grande valeur post (v ) calculée lors d’un
parcours DFS se trouve dans une c.f.c. source.
Cette propriété est déduite du fait suivant.
0
Propriété 3 : Soit deux c.f.c. C et C , telles qu’il existe un arc d’un sommet de C
0
vers un sommet de C , alors :

max{post (u )} > max{post (u )} (6)

u ∈C 0
u ∈C

Preuve : Deux cas sont à considérer.

DFS commence à partir d’un sommet u ∈ C. Alors DFS visite Γ∗u (tous les sommets
0 0
appartenants à C et C ) et post (u ) > post (v ), ∀v ∈ C ∪ C (propriété 1).
0 0
DFS commence à partir d’un sommet u ∈ C . Alors tous les sommets de C sont
visités avant de commencer la visite de C. Donc, post (u ) > post (u ).
u ∈C 0
u ∈C

79/186 79/186
Application de DFS : Composantes fortement connexes (suite)

Grace à la propriété 3, nous savons comment trouver une c.f.c. source dans G.
Déterminer les sommets appartenant aux c.f.c. nécessite que le parcours
commence à partir d’une c.f.c. puits. Comment trouver une telle c.f.c. ?
Idée : Renverser le graphe (c.-à-d. changer l’orientation de tous les arcs). Le
graphe ainsi obtenu sera noté GR .
Alors les c.f.c. ne changent pas (facile à vérifier). Mais les sommets puits se
transforment en sources et vice versa. Le graphe G̃ se renverse aussi (voir les
graphes des figures (46) et (51).
La linéarisation du DAG G̃R permet de trier topologiquement les sommets de
DAG G̃ dans l’ordre des sommets-puits vers les sommets-sources.

80/186 80/186
Application de DFS : Composantes fortement connexes (suite)

F IGURE 50 – a) Un graphe orienté G et ses c.f.c. b) Son graphe réduit G̃

F IGURE 51 – a) GR : le graphe renversé du graphe G et ses c.f.c. b) G˜R : le graphe réduit de GR

81/186 81/186
Application de DFS : Algorithme de Kosaraju pour la détection des CFC

Algorithm 7 Déterminer les CFC d’un graphe orienté G.

Require: G=(V,E)
Ensure: Detect the strongly connected components (SCC) of G
1: Reverse all the edges in G, yielding digraph GR .
2: Run DFS on GR , obtaining the post (v ) numbers for all vertices v .
3: k ← 1.
4: Run EXPLORE(G,v) in G from the vertex v that has the highest post (v ) value in
GR , and has not yet been assigned to any SCC. Assign all vertices mapped out by
the exploration into SCC k .
5: Set k ← k + 1 and repeat from step 4, until all vertices have been assigned to
SCCs.

Complexité : linéaire.
Appliquer l’algorithme 7 pour trouver les C.F.C. du graphe de fig. (50)

82/186 82/186
Application de l’algorithme de Kosaraju (algorithme 7) : suite

F IGURE 53 – Le graphe GR = (V , ER )
avec la numérotation [pre, post ] [in,
F IGURE 52 – Le graphe G = (V , E ). out obtenue avec un parcours
DFS (GR , A).

83/186 83/186
Application de l’algorithme de Kosaraju (algorithme 7) : suite et fin

F IGURE 55 – Les cinq CFC

découvertes par l’algorithme de
F IGURE 54 – Le graphe G = (V , E ) Kosaraju et le meta-graphe associé
avec la numérotation [pre, post ] (on dit aussi son graphe réduit G̃)
obtenue lors du parcours DFS (GR , A).

On applique EXPLORE(G,v) sur le graphe d’origine G = (V , E ) dans l’ordre

décroissant des valeurs post (v ) qui ont été obtenues lors du parcours de du graphe
renversé DFS (GR , A). Cela donne l’ordre suivant : EXPLORE(G,G), EXPLORE(G,D),
EXPLORE(G,C), EXPLORE(G,B), EXPLORE(G,A).

84/186 84/186
Application de DFS : Composantes fortement connexes (suite)

F IGURE 56 – a) Un graphe orienté G et ses c.f.c. b) Le graphe réduit G̃

F IGURE 57 – Ce
meta-graphe a deux F IGURE 58 – On enlève F IGURE 59 – On enlève
sommets-puits (en gris). On l’unique sommet-puits. l’unique sommet-puits.
peut les enlever.
La connaissance des sommets-puits permet de les enlever un par un et de découvrir
ainsi toutes les c.f.c. du graphe. Pour se faire, on peut utiliser le deuxième algorithme
de tri topologique (Alg 7).
85/186 85/186
Application de DFS : linéarisation d’un DAG (suite)

Propriété : Chaque DAG a au moins un sommet source (sommet sans

prédécesseurs) et au moins un sommet puits (sommet sans successeurs)
Preuve : Ce sont respectivement le sommet avec la plus grande, et la plus petite
valeur de la numérotation post.

Algorithm 8 Deuxième algorithme pour linéariser un DAG.

1: Find a source, output it, and delete it from the graph.

2: Repeat until the graph is empty.

Devoir : Analyser et donner la complexité des algorithmes 6 et 8.

86/186 86/186
Linéarisation d’un DAG par l’algorithme 8

F IGURE 60 – B est un sommet-source F IGURE 61 – D est un sommet-source

dans le graphe d’origine G = (V , E ). dans le graphe induit GB = (VB , EB ).
On l’enlève du G. On l’enlève du GB .

F IGURE 62 – A est un sommet-source F IGURE 63 – C est un sommet-source

dans le graphe induit GD = (VD , ED ). dans le graphe induit GA = (VC , EC ).
On l’enlève du GB . On l’enlève du GA .

Les deux dernières tâches E et F peuvent être exécutées dans un ordre quelconque.
L’ordre d’exécution des tâches est donné par l’odre d’enlèvement des
sommets-sources : B, D, A, C, E, F.
87/186 87/186
Linéarisation d’un DAG par l’algorithme 8

Algorithm 9 topological_sort_2(G, d − , Z )
Require: G = (V , E ) given by the list of successor succ, d − the list of input degree
value, Z a LIFO/FIFO queue containing the indices of vertices v such that d − [v ] =
0, i .e. Z = {v ∈ V | d − [v ] = 0}.
Ensure: the list top is a topological sort of the graph G
1: top ← [ ]
2: while Z 6= 0 / do
3: u ← Z .pop()
4: for v ∈ succ [u ] do
5: d − [v ] ← d − [v ] − 1
6: if d − [v ] = 0 then
7: Z .add (v )
8: end if
9: end for
10: top.add (u )
11: end while
12: return top

On peut démontrer que la complexité de cet algorothme est Θ(|V | + |E |).

88/186 88/186
Le problème du flot maximum dans les réseaux :
l’algorithme de Ford-Fulkerson

89/186 89/186
Réseaux : définitions

Un réseau est un graphe connexe orienté (triplet) G = (V , U , C ), où

V = {v1 , v2 , . . . , vn } est l’ensemble des sommets/noeuds et U est l’ensemble
des arcs (couples (i , j ) ∈ V × V ). A tout arc u ∈ U on affecte une valeur
(capacité) cu qui est une borne supérieure du flot sur l’arc.
Soit deux sommets particuliers s ∈ V (source) et t ∈ V (puits). Considérons le
graphe G0 = (V , U 0 ) où U 0 = U ∪ {(t , s)}. L’arc (t , s) est appelé l’arc de retour
du flot (numéroté 0). Notons n = |V | et m = |U |.

F IGURE 64 – Un réseau G = (V , U , C ). Chaque arc u ∈ U est muni d’une capacité cu .

90/186 90/186
Exemple de flot

On dit que [φ1 , φ2 , . . . φm ]T est un flot de s à t ssi la loi de conservation du flot est
vraie ∀u ∈ V \{s, t }, i.e.

∑ φ(u ,v ) = ∑ φ(v ,u ) (7)

v ∈Γ+ (u ) v ∈Γ− (u )

La valeur du flot est notée par φ0 . Elle est définie par

∑ φ(s,v ) = ∑ φ(u ,t ) = φ0 (valeur du flot) (8)

v ∈Γ+ (s) u ∈Γ− (t )

But : Trouver dans G0 un flot compatible φ0 = [φ0 , φ1 , φ2 , . . . φm ] (c.-à-d.

0 ≤ φu ≤ cu ∀u ∈ U) et tel que la valeur φ0 soit maximale.

F IGURE 65 – Un flot de valeur 6. La première valeur dans un couple (φu , cu ) sur l’arc u
correspond au flot, tandis que la deuxième valeur indique sa capacité.
91/186 91/186
Définition d’une coupe et de sa capacité
Soit le réseau G = (V , U , C ). Une coupe séparant s et t (notée s − t) est une
partition (L, R ) de V , telle que s ∈ L et t ∈ R = L̄ = V \ L.
La capacité C (L, R ) de la coupe s − t est définie par C (L, R ) = ∑ ce où
e∈ω+ (L)
ω+ (L) représente le sous-ensemble d’arcs qui ont leur extrémité initiale dans L
et leur extrémité terminale dans L̄ = R.
Lemme : La valeur maximale d’un flot de s à t compatible avec C n’excède
jamais la capacité d’une coupe séparant s et t.

F IGURE 66 – Une coupe s − t définie par la partition L = {s, a, b} and R = {c , d , e, t }. Chaque

flot s ; t doit passer de L à R et traverser ainsi la coupe s − t. Donc, la valeur d’un flot ne peut
dépasser la valeur de la capacité C (L, R ) qui vaut 7. Ainsi, chaque flot s ; t de valeur 7, devrait
être maximum (certificat d’optimalité).

92/186 92/186
L’égalité entre le flot et la capacité d’une coupe est un certificat d’optimalité

F IGURE 67 – Les valeurs en rouges sont les F IGURE 68 – Les valeurs en bleu visualisent
poids des arcs. le flot sur les arcs.

La valeur du flot sur le réseau ci-dessous vaut 20. La capacité de la coupe

({S , B , E , C }, {A, G, D , F , T }) est donnée par la somme des capacités des arcs
(S,A), (C,G), (E,D), (B,D), (E,F) est égale aussi à 20. Cette égalité sert comme un
certificat d’optimalité du flot et de la coupe respectivement. C’est la preuve que ce flot
est maximal, tandis que la coupe est minimale. On observe que tous les arcs sur
cette coupe sont saturés - ce qui est indiqué par deux traits verticaux.
93/186 93/186
Graphe d’écart (graphe résiduel)

Soit φ = [φ1 , φ2 , . . . φm ]T un flot entre s et t compatible avec C

Le graphe d’écart associé à φ est le graphe Ḡ(φ) = (V , Ū (φ)) où Ū (φ) est
constitué de la façon suivante :
∀u = (i , j ) ∈ U de G on associe au plus deux arcs de Ḡ(φ)
u + = (i , j ) si φu < cu avec capacité (résiduelle) cu − φu > 0
u − = (j , i ) si φu > 0 avec capacité (résiduelle) φu > 0
Remarque : si φu = cu , on lui associe seulement u − , si φu = 0, on lui associe
seulement u + .

F IGURE 69 – a) Un réseau G avec un flot φ de valeur 5. Le couple (φu , cu ) associé à chaque arc
u indique la valeur du flot φu et sa capacité cu . b) : Le graphe d’écart Ḡ(φ) associé au flot φ.

94/186 94/186
Un chemin améliorant

Etant donné un flot φ, un chemin améliorant (s ; t ) est un chemin simple 2 de s

à t dans le réseau résiduel Ḡ(φ).
Soit ε > 0 le minimum des capacités résiduelles d’un chemin améliorant π.
On ajoute ε au flot sur les arcs de type u + et on l’enlève du flot des arcs de type
u − ; la loi de conservation du flot est satisfaite ainsi.
0
On obtient ainsi un nouveau flot de valeur φ0 = φ0 + ε > φ0 .

F IGURE 70 – a) Le chemin π = ((S , A)(A, B )(B , T )) est un chemin améliorant (s ; t ) dans le

graphe résiduel Ḡ(φ) et ε = 1 sur ce chemin. On ajoute cette valeur à la valeur du flot sur les
arcs (S , A) et (B , T ) ; on la soustrait de la valeur de l’arc (A, B ). b) Le nouveau flot de valeur
0
φ0 = 6. Peut-on l’améliorer ? Le réponse est donnée par le critère d’arrêt dans l’algorithme de
Ford et Fulkerson.

2. On dit aussi un chemin élémentaire. C’est un chemin qui passe au plus une fois par chaque sommet.
95/186 95/186
Algorithme de Ford et Fulkerson (1956)

La notion du chemin améliorant est à la base de l’algorithme de Ford et Fulkerson.

k = 0. Partir d’un flot initial φ0 compatible avec les capacités.

Soit φk le flot courant.
Tant qu’il existe un chemin améliorant (s ; t ) dans Ḡ(φk ) faire
soit πk un chemin améliorant (s ; t ) dans Ḡ(φk ).
Soit εk le minimum des capacités résiduelles du πk .
Définir le flot φk +1 par
φku +1 = φku + εk si u + ∈ πk (9)

φku +1 = φku − εk si u − ∈ πk (10)

φk0 +1 = φk0 k
+ε (11)
k ← k +1
fin tant que : le flot φk est de valeur maximale.

96/186 96/186
Algorithme de Ford et Fulkerson : illustration

F IGURE 71 – Un réseau G = (V , U , C ). On cherche le flot de valeur maximale.

F IGURE 72 – Le fonctionnement de l’algorithme de Ford et Fulkerson sur le réseau de la figure

71. Le flot courant est visualisé à gauche, son graphe d’écart est représenté à droite. Les figures
a) et b) visualisent les deux premières itérations avec le flot nul (la figure a) à gauche) et le flot
de valeur 1 (la figure b) à gauche).
97/186 97/186
Algorithme de Ford et Fulkerson : illustration (suite)

F IGURE 73 – Un réseau G = (V , U , C ). On cherche le flot de valeur maximale.

F IGURE 74 – Le fonctionnement de l’algorithme de Ford et Fulkerson sur le réseau de la figure

73. Le flot courant est visualisé à gauche, son graphe d’écart est représenté à droite. Les figures
c) et d) visualisent les itérations 3 et 4 respectivement.
98/186 98/186
Algorithme de Ford et Fulkerson : illustration (fin)

F IGURE 75 – Les figures e) et f) visualisent les dernières itérations de l’algorithme de Ford et

Fulkerson. Le flot de valeur 7 (la figure (f) à gauche) est l’optimal. L’optimalité est démontrée par
le fait qu’il n’existe pas de chemin (s ; t ) dans le graphe d’écart Ḡ(φk ) (la figure (f) à droite). Il
n’y a que les sommets a et b qui sont joignables à partir du sommet s. Une coupe de capacité
minimale, égale à la valeur du flot, est visualisée.

99/186 99/186
La relation entre le flot maximum et la coupe minimale

Théorème : Soit φ un flot compatible dans le réseau G. Les conditions suivantes sont
équivalentes :
1. φ est un flot maximum dans G.
2. Le réseau résiduel Ḡ(φ) ne contient aucun chemin améliorant.
3. La valeur du flot φ est égale à la capacité d’une coupe de capacité minimale
séparant s et t.
Démonstration :
(1) ⇒ (2) : Evident
(2) ⇒ (3) : On définit L = {v ∈ V : ∃ un chemin de s à v dans Ḡ(φ)}.
Soit R = V \ L. La partition (L, R ) est une coupe : de façon triviale s ∈ L et t ∈ R.
Par hypothèse, pour chaque arc (u , v ) tq u ∈ L et v ∈ R on a φ(u , v ) = c (u , v ).
D’autre part, pour chaque arc (v , u ) tq v ∈ R et u ∈ L on a φ(v , u ) = 0 .
Donc, size(φ) = C (L, R ).
(3) ⇒ (1) : Conséquence du lemme : La valeur maximale d’un flot de s à t
compatible avec C n’excède jamais la capacité d’une coupe séparant s et t.

100/186 100/186
Analyse de complexité de l’algorithme de
Ford-Fulkerslon

101/186 101/186
Le cas où la valeur de chaque capacité est égale à 1

La recherche d’un chemin améliorant dans le graphe résiduel peut se faire en

O (|V | + |U |) (avec un des parcours vus en cours).
Comme le graphe est connexe chaque sommet est incident à au moins un arc.
|V |
Alors m = |U |, m ≥ 2 et O (|V | + |U |) = O (m)
La mise à jour du flot dans chaque itération de la boucle tant que (équations (9)
et (10) de l’algorithme de Ford-Fulkerslon ) nécessite O (m)
soustractions/additions.
Considérons le cas où la valeur de chaque capacité vaut 1. Alors chaque
itération de la boucle tant que sature exactement un arc. Donc, le nombre
d’itérations de la boucle tant que ne dépasse pas min(d + (s), d − (t )).
En conséquence, le temps total de l’algorithme de Ford-Fulkerson (FF) dans le
cas où la valeur de chaque capacité égale à 1 est en
O (min(d + (s), d − (t )) × m).

102/186 102/186
Le cas où la valeur de chaque capacité est une valeur entière ≥ 1

Réécrivons l’algorithme de Ford-Fulkerson de la manière suivante :

Algorithm 10 Ford-Fulkerson algorithm-bis

1: Initialisation : set φ(e) = 0, ∀e ∈ E to be the initial flow

2: while there is an s ; t path in the residual graph Ḡ(φ) do
3: Let π be the current s ; t path in Ḡ(φ)
4: φ0 = augment (φ, π)
5: Update φ to be φ0
6: Update the residual graph Ḡ(φ) to be Ḡ(φ0 )
7: end while
8: Return φ

Theorem
Si les capacités initiales C sont entières alors à chaque étape intermédiaire les
valeurs du flot φ(e) et celles des capacités résiduelles Ḡ(φ) sont aussi entières.

103/186 103/186
Analyse de complexité quand les capacités sont des entiers ≥ 1

Theorem
Notons φ le flot dans G, et soit π un chemin simple s ; t dans Ḡ(φ). Alors
size(φ0 ) = size(φ) + ε(π, φ) ; et puisque ε(π, φ) > 0, on a size(φ0 ) > size(φ).

Pour démontrer la terminaison de l’algorithme, nous allons expliciter une borne

supérieure des valeurs du flot.
Supposons que tous les arcs sortants de s et entrant dans t soient saturés ; la
valeur du flot dans ce cas devrait être égale à c = min( ∑ ce , ∑ ce ).
e∈Γ+ (s) e∈Γ− (t )

Nous avons ainsi size(φ) ≤ c pour chaque flot s ; t.

Theorem
L’algorithme de Ford-Fulkerson effectue au plus c itérations de la boucle tant que.

Theorem
L’algorithme de Ford-Fulkerson a une complexité temporelle en O (m × c ).

104/186 104/186
Un cas difficile pour l’algorithme de Ford et Fulkerson

F IGURE 76 – a) Analysons le comportement de l’algorithme de FF pour ce reseau ; b) Le

chemin améliorant (S,B,A,T) permet d’obtenir un flot de valeur 1 ; c) Le graphe résiduel associé
à ce flot ; d) Le chemin améliorant (S,A,B,T) sur ce graphe permet d’améliorer la valeur du flot
et elle devient 2 ; Ainsi l’algorithme de Ford et Fulkerson peut continuer de sélectioner les
chemins (S,B,A,T) et (S,A,B,T) alternativement 100 fois en améliorant chaque fois la valeur du
flot d’une unité. Cette stratégie dépend de la valeur des capacités et n’est pas efficace. On peut
facilement l’améliorer en choisisant le chemin le plus court de s vers t (cette stratégie est connue
sous le nom de l’algorithme d’Edmonds-Karp).

105/186 105/186
Analyse de complexité : amélioration par l’algorithme de Edmonds-Karp

La borne de l’algorithme de Ford-Fulkerson peut être améliorée si on implémente la

recherche du chemin améliorant à la ligne 2 avec une recherche en largeur (c.à.d. le
chemin améliorant est un plus court chemin de s vers t dans le graphe résiduel, où
chaque arc possède une pondération unitaire). Cette implémentation a pour nom
algorithme de Edmonds-Karp. On peut démontrer que cet algorithme s’exécute en
O (|V | × |U |2 ) = O (n × m2 ) où V est l’ensemble de sommets et U est l’ensemble
d’arcs.

106/186 106/186
Applications

107/186 107/186
Barrage routier par les flots

F IGURE 77 – Le réseau routier d’une île. Pour exprimer leur mécontentement, les agriculteurs
décident de bloquer toute possibilité d’aller de A à B. Pour réduire la gêne occasionnée, on
envisage bloquer seulement les routes, pas les agglomérations.

Proposer une méthode générale pour déterminer où placer les barrages routiers.
Déterminer le nombre minimal de barrages nécessaires et leur emplacement.
Les forces publiques de la vile A ont décidé de surveiller les routes au départ de
A. Toute possibilité de dresser un barage sur ces routes est donc exclue.
Déterminer à nouveau le nombre minimal de barrages nécessaires et leur
emplacement.

108/186 108/186
Barrage routier par les flots - suite
Le problème consiste à supprimer un nombre minimal d’arcs de façon à ce qu’il n’existe plus de
chemin de A vers B. Le problème se ramène à la recherche d’une coupe de capacité minimale.
On affecte une capacité 1 à chaque arc. La valeur d’une coupe fournit le nombre d’arcs à
supprimer afin d’éliminer toute communication de A vers B.

F IGURE 78 – On construit un flot de valeur 3.

F IGURE 79 – Le flot trouvé est le flot maximum puisqu’il n’existe pas de chemin dans le graphe
résiduel. La coupe associée (donnée par la partition des sommets en sommets rouges et
blancs) est la coupe minimale. Elle suggère l’emplacement des barages – en l’occurrence sur
les arcs (A, 1), (13, B ), (14, B ).
109/186 109/186
Barrage routier par les flots - suite
Pour modéliser le fait que les forces publiques de la vile A ont décidé de surveiller les routes au
départ de A, on affecte une capacité ∞ aux arcs sortants de A.

F IGURE 80 – On construit un flot de valeur 3.

F IGURE 81 – Le flot trouvé est le flot maximum puisqu’il n’existe pas de chemin dans le graphe
résiduel. La coupe associée (donnée par la partition des sommets en sommets rouges et
blancs) est la coupe minimale. Elle suggère l’emplacement des barages – en l’occurrence sur
les arcs (1, 5), (13, B ), (14, B ).

110/186 110/186
Construction d’autoroutes

Avant d’établir un projet de construction d’autoroute on désire étudier la capacité du

réseau routier, représenté par le graphe ci-dessous, reliant la ville S à la ville T.
Pour cela, on a évalué le nombre maximal de véhicules que chaque route peut
écouler par heure, compte tenu des ralentissements aux traversées des villes et
villages, des arrêts aux feux, etc. Ces évaluations sont indiquées entre crochets, en
centaines de véhicules par heure sur les arcs du graphe. On cherche le débit horaire
total maximal de véhicules susceptible de s’écouler entre les villes S et T.

a d
[4]
[2]
[2] [2]
[3] [3] [7]

S b e T
[7] [4] [6]
[1]
[9] [5] [5]
c f
[3]

F IGURE 82 – Capacité d’un réseau routier.

111/186 111/186
Arbres couvrants minimaux (ACM)

112/186 112/186
 Définitions et propriétés principales

Définition : Un graphe, non-orienté, connexe et acyclique est dit arbre.

On peut démontrer les propriétés suivantes :
Propriétés : Un arbre avec n sommets possède n − 1 arêtes.
Si le graphe G = (V , E ), non-orienté et connexe, est tel que |E | = |V | − 1, alors G
est un arbre.
Un graphe non-orienté est un arbre si, et seulement si, entre chaque couple de
sommets il existe un seul chemin.
Problème : Étant donné un graphe G = (V , E , w ) non-orienté, connexe où w est une
fonction de pondération des arêtes, on cherche T ⊆ E qui connecte tous les
sommets et qui minimise le poids total w (T ) = ∑ w (u , v ).
(u ,v )∈T
On voit facilement que T est acyclique, donc un arbre. T est appelé Arbre
Couvrant Minimal (ACM) 3 .

3. " Arbre Couvrant Minimal" est un racourci pour "Arbre Couvrant de poids Minimal". Tous les arbres
couvrants comportent exactement |V | − 1 arêtes.
113/186 113/186
Arbre Couvrant Minimal : Illustration

F IGURE 83 – Un graphe connexe. Les arêtes de l’arbre couvrant sont grisées. Le poids total de
l’arbre montré est 37. L’arbre n’est pas unique : on peut remplacer l’arête (b, c ) par l’arête (a, h)
et on obtient un autre arbre de même poids.

114/186 114/186
Une application des arbres couvrants minimaux

Des chemins forestiers

Les Eaux et Forêts ont décidé d’abattre 5 bosquets situés dans une forêt. Les
distances mutuelles entre les bosquets sont données (en km) par la matrice suivante.

a b c d e
a 10 1 2 5
b 10 6 4 3
c 1 6 8 9
d 2 4 8 7
e 5 3 9 7

Pour mener à bien cette exploitation il est nécessaire de tracer un réseau de chemins
de coût de construction minimum qui permette de circuler entre tous les bosquets.
Les coûts de construction de ces chemins sont proportionnels à leur longueur.

115/186 115/186
 Définitions et propriétés principales

Problème : Étant donné un graphe G = (V , E , w ) non-orienté, on cherche T ⊆ E qui

connecte tous les sommets et qui minimise le poids total
w (T ) = ∑ w (u , v ). On voit facilement que T est acyclique, donc un arbre.
(u ,v )∈T
T est appelé Arbre Couvrant Minimal (ACM).
Définitions : Soit T un ACM, et soit X ⊆ T . Une arête (u , v ), telle que X ∪ {(u , v )} ⊆ T , est
appelée arête sure pour X .
Une coupure (S , V \S ) du graphe G(V , E ) est une partition des sommets V .
Une arête traverse la coupure (S , V \S ) si l’une de ses extrémités appartient à S et
la seconde appartient à V \S.
Un ensemble d’arêtes X traverse la coupure (S , V \S ) si ∃ au moins une arête e ∈ X
qui traverse cette coupure.
Une arête est dite minimale pour la traversée de la coupure si son poids est minimal
parmi toutes les arêtes qui traversent la coupure.
Théorème : Soit T un ACM, et soit X ⊂ T . Soit S ⊂ V tq X ne traverse pas la coupure
(S , V \S ) (on dira que la coupure respecte X ), et soit (u , v ) une arête minimale
traversant (S , V \S ). Alors (u , v ) est une arête sûre pour X .

116/186 116/186
Théorème de l’arête minimale qui traverse la coupure : Illustration

Soit T un ACM, et soit X ⊂ T . Soit S ⊂ V tq X ne traverse pas la coupure (S , V \ S )

(on dira que la coupure respecte X ), et soit e = (u , v ) une arête minimale traversant
(S , V \S ). Alors e est une arête sûre pour X .

F IGURE 84 – (a) Un graphe G = (V , E , w ) ; (b) l’ensemble X = {(A, B ), (A, C ), (E , F )} partie de

l’ACM T visualisé sur (c) ; (d) S = {A, B , C , D }, la coupure (S , V \ S ) respecte X
puisqu’aucune arête de X ne la traverse (e) l’arête minimale est e = (D , E ). D’après le
théorème de l’arête minimale X ∪ {e} fait partie d’un ACM (en l’occurrence T 0 ).

117/186 117/186
Théorème de l’arête minimale qui traverse la coupure : preuve

Soit T un ACM et soit X ⊂ T . Soit S ⊂ V tq X ne traverse pas la coupure (S , V \ S )

(on dira que la coupure respecte X ) et soit e = (u , v ) une arête minimale traversant
(S , V \S ). Alors e est une arête sure pour X .
Preuve : Si e ∈ T il n’y a rien à démontrer. Supposons e ∈ / T . Puisque T est un
arbre, ∃ dans T un chemin entre les sommets u ∈ S et v ∈ V \ S. Soit e0 ∈ T l’arête
de ce chemin qui traverse la coupure (S , V \ S ). Notons T 0 = T ∪ {e} \ {e0 }. T 0 est
un arbre (puisque c’est un graphe connexe qui a le même nombre d’arêtes que T ).
De plus, w (T 0 ) = w (T ) − w (e0 ) + w (e) ≤ w (T ) puisque w (e) ≤ w (e0 ). T 0 est donc
un ACM.

118/186 118/186
Algorithme générique pour la construction d’un ACM

Algorithm 11 ACM_generique (G(V,E),w)

Require: Un graphe G = (V , E ) avec des poids we , e ∈ E.

Ensure: Un ACM défini par les arêtes de l’ensemble X .
X ← 0/
while X ne forme pas un arbre couvrant do
trouver pour X une arête sure (u , v )
X ← X ∪ {(u , v )}
end while
return X

119/186 119/186
Illustration pour l’algorithme ACM_Prim (G(V,E),w,A)

itér S F

A B C D E F
0 {} 0 ∞, nil ∞, nil ∞, nil ∞, nil ∞, nil
1 {A} — 5, A 6, A 4, A ∞, nil ∞, nil
2 {A; D } — 2, D 2, D — ∞, nil 4, D
3 {A; D ; B } — — 1, B — ∞, nil 4, D
4 {A; D ; B ; C } — — — — 5, C 3, C
5 {A; D ; B ; C ; F } — — — — 4, F —
6 {A; D ; B ; C ; F ; E } — — — — — —

F IGURE 85 – Un graphe et son ACM de poids 14 trouvé par l’algorithme de Prim.

120/186 120/186
Algorithme de Prim pour la construction d’un ACM (version tbl)

Algorithm 12 ACM_Prim (G(V,E),w,r)

Require: Un graphe G = (V , E ) avec des poids we , e ∈ E. r est le sommet initial.

Ensure: Un ACM défini par les pointeurs prev (v ), ∀v ∈ V .
1: Initialisation : ∀u ∈ V : clef (u ) ← ∞ and prev (u ) ← nil ; S ← 0
/ ; clef (r ) ← 0 ;
2: F ← maketbl(V) {crée un tbl F avec clef (v ), v ∈ (V ) comme clés}
3: while F is not empty do
4: u ← ExtractMin(F) // l’élément u sort de F
5: S ← S ∪ {u }
6: for all edges (u , v ) ∈ E do
7: if v ∈ F and clef (v ) > w (u , v ) then
8: clef (v ) ← w (u , v )
9: prev (v ) ← u
10: end if
11: end for
12: end while
13: return prev

Complexité : pour chaque u de la ligne 4 on fait d (u ) mises à jour pour un total

∑v ∈V d (u ) = O (|E |) mises à jour. Le coût de O (|V |) recherches de min dans
un tableau est O (|V |2 ). Au total O (|V |2 + |E |) = O (|V |2 ).

121/186 121/186
Arbres parfaits partiellement ordonnés et tas binaire (Binary heap)

Le tas binaire (Binary heap) est une file de priorité fréquemment utilisée pour
améliorer la complexité des algorithmes comme le tri par tas, l’alg. de Dijkstra,
l’alg. de Prim ...
Définition : Soit π(j ) la clé associée avec l’élément j de la file F. F est un tas
binaire si la condition suivante est satisfaite (relation entre le père et ses deux
fils) :
j
π(j ) ≥ π(b c) ∀j (12)
2
⇐⇒ π(j ) ≤ π(2j ) and π(j ) ≤ π(2j + 1) ∀j
On représente le tas binaire par un arbre parfait partiellement ordonné :
Tout niveau est rempli de gauche à droite ;
Tout niveau est complètement rempli avant de commencer le niveau suivant ;
la condition (12) est satisfaite (l’élément contenu dans tout nœud est inférieur ou
égal aux deux éléments contenus dans ses fils).
Le tas est facile à implémenter avec un tableau.

122/186 122/186
Arbres parfaits partiellement ordonnés et tas binaire : implementation à l’aide
d’un tableau

F IGURE 86 – L’arbre parfait qui visualise un tas binaire avec 10 éléments. Seules les clés sont
indiquées. Ci-dessous le tableau π associé avec ce tas binaire.

j 1 2 3 4 5 6 7 8 9 10
π(j ) 3 10 5 11 12 6 8 15 20 13

On a les règles suivantes :

π(1) est la racine qui contient l’élément le plus petit ;
π(2j ) and π(2j + 1) sont les deux fils, s’ils existent, de π(j ). De plus,
π(j ) ≤ π(2j ) and π(j ) ≤ π(2j + 1) : exemple : π(4) = 11, π(8) = 15, π(9) = 20 ;
π(b 2j c) est père de π(j ) pour j > 1 : exemple : π(9) = 20, π(b 92 c) = π(4) = 11 ;

123/186 123/186
Arbres parfaits partiellement ordonnés et tas binaire : propriétés

Propriétés d’un tas de k éléments :

Chaque élément d’un tas binaire est caractérisé par le couple (nom, valeur
numérique) (v , clef (v )).
la racine contient le plus petit élément. L’opération « accès à la racine » se fait en
Θ(1) ;
l’opération « insertion » se fait en O (log2 k ) ;
l’opération « suppression du minimum » se fait en O (log2 k ).

124/186 124/186
 Arbres parfaits partiellement ordonnés et tas binaire : illustration du
fonctionnement

F IGURE 87 – (a) : un tas binaire avec 10 éléments. Seules les clés sont indiquées. (b)-(d) :
illustration de l’opération « insertion ». (e)-(h) : illustration de l’opération « extraction et
suppression du minimum ».
125/186 125/186
Algorithme de Prim pour la construction d’un ACM (version tas binaire)
Algorithm 13 ACM_Prim (G(V,E),w,r)

Require: Un graphe G = (V , E ) avec des poids we , e ∈ E. r est le sommet initial.

Ensure: Un ACM défini par les pointeurs prev (v ), ∀v ∈ V .
1: Initialisation : ∀u ∈ V : clef (u ) ← ∞ and prev (u ) ← nil ; clef (r ) ← 0 ;
2: F ← makequeue(V) {crée une file de priorité F (binary heap) }
3: while F is not empty do
4: u ← ExtractMin(F)
5: for all edges (u , v ) ∈ E do
6: if clef (v ) > w (u , v ) then
7: clef (v ) ← w (u , v )
8: prev (v ) ← u
9: ChangeKey(F,v) {F is updated according to the new value of clef (v ) }
10: end if
11: end for
12: end while
13: return prev
Complexité :
La ligne (2) s’exécute en O (|V | log |V |).
pour un sommet u donné par la ligne 4 on fait d (u ) mises à jour de la clef.
En total, pour ∀v ∈ V , on fait O (|E |) mises à jour de la clef. Donc la boucle (3-11) s’exécute en
|E | log |V | puisque chaque mise à jour se fait en O (log |V |).
On obtient en total : O (|V | log |V | + |E | log |V |) = O (|E | log |V |).
126/186 126/186
 Algorithme de Kruskal pour la construction d’un ACM ACM_Kruskal
(G(V,E),w) : Illustration

Arête Poids Garder count

considérée l’arête
(B,C) 1 Oui 1
(C,D) 2 Oui 2
(B,D) 2 Non 2
(C,F) 3 Oui 3
(A,D) 4 Oui 4
(D,F) 4 Non 4
(E,F) 4 Oui 5
(A,B) 5 Non -
(C,E) 5 Non -
(A,C) 6 Non -
c)

F IGURE 88 – a) un graphe G = (V , E ) ; b) son l’ACM de poids 14 ; c) Illustration du

fonctionnement de l’alg. de Kruskal pour ce graphe. L’algorithme s’arrête quand le conteur count
atteint la valeur |V | − 1.

127/186 127/186
Algorithme de Kruskal pour la construction d’un ACM

Algorithm 14 ACM_Kruskal (G(V,E),w)

Require: Un graphe G = (V , E ) avec des poids we , e ∈ E.

Ensure: Un ACM défini par les arêtes de l’ensemble X .
for all u ∈ V do
makeset(u)
end for
X ← 0/
trier les arêtes E par leur poids
for all (u , v ) ∈ E, dans l’ordre croissant des poids do
if find(u) 6= find(v) then
X ← X ∪ {(u , v )}
union(u,v)
end if
end for
return X

Complexité : On fait |V | makeset, 2|E | find et |V | − 1 unions.

128/186 128/186
Opérations et structures de données pour les ensembles disjoints (Union-Find)

La structure de données maintient à jour une collection {S1 , S2 , . . . , Sk } d’ensembles

dynamiques disjoints.

Chaque ensemble est un arbre orienté, dont la racine est le représentant de cet
ensemble.

Chaque noeud i de l’arbre est muni d’un pointeur, π (i ), vers son père, ainsi que d’un
rang, (rank), qui équivaut à la taille du sous-arbre enraciné à ce noeud.

Cette structure permet de connaître rapidement à quel ensemble appartient un

élément donné, et de pouvoir réunir deux ensembles.

129/186 129/186
Opérations et structures de données pour les ensembles disjoints (suite)
Algorithm 15 procedure makeset (x)

Ensure: crée un nouvel ensemble dont le seul élément (donc le représentant) est x.
π(x ) ← x
rank (x ) ← 0

Algorithm 16 function find(x)

Ensure: retourne un pointeur vers le représentant de l’unique ensemble contenant x.

if x6= π(x ) then
return find(π(x ))
end if
return x

Algorithm 17 function find_bis(x)

Ensure: effectue une compression du chemin lors de l’opération find

if x6= π(x ) then
π(x ) ←find(π(x ))
end if
return π(x )

130/186 130/186
Opérations et structures de données pour les ensembles disjoints (suite)
Algorithm 18 procedure union (x,y)

Require: Deux ensembles dynamiques Sx et Sy représentés par leurs racines. Sx et

Sy sont supposés disjoints avant l’opération.
Ensure: Réunit les ensembles dynamiques Sx et Sy dans Sx ∪ Sy . On fait pointer la
racine du moindre rang sur celle de rang supérieur au moment de l’union. Comme
les ensembles de la collection sont obligatoirement disjoints, on supprime les en-
sembles Sx et Sy .
rx ← find(x)
ry ← find(y)
if rx = ry then
return
end if
if rank(rx ) > rank(ry ) then
π(ry ) ← rx
else
π(rx ) ← ry
if rank(rx ) = rank(ry ) then
rank(ry ) ← rank(ry ) + 1
end if
end if

131/186 131/186
Illustration pour les opérations sur les ensembles disjoints

F IGURE 89 – Résultat des opérations makeset et union sur des ensembles disjoints

132/186 132/186
Analyse de complexité des opérations sur les ensembles disjoints

Propriétés des structures de données pour les ensembles disjoints :

∀x 6= la racine, rank(x) < rank(π(x))
Chaque racine de rang k a au moins 2k noeuds dans son arbre.
n
Chaque ensemble de n éléments possède au plus 2k
noeuds de rang k .
La hauteur de l’arbre représentant un ensemble de n éléments ne dépasse pas
log2 n.

Corolaire 1 La complexité des opérations find et union est en O (log |V |).

Corolaire 2 La complexité de l’algorithme de Kruskal est en
O (|E |(log |E | + log |V |)) = O (|E | log |V |) puisque log |E | ≈ log |V |
(la même que la complexité de l’algorithme de Prim).

133/186 133/186
Algorithme de Prim versus l’algorithme de Kruskal

Une instance géometrique du problème de l’arbre couvrant de poids minimal (ACM) :

les poids des arêtes sont proportionnels à la distance géometrique entre les sommets.

F IGURE 90 – (a) visualise les quatre premières arêtes ajoutées par l’algorithme de Prim à partir
du sommet r ; (b) visualise les quatre premières arêtes ajoutés par l’algorithme de Kruskal. Pout
les deux cas la ligne indiquée en pointillés est la suivante à être ajoutée.
134/186 134/186
 Calcul des Plus Courts Chemins (PCC)
dans les graphes

Le cas des valeurs positives des arcs/arêtes

135/186 135/186
Parcours en largeur d’abord et calcul des PCC de s aux autres sommets :
le cas où la longueur de chaque arête vaut 1

G = (V , E ) | ∀(u , v ) ∈ E , l (u , v ) = 1 (la longueur de chaque arête vaut 1).

La distance du sommet s à tout sommet v ∈ V accessible depuis s, est notée
v.dist. Elle représente la longueur d’UN plus court chemin PCC(s ; v ), en
nombre d’arêtes entre s et v .
Ces distances sont calculées par la version suivante de l’algorithme BFS(G,s) :

Algorithm 19 BFS(G,s) (2e version du parcours en largeur d’abord).

Require: G=(V,E), ∀(u , v ) ∈ E l(u,v)=1, start vertex s.

Ensure: For all vertices u reachable from s, u.dist is set to the distance from s to u.
1: Initialisation : ∀v ∈ V : v .visited ← false and v .dist = ∞ ; F ← [s] ; s.dist ← 0 ;
s.visited ← true ;
2: while (F 6= 0 / ) do
3: u ← ExtractMin(F) : { u reçoit le sommet de la file F qui en est supprimé }
4: while (∃(u , v ) ∈ E | v .visited = false ) do
5: v.visited ← true
6: v.dist ← u.dist+1
7: inject(F,v) { le sommet v est inséré dans F }
8: end while
9: end while

136/186 136/186
Illustration

F IGURE 91 – Fonctionnement de l’algorithme 19 et la file F (FIFO) pour le graphe ci-dessus. On

obtient S .dist = 0, A.dist = C .dist = D .dist = E .dist = 1 et B .dist = 2.

Remarque : tous les chemins partant de la racine s sont des PCC (c.-à-d. que ceci
est un arbre des PCC de s à tous les autres sommets).

137/186 137/186
BFS(G,s) : validation formelle

Proposition : BFS(G,s) visite chaque sommet accessible à partir de s.

Preuve : Par induction à la base des propriétés suivantes :
Lors de l’exécution de BFS(G,s), pour chaque valeur des distances
d = 0, 1, 2, . . . , max_dist il existe un moment tel que :
pour chaque v éloigné de s à une distance ≤ d, la valeur v .dist a été correctement
calculée.
pour tous les autres sommets u , u .dist = ∞.
la file F contient uniquement les sommets u éloigné de s à une distance égale à d.
Analyse de complexité (similaire à l’analyse de DFS(G,s)) :
chaque sommet est inséré une fois dans F lors de sa première visite, et est éjecté de
F lorsque tous ses voisins ont été visités (au total 2 × |V | opérations
insertion/éjection) .
Chaque arête (u,v)∈ E est examinée exactement deux fois (en cas d’un graphe non
orienté) ; chaque arc est examiné une seule fois (en cas d’un graphe orienté). Donc,
Θ(|E |) opérations sur les arêtes/arcs.
Au total Θ(|V | + |E |).

138/186 138/186
Calcul des PCC de s aux autres sommets dans le cas le > 0 : ∀e ∈ E

Algorithm 20 Dijkstra_a (G,l,s).

Require: Graph G=(V,E) with positive edge weights le > 0 : ∀e ∈ E, vertex s ∈ V

Ensure: ∀u ∈ V , dist (u ) is set to the shortest distance from s to u ; prev (u ) points
to the predecessor of u on this shortest path
1: Initialisation : ∀u ∈ V : dist (u ) ← ∞ and prev (u ) ← nil ; dist (s ) ← 0 ;
2: P ← 0 / , (P contient les sommets v , tq dist (v ) est définitif)
3: T ← V (T contient des sommets v , tq dist (v ) n’est qu’une borne supérieure)
4: while T is not empty do
5: u ← argmin dist (v ) // u = v ∈ T | dist (v ) is minimal
v ∈(T )
P ← P {u }
S
6:
7: T ← T \{u }
8: for all edges (u , v ) ∈ E do
9: dist_update(u,v)
10: end for
11: end while

139/186 139/186
Algorithme de Dijkstra (suite)

Algorithm 21 dist_update(u,v).

1: if dist (v ) > dist (u ) + l (u , v ) then

2: dist (v ) = dist (u ) + l (u , v )
3: prev (v ) ← u
4: end if

Exemple :

140/186 140/186
Application de l’algorithme de Dijkstra sur un graphe
B D B D
4 2 2

3
A 1 3 1 A 1
4 3
2 2
C E C E
5

itér P T

A B C D E
0 ∅ 0 ∞, nil ∞, nil ∞, nil ∞, nil
1 {A} — 4, A 2, A ∞, nil ∞, nil
2 {A; C } — 3, C — 6, C 7, C
3 {A; C ; B } — — — 5, B 6, B
4 {A; C ; B ; D } — — — — 6, B
5 {A; C ; B ; D ; E } — — — — —

F IGURE 92 – A est le sommet de départ. Chaque colonne u contient le couple

(dist (u ), prev (u )). A chaque itération l’opération u ← argmin dist (v ) (v ∈ (T )) est effectuée.
Les valeurs dist (v ) sont mises à jour suivant dist_update(u , v ). Les valeurs prev (v ) permettent
de construire l’arbre des plus courts chemins de A vers chaque sommet v du graphe.

141/186 141/186
Justification de l’alg. de Dijkstra

Soit le graphe G = (V , E , le > 0 : e ∈ E ). On cherche les PCC (s ; u ) : les plus

courts chemins de s aux autres sommets u ∈ V \{s}. Notons dist ∗ (u ) la
longueur du PCC (s ; u ).
L’algorithme procédera en |V | − 1 itérations. Au début de chacune des itérations
V est partitionné en deux sous-ensembles P et T , avec s ∈ P.
Chaque sommet u ∈ V est muni d’une attribut dist (u ) qui vérifie les propriétés
suivantes ;
si u ∈ P : dist (u ) = dist ∗ (u )
si u ∈ T : dist (u ) = min dist (v ) + l (v , u )
v ∈P , v ∈Γ−1 (u )

La valeur dist (u ), u ∈ T donne la longueur du PCC (s ; u ) à condition que tous

les sommets excepté u soient dans P. Ainsi, à chaque itération dist (u ) fournit
une borne supérieure de la valeur cherchée dist ∗ (u ). Initialement dist (u ) = ∞, à
la fin du calcul, dist ∗ (u ) = dist (u ).

142/186 142/186
Justification de l’alg. de Dijkstra

L’algorithme procéde en |V | − 1 itérations. Au début de chacune des itérations V

est partinionné en deux sous-ensembles P et T , avec s ∈ P.
Chaque sommet u ∈ V est muni d’une étiquette dist (u ) qui vérifie :
si u ∈ P : dist (u ) = dist ∗ (u )
si u ∈ T :
dist (u ) = min dist (v ) + l (v , u ) (13)
v ∈P ,v ∈Γ−1 (u )

Lemme : Soit u ∈ T tq

dist (u ) = min dist (v ) (14)

v ∈T

Alors dist ∗ (u ) = dist (u ).

Preuve : Il ∃ évidemment un chemin λ : s ; u de longueur dist (u ).
Considérons un autre chemin µ : s ; u, et divisons le en deux parties µ1 : s ; h
et µ2 : h ; u, où h est le premier sommet de T rencontré, et µ2 le reste du
chemin. Alors length(µ1 ) ≥ dist (h) d’après (13) ; et dist (h) ≥ dist (u ) d’après
(14). Puisque length(µ2 ) ≥ 0, on obtient
length(µ) = length(µ1 ) + length(µ2 ) ≥ length(µ1 ) ≥ dist (h) ≥ dist (u ) et donc λ
est le plus court chemin s ; u.

143/186 143/186
Analyse de complexité - version tableaux (Array)
Algorithm 22 Dijkstra_a (G,l,s).

Require: Graph G=(V,E) with positive edge weights {le > 0 : e ∈ E }, vertex s ∈ V
Ensure: ∀u ∈ V , dist (u ) is set to the shortest distance from s to u ; prev (u ) points
to the predecessor of u on this shortest path
1: Initialisation : ∀u ∈ V : dist (u ) ← ∞ and prev (u ) ← nil ; dist (s ) ← 0 ;
2: P ← 0 / , (P contient les sommets v , tq dist (v ) est définitif)
3: T ← V (T contient des sommets v , tq dist (v ) n’est qu’une borne supérieure)
4: while T is not empty do
5: u ← argmin dist (v )
v ∈(T )
P ← P {u }
S
6:
7: T ← T \{u }
8: for all (u , v ) ∈ E do
9: dist_update(u,v)
10: end for
11: end while

Alg 22 nécessite |V | opérations argmin plus |E | opérations update. La coût de

ces opérations dépend du choix de la structure de données.
Si on utilise Array : on obtient Θ(|V |2 + |E |).
144/186 144/186
Arbres parfaits partiellement ordonnés et tas binaire (Binary heap)

Le tas binaire (Binary heap) est une file de priorité importante fréquemment
utilisée pour améliorer la complexité des algorithmes comme le tri par tas, l’alg.
de Dijkstra, l’alg. de Prim ....
Définition : Soit π(j ) la clé associée avec l’élément j de la file F. F est un tas
binaire si la condition suivante est satisfaite (relation entre le père et ses deux
fils) :
j
π(j ) ≥ π(b c) ∀j (15)
2
⇐⇒ π(j ) ≤ π(2j ) and π(j ) ≤ π(2j + 1) ∀j
On représente le tas binaire par un arbre parfait partiellement ordonné :
∀ niveau est rempli de gauche à droite ;
∀ niveau est complètement rempli avant de commencer le niveau suivant ;
la condition (15) est satisfaite (l’élément contenu dans tout nœud est inférieur ou
égal aux éléments contenus dans les fils de ce nœud).
Le tas est facile à implémenter en tableau.
Les propriétés essentielles d’un tas binaire de k éléments :
la racine contient le plus petit élément. L’opération « accès à la racine » se fait en
O (1) ;
l’opération « insertion » se fait en O (log2 k ) ;
l’opération « suppression du minimum » se fait en O (log2 k ).

145/186 145/186
Version tas binaire de l’alg. de Dijkstra

Algorithm 23 Dijkstra_bis(G,l,s).

Require: Graphe G=(V,E) directed or undirected, with positive edge weights {le : e ∈
E } ; vertex s ∈ V
Ensure: For all vertices u ∈ V , dist (u ) is set to the shortest distance from s to u ;
prev (u ) points to the previous of u on this shortest path
1: Initialisation : ∀u ∈ V : dist (u ) ← ∞ and prev (u ) ← nil ; dist (s ) ← 0
2: P ← {s } // P contient les sommets v tq dist (v ) est définitif
3: T ← makequeue(V) // crée une file de priorité T avec dist () comme clé
4: while T is not empty do
5: u ← ExtractMin(T)
P ← P {u }
S
6:
7: T ← T \{u }
8: for all (u , v ) ∈ E do
9: dist_update_bis(T,(u , v ))
10: end for
11: end while

146/186 146/186
Version tas binaire de l’alg. de Dijkstra (suite)

Algorithm 24 dist_update_bis(T,(u , v )).

Require: Priority queue T using dist as keys ; an edge (u , v ) ∈ E

Ensure: T is updated if the value of dist (v ) has been modified
if dist (v ) > dist (u ) + l (u , v ) then
dist (v ) ← dist (u ) + l (u , v )
prev (v ) ← u
ChangeKey(T,v) // T est mis à jour selon la nouvelle valeur de dist (v )
end if

Analyse de complexité de la version tas binaire de l’alg. de Dijkstra

makequeue(V) nécessite O (|V | log |V |) opérations.

la boucle WHILE (ligne 4) nécessite O (|V |) ExtractMin plus O (|E |)
ChangeKey (mises à jour) : O ((|V | + |E |) log |V |) opérations.
Au total : O ((|V | + |E |) log |V |).

147/186 147/186
Calcul des chemins les plus courts dans les graphes :

Présence de poids négatifs

148/186 148/186
Présence de poids négatifs

Les valeurs dist () dans l’alg. de Dijkstra sont soit des valeurs exactes (valeur du
chemin le plus court), soit des bornes supérieurs. On a dist (u ) = dist ∗ (u ) si tous les
sommets intermédiaires des chemins s ; u sont dans P. Les valeurs successives
dist () peuvent être vues comme une suite des mises à jour :

Algorithm 25 update((u , v ) ∈ E).

dist (v ) = min{dist (v ), dist (u ) + l (u , v )}

Propriétés :
dist (v ) = dist ∗ (v ) si dist (u ) = dist ∗ (u ) et si u est l’avant-dernier sommet
(u = prev (v )) sur le PCC(s;v) ;
la procédure update((u , v )) ne génère que des bornes supérieures à la valeur
dist ∗ (v ).
Utilisation pour chercher le PCC(s;v) :
(a) | PCC (s ; v ) |≤| V | −1 ;
(b) si update() est appliqué aux arêtes du PCC(s;v)
(s, u1 ), (u1 , u2 ), (u2 , u3 ), . . . (u , v ) dans cet ordre, alors dist (v ) = dist ∗ (v ).

149/186 149/186
Présence de poids négatifs : Algorithme de Bellman-Ford

Algorithm 26 Bellman-Ford (G,l,s).

Require: Graphe G=(V,E) directed, edge weights {le : e ∈ E } with no negative cycles ;
vertex s ∈ V
Ensure: For all vertices u ∈ V reachable from s, dist (u ) is set to the shortest distance
from s to u ;
1: for all u ∈ V do
2: dist (u ) ← ∞
3: end for
4: dist (s ) ← 0
5: k ← 1
6: while (k ≤ |V | − 1) do
7: for all edges (u , v ) ∈ E do
8: dist (v ) ← min{dist (v ), dist (u ) + l (u , v )}
9: end for
10: k ← k +1
11: end while

Complexité de l’algorithme (26) : O (|V |.|E |)

150/186 150/186
Algorithme de Bellman-Ford (variant)

Une autre approche est d’utiliser la fonction multivoque Γ−1 et l’observation que le
(PCC(s;v)) passe par un des prédécesseurs u ∈ Γ−1 (v ). On doit donc avoir
dist (v ) = min {dist (u ) + l (u , v )} = min{dist (v ), min {dist (u ) + l (u , v )}}
u ∈Γ−1 (v ) u ∈Γ−1 (v )
(16)
On obtient la variante suivante.

Algorithm 27 Bellman-Ford_bis (G,l,s).

Require: Graphe G=(V,E) directed, edge weights {le : e ∈ E } ; vertex s ∈ V

Ensure: dist k (u ) is set to the shortest distance from s to u over all paths with at most
k arcs. It also detects the presence of negative cycle.
0 0
1: Initialisation : ∀u ∈ V : dist (u ) ← ∞ ; dist (s ) ← 0 ; stable ← false ; k ← 1 ;
2: while ((k ≤ |V |) and (non stable)) do
3: dist k (s) ← 0
4: for all vertices v ∈ V \ {s} do
5: dist k (v ) = min{dist k −1 (v ), min dist k −1 (u ) + l (u , v )}
u ∈Γ−1 (v )
6: end for
7: stable ← (dist k (v ) = dist k −1 (v ), for all v ∈ V ) ; k ← k + 1 ;
8: end while
9: if (k = |V | + 1) then ∃ negative cycle
10: end if
151/186 151/186
Illustration de l’algorithme de Bellman-Ford

F IGURE 93 –

Algorithm 28 Procédure update((u , v ) ∈ E).

dist (v ) = min{dist (v ), dist (u ) + l (u , v )}

152/186 152/186
Techniques d’accélération de l’algorithme de Bellman-Ford_bis

dist k (v ) représente la valeur du PCC (s ; v ) qui ne contient pas plus de k arcs.

Dans l’algorithme (27) on a le choix de l’ordre à la ligne 4 et on a intérêt à définir
un ordre astucieux sur les sommets.
Par exemple si les le sont positifs et l’ordre est défini par l’alg de Dijkstra, alors
l’alg. (27) converge en une seule étape.
Si peu d’arcs ont une valeur négative, on a aussi intérêt à d’abord exécuter l’alg.
de Dijkstra qui donnera une bonne initialisation des valeurs dist (v ) et on prendra
alors comme ordre celui des dist (v ) croissants.

153/186 153/186
Accélérations posibles pour l’algorithme de Bellman-Ford_bis (exemple)

2
4

2 5
1

7
−2
1 2
2 3

3 6
2

154/186 154/186
Calcul des chemins les plus courts/longs (PCC/PLC)
dans les graphes

L’approche programmation dynamique

155/186 155/186
Les principes de la programmation dynamique

Soit le graphe G = (V , E , le , ∀e ∈ E ), où le est la longueur de l’arc e, et soit un

sommet donné s ∈ V .
Problème : Trouver les PCC du sommet s ∈ V à tous les autres v ∈ V \{s}.
Observation : Pour calculer le PCC(s;v), dont la valeur est calculée dans la
variable dist (v ), on observe que le PCC(s;v) passe par un des prédécesseurs
u ∈ Γ−1 (v ). On doit donc avoir

dist (v ) = min {dist (u ) + l (u , v )} (17)

u ∈Γ−1 (v )

L’équation (17) permet de calculer la valeur dist (v ) sous l’hypothèse que les
valeurs dist (u ), ∀u ∈ Γ−1 (v ) sont calculées. Cette stratégie permet de résoudre
un ensemble de sous-problèmes en commençant par les plus « petits », et en
allant vers les plus « grands ». Pour les « plus petits » la solution est connue.
C’est une méthode de résolution applicable aux problèmes qui satisfont le
principe d’optimalité de Bellman (1955) : chaque sous-chemin d’un chemin
optimal est lui-même optimal.
C’est un principe générique. La fonction min de la l’équation (17) peut être
remplacée par la fonction max et l’opérateur binaire « addition » par
« multiplication ».

156/186 156/186
L’alg. de Bellman-Ford vu dans le contexte de la programmation dynamique

Notons dist k (v ) la valeur du PCC (s ; v ) qui contient au plus k arcs et réécrivons

(17) sous la forme :

dist k (v ) = min{dist k −1 (v ), min dist k −1 (u ) + l (u , v )} (18)

u ∈Γ−1 (v )

La récurrence (18) permet ainsi de calculer la valeur dist k (v ) sous l’hypothèse que
les valeurs dist k −1 (u ), ∀u ∈ Γ−1 (v ) ont été calculées. Ce qui nécessite de résoudre
des sous- problèmes possedant un arc de moins par rapport au problème originel.

157/186 157/186
Les principes de la programmation dynamique

Trouver le PCC est particulièrement simple dans le cas d’un graphe G = (V , E )

de type DAG (graphe orienté, sans circuit).
Cela est dû à la propriété des DAG d’être linéarisés (les sommets peuvent être
numérotés de façon que pour chaque arc (u , v ) ∈ E on a num(u ) > num(v )).
Le calcul des valeurs dist dans l’ordre linéaire décroissant garantit que les
valeurs nécessaires pour le calcul de dist (v ) sont déjà connues au moment de
ce calcul.
Cela permet de trouver les valeurs dist avec un seul parcours des sommets.

F IGURE 94 – À gauche : un graphe G ; A droite : le même graphe après l’avoir trié/ordonné

topologiquement/linéairement. Un seul parcours de gauche à droite permet de calculer les
valeurs dist.

A B 3
6

1 2
S 4 1 E S0 C0 A0 B0 D0 E0
2 4 6 1 1

2 1
1 2
C D
3

158/186 158/186
Algorithmes pour linéariser un DAG (graphe orienté sans circuit) (rappel)

Propriétés importantes des DAG :

(a) Chaque DAG a au moins un sommet source (sommet sans prédécesseurs) et au
moins un sommet puits (sommet sans successeurs)
(b) Les sommets du graphe peuvent être numérotés dans l’ordre topologique (ils
peuvent être placés sur une ligne de façon que tous les arcs soient orientés de
gauche à droite).

Algorithm 29 Premier algorithme pour linéariser un DAG.

Require: G=(V,E), DAG

Ensure: List vertices in linear order.
1: Perform a DFS search and obtain the number post(v) for any vertex v ∈ V .
2: List vertices in order of decreasing post(v) values.

Algorithm 30 Deuxième algorithme pour linéariser un DAG.

1: Find a source, output it, and delete it from the graph.

2: Repeat until the graph is empty.

159/186 159/186
Linéarisation d’un DAG par l’algorithme 29

F IGURE 96 – La numérotation
F IGURE 95 – Un graphe G = (V , E ). [pre, post ] obtenue avec un parcours
DFS (G, A).

F IGURE 97 – Le graphe G est trié topologiquement (linéarisé) par l’ordonnancement des

sommets v ∈ V dans l’ordre décroissant de leur numérotation post (v ) calculée lors d’un
parcours en profondeur DFS (G).

160/186 160/186
Application de l’ordre topologique/linéaire pour la détermination des chemins
les plus courts/longs dans un DAG

Algorithm 31 Procédure dag-shortest-paths(G,l,s).

Require: DAG G=(V,E), edge weights {le : e ∈ E }, vertex s∈ V

Ensure: For all vertices u reachable from s, dist (u ) is set to the distance from s to u
1: for all u ∈ V do
2: dist (u ) ← ∞
3: end for
4: dist (s ) ← 0
5: linearize G
6: for all u ∈ V , in linearized order do
7: for all edges (u , v ) ∈ E do
8: dist (v ) = min{dist (v ), dist (u ) + l (u , v )}
9: end for
10: end for

Complexité de l’algorithme (31) : Θ(|V | + |E |) ( le coût de la linéarisation à la

ligne 5 (Θ(|V | + |E |)) + le coût des boucles (6) et (7) ( ∑ du+ ) = Θ(|V | + |E |)).
u ∈V

161/186 161/186
Application de l’ordre topologique/linéaire pour la détermination des chemins
plus courts/longs dans un DAG

Algorithm 32 Procédure dag-shortest-paths(BIS)(G,l,s).

Require: DAG G=(V,E), edge weights {le : e ∈ E }, vertex s∈ V

Ensure: For all vertices u reachable from s, dist (u ) is set to the distance from s to u
1: for all u ∈ V do
2: dist (u ) ← ∞
3: end for
4: dist (s ) ← 0
5: linearize G
6: for all v ∈ V \ {s }, in linearized order do
7: for all edges (u , v ) ∈ E do
8: dist (v ) := min{dist (v ), dist (u ) + l (u , v )}
9: end for
10: end for

162/186 162/186
Les principes de la programmation dynamique

La récurrence (18) illustre bien l’approche programmation dynamique qui

consiste à résoudre un ensemble de sous-problèmes {dist (u ), u ∈ V } en
commençant par les plus « petits » (les prédécesseurs) et en allant
progressivement vers les plus « grands » (les successeurs).
Cependant, le graphe DAG peut ne pas être explicitement donné, mais il est
implicite.
Les sommets représentent dans ce cas les sous-problèmes à résoudre, tandis
que les arcs correspondent aux dépendances entre les problèmes ; si la solution
du sous-problème B nécessite une réponse du sous-problème A, on met un arc
(conceptuel) de A à B.
A est considéré ainsi comme un sous-problème plus petit que B (un
prédécesseur de B).

163/186 163/186
 La plus longue sous-séquence croissante

Donné : Une séquence de nombres S = a1 , a2 , . . . , an .

Def_1 : Une sous-séquence : chaque sous-ensemble des nombres ai1 , ai2 , . . . , aik tel
que 1 ≤ i1 ≤ i2 ≤ . . . ik ≤ n.
Def_2 : Une sous-séquence croissante : telle que les nombres ai croissent.
Problème : Trouver la plus longue sous-séquence croissante de S (PLSSC(S)).
Exemple : La plus longue sous-séquence croissante de S = 5, 2, 8, 6, 3, 6, 9, 7 est 2, 3, 6, 9.

164/186 164/186
La plus longue sous-séquence croissante

L’espace des solutions peut-être représenté par un DAG G = (V , E ) où à

chaque nombre ai est associé un sommet i ∈ V et un arc (i , j ) si i < j et ai < aj .
On établit ainsi une bijection (« une correspondence un-à-un ») entre les
chemins dans G et les sous-séquences croissantes dans S.
L’objectif est de trouver le plus long chemin (PLC) dans ce graphe.
Exemple : Le graphe DAG associé à la séquence S = 5, 2, 8, 6, 3, 6, 9, 7.

165/186 165/186
Algorithme pour la plus longue sous-séquence croissante

Algorithm 33 Algorithme longest increasing subsequence.

1: for j = 1 to n do
2: L(j ) = 1 + max{L(i ) | (i , j ) ∈ E }
3: end for
4: return maxj L(j )
where max{} = 0.

L’idée de base : L(j ) est la longueur de la PLSSC aboutissant au sommet j (+1)

(on cherche le nombre de sommets et non d’arêtes).
L(j ) est la longueur maximale parmi les PLSSC des prédécesseurs du j (+1).
On découvre ici l’approche programmation dynamique : l’ordre et les relations
entre les problèmes indiquent que pour résoudre un problème donné L(j ), il faut
que ses prédécesseurs (les sous-problèmes qui le précédent) soient résolus.
Complexité de l’algorithme (33) : le coût de la boucle for lignes de 1 à 3 :
(Θ(|V |)) ; + le coût de la ligne (2) ∑j ∈V d − (j ) = Θ(|E |). En total :
Θ(|V | + |E |) = O (n2 ).
L’algorithme (33) ne trouve que la longueur de la PLSSC. Pour connaitre la
séquence même, il faut sauvegarder les indices argmax de la ligne (2).
166/186 166/186
Attention aux appels récursifs naïfs ! ! ! !

La ligne 2 de l’algorithme (33) suggère une alternative – pourquoi ne pas utiliser

un algorithme récursif ?
En fait, c’est une mauvaise idée puisque l’algorithme récursif s’exécute en temps
exponentiel.
Considérons par exemple le cas d’une séquence croissante. Elle contient tous
les arcs {(i , j ) | i < j }. La formule devient
L(j ) = 1 + max{L(1), L(2), . . . , L(j − 1)}.
Pour L(5) on obtient alors :

Et ce sous-problème sera résolu plusieurs fois ! Pour L(n) la taille de l’arbre sera
exponentielle. Cela s’explique par les dépendances entre les problèmes L(j ) et
L(j − 1) ; ils sont presque de la même taille.
Pour améliorer l’efficacité il faut mémoriser les solutions des sous-problèmes
résolus, et les calculer dans le bon ordre (cela évoque déjà la programmation
dynamique).
167/186 167/186
La fonction rang pour les graphes sans circuit (DAG)

Propriétés importantes des DAG (rappel) :

(a) Il existe au moins un sommet s tel que Γ−1
s =0
/ (c.-à-d. s est sans prédécesseurs).
(b) Les sommets du graphe peuvent être numérotés dans l’ordre topologique (ils
peuvent être placés sur une ligne de façon que tous les arcs soient orientés de
gauche à droite).
Afin de générer un ordre topologique, en plus les algorithmes 29 et 30, on peut
aussi utiliser l’algorithme (34) qui calcule la fonction rang.
Pour introduire rapidement cette notion, nous supposerons que le graphe
possède un seul sommet sans prédécesseurs (disons le sommet s).
La fonction rang associe à chaque sommet v ∈ V \{s} la valeur rank (v ) qui
correspond au nombre d’arcs d’un chemin de cardinalité maximum entre s et v .

168/186 168/186
Une application de la fonction rang
Obtention d’un diplôme Master d’informatique (sujet d’examen)

Pour obtenir un Master d’informatique, il est nécessaire d’avoir passé un certain

nombre de modules. Chaque module demande un certain nombre de prérequis. Un
master simplifié pourrait se composer (prérequis entre parenthèses) de :
Système (Programmation) ;
MAG (Programmation, Maths discrètes) ;
Sécurité réseau (Système, Initiation réseau) ;
Initiation réseau (Programmation, MAG) ;
Systèmes répartis (MAG, Systèmes, Initiation réseau).

1. Modéliser les pré-requis à l’aide d’un graphe.

2. Quel est le nombre minimum de semestres pour obtenir ce master ? On suppose
bien sur que vous passez tous les examens avec succès, que chaque module
dure un semestre et est enseigné chaque semestre. Le nombre de modules
suivis par un étudiant pendant un semestre n’est pas limité et il n’y a pas de
problème d’emploi du temps. Indiquer l’algorithme utilisé et justifiez votre choix.
3. Un étudiant décide d’étudier un module dès qu’il a obtenu les modules
prérequis. Quel est le nombre maximum de modules qu’il devra suivre
simultanément en appliquant cette stratégie ? Quel algorithme permet de le
calculer ? Justifiez votre choix.
169/186 169/186
Obtention d’un diplôme Master d’informatique : suite 1

1. Modéliser les prérequis à l’aide d’un graphe.

F IGURE 98 – Modélisation à l’aide d’un graphe : les sommets correspondent aux modules, les
arcs - aux pré-requis.

170/186 170/186
Cas des graphes sans circuit (DAG) : calcul de la fonction rang
Les questions suivantes nécessitent l’utilisation de la fonction rang calculée par :

Algorithm 34 Vertex-rank(G).

Require: DAG G = (V , E ), vertex s∈ V such that d − (s) = 0.

Ensure: For all vertices u reachable from s, rank (u ) is set to the number of arcs in
the longest (in cardinality) path from s to u
− −1
1: Initialisation : ∀u ∈ V : d (u ) ← |Γ (u )| ; k ← 0 ; S0 ← {s } ;
2: while |Sk | > 0 do // Sk est l’ensemble des sommets v tels que d − (v ) = 0
3: Sk +1 ← 0/
4: for all u ∈ Sk do
5: rank (u ) ← k
6: for all edges (u , v ) ∈ E do
7: d − (v ) ← d − (v ) − 1
8: if (d − (v ) = 0) then
Sk +1 ← Sk +1 {v }
S
9:
10: end if
11: end for
12: end for
13: k ← k +1
14: end while

Complexité de l’algorithme (34) : Θ(|V | + |E |).

171/186 171/186
Calcul de la fonction rang : Illustration de l’algorithme vertex-rank(G)

k Sk d − (Sys) d − (SecR ) d − (Prog ) d − (MD ) d − (MAG) d − (SysRep) d − (IniR )

0 Prog , MD 1 2 0 0 2 3 2
1 Sys, MAG 0 2 0 3 1
2 IniR 1 1 0
3 SysRep, SecR 0 0

F IGURE 99 – Sk est l’ensemble des sommets v tels que d − (v ) = 0 ; La fonction rang associe à
chaque sommet v ∈ V le nombre rank (v ) tel que rank (v ) =le nombre d’arcs dans un chemin
de cardinalité maximum entre les sommets sans prédécesseurs et v . On obtient ici
rank (Prog ) = rank (MD ) = 0, rank (Sys) = rank (MAG) = 1, rank (IniR ) = 2 et
rank (SysRep) = rank (SecR ) = 3.

172/186 172/186
Obtention d’un diplôme Master d’informatique : suite

Les valeurs da la fonction rang calculées précédement (rank (Prog ) = rank (MD ) = 0,
rank (Sys) = rank (MAG) = 1, rank (IniR ) = 2 et rank (SysRep) = rank (SecR ) = 3)
permettent de visualiser le graphe par niveaux et de répondre aux questions
suivantes.
1. Quel est le nombre minimum de semestres pour obtenir ce master ?

F IGURE 100 – Les modules sont ordonnancés dans l’ordre croissant de leur numéro rank . Le
graphe est représenté par niveaux, chaque niveau correspond aux sommets ayant la même
valeur rank .
173/186 173/186
Obtention d’un diplôme Master d’informatique : suite

1. Quel est le nombre minimum de semestres pour obtenir ce master ?

F IGURE 101 – Au moins 4 semestres sont nécessaires pour obtenir ce master. Cela peut se
calculer par l’algorithme Vertex-rank-longest-paths(G,l,s) qui permet de calculer le plus long
chemin (PLC) du premier au dernier niveau dans un graphe par niveaux.

174/186 174/186
Calcul des PCC/PLC dans un graphe sans circuit (DAG)

Algorithm 35 Vertex-rank-shortest-paths(G,l,s).

Require: DAG G = (V , E ), edge weights {le : e ∈ E }, vertex s∈ V , G is represented

by vertex-rank levels
Ensure: For all vertices u reachable from s, dist (u ) is set to the shortest distance from
s to u
1: for all u ∈ V do
2: dist (u ) ← ∞
3: end for
4: dist (s ) ← 0
5: for all vertices v ∈ V \ {s } in rank order do
6: dist (v ) = min {dist (u ) + l (u , v )}
u ∈Γ−1 (v )
7: end for

Complexité : la boucle des lignes (1-3) : Θ(|V |) ; + le coût de la boucle (5-7) :

∑ d − v = Θ(|V | + |E |). Total pour l’algorithme (35) : Θ(|V | + |E |).
v ∈V
l’opérateur min à la ligne 6 peut être remplacé par l’opérateur max (d’après le le
principe de la programmation dynamique). On modifie respectivement la ligne 2
en dist (u ) ← −∞ et on obtient ainsi l’algorithme
Vertex-rank-longest-paths(G,l,s) qui permet de calculer les PLC.
175/186 175/186
Obtention d’un diplôme Master d’informatique : suite

1. Quel est le nombre maximum de modules que l’étudiant doit suivre

simultanément en appliquant cette stratégie ?

F IGURE 102 – Le nombre maximum de modules qu’il devra suivre simultanément vaut 2 : c’est le
nombre maximum de sommets dans un niveau (colonne) du graphe représenté par niveaux, où
chaque niveau correspond aux sommets ayant la même valeur rank .

176/186 176/186
Ordonnancement de tâches

177/186 177/186
Ordonnancement de tâches

Problème : Déterminer l’ordre et le calendrier d’exécution de N tâches d’un projet

supposées indivisibles et soumises à des contraintes de succession dans le temps,
afin de minimiser la durée totale du projet.

L’approche « graphe potentiel-tâches »

À partir d’un projet donné, on construit un graphe sans circuit (DAG) comme suit :

A toute tâche i est associé un sommet i ; plus précisément, le sommet est

associé au début de la tâche. Les contraintes sont définies sur le début de
chaque tâche.

i di j
On ajoute un arc (i , j ) de longueur di , noté par , si la
tâche i de durée di doit précéder la tâche j ;
On ajoute deux tâches fictives α (début) et ω (fin) ;
α est reliée aux sommets sans prédécesseur ;
ω est reliée aux sommets sans successeur.
On structure alors le graphe en niveaux après avoir calculé sa fonction rang ;

178/186 178/186
Ordonnancement de tâches

Exemple : Construction d’un pavillon

La construction d’un pavillon demande la réalisation d’un certain nombre de tâches.
La liste des tâches à effectuer, leur durée et les contraintes d’antériorité à respecter
sont données dans le table ci-dessous. Le travail commençant à la date 0, on cherche
un planning des opérations permettant de minimiser la durée totale.

Code tâche libellé durée antériorité

(semaines)
A Travaux de maçonnerie 7 -
B Charpente de la toiture 3 A
C Toiture 1 B
D Installation électrique 8 A
E Façade 2 D,C
F Fenêtres 1 D,C
G Aménagement du jardin 1 D,C
H Travaux de plafonnage 2 F
J Peinture 2 H
K Emménagement 1 E,G,J

F IGURE 103 – Liste des tâches, durée et contraintes.

179/186 179/186
Les tâches pour la construction d’un pavillon

F IGURE 104 – La représentation du graphe des tâches par niveaux après avoir calculé sa
fonction rang et l’ajout des deux tâches fictives début et fin.

180/186 180/186
Ordonnancement de tâches : l’approche « graphe potentiel-tâches »
Notions principales :
La tâche fictive α (début) est reliée aux sommets sans prédécesseur ;
La tâche fictive ω (fin) est reliée aux sommets sans successeur ;
Le graphe est représenté par niveaux après avoir calculé sa fonction rang ;
La date au plus tôt ti de début de la tâche i : ti = max (tj + dj )
j ∈Γ−
i
1

(c.-à-d. la longueur du plus long chemin de α à i l (PLC (α → i ))).

La durée minimale tω : l (PLC (α → ω)).
Si la durée du projet est fixé à tω , la date au plus tard Ti pour commencer la
tâche i sans compromettre tω est :
Tω = tω ; Ti = min(Tj − di ) ⇒ Ti = tω − l (PLC (i → ω))
j ∈Γi
La marge totale (MTi ) de la tâche i : MTi = Ti − ti . Pour une durée de projet
fixée à tω la marge totale d’une tâche correspond au retard maximale que peut
prendre son début sans retarder la date tω .
Si MTi = 0, la tâche i est dite tâche critique.
La marge libre (MLi ) la la tâche i : MLi = min (tj − ti − di ). Pour un calendrier
(i ,j )∈E
donné, la marge libre d’une tâche correspond au retard maximal que peut
prendre son début sans modifier les dates de début des autres tâches.

181/186 181/186
Ordonnancement de tâches : calcul des dates au plus tôt et au plus tard
Soit le graphe G=(V,E) orienté, sans circuit, avec les durées des tâches comme des
poids sur les arcs {de : e ∈ E }, le sommet α pour le début des tâches, le sommet ω
pour la fin. Les dates les plus tôt et les plus tard peuvent être calculées par les
algorithmes suivants :

Algorithm 36 Dates_au_plus_tôt (G, d , α, ω).

Ensure: Les dates au plus tôt ti , ∀i ;

tα ← 0 ; dα ← 0 ;
for all i ∈ V do dans l’ordre croissant des rangs
ti := max (tj + di )
(j ,i )∈E
end for

Algorithm 37 Dates_au_plus_tard (G, d , α, ω).

Require: que tω soit calculé ;

Ensure: Les dates au plus tard pour calculer Ti , ∀i sans impacter tω ;
Tω ← tω ;
for all i ∈ V do dans l’ordre décroissant des rangs
Ti ← min (Tj ) − di
(i ,j )∈E
end for
182/186 182/186
L’ordonnancement des tâches pour la construction d’un pavillon

F IGURE 105 – L’étiquette (ti , Ti ) associé au sommet i représente les dates au plus tôt et au
plus tard. Les dates au plus tôt (ti ) sont calculées par l’algorithme (36), tandis que les dates au
plus tard (Ti ) sont calculées par l’algorithme (37). Les tâches i dont les marges MTi = Ti − ti
sont nulles sont appllées des tâches critiques. Les tâches critiques et les arcs du chemin critique
obtenu pour la construction de ce pavillon sont soulignés. Si un quelconque retard est pris sur
une de ces tâches la durée minimale de la construction de la villa sera augmentée d’autant.
183/186 183/186
L’ordonnancement des tâches pour la construction d’un pavillon

Code tâche date au date au marge totale marge libre

plus tôt ti plus tard Ti MTi MLi
A 0 0 0 0
B 7 11 4 0
C 10 14 4 4
D 7 7 0 0
G 15 19 4 4
E 15 18 3 3
F 15 15 0 0
H 16 16 0 0
J 18 18 0 0
K 20 20 0 0
fin 21 21 0 0

F IGURE 106 – Caractéristiques de l’ordonnancement des tâches. Les tâches peuvent être
classée en trois catégories : a) tâches pour lesquelles le moindre retard de démarrage allonge le
délai de réalisation du projet. Ce sont les tâches critiques (MTi = 0 - ici {A, D, F, H, J, K } ) ; b)
tâches pour lesquelles le moindre retard de démarrage pérturbe le calendrier (MLi = 0 - ici {B }) ;
c) tâches pour lesquelles un léger retard ne modifie pas le planning (MLi 6= 0 - ici {C, G, E }) ;

184/186 184/186
Compléments pratiques

Les contraintes de type potentiel (la tâche j doit commencer après la fin de i, ou bien
après la moitié de la réalisation de de i, ou bien un certain temps après la fin de i,
etc.) se modélisent facilement dans l’approche « graphe potentiel-tâches ».
la contrainte : j ne doit pas commencer avant la moitié de la réalisation de la
tâche i se représente par un arc supplémentaire (i , j ) de longueur d2i , c.-à-d.

i di /2 j
.
la contrainte : j ne peut commencer qu’un temps t après la fin de i se représente

i di + t j
par un arc (i , j ) de longueur di + t, c.-à-d. .
la contrainte : j ne peut commencer qu’après la date bj , se représente par un arc

α bj j
(α, j ) de longueur bi , c.-à-d. .

185/186 185/186
Compléments pratiques (suite)

la contrainte : j doit commencer au plus tard d unités de temps après le début de

i −d j
i, se représente par un arc (j , i ) de longueur −d, .
la contrainte : j doit commencer avant la date cj , se représente par un arc (j , α)

α −cj j
de longueur −cj , .
la contrainte : j doit suivre immédiatement i, s’écrit ti + di = tj et se représente
par un arc (i , j ) de longueur di et un arc (j , i ) de longueur −di
di

i j

−di

Remarque : Les trois dernières contraintes introduisent des circuits et des arcs de
longueur négative. La condition d’existence d’un ordonnancement devient alors il
n’existe pas de circuit de longueur strictement positive . On devra utiliser un des
algorithmes vus en cours plus adaptés à de telles situations.
186/186 186/186