MIAGE Master 1
MIAGE Master 1
Recherche Opérationnelle 1
TD7: le 16/11/2006
Algorithmes de flot maximum
Trouver un flot maximum pour le réseau
donné:
- 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.
- 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
correction: au début la hauteur de la source est n le nombre de sommets et
celle de chaque autre sommet est 0; on ne change pas la hauteur de la
source ou du puits.
Essayez de ne pas utiliser le même algorithme que vos voisins; quand vous
aurez terminé vérifier 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), FI(6), GI(5), HI(3)
File translated from
TEX
by
TTH,
version 3.05.
On 17 Nov 2006, 09:25.