Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
134
les deux pre mières sommes étant iden tiques (chaque arc (i, j), i H S, j x S, appa raît
une fois dans cha cune), nous obte nons :
V(f) 5 a
i HS, jxS
w ij 2 a
i HS, jxS
w ji
Cette prop riété montre que pour tout ensemble de som mets S conte nant la source
et ne conte nant pas le puits, la somme des flux sor tant diminuée de la somme des flux
entrant est égale à la valeur du flot.
Nous allons mon trer une seconde prop riété reliant la valeur d’une coupe à celle
d’un flot. L’énoncé de cette prop
riété est le sui vant :
Pour toute coupe C (de capa cité C(S)) et tout flot (de valeur V()), on a : C(S) > V(F).
En effet, pour tout arc (i, j) nous avons : 0 < w ij < c ij , d’où nous obte nons :
C(S) 5 a
i HS, jxS
c ij > a
i HS, jxS
w ij > a
i HS, jxS
w ij 2 a
i HS, jxS
w ji 5 V(F).
On en déduit, en rai son nant par l’absurde, que s’il existe une coupe S
*
et un flot
f
*
tels que : C(S
*
) 5 V(f
*
), alors f
*
est un flot de valeur maximale et S
*
, une coupe
de capa cité mini male.
Nous sommes main te nant en mesure de mon trer le théo rème de Ford- Fulkerson
qui s’énonce de la façon sui vante :
Dans tout réseau de tran sport, la capa cité mini male des coupes est égale à la
valeur maximale des flots.
Soit le der
nier flot obtenu par appplication de l’algo rithme, pour lequel il
n’existe donc pas de chaîne amé lio rante. Nous avons déjà observé que dans ce cas,
après l’application de la procédure de mar quage, p n’est pas mar qué. Consi dé rons
alors S l’ensemble des som mets mar qués. s étant mar qué, et p n’étant pas mar qué,
l’ensemble S et son com plé men taire S (les som mets non mar qués) sont non vides et
défi nissent bien une coupe. Tout arc (i, j) avec i H S, j x S est nécessairement saturé,
c’est- à-dire nous avons w ij 5 c ij car, sinon, j aurait été mar qué. D’autre part, pour
tout arc (j, i) avec j x S, et i H S, on a nécessairement w ji 5 0, puisque j n’a pas été
mar qué. Nous obte nons alors :
C(S) 5 a
i HS, jxS
c ij 5 a
i HS, jxS
w ij 2 a
i HS, jxS
w ij 5 V(F).
En uti li sant la prop riété pré cé dente nous arri vons au résul tat annoncé. Celui- ci
jus
ti
fie l’algo rithme puisque l’algo rithme se ter
mine lors qu’il n’y a plus de chaîne
amé lio
rante et permet d’exhiber une coupe et un flot de même valeur. Le flot consi
déré à cette étape est donc opti mal (de valeur maximale).
4.5 flot de vAleur mAximAle à coût mini mAl
Dans de nom breux pro blèmes, outre les capa ci tés limi tées de tran sport, le coût
d’ache mi ne ment d’une mar chan dise (ou d’une cer taine quan tité de pro duit) doit être
pris en compte. Le pro blème de la recherche d’un flot maximal
(1)
à coût mini mal per -
met de prendre en compte ce second objec tif dans le cadre d’un réseau de tran sport.
D’autant que, si la valeur maximale V
*
d’un flot est évi dem ment unique, il existe
134
les deux pre mières sommes étant iden tiques (chaque arc (i, j), i H S, j x S, appa raît
une fois dans cha cune), nous obte nons :
V(f) 5 a
i HS, jxS
w ij 2 a
i HS, jxS
w ji
Cette prop riété montre que pour tout ensemble de som mets S conte nant la source
et ne conte nant pas le puits, la somme des flux sor tant diminuée de la somme des flux
entrant est égale à la valeur du flot.
Nous allons mon trer une seconde prop riété reliant la valeur d’une coupe à celle
d’un flot. L’énoncé de cette prop
riété est le sui vant :
Pour toute coupe C (de capa cité C(S)) et tout flot (de valeur V()), on a : C(S) > V(F).
En effet, pour tout arc (i, j) nous avons : 0 < w ij < c ij , d’où nous obte nons :
C(S) 5 a
i HS, jxS
c ij > a
i HS, jxS
w ij > a
i HS, jxS
w ij 2 a
i HS, jxS
w ji 5 V(F).
On en déduit, en rai son nant par l’absurde, que s’il existe une coupe S
*
et un flot
f
*
tels que : C(S
*
) 5 V(f
*
), alors f
*
est un flot de valeur maximale et S
*
, une coupe
de capa cité mini male.
Nous sommes main te nant en mesure de mon trer le théo rème de Ford- Fulkerson
qui s’énonce de la façon sui vante :
Dans tout réseau de tran sport, la capa cité mini male des coupes est égale à la
valeur maximale des flots.
Soit le der
nier flot obtenu par appplication de l’algo rithme, pour lequel il
n’existe donc pas de chaîne amé lio rante. Nous avons déjà observé que dans ce cas,
après l’application de la procédure de mar quage, p n’est pas mar qué. Consi dé rons
alors S l’ensemble des som mets mar qués. s étant mar qué, et p n’étant pas mar qué,
l’ensemble S et son com plé men taire S (les som mets non mar qués) sont non vides et
défi nissent bien une coupe. Tout arc (i, j) avec i H S, j x S est nécessairement saturé,
c’est- à-dire nous avons w ij 5 c ij car, sinon, j aurait été mar qué. D’autre part, pour
tout arc (j, i) avec j x S, et i H S, on a nécessairement w ji 5 0, puisque j n’a pas été
mar qué. Nous obte nons alors :
C(S) 5 a
i HS, jxS
c ij 5 a
i HS, jxS
w ij 2 a
i HS, jxS
w ij 5 V(F).
En uti li sant la prop riété pré cé dente nous arri vons au résul tat annoncé. Celui- ci
jus
ti
fie l’algo rithme puisque l’algo rithme se ter
mine lors qu’il n’y a plus de chaîne
amé lio
rante et permet d’exhiber une coupe et un flot de même valeur. Le flot consi
déré à cette étape est donc opti mal (de valeur maximale).
4.5 flot de vAleur mAximAle à coût mini mAl
Dans de nom breux pro blèmes, outre les capa ci tés limi tées de tran sport, le coût
d’ache mi ne ment d’une mar chan dise (ou d’une cer taine quan tité de pro duit) doit être
pris en compte. Le pro blème de la recherche d’un flot maximal
(1)
à coût mini mal per -
met de prendre en compte ce second objec tif dans le cadre d’un réseau de tran sport.
D’autant que, si la valeur maximale V
*
d’un flot est évi dem ment unique, il existe