COURS DE THEORIE DES GRAPHES ET APPLICATIONS

Prof Adama COULIBALY 1

16 janvier 2020

1. Université Félix Houphouët-Boigny, UFR de Mathématiques et Informatique ; 22 BP 582 Abidjan

22
Table des matières

1 Généralités sur les graphes 3

1.1 Graphes orientés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Définitions et propriétés de base . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Cheminement dans un graphe . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.3 Connexité et forte connexité . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Graphes non orientés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2 Chaı̂ne, cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Autres représentations des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.1 Cas des graphes orientés . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.2 Cas des graphes non orientés . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Chemins optimaux 14
2.1 Position du problème de cheminement . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Plus court chemin et distance . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 Condition d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Quelques algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Cas où les longueurs sont positives . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 Cas où les longueurs sont quelconques . . . . . . . . . . . . . . . . . . . . 17
2.2.3 Cas d’un graphe sans circuit . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Problèmes d’ordonnancement 20
3.1 Méthode MPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.1 Principe de la représentation du réseau MPM . . . . . . . . . . . . . . . . 21
3.1.2 Construction du réseau MPM . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.3 Détermination des dates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.4 Les marges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Méthode PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2.1 Principe de la représentation du graphe PERT . . . . . . . . . . . . . . . 22
3.2.2 Construction du graphe PERT . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.3 Détermination des dates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.4 Les marges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4 Problèmes de flots 27
4.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Flot complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2.2 Algorithme de recherche d’un flot complet . . . . . . . . . . . . . . . . . . 30
4.2.3 Variante pour déterminer un flot complet . . . . . . . . . . . . . . . . . . 30
4.3 Algorithme de Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3.1 Prcocédure de détection d’une chaine améliorante . . . . . . . . . . . . . . 35
4.3.2 Prcocédure de modification d’un flot relativement à une chaine améliorante 36
4.3.3 Algorithme de Ford et Fulkerson . . . . . . . . . . . . . . . . . . . . . . . 36
Chapitre 1

Généralités sur les graphes

1.1 Graphes orientés

1.1.1 Définitions et propriétés de base
Définition 1.1.1 Un graphe orienté G est défini par la donnée d’un ensemble fini X dont les
éléments sont appelés des sommets ou noeuds et d’un ensemble U dont les éléments sont des
couples d’éléments de X appelés arcs. On le note G = (X, U ).

Définition 1.1.2 Etant donné un graphe orienté G = (X, U ). Le nombre n de sommets de G

est appelé l’ordre du graphe et m celui des arcs de G est appelé sa taille.

Définition 1.1.3 Dans un graphe orienté, un arc dont les deux extrémités coı̈ncident est appelé
une boucle.

Graphiquement, les sommets sont représentés par des points ou des cercles et un arc u =
(x, y) est représenté par une flèche joignant les sommets x et y, la flèche étant pointée sur y. On
parle alors de représentation sagittale du graphe.

Exemple 1.1.1

Soit G = (X, U ) le graphe orienté défini par : X = {x, y, z} et U = {a, b, c, d, e} où a = (x, z),
b = (z, x), c = (x, y), d = (z, y) et e = (y, y).

z
d
e

a b y

Définition 1.1.4 Etant donné G = (X, U ) un graphe orienté, si u = (x, y) est un arc, alors les
sommets x et y sont dits adjacents ou voisins. En outre le sommet x est dit origine de u et y
extrémité de u. On dit aussi parfois que x est l’extrémité initiale et y l’extrémité terminale de
u.
Définition 1.1.5 Etant donné G = (X, U ) un graphe orienté et x, y deux sommets de G, on
dit que x est un précédent ou un prédécesseur de y, s’il existe un arc de la forme u = (x, y).
Dans ce cas y est un suivant ou un successeur de x. Aussi l’arc u est dit incident à x et y. Plus
précisément il est dit sortant en x ou incident extérieurement à x, et rentrant en y ou incident
intérieurement à y.

Définition 1.1.6 Un sommet qui n’est adjacent à aucun sommet est dit isolé.
Un graphe dont les sommets sont isolés est dit discret.

Définition 1.1.7 Deux arcs sont adjacents s’ils ont une extrémité en commun.

Définition 1.1.8 Le demi-degré extérieur ou demi-degré sortant de sommet x, noté d+ G (x) ou

plus simplement d+ (x) est le nombre d’arcs ayant x pour extrémité initiale.
Le demi-degré intérieur ou demi-degré entrant de sommet x, noté d−
G (x) ou plus simplement
−
d (x) est le nombre d’arcs ayant x pour extrémité finale.
Le degré du sommet x, noté dG (x) ou plus simplement d(x) est : d(x) = d+ (x) + d− (x).

On a le résultat suivant dont la démonstration est évidente.

Proposition 1.1.1 Etant donné G = (X, U ) un graphe orienté, on a toujours :

X X
d+
G (x) = d−
G (x).
x∈X x∈X

Proposition 1.1.2 La somme des degrés des sommets de G est égale à deux fois la taille de G.

Preuve : Il suffit de remarquer que dans la somme des degrés chaque arc est compté deux
fois : une fois dans le demi-degré extérieur et une autre fois dans le demi-degré intérieur. 

Corollaire 1.1.1 Dans un graphe orienté, le nombre de sommets de degrés impairs est pair.

Etant donné S ⊂ X, on définit :

• w+ (S) est l’ensemble des arcs ayant leur extrémité initiale dans S et leur extrémité ter-
minale dans X − S.
• w− (S) est l’ensemble des arcs ayant leur extrémité initiale dans X − S et leur extrémité
terminale dans S.
• w(S) = w+ (S) ∪ w− (S) est appelé un cocycle du graphe.

Propriétés des graphes

Soit G = (X, U ) un graphe orienté. On dit que G est :
- strict si G est sans boucle et ∀ (x, y) ∈ X 2 , il existe au plus un arc de x vers y.
- réflexif si ∀ x ∈ X, (x, x) ∈ U . Il y a une boucle sur chaque sommet.
- anti-réflexif si ∀ x ∈ X, (x, x) ∈
/ U . C’est un graphe sans boucle.
- symétrique si ∀ x ∈ X, ∀ y ∈ X : (x, y) ∈ U ⇒ (y, x) ∈ U .
L’existence d’un arc implique l’existence de l’arc opposé.
- anti-symétrique si ∀ x ∈ X, ∀ y ∈ X : (x, y) ∈ U et (y, x) ∈ U ⇒ x = y.
L’existence d’un arc interdit l’existence de l’arc opposé, sauf dans le cas d’une boucle.
- transitif si ∀ x, y, z ∈ X : (x, y) ∈ U et (y, z) ∈ U ⇒ (x, z) ∈ U .
- biparti si l’ensemble des sommets X peut être partitionné en deux sous ensembles X1 et
X2 de tel sorte que, tout arc a une extrémité dans X1 et l’autre dans X2 .
- complet si G est sans boucle et deux sommets distincts quelconques sont reliés par un seul
arc.
Sous-graphes, graphes partiels et sous-graphes partiels
Soient G = (X, U ) un graphe orienté, Y une partie de X et V une partie de U .

On appelle sous-graphe engendré par Y , le graphe noté GY dont les sommets sont les
éléments de Y et dont les arcs sont les arcs de G ayant leurs deux extrémités dans Y . On
a : GY = (Y, U ∩ (Y × Y )).

On appelle graphe partiel engendré par V , le graphe noté G[V ] ayant le même ensemble X
de sommets que G et dont les arcs sont ceux de V . On a : G[V ] = (X, V ).

Le sous-graphe partiel engendré par Y et V noté GY [V ] est le graphe partiel de GY engendré

par V . On a : GY [V ] = (Y, V ∩ (Y × Y )).

Exemple 1.1.2

On considère le graphe G = (X, U ) ci-dessous.

6

4 5

2 3

1
Le sous-graphe engendré par Y = {2, 3, 4, 5} est
4 5

2 3
Le graphe partiel engendré par V = U − {(2, 5), (3, 4)} est :
 6

4 5

2 3

1
Le sous-graphe partiel engendré par Y et V est :
4 5

2 3

1.1.2 Cheminement dans un graphe

Chemin, circuit

Définition 1.1.9 Etant donné un graphe orienté G = (X, U ) et x, y deux sommets de G, on

appelle chemin de x à y toute suite ordonnée d’arcs µ = (u1 , · · · , uq ) telle que :
i) l’origine de u1 est x,
ii) pour tout i ∈ {1, · · · , q − 1}, l’origine de ui+1 est l’extrémité de ui ,
iii) l’extrémité de uq est y.
Les sommets x et y sont alors dits extrémités du chemin µ qui est de longueur q au sens des
arcs.

Exemple 1.1.3
u3
x2 x4

u1 u8

x1 u4 u5 u9 u7 x6

u2 u10

u6
x3 x5

dans le graphe ci-dessus, µ = (u1 , u3 , u7 , u9 , u4 , u5 , u8 ) est un chemin de x1 à x6 .

Un chemin élémentaire est un chemin tel qu’en le parcourant, on ne rencontre pas deux fois
le même sommet. Dans un chemin élémentaire tous les sommets sont de degré 2 au plus.
 Un chemin simple est chemin dont la sequence d’arcs ne contient pas plusieurs fois un même
élément. C’est-à-dire en le parcourant, on ne rencontre pas plusieurs fois un même arc.

Proposition 1.1.3 Tout chemin élémentaire est simple.

Proposition 1.1.4 De tout chemin on peut extraire un chemin élémentaire.

