h)
s
b
t
a
[0, 2]
[1, 4]
[0, 2]
[3, 4]
[4, 5]
Pour le graphe G suivant, représenter le graphe G
∗ , trouver un flot saturant f
∗ sur G
∗ et calculer le flot admissible
f . Le flot f est-il maximum ? Quelle est la valeur d’un
flot maximum sur G ?
Voici une méthode pour rechercher un flot admissible sur
G ou pour montrer qu’il n’en existe pas :
® trouver un flot maximum f
∗ sur G
∗ , en utilisant par exemple l’algorithme du
flot maximum ;
® si f
∗ est saturant, alors le flot f défini comme ci-dessus est un flot admissible
sur G ;
® si f
∗ n’est pas saturant, on peut montrer qu’il n’existe pas de flot admissible
sur G.
100 – EXERCICES
s
b
t
a
[0, 2]
[1, 4]
[0, 2]
[3, 4]
[4, 5]
Pour le graphe G suivant, représenter le graphe G
∗ , trouver un flot saturant f
∗ sur G
∗ et calculer le flot admissible
f . Le flot f est-il maximum ? Quelle est la valeur d’un
flot maximum sur G ?
Voici une méthode pour rechercher un flot admissible sur
G ou pour montrer qu’il n’en existe pas :
® trouver un flot maximum f
∗ sur G
∗ , en utilisant par exemple l’algorithme du
flot maximum ;
® si f
∗ est saturant, alors le flot f défini comme ci-dessus est un flot admissible
sur G ;
® si f
∗ n’est pas saturant, on peut montrer qu’il n’existe pas de flot admissible
sur G.
100 – EXERCICES