4.4 Pro blème du flot de valeur maximale
133
© Dunod – Toute reproduction non autorisée est un délit.
4.4.2 Théo rème de Ford- Fulkerson
Nous allons don ner le théo
rème, dû à Ford et Fulkerson, jus ti fiant l’algo rithme pré
senté plus haut. Rap pe lons les défi ni tions et nota tions uti li sées.
Nous note rons, ici, s le som met source 1 G
2
1 s 2 5 [2 et p le som met puits
1 G
1
1 p2 5 [2 du réseau de tran sport. Pour tout arc (i, j) du réseau, c ij est la capa -
cité cet arc et w ij est son flux. Les contraintes que doivent res
pec ter un flot sont les
sui vantes :
1. pour tout arc (i, j), on a : 0 < w ij < c ij
2. pour tout som met i 2 s, p, on a : a
jHG
2 (i)
w ji 5 a
jHG
1 (i)
w ij (loi de Kirchhoff).
Par défi ni tion la valeur d’un flot F 5 (w 1 , c , w m ), notée V(F), est la quan tité
sui vante : V(F) 5 a w si . (Par abus de nota tion, dans cette par tie, nous écri vons
a w si pour a
iPG
1 1s2
w si .) ; on a dési gné par w k le flux sur l’arc u k (k 5 1, c , m).
Consi dé rons S un sous- ensemble de som mets du réseau de tran sport conte nant
la source mais ne conte nant pas le puits : s H S, p x S. Cet ensemble et son com plé -
men taire S 5 X 2 S forment une « coupe » et C(S), la « capacité » de cette coupe,
est par définition :
C(S) 5 a
iPS, jPS
c ij
Mon trons la prop riété sui vante : pour toute coupe 1 S, S 2 et tout flot , on a :
V(F) 5 a
i HS, jxS
w ij 2 a
i HS, jxS
w ji .
La valeur du flot, v(F), égale la somme des flux sor tants de S, dimi nuée de la
somme des flux entrants dans S.
En uti li sant la loi de Kirchhoff pour chaque som met i 2 s, appar te nant à
l’ensemble S, et la défi
ni tion de la valeur du flot nous obte nons :
V(F) 5 a w si 1 a
i HS, i 2s
a a w ij 2 a w ji b
(''')'''*
5 0
La source s n’ayant pas de pré dé ces seur A a w js 5 0B, il vient :
V(F) 5 a
i HS
w ij 2 a
i HS
w ji
en décom po sant cha cune de ces deux sommes, sui vant que j appar tient ou non à
l’ensemble S nous avons :
V(F) 5 a
i HS, jHS
w ij 2 a
i HS, jHS
w ji 1 a
i HS, jxS
w ij 2 a
i HS, jxS
w ji
133
© Dunod – Toute reproduction non autorisée est un délit.
4.4.2 Théo rème de Ford- Fulkerson
Nous allons don ner le théo
rème, dû à Ford et Fulkerson, jus ti fiant l’algo rithme pré
senté plus haut. Rap pe lons les défi ni tions et nota tions uti li sées.
Nous note rons, ici, s le som met source 1 G
2
1 s 2 5 [2 et p le som met puits
1 G
1
1 p2 5 [2 du réseau de tran sport. Pour tout arc (i, j) du réseau, c ij est la capa -
cité cet arc et w ij est son flux. Les contraintes que doivent res
pec ter un flot sont les
sui vantes :
1. pour tout arc (i, j), on a : 0 < w ij < c ij
2. pour tout som met i 2 s, p, on a : a
jHG
2 (i)
w ji 5 a
jHG
1 (i)
w ij (loi de Kirchhoff).
Par défi ni tion la valeur d’un flot F 5 (w 1 , c , w m ), notée V(F), est la quan tité
sui vante : V(F) 5 a w si . (Par abus de nota tion, dans cette par tie, nous écri vons
a w si pour a
iPG
1 1s2
w si .) ; on a dési gné par w k le flux sur l’arc u k (k 5 1, c , m).
Consi dé rons S un sous- ensemble de som mets du réseau de tran sport conte nant
la source mais ne conte nant pas le puits : s H S, p x S. Cet ensemble et son com plé -
men taire S 5 X 2 S forment une « coupe » et C(S), la « capacité » de cette coupe,
est par définition :
C(S) 5 a
iPS, jPS
c ij
Mon trons la prop riété sui vante : pour toute coupe 1 S, S 2 et tout flot , on a :
V(F) 5 a
i HS, jxS
w ij 2 a
i HS, jxS
w ji .
La valeur du flot, v(F), égale la somme des flux sor tants de S, dimi nuée de la
somme des flux entrants dans S.
En uti li sant la loi de Kirchhoff pour chaque som met i 2 s, appar te nant à
l’ensemble S, et la défi
ni tion de la valeur du flot nous obte nons :
V(F) 5 a w si 1 a
i HS, i 2s
a a w ij 2 a w ji b
(''')'''*
5 0
La source s n’ayant pas de pré dé ces seur A a w js 5 0B, il vient :
V(F) 5 a
i HS
w ij 2 a
i HS
w ji
en décom po sant cha cune de ces deux sommes, sui vant que j appar tient ou non à
l’ensemble S nous avons :
V(F) 5 a
i HS, jHS
w ij 2 a
i HS, jHS
w ji 1 a
i HS, jxS
w ij 2 a
i HS, jxS
w ji