Définition 1.1.10 Etant donné un graphe orienté G = (X, U ), un sommet y est dit descendant
de x, s’il existe un chemin de x à y. dans ce cas , x est un ascendant de y.

Un circuit est un chemin dont les extrémités coı̈ncident.

Un circuit élémentaire est un chemin élémentaire dont les deux extrémités coı̈ncident.
Un circuit simple est un chemin simple dont les deux extrémités coı̈ncident.
On montre que

Proposition 1.1.5 Tout circuit simple est union disjointe de circuits élémentaires.

Définition 1.1.11 Etant donné un graphe orienté G = (X, U ),

- un chemin est hamiltonien s’il passe une fois et une seule par chaque sommet du graphe.
Ou encore un chemin élémentaire passant par tous les sommets du graphe.
- Un circuit hamiltonien est un chemin hamiltonien dont les deux extrémités coı̈ncident.

On parle de chemin pré-hamiltonien s’il passe au moins une fois par chaque sommet du
graphe.

Définition 1.1.12 Etant donné un graphe orienté G = (X, U ),

- un chemin est eulérien s’il passe une fois et une seule par chaque arc du graphe. Ou encore
un chemin simple passant par tous les arcs du graphe.
- Un circuit eulérien est un chemin eulérien dont les deux extrémités coı̈ncident.

On parle de chemin pré-eulérien s’il passe au moins une fois par chaque arc du graphe.

Chaı̂ne, cycle
Une Chaı̂ne de longueur k est une suite µ = a1 , a2 , . . . ak de k arcs telle que deux arcs
consécutifs sont adjacents. On notera µ = x0 a1 x1 . . . xk−1 ak xk , si l’on veut préciser les sommets
rencontrés. Les sommets x0 et xk sont appelés les extrémités de la chaı̂ne µ. On dit que la chaı̂ne
µ rélie les sommets x0 et xk .

Une chaı̂ne peut être ”vue” comme une suite de sommets telle que deux sommets consécutifs
soient liés par un arc, certains arcs peuvent être parcourus dans le sens de la chaı̂ne (sens +),
les autres arcs dans le sens opposé (sens -).
Une chaı̂ne élémentaire est une chaı̂ne telle qu’en la parcourant, on ne rencontre pas deux
fois le même sommet.
Une chaı̂ne simple est une chaı̂ne dont la sequence d’arcs ne contient pas plusieurs fois un
même élément.

Proposition 1.1.6 Toute chaı̂ne élémentaire est simple.

Proposition 1.1.7 De toute chaı̂ne on peut extraire un chaı̂ne élémentaire.

 Un cycle est une chaı̂ne dont les extrémités coı̈ncident.
Un cycle élémentaire (resp. simple) est une chaı̂ne élémentaire (resp. simple) dont les deux
extrémités coı̈ncident.

Proposition 1.1.8 Tout cycle simple est union disjointe de cycles élémentaires.

Définition 1.1.13 Etant donné un graphe orienté G = (X, U ),

- une chaı̂ne est hamiltonienne si elle passe une fois et une seule par chaque sommet du
graphe. Ou encore une chaı̂ne élémentaire passant par tous les sommets du graphe.
- Un cycle hamiltonien est une chaı̂ne hamiltonienne dont les deux extrémités coı̈ncident.
Le graphe G est dit hamiltonien s’il possède un cycle hamiltonien.

On parle de chaı̂ne pré-hamiltonienne si elle passe au moins une fois par chaque sommet du
graphe.

Définition 1.1.14 Etant donné un graphe orienté G = (X, U ),

- une chaı̂ne est eulérienne si elle passe une fois et une seule par chaque arc du graphe. Ou
encore une chaı̂ne simple passant par tous les arcs du graphe.
- Un cycle eulérien est un cycle simple passant par tous les arcs du graphe.
Le graphe G est dit eulérien s’il possède un cycle eulérien

1.1.3 Connexité et forte connexité

Graphe connexe

Définition 1.1.15 Soit G = (X, U ) un graphe orienté. On dit que G est connexe si, pour tout
couple de sommets (x, y), il existe une chaı̂ne reliant x et y.

On associe à cette notion de connexité une relation d’équivalence R définie par :

