Solu tions des exer cices du cha pitre 4
471
© Dunod – Toute reproduction non autorisée est un délit.
Les arcs « directs » de μ sont ceux qu’on ren contre dans le sens de leur orien ta tion lors -
qu’on par court la chaîne de la source jus qu’au puits ; ce sont : (x 3 , x 1 ), (x 2 , x 5 ), (x 5 , x 4 ) (ces
arcs ont donné lieu à un mar quage +). Ici il y a un seul arc « indi rect » : (x 2 , x 1 ) (qui a donné
lieu à un mar quage 2).
Les capa ci tés rési duelles des arcs directs sont : 522, 522, 1229 : la plus petite capa cité
rési duelle est donc δ
+
= 3 ; le flux de l’arc indi rect (x 2 , x 1 ) est : 2, donc δ
2
= 2. Le flot peut être
amé lioré de δ = min (δ
+
, δ
2
): sur tout arc direct, le flux est aug menté de δ, soit ici de 2 uni tés ;
sur tout arc indi rect, le flux est dimi nué de δ (22 uni tés sur (x 2 , x 1 )).
Le flot amé lioré, de valeur 9 + δ = 11 , est le sui vant :
x 1
+ x 3
+ x 2
x 3
x 5
x 4
x 2
[4] 4
4
1
0
3
4
3
[5]
[1]
[2]
[3]
[5]
[3]
[12] 11
coupe minimale
+
Appli quons lui la pro cé dure de mar quage : on marque la source x 3 puis x 1 : aucun autre
som met ne peut être mar qué (x 2 ne peut pas être mar qué –x 1, car le flux sur l’arc (x 2 , x 1 ) est
désor mais nul). Le puits n’étant pas mar qué ce flot est opti mal ; il a pour valeur v
* 5 11.
La coupe mini male est consti tuée des arcs dont l’extré mité ini tiale est mar quée : x 1 ou x 3 ,
et l’extré mité ter mi nale est non mar quée ; elle consti tue le gou let d’étran gle ment du réseau
de tran sport ; voici la rai son intui tive de l’optimalité du flot final : tous les arcs qui tra versent
la coupe dans le sens direct (de la source vers le puits) sont satu rés ; ceux dans le sens indi rect
sont de flux nul (ici, un seul (x 2 , x 1 )).
* 4.13 Sous trayons des élé ments de chaque ligne le plus petit élé ment de celle- ci : on obtient
le tableau 1 ; puis opé rons de même pour les colonnes b et e ne conte nant pas encore de zéro;
il vient le tableau 2.
tableau 1
A
a
B
b
C
c
D
d
E
e
F
f
0
0
60
66
0
8
26
19 56 11 58 55
55
57
68
42
29
4
17
80
11
16
15
52
63 29 58
10
71
10
77
12
41
0
0
0
↑
↑
8
10
tableau 2
A
B
C
D
E
F
0
0
0
60
66
0
18
77
56
11
11
48
55
55
57
68
42
19
4
17
3
16
15
52
63 29
48
61
72
12
33
0
0
0
0
0
a
b
c
d
e
f
471
© Dunod – Toute reproduction non autorisée est un délit.
Les arcs « directs » de μ sont ceux qu’on ren contre dans le sens de leur orien ta tion lors -
qu’on par court la chaîne de la source jus qu’au puits ; ce sont : (x 3 , x 1 ), (x 2 , x 5 ), (x 5 , x 4 ) (ces
arcs ont donné lieu à un mar quage +). Ici il y a un seul arc « indi rect » : (x 2 , x 1 ) (qui a donné
lieu à un mar quage 2).
Les capa ci tés rési duelles des arcs directs sont : 522, 522, 1229 : la plus petite capa cité
rési duelle est donc δ
+
= 3 ; le flux de l’arc indi rect (x 2 , x 1 ) est : 2, donc δ
2
= 2. Le flot peut être
amé lioré de δ = min (δ
+
, δ
2
): sur tout arc direct, le flux est aug menté de δ, soit ici de 2 uni tés ;
sur tout arc indi rect, le flux est dimi nué de δ (22 uni tés sur (x 2 , x 1 )).
Le flot amé lioré, de valeur 9 + δ = 11 , est le sui vant :
x 1
+ x 3
+ x 2
x 3
x 5
x 4
x 2
[4] 4
4
1
0
3
4
3
[5]
[1]
[2]
[3]
[5]
[3]
[12] 11
coupe minimale
+
Appli quons lui la pro cé dure de mar quage : on marque la source x 3 puis x 1 : aucun autre
som met ne peut être mar qué (x 2 ne peut pas être mar qué –x 1, car le flux sur l’arc (x 2 , x 1 ) est
désor mais nul). Le puits n’étant pas mar qué ce flot est opti mal ; il a pour valeur v
* 5 11.
La coupe mini male est consti tuée des arcs dont l’extré mité ini tiale est mar quée : x 1 ou x 3 ,
et l’extré mité ter mi nale est non mar quée ; elle consti tue le gou let d’étran gle ment du réseau
de tran sport ; voici la rai son intui tive de l’optimalité du flot final : tous les arcs qui tra versent
la coupe dans le sens direct (de la source vers le puits) sont satu rés ; ceux dans le sens indi rect
sont de flux nul (ici, un seul (x 2 , x 1 )).
* 4.13 Sous trayons des élé ments de chaque ligne le plus petit élé ment de celle- ci : on obtient
le tableau 1 ; puis opé rons de même pour les colonnes b et e ne conte nant pas encore de zéro;
il vient le tableau 2.
tableau 1
A
a
B
b
C
c
D
d
E
e
F
f
0
0
60
66
0
8
26
19 56 11 58 55
55
57
68
42
29
4
17
80
11
16
15
52
63 29 58
10
71
10
77
12
41
0
0
0
↑
↑
8
10
tableau 2
A
B
C
D
E
F
0
0
0
60
66
0
18
77
56
11
11
48
55
55
57
68
42
19
4
17
3
16
15
52
63 29
48
61
72
12
33
0
0
0
0
0
a
b
c
d
e
f