4.4 Pro blème du flot de valeur maximale
129
© Dunod – Toute reproduction non autorisée est un délit.
Figure 4.20 Construc tion d’un réseau de tran sport
Le pro blème se ramène alors à faire pas ser un flot de valeur maximale de Ο vers Ρ
(ou, si l’on veut, sur un arc ima gi naire, dit « de retour », qui revien drait de Ρ vers O).
Voici un flot f sur ce réseau de tran sport :
Figure 4.21 Exemple de flot
Sur chaque arc u 5 1 x, y2 , on a rap pelé [entre cro chets] la capa cité de l’arc, puis
indi qué le flux w(u) de cet arc. Le lec teur véri fiera aisé ment la loi de Kirchhoff en
tout som met autre que Ο et P. La valeur V(f) de ce flot initial est 80 (1/s).
129
© Dunod – Toute reproduction non autorisée est un délit.
Figure 4.20 Construc tion d’un réseau de tran sport
Le pro blème se ramène alors à faire pas ser un flot de valeur maximale de Ο vers Ρ
(ou, si l’on veut, sur un arc ima gi naire, dit « de retour », qui revien drait de Ρ vers O).
Voici un flot f sur ce réseau de tran sport :
Figure 4.21 Exemple de flot
Sur chaque arc u 5 1 x, y2 , on a rap pelé [entre cro chets] la capa cité de l’arc, puis
indi qué le flux w(u) de cet arc. Le lec teur véri fiera aisé ment la loi de Kirchhoff en
tout som met autre que Ο et P. La valeur V(f) de ce flot initial est 80 (1/s).