(
soit x = y,
xRy ⇔
soit il existe une chaı̂ne reliant x et y.
Les classes d’équivalence induites sur X par cette relation sont appelées classes connexes
de G : elles forment une partition de X en : X1 , . . . , Xp . Le nombre p de classes distinctes est
appelé le nombre de connexité du graphe. Les sous-graphes induits par les classes connexes sont
appelés composantes connexes de G. Il s’ensuit alors que G est connexe si et seulement si son
nombre de connexité est p = 1.

Définition 1.1.16 Un point d’articulation (resp. ensemble d’articulation) d’un graphe est un
sommet (resp. un ensemble de sommets) dont la suppression augmente le nombre de composantes
connexes.
Un isthme est un arc dont la suppression a le même effet.

On peut alors remarquer que :

Remarque 1.1.1 Lorsque G est connexe, Y est un ensemble d’articulation si et seulement si

GX\Y n’est plus connexe et u un arc de G est un isthme si et seulement si G[U \ {u}] n’est plus
connexe.
Graphe fortement connexe

Définition 1.1.17 Soit G = (X, U ) un graphe orienté. On dit que G est fortement connexe si,
pour tout couple de sommets (x, y), il existe un chemin allant de x à y.

On associe à cette notion de forte connexité une relation d’équivalence T définie par :

(
soit x = y,
xT y ⇔
soit il existe un chemin allant de x à y et un chemin allant de y à x.

Les classes d’équivalence induites sur X par cette relation forment une partition de X en :
X1 , . . . , Xq . Le nombre q de classes distinctes est appelé le nombre de forte connexité du graphe.

Les sous graphes G1 , . . . , Gq engendrés par les sous ensembles X1 , . . . , Xq sont appelés les
composantes fortement connexes du graphe G. Chaque composante fortement connexe est un
graphe fortement connexe. Le graphe G est fortement connexe s’il n’a qu’une seule composante
fortement connexe.

Exemple 1.1.4

Considérons le graphe ci-dessous

x1 x3 x2

x5 x8

x7

x4

x6

Les classes fortement connexes sont

{x1 , x3 , x4 , x5 , x6 }, {x2 , x8 }, {x7 }.

Les composantes fortement connexes sont :

 x3 x2

x1 x5 x7 x8

x6 x4

1.2 Graphes non orientés

Dans l’étude de certaines propriétés des graphes, il arrive que l’orientation des arcs, c’est-
à-dire la distinction entre extrémité initiale et extrémité terminale ne joue aucun rôle. On
s’intéresse simplement à l’existence ou non d’un arc entre deux sommets sans en préciser l’ordre.
On parle alors de graphe non orienté ou simplement de graphe.

1.2.1 Définitions
Définition 1.2.1 Un graphe non orienté G est défini par la donnée d’un ensemble fini X dont
les éléments sont appelés des sommets ou noeuds et d’un ensemble E dont les éléments sont des
sous-ensembles à 1 ou 2 éléments de X appelés arêtes. On le note G = (X, E). Le nombre n de
sommets de G est appelé l’ordre de G et le nombre m des arêtes de G est appelée la taille de G.
Les arêtes de la forme u = {x} ∈ E sont appelées boucles.

Exemple 1.2.1

Soit G = (X, E) le graphe défini par : S = {x, y, z} et E = {a, b, c, d} où b = {z, x}, c = {x, y}
et d = {z, y}.

d
b y

A un graphe orienté, on associe un graphe non orienté en ”laissant tomber l’orientation”.

De même à un graphe non orienté, on associe un graphe orienté, soit en introduisant pour toute
arête les deux arcs qui lui correspondent, soit en choisissant un seul des deux arcs.

Définition 1.2.2 Etant donnée une arête u = {x, y} d’un graphe non orienté G = (X, E), on
dit que les sommets x et y sont les extrémités de u. On dit également que les sommets x et y
sont adjacents et que l’arête u est incidente à x et y. On appelle voisinage de x, l’ensemble des
sommets adjacents à x. On le note V(x).
Un sommet qui n’est adjacent à aucun autre sommet est dit isolé.
Définition 1.2.3 Un graphe non orienté G est dit simple s’il est sans boucle.

Définition 1.2.4 Un graphe non orienté G est dit discret si sa taille est nulle. C’est-à-dire tous
ses sommets sont isolés.

Définition 1.2.5 Un graphe non orienté G est dit complet si deux sommets quelconques sont
adjacents.

Définition 1.2.6 Deux arêtes sont adjacentes si elles sont incidentes à au moins une extrémité
commune.
Le degré du sommet x, noté dG (x) ou plus simplement d(x) est le nombre d’arêtes ayant x pour
extréminté.

Définition 1.2.7 Etant donné Y ⊂ X, on appelle cocycle de G l’ensemble w(Y ) des arêtes
ayant une extrémité dans Y et l’autre extrémité dans X − Y .

Les résultats de la proposition 1.1.2 et du corollaire 1.1.1 restent valables.

Proposition 1.2.1 Soit G = (X, E) un graphe non orienté simple d’ordre n et de taille m.
Alors on a m ≤ n(n−1)
2 .

Proposition 1.2.2 Soit G = (X, E) un graphe non orienté simple d’ordre n et de taille m.
Alors G est complet si et seulement si m = n(n−1)
2 .

Proposition 1.2.3 Soit G = (X, E) un graphe non orienté simple d’ordre n et de taille m.
Alors il existe au moins deux sommets ayant même degré.

1.2.2 Chaı̂ne, cycle

Une Chaı̂ne de longueur k est une suite µ = e1 , e2 , . . . , ek de k arêtes telle que deux arêtes
consécutives sont adjacentes. On notera µ = x1 e1 x2 . . . xk ek xk+1 , si l’on veut préciser les som-
mets rencontrés. Les sommets x1 et xk sont appelés les extrémités de la chaı̂ne µ. On dit que la
chaı̂ne µ rélie les sommets x1 et xk .

Une chaı̂ne élémentaire est une chaı̂ne telle qu’en la parcourant, on ne rencontre pas deux
fois le même sommet.
Une chaı̂ne est simple si la séquence d’arêtes qui la constitue ne comporte pas plusieurs fois
le même élément.
La proposition 1.1.7 est valable pour les chaı̂nes.

Un cycle est une chaı̂ne dont les extrémités coı̈ncident.

Un cycle élémentaire est un cycle minimal pour l’inclusion i.e ne contenant strictement aucun
autre cycle.
Les notions de demi-degré, chemin, connexité forte et circuit sont essentiellement orientées.
Elles n’ont donc pas de correspondant dans l’univers des graphes non orientés. Par contre celle
d’isomorphie, de connexité de sous-graphe et graphes partiel s’étendent de manière directe au
cas des graphes non orientés.
1.3 Autres représentations des graphes
1.3.1 Cas des graphes orientés
Définition 1.3.1 (Matrice d’incidence (sommets-arcs)) Soit G = (X, U ) un graphe orienté
tel que X = {x1 , · · · , xn } et U = {u1 , · · · , um }. La matrice d’incidence sommets-arcs de G est
la n × m matrice A = (aij ) à coefficients entiers : 0, -1 et 1 telle que

 1
 si xi est origine de l’arc uj
aij = −1 si xi est extrémité de l’arc uj

0 dans les autres cas


Exemple 1.3.1
a
1 2
b
c
d
4 3
e
On obtient la matrice d’incidence :
 
1 0 0 1 0
 −1 1 1 0 0 
 
 0 0 −1 −1 1 
0 −1 0 0 −1

Définition 1.3.2 (Matrice d’adjacence (sommets-sommets)) Soit G = (X, U ) un graphe

orienté tel que X = {x1 , · · · , xn }. La matrice d’adjacence sommets-sommets ou matrice booléenne
de G est la matrice carrée d’ordre n A = (aij ) à coefficients entiers : 0 et 1 telle que pour tout
xi et xj dans X on a :
aij = 1 si et seulement si (xi , xj ) ∈ U.

La matrice d’adjacence de l’exemple précédent est

 
0 1 1 0
 0 0 1 1 
 
 0 0 0 1 
0 0 0 0

Définition 1.3.3 Soit G un graphe orienté. On appelle dictionnaire des précédents (resp. sui-
vants), le tableau à simple entrée qui à tout sommet x énumère les précédents P (x) (resp. les
suivants S(x)) de x.

1.3.2 Cas des graphes non orientés

Définition 1.3.4 (Matrice d’incidence (sommets-arêtes)) Soit G = (X, U ) un graphe non
orienté tel que X = {x1 , · · · , xn } et E = {e1 , · · · , em }. La matrice d’incidence sommets-arêtes
de G est la n × m matrice A = (aij ) à coefficients entiers : 0 et 1 telle que
(
1 si xi est une extrémité l’arête uj
aij =
0 dans les autres cas
Exemple 1.3.2
a
1 2
b
c
d
4 3
e
On obtient la matrice d’incidence :
 
1 0 0 0 0
 1 1 1 0 0 
 
 0 0 1 1 1 
0 1 0 0 1

Définition 1.3.5 (Matrice d’adjacence (sommets-sommets)) La matrice d’adjacence sommets-

sommets ou matrice booléenne d’un graphe non orienté G = (X, E) avec X = {x1 , · · · , xn } est
la matrice A = (aij ) à coefficients entiers : 0 et 1 telle que pour tout xi et xj dans X on a :

aij = 1 si et seulement si {xi , xj } ∈ E.

La matrice d’adjacence de l’exemple précédent est

 
0 1 1 0
 1 0 1 1 
 
 1 1 0 1 
0 1 1 0
Chapitre 2

Chemins optimaux

2.1 Position du problème de cheminement

2.1.1 Plus court chemin et distance
Définition 2.1.1 Un graphe G = (X, U ) est valué lorsqu’à chaque arc ou arête u ∈ U est
associé un nombre réel l(u). On le note alors G = (X, U, l).

Définition 2.1.2 Soient G = (X, U, l) un graphe valué et µ(x0 , xk ) un chemin allant de x0 à

xk . On appelle longueur du chemin ou bien poids du chemin µ(x0 , xk ) et on note l(µ(x0 , xk )) la
somme des poids des arcs de µ(x0 , xk ).

Le problème du plus court chemin entre deux sommets x et y de G = (X, U, l) est de

déterminer un chemin µ entre x et y qui soit de longueur minimale.
De façon analogue le problème du plus long chemin entre x et y de G = (X, U, l) est de
déterminer un chemin µ entre x et y qui soit de longueur maximale.
Remarquer que si la valuation l est constante égale à 1 alors la notion définie ici coı̈ncide
avec la notion de longueur d’un chemin comme nombre de ses arcs. On parle de longueur au
sens des arcs.
La recherche d’un plus long chemin est analogue à la recherche d’un plus court chemin. En
effet, rechercher un plus long chemin entre deux sommets x et y dans G = (X, U, l) est équivalent
à la recherche du plus court chemin entre x et y dans G = (X, U, −l). On peut donc sans perdre
de généralités se restreindre au problème du plus court chemin.
Le problème de plus court chemin a de nombreuses applications pratiques car la longueur
l(u) d’un arc u peut s’interpréter comme un coût de transport sur l’arc, comme les dépenses de
construction de l’arc, ou comme le temps nécessaire pour parcourir l’arc u.
Les algorithmes de résolutions du problème de plus court chemin sont différents selon les
propriétés du graphe et le problème considéré.
Parmi les propriétés du graphe, on distingue les cas suivants :
1. on a l(u) ≥ 0 pour tout u ∈ A,
2. on a l(u) = 1 pour tout u ∈ A,
3. l(u) est quelconque,
4. le graphe G est sans circuit.
Les problèmes considérés sont :
1. Recherche d’un plus court chemin d’un sommet à un autre (problème de 2 sommets).
2. Recherche d’un plus court chemin d’un sommet à tous les autres (problème avec un
sommet origine unique).
 3. Recherche d’un plus court chemin entre tous les couples de sommets (problème de tous
les couples de sommets).
On remarque que les problèmes 1) et 2) sont identiques. Dans la suite on ne s’intéressera
qu’aux problèmes 2) et 3).

2.1.2 Condition d’optimalité

Définition 2.1.3 Un circuit de longueur strictement négative est appelé circuit absorbant.

Proposition 2.1.1 Soient s et t deux sommets de G. Pour qu’il existe un plus court chemin
allant de s à t il faut et il suffit que tout chemin allant de s à t ne contienne pas de circuit
absorbant.

Preuve : Soit C l’ensemble des chemins de s à t. Si µ ∈ C contient un circuit ω alors on note µ′

le chemin de s à t associé à µ mais n’empruntant pas le circuit ω et on a : l(µ) = l(µ′ ) + l(ω).
• S’il existe un chemin µ ∈ C contenant un circuit absorbant alors il n’existe pas de plus
court chemin de s à t. Il suffit en effet de considérer le chemin obtenu à partir de µ en
passant un assez grand nombre de fois par le circuit absorbant.
• Si tout chemin µ ∈ C ne contient pas de circuit absorbant alors l(ω) ≥ 0, l(µ′ ) ≤ l(µ) et
on peut se restreindre aux chemins élémentaires. Comme ils forment un ensemble fini, il
existera un plus court chemin. 
Soit G = (S, A, l) un graphe orienté, valué et sans circuits absorbants. On appelle distance de s
à t, deux sommets de G et on note d(s, t) la plus petite longueur des chemins de s à t dans le
graphe G.
Un plus court chemin de s à t est un chemin µ tel que l(µ) = d(s, t).

2.2 Quelques algorithmes

2.2.1 Cas où les longueurs sont positives
Soit G = (X, U, l) un graphe orienté sans boucle où X = {x1 , x2 , . . . , xn }.

Algorithme de Dijkstra
Principe
On cherche un plus court chemin d’un sommet initial x1 à tous les autres sommets dans un
graphe valué par des pondérations positives.
A chaque itération de l’algorithme de Dijkstra, on dispose d’un ensemble X ′ contenant les
sommets pour lesquels on a déterminé la distance du plus court chemin issu de x1 . Au debut,
X ′ ne contient que x1 . Chaque sommet x de X possède un paramètre λ(x) défini comme suit :
- si x ∈ X ′ , λ(x) est égal à la plus courte distance de x1 à x.
- si x ∈/ X ′ , λ(x) est égal à la longueur d’un plus court chemin dont tous les sommets
appartiennent à X ′ sauf son extrémité x.
Une itération consiste à faire renter dans X ′ le sommet x∗ appartenant X \ X ′ qui vérifie :

λ(x∗ ) = min[λ(x) : x ∈ X \ X ′ ]
puis mettre à jour les paramètres des successeurs de x∗ qui ne sont pas dans X ′ . On s’arrête dès
que tous les sommets sont dans X ′ .
Algorithme
 1. Initialisation
