MIAGE Master 1 Recherche Opérationnelle 1 TD10 : le 25/11/2009 Algorithmes de flot maximum

Trouver un flot maximum pour le réseau donné :

1. Soit par l’algorithme de Ford et Fulkerson ; vous allez dessiner le flot dans le réseau après chaque recherche d’une chaîne augmentante.

2. Soit par l’algorithme des hauteurs ; rappel : tant que possible on ajoute un flot d’un sommet à un voisin moins haut ; si ceci est impossible on incrémente la hauteur d’un sommet au minimum qui le rend possible.

Essayez de ne pas utiliser le même algorithme que vos voisins ; quand vous aurez terminé vérifiez que la quantité transférée est la même pour les deux algorithmes ; avez-vous exactement le même flot que vos voisins?

Quelle est la coupe minimum?

Sommets : A(source), B, C, D, E, F, G, H, I(destination)

Arêtes : (avec capacités dans chaque sens): AB(2), AC(5), AD(7), BF (6), BG(5), CD(3), CF (3), CG(4), CH(3), DE(4), EG(4), EH(1), F I(6), GI(5), HI(3)