Université de la Manouba
Institut Supérieur des Arts Multimédias de la Manouba
Département Informatique
TD 3
Exercice 1.
Déterminer une solution optimale au problème du flot maximum sur le réseau ci-
dessous ; donner une coupe de capacité minimale.
A. 8 E.
5
10 3 4 2 10
B . 7 . F
20 6 10
S. 5 3 .P
10 3 20
C . 1 .G
10 5 10
4 7 5
. 2 .
D H
Exercice 2.
Trois villes J, K, L sont alimentées en eau grâce à quatre réserves A, B , C, et
D ; les réserves journalières disponibles sont respectivement de 15, 10, 15 et 15
milliers de m3. Le réseau de distribution peut être schématisé par le graphe ci-
dessous (les poids portés sur les arcs représentant les débits maximums en m 3 par
jour).
Université de la Manouba
Institut Supérieur des Arts Multimédias de la Manouba
Département Informatique
Ces trois villes sont en pleine évolution et désirent améliorer leur réseau
d’alimentation afin de satisfaire des besoins futurs plus importants. Une étude a été
faite et a permis de déterminer les demandes journalières maximales probables, à
avoir 15, 20 et 15 milliers de m3 pour les villes J, K et L respectivement.
1. Déterminer la valeur du flot maximal pouvant passer dans le réseau
actuel et donner la coupe minimale correspondante.
2. La valeur de ce flot est jugée nettement insuffisante; aussi le conseil
intercommunal décide-t-il de refaire les canalisations (A, E) et (I, L).
Déterminer les capacités à prévoir pour ces deux canalisations ainsi
que la valeur du nouveau flot optimal.
Exercice 3.
Considérons le réseau non orienté :
1. Peut-on parler de flot dans un réseau non orienté ? Comment
s’interprète alors la valeur du flot sur un arc, et les capacités ?
2. Proposer (et appliquer) une variante simple de l’algorithme de
Ford-Fulkerson pour déterminer un flot maximum entre S et P
sur le réseau ci-dessous.
Université de la Manouba
Institut Supérieur des Arts Multimédias de la Manouba
Département Informatique
Exercice 4.
Existe-il un flot réalisable dans les réseaux ci-dessous, où les nombres (b(u), c(u)) associés à
chaque arc u désignent respectivement la borne inférieure et supérieure du flot sur cet arc.
A (2 ;3) B
(1 ;4) C (0 ;6) D (4 ;5)
(0 ;1) (3 ;6) (1 ;4) (1 ;6)
(2 ;4) E (0 ;4) F (1 ;2)
G (2 ;5) H
Exercice 5.
Trouver un flot maximum dans le réseau ci-dessous, où les nombres (b(u), c(u)) associés à
chaque arc u représentent respectivement les bornes inférieures et supérieures du flot sur cet arc.
(2 ;3)
(4 ;5)
(1 ;3)
(0 ;4) (0 ;11)
(0 ;3) (8 ;11)
(5 ;9)
(2 ;2)