S = {x2 , x3 , . . . , xn }, X ′ = {x1 }
λ(x1 ) = 0
λ(xi ) = l(x1 , xi ) si xi est un successeur de x1 sinon λ(xi ) = +∞
2. Sélection d’un sommet
Sélectionner xi ∈ S tel que λ(xi )S= minxk ∈S (λ(xk ))
Faire S ← S \ {xi }, X ′ ← X ′ {xi }
Si S est vide FIN
Sinon aller en 3
3. Calcul des valeurs de λ
Faire pour tout xj à la fois dans S(xi ) et dans S
λ(xj ) ← min(λ(xj ), λ(xi ) + l(xi , xj ))
et retourner en 2
L’algorithme considère les sommets dans un ordre qui dépend des valeurs des paramètres λ(xi )
appelées aussi labels. A la fin on a λ(xi ) = d(x1 , xi ) pour tout xi ∈ X.
Exemple d’application On considère le graphe suivant avec a comme sommet source :
4
b d

7
2 5
1
a 5 e

1 2 3

7
c f

On obtient alors :

Sommets a b c d e f
Initialisation 0 7 1∗ ∞ ∞ ∞
.. ..
Itération 1 . 6 . ∞ 3∗ 8
.. .. ..
Itération 2 . 5∗ . 8 . 8
.. .. .. ..
Itération 3 . . . 8 . 6∗
.. .. .. .. ..
Itération 4 . . . 8∗ . .
On obtient une arborescence de parcours

b d

2 5
1
a e

1 2

c f
Convergence
Proposition 2.2.1 L’algorithme converge si et seulement si les valuations sont toutes positves.

2.2.2 Cas où les longueurs sont quelconques

Soit G = (X, U, l) un graphe orienté valué strict où X = {x1 , x2 , . . . , xn }. On se propose de
déterminer les plus courts chemins de x1 à tous les autres sommets du graphe.

Algorithme de Bellman
Cet algorithme permet de rechercher le plus court chemin d’un sommet s aux autres sommets
dans un graphe quelconque ou de rechercher un circuit de longueur négative.
Principe
L’algorithme consiste à déterminer à chaque itération k les valeurs des plus courts chemins
de s aux autres sommets ne contenant pas plus de k arcs. On note λk (x) la longueur d’un chemin
de s à x à la kieme itération.
Algorithme
1. Initialisation
λ0 (x1 ) = 0
λ0 (xi ) = +∞ pour tout xi 6= x1
k=1
2. A l’itération k
Faire λk (x1 ) = 0
et λk (xj ) = Min(λk−1 (xj ), Minxi ∈P (xj ) (λk−1 (xi ) + l(xi , xj ))) pour tout xj 6= x1

3. Si λk (xi ) = λk−1 (xi ) pour tout i alors FIN

Si k ≤ n − 1 aller en 2 avec k ← k + 1
Si k = n alors il existe un circuit absorbant
A la fin de l’algorithme s’il n y a pas de circuit absorbant, les valeurs λ(xi ) désigne, pour
chaque sommet xi , la plus courte distance de x1 à xi .

Remarque 2.2.1 Dans l’algorithme de Bellman, on peut considérer à l’étape 3 la condition

suivante :
λk (xj ) = Min(λk−1 (xj ), Minxi ∈P (xj ) (λp (si ) + l(xi , xj )))

où p est inférieur à k est l’étape de la dernière mise à jour relative au sommet xi .

Exemple d’application
On considère le graphe suivant avec a comme sommet source :
4
b d

7 1
2
2
a 2 e

8 3
-2
2
c f
 On obtient alors :

Sommets a b c d e f
Initialisation 0 ∞ ∞ ∞ ∞ ∞
Itération 1 0 7 8 ∞ ∞ ∞
Itération 2 0 7 8 11 8 9
Itération 3 0 7 6 10 8 9
Itération 4 0 7 6 10 8 8
Itération 5 0 7 6 10 8 8
On obtient une arborescence de parcours

2.2.3 Cas d’un graphe sans circuit

B) Ordonnancement par niveaux

Définition 2.2.1 Soit G un graphe orienté sans circuit. On appelle niveau d’un sommet x, la
longueur (au sens des arcs) du plus long chemin ayant pour extrémité terminale x.

Soit G un graphe orienté sans circuit. Pour déterminer les niveaux des sommets de G on
peut utiliser soit le dictionnaire des précédents soit la matrice booléenne.

Algorithme utilisant le dictionnaire des précédents

1. On note N0 l’ensemble des sommets de G qui n’ont pas de précédents, c’est-à-dire de
niveau 0.
2. Barrer dans le dictionnaire des précédents les éléments de N0 partout où ils se trouvent.
Les sommets n’ayant plus de précédents sont de niveau 1. Soit N1 cet ensemble.
3. On réitère cette procédure en augmentant de 1, la valeur des niveaux jusqu’à ce que tous
les sommets soient barrés.

Algorithme utilisant la matrice booléenne

1. L’ensemble N0 des sommets de niveau 0 est l’ensemble des sommets dont les colonnes
sont nulles.
2. Barrer dans la matrice booléenne les colonnes et les lignes des éléments de N0 . Les
sommets dont les colonnes sont nulles dans la matrice ainsi obtenue sont de niveau 1.
Soit N1 cet ensemble.
3. On réitère cette procédure en augmentant de 1, la valeur des niveaux jusqu’à ce que
toutes les colonnes soient barrées.
Le graphe ordonnancé par niveau du graphe est une représentation graphique plus simple
(avec moins d’intersections possibles des arcs). Pour ce faire, on place les sommets d’un même
niveau sur une verticale. Les niveaux sont placés de gauche à droite par ordre croissant.

Exemple d’application 1
On considère le graphe suivant :
 4
b d

7 2
5
2 1
a 5 e

1
2 3
7
c f

On a les niveaux suivants :

N0 = {a}, N1 = {b}, N2 = {e}, N3 = {c}, N4 = {d, f }.

Dresser le graphe ordonnancé par niveaux.

Exemple d’application 2
On considère le graphe suivant donné par son dictionnaire des précédents : Déterminer les
niveaux des sommets et dresser le graphe ordonnancé par niveaux.
Sommets Précédents
a -
b a
c b
d a
e a
f d
g f
h e, c, g
i h, k
j a
k j
m k
n m

C) Algorithme de Ford
Soit G = (X, U, l) un graphe orienté valué sans circuit où X = {x1 , x2 , . . . , xn }. On suppose
que P (x1 ) = ∅.
L’algorithme de Ford détermine les plus courtes distances de x1 à tous les autres sommets
du graphe.
1. Initialisation Poser λ(x1 ) = 0 et X ′ = {x1 }
2. Rechercher un sommet xj ∈ / X ′ tel que P (xj ) ⊂ X ′
3. Poser λ(xj ) = min[λ(xi ) + l(xi , xj ) : xi ∈ P (xj )], X ′ := X ′ ∪ {xj }
4. Si |X ′ | = n, FIN
5. Aller à 2
A la fin de l’algorithme, les valeurs λ(xi ) est la plus courte distance de x1 à xi .

Exemple d’application
Appliquer l’algorithme de Ford aux graphes ci-dessus.
Chapitre 3

Problèmes d’ordonnancement

L’objet d’un problème d’ordonnancement est de faciliter la mise en œuvre et de guider

l’exécution d’un ensemble complexe de tâches (programme de recherche ou de production, lan-
cement d’un produit, construction d’un édifice ...). La technique d’analyse la plus connue, appelée
méthode PERT (Program Evaluation and Review Technique) a été introduite aux Etats-Unis
en 1958 pour la conduite du programme de recherche et de construction des fusées Polaris. Cette
méthode tient une place dominante par sa simplicité, son efficacité et la variété d’extensions qui
ont pu être développées.
En toute généralité, les problèmes d’ordonnancement se posent sous la forme suivnate. Etant
donné un objectif qu’on se propose d’atteindre et dont la réalisation suppose l’exécution préalable
de multiples tâches, soumises à de nombreuses contraintes, déterminer l’ordre et le calendrier
d’exécution des diverses tâches.
Le critère d’optimalité peut porter sur la minimisation de la durée et/ou du coût de la
réalisation du projet. Nous supposerons que le projet est décomposable en un nombre fini de
tâches, caractérisées par leur durée d’exécution (généralement fixe, parfois aléatoire), éventuellement
aussi par leur coût d’exécution, et soumises à des contraintes de postériorité stricte (une tâche
ne peut commencer que si certaines autres tâches sont complètement terminées). Ce type de
problème se nomme problème central de l’ordonnancement. Des cas plus complexes peuvent
également être envisagés comme par exemple le cas des contraintes disjonctives, c’est-à-dire le
cas où, en plus des contraintes de succession, on impose la réalisation non simultanée de certaines
paires de tâches.
En pratique, le travail préliminaire à accomplir sera donc de dresser une liste des différentes
opérations à mener que l’on décomposera plus ou moins finement selon la précision souhaitée.
Généralement, les tâches sont définies pour que leurs durées d’exécution soient du même ordre
de grandeur ; de plus, les contraintes de postériorité entre les tâches doivent pouvoir être établies
avec précision. Ce travail important est souvent long et nécessite une collaboration étroite entre
les différents acteurs du projet.
La représentation par un graphe d’un problème d’ordonnancement permet une bonne appréhension
globale du problème. L’étude de ce graphe conduit à l’identification des tâches prioritaires et
la détection des retards ou des dépassements de moyens afin de prendre les mesures correctives
nécessaires.
La schématisation d’un problème d’ordonnancement sous forme d’un graphe peut se faire
selon deux modes de repprésentation :
- la méthode MPM (Méthode des potentiels Metra) développée en France par Bernard Roy
de la SEMA à l’occasion de la construction d’une centrale nucléaire ;
- la méthode PERT.
Soit un projet décomposé en n tâches élémentaires 1, 2, . . . , n. Pour chaque tâche i, il est
donné sa durée di et les tâches antérieures c’est-à-dire les tâches qui doivent être achévées pour
que la tâche i puisse commencer.
 Tâches Durées Tâches antérieures
