Solutions
470
4.12 Voici le tracé du graphe :
x 1
 x 1
 x 3
 x 5
 x 2
x 3
x 5
x 4
x 2
Flot initial
(de valeur 9)
[4], 4
2
1
2
3
2
3
[5]
[1]
[2]
[3]
[5]
[3]
[12] 9

1) Ce graphe est bien un « réseau de tran sport » : il est fini, sans boucle, com porte un
sommet- source (x 3 ) et un sommet- puits (x 4 ) et tout arc est valué par un entier posi tif (nommé :
« capa cité »).
2) Les flux pro po sés forment bien un flot : tout flux sur un arc est supé rieur ou égal à zéro
et inférieur ou égal à sa capacité : en tout som met autre que la source et le puits, on véri fie la loi
de Kirchhoff : la somme des flux entrant sur le som met égale celle des flux sor tant ; ainsi en x 1
il entre 2 + 2 = 4 et repart 1 + 3 = 4, etc.
Le flot pro posé est com plet: tout che min de la source au puits com porte au moins un arc
saturé (il n’est donc pas trivialement amé lio rable).
Appli quons la pro cé dure de mar quage de Ford- Fulkerson : on l’ini tia lise en mar quant la
source x 3 du signe + ; puis x 1 est mar qué +x 3 , car l’arc (x 3 , x 1 ) n’est pas saturé ; puis x 2 est mar -
qué –x 1 car l’arc (x 2 , x 1 ) est de flux non nul ; puis x 5 est mar qué +x 2 car l’arc (x 2 , x 5 ) n’est pas
saturé ; enfin x 4 est mar qué +x 5 . Puisque le puits est mar qué, le flot pro posé n’est pas opti mal.
Voici la chaîne amé lio rante μ (qu’on trouve en remon tant le mar quage, depuis le puits).
x 1
x 5
x 4
x 2
x 3
9
2
2
2
[12]
[5]
[5]
+x 3
+x 2
+x 5
x 1
chaîne améliorante µ
+