Problèmes de flots
241
Graphe associé:
On peut sur ce graphe marquer le sommet par la chaîne
.
On améliore donc le flot qui devient:
On obtient en conséquence un couplage maximal de taille 6; cela veut dire que nous
avons obtenu l'optimum, la matrice des coûts 8 étant équivalente à la matrice1, et la
fonction économique calculée sur la matrice 8 à partir de l'affectation donnée par le
couplage obtenu étant la valeur nulle.
x 0
A
B
C
D
E
F
a
b
c
d
e
f
z
x 0
- d
+D
- b
- e
- f
+B
+C
+B
+A
- a
+F
x 0
A
B
C
D
E
F
a
b
c
d
e
f
z
+D
+F
+f
241
Graphe associé:
On peut sur ce graphe marquer le sommet par la chaîne
.
On améliore donc le flot qui devient:
On obtient en conséquence un couplage maximal de taille 6; cela veut dire que nous
avons obtenu l'optimum, la matrice des coûts 8 étant équivalente à la matrice1, et la
fonction économique calculée sur la matrice 8 à partir de l'affectation donnée par le
couplage obtenu étant la valeur nulle.
x 0
A
B
C
D
E
F
a
b
c
d
e
f
z
x 0
- d
+D
- b
- e
- f
+B
+C
+B
+A
- a
+F
x 0
A
B
C
D
E
F
a
b
c
d
e
f
z
+D
+F
+f