.. .. ..
. . .
i di j, k
.. .. ..
. . .
En ne prenant en compte que les contraintes de succession, il s’agit de trouver un calendrier
de déroulement des tâches du projet, c’est-à-dire déterminer les dates de démarrage de chaque
tâche, qui minimisent le temps total de réalisation du projet et d’indiquer les tâches critiques.

3.1 Méthode MPM

La méthode MPM consiste à représenter ce problème d’ordonnancement de projet par un
graphe dit graphe potentiel-tâches ou graphe MPM ou réseau MPM.

3.1.1 Principe de la représentation du réseau MPM

Le graphe potentiel-tâches associé au projet est un graphe orienté valué strict et sans circuits,
G = (S, A, l) avec S = {α, 1, 2, . . . , n, ω} où α désigne le début et ω la fin du projet, considérés
comme des tâches fictives de durée nulle. (i, j) ∈ A si la tâche i est antérieure à la tâche j.
La longueur ou le poids de l’arc (i, j) est l(i, j) = di , c’est-à-dire la durée de la tâche i. La
tâche début des travaux α de durée 0 sera reliée à tous les sommets sans précédents et tous les
sommets qui n’ont pas de suivants sont reliés à la tâche fin des travaux ω.

3.1.2 Construction du réseau MPM

On considère le tableau qui donne la liste des opérations préréquises c’est-à-dire le diction-
naire des précédents. On détermine les niveaux des sommets.
Pour construire le graphe, on place d’abord les niveaux (qui sont schématisés par des traits
verticaux) par ordre croissant de gauche à droite. Les sommets sont placés par niveau. A un
même niveau, ils sont situés de façon à limiter le nombre d’intersections entre les arcs.
Un arc reliera un sommet i à un sommet j, si i ∈ P (j). Chaque sommet sera figuré par un
rectangle du type :

Ti Ti∗
i
où i désigne le nom de la tâche, Ti la date de début au plus tôt de la tâche et Ti∗ la date de
début au plus tard de la tâche.

3.1.3 Détermination des dates

