Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Application de l’algorithme de FORD-FULKERSON Soit le graphe orienté et valué s

Application de l’algorithme de FORD-FULKERSON Soit le graphe orienté et valué suivant : Valuation      = = = ) ( 0 compte en pris non coût d capacité c b Chercher le flot complet du réseau. a 7 Capacité b c d S P e 10 8 3 3 8 4 2 3 4 7 6 4 a () 7 Capacité b () c () d () S () P () e () 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] Flot nul a (+S) 7 Capacité b (+S) c (+a) d (+a) S (+) P (+c) e (+b) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] Premier marquage : L’ordre dans lequel on traite les sommets marqués est une file : S, a, b, c, d, e, P a (+S) 7 Capacité b (+S) c (+a) d (+a) S (+) P (+c) e (+b) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] Augmentation possible du flot dans la chaîne améliorante : a 7 c S P 8 4 La capacité minimale de la chaîne : 4 On va donc augmenter le flot sur cette chaîne, au maximum, cad jusqu’à la capacité minimale de la chaîne. a (+S) 7 Capacité b (+S) c (+a) d (+a) S (+) P (+c) e (+b) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [0] [4] [4] [0] [0] [0] [0] [0] [0] [0] [4] [0] [0] Le flot sur cette chaîne est maintenant : 4 / 1 1 = v f On remarque que le flot est complet dans P c → , cet arc est saturé. a () 7 Capacité b () c () d () S () P () e () 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [0] [4] [4] [0] [0] [0] [0] [0] [0] [0] [4] [0] [0] Nouveau marquage : L’ordre dans lequel on traite les sommets marqués est une file : S, a, b, c, d, e, P a (+S) 7 Capacité b (+S) c (+a) d (+a) S (+) P (+d) e (+b) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [0] [4] [4] [0] [0] [0] [0] [0] [0] [0] [4] [0] [0] Augmentation possible du flot dans la chaîne améliorante : a 3 d S P 4 7 La capacité minimale de la chaîne : 3 On va donc augmenter le flot sur cette chaîne, au maximum, cad jusqu’à la capacité minimale de la chaîne. a (+S) 7 Capacité b (+S) c (+a) d (+a) S (+) P (+d) e (+b) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [0] [4+3] [4] [3] [0] [0] [0] [0] [0] [0] [4] [3] [0] Le flot sur cette chaîne est maintenant : 3 / 2 2 = v f On remarque que le flot est complet dans a S → , cet arc est saturé. a () 7 Capacité b (+S) c () d () S (+) P () e () 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [0] [7] [4] [3] [0] [0] [0] [0] [0] [0] [4] [3] [0] Nouveau marquage : Le sommet a n’est pas marquable depuis S car il est saturé. a (-c) 7 Capacité b (+S) c (+b) d (+b) S (+) P () e (+b) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [0] [7] [4] [3] [0] [0] [0] [0] [0] [0] [4] [3] [0] On continue le marquage : Le sommet b traité, on traite c. Or on a 0 ) , ( > c a f , on note donc le sommet a par ) ( c − . Ensuite on a P c → saturé, on ne peut donc pas encore marquer P. Les autres sommets encadrants c sont déjà marqués (b et d), on passe donc au suivant. a (-c) 7 Capacité b (+S) c (+b) d (+b) S (+) P (+d) e (+b) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [0] [7] [4] [3] [0] [0] [0] [0] [0] [0] [4] [3] [0] On continue le marquage : On traite d. on a ) , ( ) , ( P d c P d f < , on note donc le sommet P par ) ( d + . a (-c) 7 Capacité b (+S) c (+b) d (+b) S (+) P (+d) e (+b) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [0] [7] [4] [3] [0] [0] [0] [0] [0] [0] [4] [3] [0] Augmentation possible du flot dans la chaîne améliorante : b 10 d S P 3 4 La capacité minimale de la chaîne : 3 On va donc augmenter le flot sur cette chaîne, au maximum, cad jusqu’à la capacité minimale de la chaîne. a (-c) 7 Capacité b (+S) c (+b) d (+b) S (+) P (+d) e (+b) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [3] [7] [4] [3] [0] [0] [3] [0] [0] [0] [4] [3+3] [0] Le flot sur cette chaîne est maintenant : 3 / 3 3 = v f On remarque que le flot est complet dans d b → , cet arc est saturé. a (-c) 7 Capacité b (+S) c (+b) d (+b) S (+) P (+e) e (+b) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [3] [7] [4] [3] [0] [0] [3] [0] [0] [0] [4] [6] [0] Nouveau marquage L’ordre dans lequel on traite les sommets marqués est une file : S, b, c, e, a, d, P a (-c) 7 Capacité b (+S) c (+b) d (+b) S (+) P (+e) e (+b) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [3] [7] [4] [3] [0] [0] [3] [0] [0] [0] [4] [6] [0] Augmentation possible du flot dans la chaîne améliorante : b 7 e S P 3 6 La capacité minimale de la chaîne : 3 On va donc augmenter le flot sur cette chaîne, au maximum, cad jusqu’à la capacité minimale de la chaîne. a (-c) 7 Capacité b (+S) c (+b) d (+b) S (+) P (+e) e (+b) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [3+3] [7] [4] [3] [0] [0] [3] [3] [0] [0] [4] [6] [3] Le flot sur cette chaîne est maintenant : 3 / 4 4 = v f On remarque que le flot est complet dans e b →, cet arc est saturé. a (-c) 7 Capacité b (+S) c (+b) d (+c) S (+) P (+d) e (+d) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [6] [7] [4] [3] [0] [0] [3] [3] [0] [0] [4] [6] [3] Nouveau marquage : L’ordre dans lequel on traite les sommets marqués est une file : S, b, c, d, a, P, e Augmentation possible du flot dans la chaîne améliorante : d 1 b 4 c S P 2 3 La capacité minimale de la chaîne : 1 a (-c) 7 Capacité b (+S) c (+b) d (+c) S (+) P (+d) e (+d) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [6+1] [7] [4] [3] [0] [1] [3] [3] [0] [1] [4] [6+1] [3] Le flot sur cette chaîne est maintenant : 1 / 5 5 = v f On remarque que le flot est complet dans P d → , cet arc est saturé. a (-c) 7 Capacité b (+S) c (+b) d (+c) S (+) P (+e) e (+d) 10 8 3 3 8 4 2 3 4 7 6 4 [] Flot () Marquage [7] [7] [4] [3] [0] [1] [3] [3] [0] [1] [4] [7] [3] Nouveau marquage : L’ordre dans lequel on traite les sommets marqués est une file : S, b, c, d, a, e, P Augmentation possible du flot dans la chaîne améliorante : d 4 b 3 c S e 1 2 3 P La capacité minimale de la chaîne : 1 a (-c) 7 Capacité b (+S) c (+b) d (+c) S (+) P (+e) e (+d) 10 8 3 3 uploads/Marketing/ algorithme-de-ford-fulkerson.pdf