Problèmes de flots
207
On a indiqué en les entourant les capacités des arcs.
On peut améliorer le flot en jouant uniquement sur cette chaîne. Sur l'exemple, on voit
bien que l'on peut ajouter un flot égal à +1 sur les arcs
, , , et retrancher une
unité également à l'arc
(loi des nœuds). Le flot arrivant en augmente d'une unité.
Cela dit, on peut essayer d'augmenter davantage le flot, en ajoutant et en retranchant des
flots aux arcs jusqu'à ce que, soit sur un arc parcouru dans le sens
le flot atteigne la
capacité, soit sur un arc parcouru dans le sens contraire, le flot devienne nul.
On voit qu'ici en fait on est tout de suite limité par la capacité de l'arc
, égale à 4 alors
que le flot existant est 3. On ne peut donc, à partir de cette chaîne qu'augmenter le flot
d'une unité. On obtient ainsi le nouveau flot.
Sur ce même graphe, on a indiqué le nouveau marquage, qui permet de marquer , donc
d
' augmenter encore le flot total.
Prenons une nouvelle chaîne.
Sur cette chaîne également, on ne peut augmenter le flot arrivant en que d'une unité, à
cause de l'arc
, parcouru dans le sens
et qui porte un flot d'une unité. On obtient le
flot :
A
B
C
D
E
F
G
H
J
I
K
2
1
0
1
4
5
4
1
0
4
6
5
2
3
1
2
4
1
0
+A
+C
+A
-G
-F
+B
+B
+E
+F
+I
+D
+J
+F
A
B
D
F
G
J
I
K
[7]
[4]
[3]
[5]
[11]
[8]
[2]
2
1
1
1
4
2
5