La date au plus tôt Tj d’une tâche j est la date la plus rapprochée (optimiste) à laquelle j
peut commencer. C’est la longueur du plus long chemin conduisant α à j. On montre que :
(
Tα = 0
Tj = Maxi∈P (j) (Ti + di ) pour j ∈ {1, . . . , n, ω}
et que Tω est la durée minimum du projet.
Ces valeurs sont calculeés en prenant les sommets par niveau croissant.
La date au plus tard Ti∗ d’une tâche i est la date la plus tardive (pessimiste) à laquelle i
doit commencer pour que la durée minimale de réalisation du projet soit respectée : c’est-à-dire
Tω∗ = Tω . Les dates au plus tard se calculent par un compte à rebours à partir de Tω∗ et
Ti∗ = Minj∈S(i) (Tj∗ − di ) pour i = n, n − 1, . . . , 2, 1, α
 La date de fin au plus tard Ti′ d’une tâche i est la date la plus pessimiste de fin d’une tâche
et se calcule par la formule suivant :

Ti′ = Minj∈S(i) (Tj − di ) pour i = n, n − 1, . . . , 2, 1, α

Exemple : On considère un projet qui comporte 7 tâches : a, b, c, d, e, f, g.

Tâches a b c d e f g
Durées 4 3 6 2 8 7 1
Tâches antérieures a,b b c,d,e c
On obtient le graphe potentiel-tâches G = (S, A, l) ci-dessous, où S = {deb, a, b, c, d, e, f, g, f in}
4 6
a c g

3 6 1

3 2 7
deb b d f fin

Tâches deb a b c d e f g fin

Durées 0 4 3 6 2 8 7 1 0
Ti 0 0 0 4 3 0 10 10 17
Ti∗ 0 0 1 4 8 2 10 16 17

3.1.4 Les marges

La marge totale est le délai M T (i) = Ti∗ −Ti pouvant être accordé à une tâche sans repousser
la durée minimale du projet. On dit qu’une tâche i est critique si M T (i) = 0. La succession de
tâches qui imposent la durée minimale du projet est appelée chemin critique.
La marge libre d’une tâche i est le délai M L(i) pouvant être accordé au commencement de la
tâche sans modifier la marge totale des tâches qui suivent.

M L(i) = Minj∈Γ(i) (Tj − di ) − Ti

ou encore
M L(i) = Ti′ − Ti
. Contrairement à la marge totale, la marge libre peut être consommée sans aucune conséquence
sur les tâches qui suivent dans le projet. La marge libre d’une tâche est toujours inférieure ou
égale à sa marge totale.

3.2 Méthode PERT

La méthode PERT consiste à représenter le problème d’ordonnancement du projet par un
graphe dit graphe potentiel-étapes ou graphe PERT ou encore réseau PERT.

3.2.1 Principe de la représentation du graphe PERT

A chaque tâche correspond un arc du graphe dont la longueur est égale à la durée de la
tâche.
 Chaque sommet du graphe est un évènement (ou étape) signifiant :

toutes les tâches qui arrivent sont terminées
toutes les tâches qui partent peuvent commencer

Le schéma ci-dessous signifie par exemple : a et b doivent être terminées pour que c et d
puissent commencer.
E1 E4

a c

b d
E2 E3 E5
On définit d’abord les notions suivantes :
Les tâches successives se suivent dans le temps et sont représentées par un chemin. Par
exemple les tâches a, b, c sont successives :
a b c
E1 E2 E3 E4

Les tâches simultanées ont le même début d’exécution. Par exemple les tâches a, b sont si-
multanées :

E2

a
E1 E3

Les tâches convergentes aboutissent à la même étape. Par exemple a, b sont convergentes :

E2

a
E3 E1

Les tâches parallèles sont à la fois simultanées et convergentes.

La représentation de certaines relations d’antriorité nécessite dans la méthode PERT l’intro-
duction de tâches fictives de durée 0.
Dans un premier temps, il y a la gestion des tâches parallèles qui conduit à un multigraphe
comme l’indique le schéma ci-dessous :
a
E1 E2 E3 E4
b
Pour éviter cela on introduit une tâche fictive entre E5 et E3 . Ce qui donne la représentation
suivante :
 E5

a
E1 E2 E3 E4

Il y a aussi certaines représentations qui peuvent impliquer des conditions qui ne sont pas
prévues dans les données.
Par exemple la situation où a et b sont antérieures à c et b est antérieure à d ne peut être
représentée par le schéma ci-dessous :

E1 E4

a c

b d
E2 E3 E5

car cela impliquerait que a précède d, ce qui n’est pas une donnée du problème. On considère
la représentation suivante :
a c
E1 E3 E5

b d
E2 E4 E6

3.2.2 Construction du graphe PERT

Chaque sommet sera figuré par un cercle divisé en deux parties. Dans la partie inférieure on
indique le numéro de l’étape ou de l’évènement Ei (ce n’est pas une donnée initiale du problème
mais résulte de la construction du graphe). La partie supérieure est divisée en deux ; à droite on
note ti qui désigne la date attendue de réalisation de l’évènement Ei et à gauche on note t∗i qui
désigne la date limite de réalisation de l’évènement Ei .
On considère tout d’abord un sommet initial E0 d’où partent toutes les tâches dont la mise
en route n’est soumise à aucune contrainte d’antériorité et à la fin un sommet final EN auquel
aboutissent toutes les tâches n’ayant pas de suivants.
En pratique on trace d’abord un graphe des niveaux en reliant les tâches successives entre
deux niveaux consécutifs. Puis on trace le graphe PERT à partir de ce graphe de manière à ce
que toutes les tâches aboutissent à une étape et que l’antériorité des tâches soit respectée.

3.2.3 Détermination des dates

Ordonnancement minimum ou au plus tôt

Définition 3.2.1 On appelle date au plus tôt de réalisation de l’évènement Ej , est la longueur
du plus long chemin dans le graphe reliant E1 à Ej . C’est aussi la date attendue de réalisation
de l’évènement Ej . On la note tj .

Définition 3.2.2 On appelle ordonnancement minimum ou au plus tôt, l’ensemble de toutes les
dates attendues ti , i = 1 · · · N .
 Pratiquement on utilise les formules suivantes pour calculer les tj .
(
t0 = 0
tj = Maxi∈P (j) (ti + dij ) pour j ∈ {1, . . . , N }
où dij est la durée de la tâche (Ei , Ej ).

Définition 3.2.3 Pour toute tâche (Ei , Ej ), la date de début au plus tôt est Tij = ti .

Les dates atendues ti étant connues, on détermine le (ou les) chemin(s) critique(s) constitués
des arcs (Ei , Ej ) pour lesquels tj − ti = dij .
Les évènements Ei situés sur le chemin critique sont dits évènements critiques.

Remarque 3.2.1 Tout retard apporté sur la réalisation d’un évènement critique ralentit le
programme entier de la même durée.

Ordonnancement limite (ou au plus tard)

L’objectif étant de réaliser l’ensemble du programme en un temps minimum, on impose à
l’évènement EN , fin des travaux d’être réalisé à sa date attendue tN . On définit alors :

Définition 3.2.4 On appelle date limite (ou plus tard) de réalisation de l’évènement Ei , t∗i =
tN − τi,n où τi,n est la longueur d’un plus long chemin dans le graphe reliant Ei à EN .

Définition 3.2.5 On appelle ordonnancement limite ou au plus tard, l’ensemble de toutes les
dates limites t∗i , i = 1 · · · N .

Pratiquement on utilise les formules suivantes pour calculer les t∗i .

(
t∗N = tN
t∗i = minj∈S(i) (t∗j − dij ) pour j ∈ {1, . . . , N − 1}
Lorsque les dates limites de réalisation sont déterminées, les évènements critiques sont ceux
tels que ti = t∗i .

Définition 3.2.6 Pour toute tâche (Ei , Ej ), la date de début au plus tard est Tij∗ = t∗j − dij .

Définition 3.2.7 On appelle intervalle de flottement de l’évènement Ei , l’intervalle [ti , t∗i ].

C’est l’intervalle dans lequel peut intervenir la réalisation de Ei sans compromettre la durée
totale (minimale) d’exécution de l’ensemble du programme. Un tel intervalle est de longueur
nulle pour un évènement critique.

3.2.4 Les marges

Définition 3.2.8 La marge libre d’une tâche (Ei , Ej ) est

M L(i, j) = tj − ti − dij .

Elle représente le delai ou retard maximum que l’on peut apporter à sa mise en route sans
perturber la date attendue de réalisation de l’évènement Ej , l’évènement Ei ayant eu lieu à sa
date attendue.

Remarque 3.2.2 La marge libre d’une tâche critique est nulle.

Définition 3.2.9 La marge totale d’une tâche (Ei , Ej ) est

M T (i, j) = t∗j − ti − dij .

Elle représente pour cette opération, le delai ou retard maximum que l’on peut apporter à
sa mise en route lorsque l’évènement Ei a eu lieu à sa date attendue sans perturber la date de
fin des travaux.

Remarque 3.2.3 Pour les opérations critiques (Ei , Ej ), on a M T (i, j) = 0.

On a toujours
0 ≤ M L(i, j) ≤ M T (i, j).
Chapitre 4

Problèmes de flots

L’étude et la résolution de problèmes concernant la gestion et l’optimisation des réseaux

de télécommunication, d’électricité, de réseaux routiers passent souvent par une modélisation
sous forme d’un graphes appelé réseau. Ainsi prévoir le nombre maximal de voitures qu’un
réseau d’autoroutes peut accueillir sans embouteillage, déterminer la capacité maximale d’un
réseau informatique sont des questions courantes dans les simulateurs dédiés et ayant pour
point commun un problème de la théorie des graphes appelé : flot maximal dans un graphe.
Les problèmes qui nous intéressent ici c’est de déterminer un flot de valeur maximale dans
un réseau de capacité limitée, ou bien de déterminer un flot de valeur maximale et de coût total
minimal dans un réseau quand chaque unité de flot dans un lien engendre une dépense.

4.1 Définitions
Définition 4.1.1 On appelle réseau, un graphe G = (X, U ) orienté sans boucle possédant deux
sommets particuliers s et p appelés respectivement source et puits et qui sont respectivement
une racine et une antiracine de G (c’est-à-dire pour tout x ∈ X, il existe dans G un chemin
d’origine s et d’extremité x et un chemin d’origine x et d’extremité p) dont les arcs sont munis
de capacités données c(u) ≥ 0 pour tout u ∈ U . On le note R = (X, U, s, p, c)

Définition 4.1.2 Soit R = (X, U, s, p, c) un réseau. Un flot sur R est une application f : U −→
R+ .
Pour tout u ∈ U , f (u) est la quantité de flot ou le flux qui circule sur l’arc u.

Définition 4.1.3 On dit qu’un flot f sur R = (X, U, s, p, c) respecte les contraintes de capacité
ou que f est compatible avec c si, pour tout u ∈ U , on a : 0 ≤ f (u) ≤ c(u).

Définition 4.1.4 On dit qu’un flot f sur R = (X, U, s, p, c) est conservatif si, pour tout x ∈
X \ {s, p}, la somme des quantités de flots portées par les arcs sortant de x est égale à la somme
des quantités de flots portées par les arcs entrant en x.

Définition 4.1.5 Soit f un flot sur R. On appelle valeur de f , le nombre v(f ) égal à la
différence entre la somme des quantités de flots portées par les arcs sortant de s et la somme
des quantités de flots portées par les arcs entrant en s.

Exemple 4.1.1
 [3] 3
x1 x3

[6] 4 [4] 3

[4] 1
s p

[6] 3 [7] 4

[5] 3
x2 x4
La valeur du flot ci-dessus est v(f ) = 7.

Etant donné un flot f sur R et S ⊂ X un sous ensemble propre de X, on note : ω + (S)

l’ensemble des arcs sortant de S, ω − (S) l’ensemble des arcs rentrant en S. On a alors :

ω + (S) = {u = (x, y) ∈ U : x ∈ S, et y ∈
/ S},

ω − (S) = {u = (x, y) ∈ U : x ∈
/ S, et y ∈ S}.
Pour S = X, on a ω + (X) = ∅ et ω − (X) = ∅.
On considère X X
df (S) = f (u) − f (u),
u∈ω + (S) u∈ω − (S)

la différence entre la quantité de flot qui sort de S et celle qui entre en S.

En particulier si S est un singleton {x}, on a df ({x}) = df (x). Donc v(f ) = df (s).
Dans la suite, on notera simplement d(S) au lieu de df (S) s’il n’y a pas de confusion possible.
On remarque alors :

Remarque 4.1.1 Un flot f sur R est conservatif si, pour tout x ∈ X \ {s, p}, on a : df (x) = 0.

Etant donné un flot f sur R, on a les propriétés suivantes

Proposition 4.1.1 Si X1 et X2 sont deux sous ensembles propres de X disjoints on a :

d(X1 ∪ X2 ) = d(X1 ) + d(X2 ).

Preuve : On considère la notation

σ(V ) = Σu∈V f (u) ∀ V ⊂ U.

On a
ω + (X1 ) = (ω + (X1 ) \ ω − (X2 )) ∪ (ω + (X1 ) ∩ ω − (X2 ))
ω + (X2 ) = (ω + (X2 ) \ ω − (X1 )) ∪ (ω + (X2 ) ∩ ω − (X1 ))
ω − (X1 ) = (ω − (X1 ) \ ω + (X2 )) ∪ (ω − (X1 ) ∩ ω + (X2 ))
ω − (X2 ) = (ω − (X2 ) \ ω + (X1 )) ∪ (ω − (X2 ) ∩ ω + (X1 ))
et qui expriment que l’ensemble ω + (X1 ) des arcs qui sortent de X1 est égal à la réunion
de l’ensemble ω + (X1 ) \ ω − (X2 ) des arcs qui sortent de X1 et qui n’entrent pas dans X2 et de
l’ensemble ω + (X1 ) ∩ ω − (X2 ) des arcs qui sortent de X1 et qui entrent dans X2 etc ...
De même on a :
ω + (X1 ∪ X2 ) = (ω + (X1 ) \ ω − (X2 )) ∪ (ω + (X2 ) \ ω − (X1 ))
ω − (X1 ∪ X2 ) = (ω − (X1 ) \ ω + (X2 )) ∪ (ω − (X2 ) \ ω + (X1 ))
car l’ensemble ω + (X1 ∪ X2 ) des arcs qui sortent de X1 ∪ X2 est égal à la réunion de l’ensemble
ω + (X1 ) \ ω − (X2 ) des arcs qui sortent de X1 et qui n’entrent pas dans X2 et de l’ensemble
ω + (X2 ) \ ω − (X1 ) des arcs qui sortent de X2 et qui n’entrent pas dans X1 etc ...
On voit ainsi que :

d(X1 ) = σ [(ω + (X1 ) \ ω − (X2 )) ∪ (ω + (X1 ) ∩ ω − (X2 ))]

−σ [(ω − (X1 ) \ ω + (X2 )) ∪ (ω − (X1 ) ∩ ω + (X2 ))]
= σ (ω + (X1 ) \ ω − (X2 )) + σ (ω + (X1 ) ∩ ω − (X2 ))
−σ (ω − (X1 ) \ ω + (X2 )) − σ (ω − (X1 ) ∩ ω + (X2 )) ,

d(X2 ) = σ [(ω + (X2 ) \ ω − (X1 )) ∪ (ω + (X2 ) ∩ ω − (X1 ))]

−σ [(ω − (X2 ) \ ω + (X1 )) ∪ (ω − (X2 ) ∩ ω + (X1 ))]
= σ (ω + (X2 ) \ ω − (X1 )) + σ (ω + (X2 ) ∩ ω − (X1 ))
−σ (ω − (X2 ) \ ω + (X1 )) − σ (ω − (X2 ) ∩ ω + (X1 ))
donc

d(X1 ) + d(X2 ) = [σ (ω + (X1 ) \ ω − (X2 )) + σ (ω + (X2 ) \ ω − (X1 ))]

− [σ (ω − (X1 ) \ ω + (X2 )) + σ (ω − (X2 ) \ ω + (X1 ))]
= σ [(ω + (X1 ) \ ω − (X2 )) ∪ (ω + (X2 ) \ ω − (X1 ))]
−σ [(ω − (X1 ) \ ω + (X2 )) ∪ (ω − (X2 ) \ ω + (X1 ))]
= σ (ω + (X1 ∪ X2 )) − σ (ω − (X1 ∪ X2 ))
= d(X1 ∪ X2 )


On a le corollaire

Corollaire 4.1.1 On a :
P
1) d(S) = x∈S d(x) pour tout S ⊂ X.
2) d(S) = 0 pour tout S ⊂ X avec S ∩ {s, p} = ∅.
3) d(X) = 0.
4) d(s) + d(p) = 0
5) Si X1 et X2 constituent une partition de X avec s ∈ X1 et p ∈ X2 , on a d(X1 ) = d(s) =
v(f ).

