Flot maximal

Bonjour,

Je cherche le flot maximal du graphe ci-joint.
J'applique l'algorithme de Ford Fulkerson:

Une première chaîne augmentante est $s \rightarrow A \rightarrow D \rightarrow F \rightarrow t$ qui augmente le flot de 40
Une deuxième chaîne augmentante est $s \rightarrow A \rightarrow G \rightarrow E \rightarrow t$ qui augmente le flot de 30
Une troisième chaîne augmentante est $s \rightarrow A \rightarrow C \rightarrow D \rightarrow t$ qui augmente le flot de 20

Le flot est alors complet.

On peut marquer tous les sommets sauf t d'un +: le flot est donc maximal et vaut 90.
La coupe est alors formée de tous les arcs sauf ceux d'extrémité t; la capacité de la coupe est aussi 90.

Est-ce correct?81438
Connectez-vous ou Inscrivez-vous pour répondre.