Définition 4.1.6 On appelle flot réalisable sur R tout flot compatible avec les contraintes de
capacités et conservatif. On note FR l’ensemble des flots réalisables sur R.

On a alors FR 6= ∅ car le flot nul est réalisable.

Le problème fondamental dans l’étude des flots dans un réseau R est de trouver un flot
∗
f ∈ FR de valeur maximale. C’est-à-dire tel que :

v(f ) ≤ v(f ∗ ) ∀ f ∈ FR .

4.2 Flot complet

4.2.1 Définitions
Définition 4.2.1 Soit f ∈ FR . On dit que u ∈ U est saturé pour f si f (u) = c(u).

Définition 4.2.2 Un chemin de s à p est saturé pour un flot f ∈ FR si au moins un des arcs
qui le composent est saturé
Définition 4.2.3 Un flot f ∈ FR est complet si tout chemin de s à p est saturé pour f .

Une première idée pour maximiser un flot est de saturer successivement les chemins de s
à p. On obtiendra alors un flot complet. On verra plutard que ce flot n’est pas nécessairement
maximal mais il fournit une excellente solution de depart pour appliquer un algorithme itératif
de détermination d’un flot maximal.

4.2.2 Algorithme de recherche d’un flot complet

On part d’un flot f (par exemple le flot nul) et on l’améliore pas à pas par une procédure de
marquage.

1. Marquer s
2. Soit x un sommet marqué et non encore examiné ;
Marquer y par (+x) si y est un successeur non marqué de x avec f (x, y) < c(x, y)
3. Si p est marqué (on a un chemin augmentant), aller en (4)
Si tous les sommets marqués sont examinés alors le flot est complet ;
sinon aller en (2)
4. Améliorer le flot
Effacer les marques
Aller en (1)

une autre variante de cet algorithme est le suivant :

4.2.3 Variante pour déterminer un flot complet

1) On part d’un flot initial au jugé f0 ∈ FR par exemple le flot nul.
2) Considérer le graphe partiel G0 de G obtenu en supprimant
dans G tous les arcs saturés pour f0 .
i) Si G0 ne contient aucun chemin reliant s à p, le flot f0 est complet
(c’est-à-dire tout chemin reliant s à p est saturé pour f0 ).
ii) Sinon, il existe dans G0 un chemin µ de s à p.
C’est un chemin de G non saturé pour f0 .
a) Calculer pour un tel chemin

δ = min [c(u) − f0 (u)] .

u∈µ

b) Augmenter de δ le flux sur chaque arc de µ.

On obtient ainsi un flot f1 et un graphe partiel G1 de G
par suppression dans G de tous les arcs saturés pour f1 .
iii) Recommencer sur G1 la recherche des chemins de s à p.
Si G1 ne contient aucun tel chemin, f1 est complet.
Sinon appliquer pour un tel chemin la procédure décrite en ii).
iv) En réitérant un nombre fini de fois une telle procédure, on parvient
à un flot fp ∈ FR et un graphe partiel Gp de G ne possédant
aucun chemin de s à p. fp est un flot complet sur G.

Exemple 4.2.1
 Le flot ci-dessous est complet.
[5]2
x1 x5

[2] 2 [1]0[2]2 [2]1 [5]5

[5] 5 [2]2
s x2 x4 p

[5] 2 [2]0 [4]1 [1]1 [7]4

[2]2
x3 x6

Remarque 4.2.1 Dans l’application manuelle de l’algorithme, on peut souvent gagner du temps
en saturant en priorité les chemins pour lesquels δ est aussi grand que possible.

4.3 Algorithme de Ford-Fulkerson

On considère le réseau R = (X, U, s, p, c). On définit :

Définition 4.3.1 Une coupe de R est un ensemble de sommets contenant s et ne contenat pas
p.
On appelle capacité d’une coupe C de R, la somme des cpacités des arcs sortant de C. On
note X
c(C) = c(u).
u∈ω + (C)

Exemple 4.3.1

Considérons le réseau suivant :

[3] 3
x1 x3

[6] 4 [4] 3

[4] 1
s p

[6] 3 [7] 4

[5] 3
x2 x4

L’ensemble C = {s, x1 , x3 } est une coupe. Sa capacité est : c(C) = 4 + 4 + 6 = 14.

On montre que

Proposition 4.3.1 Si f ∈ FR et C est une coupe de R, alors

on a v(f ) ≤ c(C).
Autrement dit, la valeur de n’importe quel flot réalisable est inférieure ou égale à la capacité
de n’importe quel coupe.
Preuve : On sait que s ∈ C et p ∈ / C. Donc on a
P P
v(f ) = df (s) = df (C) = u∈ω+ (C) f (u) − u∈ω− (C) f (u)
P
≤ u∈ω+ (C) f (u)
P
≤ u∈ω+ (C) c(u) ( car f (u) ≤ c(u))
= c(C).

On peut montrer que :

Proposition 4.3.2 Si f ∈ FR et C est une coupe de R, avec v(f ) ≥ c(C), alors f est de valeur
maximale et la coupe C est de capacité minimale.

Définition 4.3.2 Soit C = (s, x1 , · · · xl , p) une chaı̂ne entre la source s et le puits p de R.

Si u = (xi , xi+1 ) ∈ U est un arc de C, on dit que cet arc est direct.
Si u = (xi+1 , xi ) ∈ U est un arc de C, on dit que cet arc est inverse.
On note C + (respectivement C − ) l’ensemble des arcs directs (respectivement inverses) de C.

Définition 4.3.3 Soit f un flot réalisable sur R. Une chaı̂ne C de s à p est dite saturée pour
f , s’il existe au moins un arc direct u ∈ C tel que f (u) = c(u) ou s’il existe au moins un arc
inverse u de C tel que f (u) = 0.
Une chaine non saturée est aussi appelée chaine augmentante, améliorante ou amplificatrice.

Remarque 4.3.1 Une chaine C de s à p est améliorante pour un flot réalisable f sur R si
- pour tout arc direct de C, on a c(u) − f (u) > 0.
- pour tout arc inverse de C, on a f (u) > 0.

On a la proposition suivante :

Proposition 4.3.3 Soit C une chaı̂ne de s à p améliorante pour f ∈ FR . Soit

δ1 = min[c(u) − f (u) : u ∈ C + ], δ2 = min[f (u) : u ∈ C − ], δ = min{δ1 , δ2 }.

Alors le flot f ′ défini par


 f (u) + δ
 si u ∈ C +
f ′ (u) = f (u) − δ si u ∈ C −

f (u) si u ∈
/C


est réalisable et on a v(f ′ ) = v(f ) + δ.

Preuve :
Pour tout arc u, on f ′ (u) ≥ 0 car soit f ′ (u) = f (u) ≥ 0 soit f ′ (u) = f (u) + δ > 0, soit enfin
f ′ (u) = f (u) − δ. Ce dernier cas ne peut se produire que pour les arcs inverses de C, et dans ce
cas on a f (u) ≥ δ2 ≥ δ. Donc on a f ′ (u) = f (u) − δ ≥ 0.
De même on a pour chaque arc u, f ′ (u) ≤ c(u) car soit f ′ (u) = f (u) ≤ c(u), soit f ′ (u) =
f (u) − δ ≤ f (u) ≤ c(u), soit f ′ (u) = f (u) + δ. Cette dernière éventualité est relative au cas où
l’arc u est direct dans la chaine C. Or dans ce cas on a δ ≤ δ1 ≤ c(u) − f (u). Ce qui implique
que f ′ (u) = f (u) + δ ≤ c(u).
 Il reste à montrer que f ′ est conservatif. C’est-à-dire que pour tout sommet x ∈ X \ {s, p}
on doit avoir X X
d′ (x) = df ′ (x) = f ′ (u) − f ′ (u) = 0.
u∈ω + (x) u∈ω − (x)

Soit {u1 , u2 , · · · , ul }, l ≤ 1 les arcs qui constituenr la chaine C.

• Si x ∈/ C, il ne passe par x aucun des arcs de C. Par conséquent

ω + (x) ∩ {u1 , u2 , · · · , ul } = ∅, ω − (x) ∩ {u1 , u2 , · · · , ul } = ∅

et pour chaque arc u de ω + (x) ou de ω − (x), on a f ′ (x) = f (u) et donc d′ (x) = d(x) = 0.
• Si x ∈ C \ {s, p} on a quatre possibilités.
a) x est extrémité de ui et est origine de ui+1
Dans ce cas f ′ (ui ) = f (ui ) + δ, ui ∈ ω − (x) et f ′ (ui+1 ) = f (ui+1 ) + δ, ui+1 ∈ ω + (x). Les
autres arcs de ω + (x) et de ω − (x) n’appartiennent pas à {u1 , u2 , · · · , ul } et sur chacun, on a
f ′ (ui ) = f (ui ). Par conséquent
X X
f ′ (u) = f (u) + δ
u∈ω + (x) u∈ω + (x)

et X X
f ′ (u) = f (u) + δ
u∈ω − (x) u∈ω + (x)

d′ (x) = d(x) = 0.
b) x est extrémité de ui et de ui+1
On a f ′ (ui ) = f (ui ) + δ, ui ∈ ω − (x) et f ′ (ui+1 ) = f (ui+1 ) − δ, ui+1 ∈ ω − (x). Les autres arcs
de ω + (x) et de ω − (x) n’appartiennent pas à {u1 , u2 , · · · , ul } et sur chacun, on a f ′ (ui ) = f (ui ).
Par conséquent X X
f ′ (u) = f (u)
u∈ω + (x) u∈ω + (x)

et X X X
f ′ (u) = f (u) + δ − δ = f (u)
u∈ω − (x) u∈ω + (x) u∈ω + (x)

Alors d′ (x) = d(x) = 0.

c) x est origine de ui et de ui+1
On a danscecasf ′ (ui ) = f (ui ) − δ, ui ∈ ω + (x) et f ′ (ui+1 ) = f (ui+1 ) + δ, ui+1 ∈ ω + (x). Et
on trouve d′ (x) = d(x) = 0.
d) x est origine de ui et extrémité de ui+1
On a danscecasf ′ (ui ) = f (ui ) − δ, ui ∈ ω + (x) et f ′ (ui+1 ) = f (ui+1 ) − δ, ui+1 ∈ ω − (x). Et
on trouve également d′ (x) = d(x) = 0.
On a f ′ qui est conservatif et par suite f ′ ∈ FR .
Montrons à présent que v(f ′ ) = v(f ) + δ.
On sait que v(f ′ ) = d′ (s).
• Si s est origine u1 , on a f ′ (u1 ) = f (u1 ) + δ u1 ∈ ω + (s), les autres arcs de ω + (s) et
de ω − (s) sont différents de u2 , u3 , · · · , ul et sur chacun d’eux f ′ (u) = f (u). Par conséquent
d′ (s) = d(s) + δ et donc v(f ′ ) = d′ (s) = d(s) + δ = v(f ) + δ.
• Si s est extrémité de u1 , on a f ′ (u1 ) = f (u1 ) − δ, u1 ∈ ω − (s), les autres arcs de ω + (s)
et de ω − (s) sont différents de u2 , u3 , · · · , ul . Ici encore on trouve d′ (s) = d(s) + δ et donc
v(f ′ ) = d′ (s) = d(s) + δ = v(f ) + δ. 

Exemple 4.3.2
 [4] 1
x1 x3

[4] 2 [4] 4

s [1] 1 [3] 3 p
[2] 1 [7] 2
[4] 3
x2 x4
[4] 4
Dans le réseau ci-dessus la valeur du flot f est v(f ) = 6.
La chaine (s, x1 , x3 , x4 , p) est une chaine améliorante pour le flot f . On a δ = 2. le nouveau
flot f ′ est le suivant et sa valeur est v(f ′ ) = 8.
[4] 3
x1 x3

[4] 4 [4] 4

s [1] 1 [3] 1 p
[2] 1 [7] 4
[4] 3
x2 x4
[4] 4
En conséquence de la proposition ci-dessus, on a :

Proposition 4.3.4 Un flot f est de valeur maximale sur R si et seulement s’il n’existe pas dans
R de chaı̂ne améliorante pour f .

Preuve :
Supposons qu’il n’existe pas dans R de chaı̂ne améliorante pour f et montrons v(f ) est
maximal. Il suffit de montrer qu’il existe une coupe C telle que v(f ) = c(C).
Considérons l’ensemble X1 défini comme suit.
i) s ∈ X1
ii) Si xi ∈ X1 et si u = (xi , xk ) est un arc alors xk ∈ X1 si et seulement si f (u) < c(u).
iii) Si xi ∈ X1 et si u = (xk , xi ) est un arc alors xk ∈ X1 si et seulement si f (u) > 0.
On remarque que :
- s ∈ X1
- Si u est un arc de G sortant d’un sommet de X1 , et si la capacité résiduelle de u c(u) − f (u)
n’est pas nulle alors l’extrémité terminale de u appartient à X1 .
- Si u est un arc de G entant en un sommet de X1 , et si le flux circulant sur u, f (u) n’est
pas nulle alors l’extrémité initiale de u appartient à X1 .
Par construction, pour tout xi nX1 (x 6= s) il existe au moins une chaine C reliant s à x avec
tous les sommets de C qui sont dans X1 .
Pour une telle chaı̂ne on a :
• pour tout arc direct u de C, on a f (u) < c(u). Ce qui implique δ1 = min[c(u) − f (u) : u ∈
C+] > 0
• pour tout arc inverse u de C, on a f (u) > 0. Ce qui implique que δ2 = min[f (u) : u ∈
C − ] > 0. Donc δ = min{δ1 , δ2 } > 0.
Montrons à présent que p ∈ X1 .
 Si p appartient à p, alors d’après ci-dessus il existe une chaı̂ne C de s à p avec δ > 0. Ce qui
implique que C est améliorante. Ce qui est une contradiction. Donc p ∈ / X1 .
On sait que v(f ) = d(s) = d(X1 ).
Or X X
d(X1 ) = f (u) − f (u)
ω + (X1 ) ω − (X1 )
on a
ω + (X1 ) = {u = (xi , xk ) : xi ∈ X1 et xk ∈
/ X1 }
Donc pour tout u ∈ ω + (X1 ) on a f (u) = c(u).

ω − (X1 ) = {u = (xk , xi ) : xk ∈
/ X1 et xi ∈ X1 }
Donc pour tout u ∈ ω − (X1 ), on a f (u) = 0.
Par suite on a X
d(X1 ) = c(u) = c(X1 ).
ω + (X1 )

Ce qui implique que v(f ) = c(C). Par suite f est de valeur maximale. 
On a alors une condition nécessaire et suffisante pour qu’un flot soit de valeur maximale.

Proposition 4.3.5 une condition nécessaire et suffisante pour que f soit de valeur maximale
est qu’il n’existe pas de chaine améliorante pour f de s à p.

On a le théorème de Ford et Fulkerson

Théorème 4.3.1 Dans R, la valeur maximale des flots réalisables est égale à la capacité mini-
male des coupes.

4.3.1 Prcocédure de détection d’une chaine améliorante

Etant donné f un flot réalisable sur R, pour déterminer une chaine améliorante pour f on
peut utiliser l’algorithme suivant.
1) Marquer s
2) Marquer s tout sommet suivant x de s tel que pour l’arc u = (s, x) on a f (u) < c(u)
2) x étant un sommet déjà marqué, marquer ”x”
- tout sommet suivant y de x non encore marqué tel que pour l’arc u = (x, y) on a
f (u) < c(u).
- tout sommet précédent y de x non encore marqué tel que pour l’arc u = (y, x) on a
f (u) > 0.
Si par cette procédure, p ne peut pas être marqué, alors il n’existe pas de chaine améliorante
reliant s à p.
Si au contraire, la procédure permet de marquer p, on obtient à partir de p, en utilisant
la marque de certains sommets marqués une chaine améliorante reliant s à p. Cette chaine se
construit à l’envers de la façon suivante.
- Relier p au sommet correspondant à la marque de p.
- Recommencer à partir du sommet obtenu et ainsi de suite jusqu’à s.

Exemple 4.3.3
 [3] 2
x1 x 5 xx5 4

[2] 2 [5] 5
[2] 2
[1] 0 [2] 1
[5] 5 [2] 2
s∗ x2 x 4 xx4 3 px6

[2] 0 [1] 1
[5] 2 [4] 1 [7] 4

x3 s xx6 2
[2] 2
Le sommet p est marqué. La chaine C = (s, x3 , x4 , x2 , x6 , p) est une chaine améliorante. Donc
le flot ci-dessus n’est pas de valeur maximale.

4.3.2 Prcocédure de modification d’un flot relativement à une chaine améliorante

Etant donné f un flot réalisable sur R et C une chaine améliorante pour f , on obtient un
flot améliorant la valeur de f à l’aide de la procédure suivante.

1) On calcule
δ1 = min [c(u) − f (u) : u ∈ C + ]
δ2 = min [f (u) : u ∈ C − ]
δ = min{δ1 , δ2 }
2) Modification
- sur chaque arc u ∈ C + augmenter le flux de δ
- sur chaque arc u ∈ C − diminuer le flux de δ

3) On obtient ainsi un flot f ′ qui améliore f . On a v(f ′ ) = v(f ) + δ.

Remarque 4.3.2 L’étape 2) signifie que

− si u ∈ C + f ′ (u) = f (u) + δ
− si u ∈ C − f ′ (u) = f (u) − δ
/ C f ′ (u) = f (u)
− si u ∈
On a à présent l’algorithme de Ford et Fulkerson pour déterminer un flot de valeur maximale

4.3.3 Algorithme de Ford et Fulkerson

1) Début
2) Initialisation
On considère un flot réalisable f sur le réseau R.
3) Marquage des sommets
On marque les sommets à l’aide de la procédure ”marquage des sommets”.
Si par cette procédure, le sommet puits p ne peut pas être marqué, alors f est de valeur
maximale. On va à l’étape 5).
Sinon, on détermine une chaine améliorante C.
4) Modification des flux
On modifie les flux à l’aide de la procédure ”modification des flux” relativement à la chaine
C.
On obtient ainsi un nouveau flot réalisable sur R encore noté f et on retourne à l’étape 3).
5) Fin