Remerciez-le!

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

Problème du Flot Dans ce chapitre, le graphe est supposé orienté. I) Position d

Problème du Flot Dans ce chapitre, le graphe est supposé orienté. I) Position du problème : Soit G=(X,U) un graphe et l’application c : U R+ U {+∞} u c(u) capacité de l’arc u Soient S et P deux sommets et ur = (PS) appelé arc de retour. Le problème de recherche d’un flot maximum de S à P dans R =(X, U, c), revient à chercher un vecteur f ∈ Rm+1 (m = |U|) tel que : i) f est un flot sur R U {ur } ii) f(u) ≤ c( u) ∀ u ∈ U iii) f(ur) maximum Si A est la matrice d’incidence aux arcs associée à G, alors: A*f = 0 (F) f ≤ c f ≥ 0 f(ur ) = Z (Max) Exemple 1: 1 5 f(Sa) + f(Sb) – f(ur) = 0 f(ab) + f((aP) – f(Sa) = 0 2 f(bP) – f((Sb) – f(ab) = 0 f(ur) – f(bP) – f(aP) = 0 4 3 f(Sa) ≤ 1 f ≥ 0 f(Sb) ≤ 4 f(ab) ≤ 2 ur f(aP) ≤ 5 f(bP) ≤ 3 f(ur) = Z(Max) II) Algorithme Ford Fulkerson (FF) : 1) Principe de l’algorithme : Initialisation : f(u) = 0 ∀ u ∈ U L’algorithme se base sur deux idées: 1ère idée : chemin augmentant de S à P : (le réel à côté de chaque arc est sa capacité) S a b P S 4 a 7 b 3 c 5 d 2 e 9 P 6 4 8 5 f g ur C 1 = (S, a, b, c, d, e, P) ε = 2 C 2 = (S, f, c, d, g, P) ε = 3 Application: l’exemple 1 1er chemin: (S, a, b, P); ε = 1; f(ur) = 1 2ème chemin: (S, b, P); ε = 2; f(ur) = 3 2ème idée : chaîne augmentante de S à P : (on a porté à côté de chaque arc u, le couple (f(u),c(u)) S (1,5) a (4, 7) b (3, 8) c (0, 4) d (2, 2) e (6, 10) P ur C + = {(Sa), (ab), (cd), (eP)} ε1 = Min(5-1, 7-4, 4-0, 10-6) = 3 C - ={(cb), (ed)} ε2 = Min(3, 2) = 2 ε = 2 Application: l’exemple 1 C+ = {(Sb), (bP)} ε1 = Min(5-0, 4-2) = 2 C- ={(ab)} ε2 = 1 ε = 1 ; f(ur) = 4 Algorithme FLOTMAX (données : X, U, I, T, ur , s, p, c; résultats : f, Y) f(u) : = 0 pour tout u ∈ U Itérer MARQUAGE (X, U, I, T, ur , s, p, c, f ; Y, A, ε) Arrêt : p ∉ Y x : = p ; C + : = {ur} ; C - : = Ø Tantque x ≠ s faire u : = A(x) si x = T(u) alors C + : = C + U {u} ; x : = I(u) Sinon /* dans ce cas, x = I(u) */ C - : = C - U {u} ; x : = T(u) Finsi Fintantque f(u) + ε si u ∈ C + f(u) : = f(u) - ε si u ∈ C - f(u) si u ∉ C + U C - Finitérer Finalgo Algorithme MARQUAGE (données : X, U, I, T, ur , s, p, c, f ; résultats : Y, A, ε) /* MARK est une variable logique qui vaut FAUX lorsqu’on ne peut plus marquer de nouveaux sommets*/ Y : = {s} ; MARK : = VRAI Tant que p ∉ Y et MARK faire Si il existe u = (xy) avec x ∈ Y, y ∉ Y et f(u) < c(u) alors /* cette étape est appelée « marquage direct ». L’arc u, s’il appartient à la chaîne décelée de s à p sera dans C +. Le flot sur u augmentera */ Y : = Y U {y} ; A (y) : = u ; δ(y) : = Min [δ(x) ; c(u) – f(u)] Sinon si il existe u = (yx) avec x ∈ Y, y ∉ Y et f(u) > 0 alors /* cette étape est appelée « marquage indirect ». L’arc u, s’il appartient à la chaîne décelée de s à p sera dans C -. Le flot sur u diminuera */ Y : = Y U {y} ; A (y) : = u ; δ(y) : = Min [δ(x) ; f(u)] Sinon MARK : = FAUX Finsi Finsi Fintantque Si MARK alors ε : = δ(p) finsi Finalgo Nature Marquage Avant marquage Après marquage Marquage Direct x* y f(u) < c(u) x* y* u ∈ C + Marquage Indirect x* y f(u) > 0 x* y* u ∈ C - Remarque : Si à l’itération i, f est un flot, alors à l’itération i+1, f est un flot aussi. f := f + ε γc (γc est le vecteur représentatif relatif au cycle C U {ur}) 2) Théorème de la coupe minimum Définition : Un ensemble d’arcs C C C C est appelé coupe séparant P de S, s’il existe Y⊂ X tel que C C C C = Ω+(Y). La capacité de C C C C est par définition : c(C C C C ) = ∑c(u) u ∈C C C C Théorème 1 : (de la coupe minimum ) Pour toute coupe C C C C séparant P de S et pour tout flot réalisable f sur R U { ur } , on a : c(C C C C ) ≤ f(ur). Théorème 2 : Au terme de l’application de l’algorithme FF, le flot courant sur ur est maximum. Algorithme FLOTMAX (données : X, U, I, T, ur , s, p, c; résultats : f, Y) f(u) : = 0 pour tout u ∈ U Itérer MARQUAGE (X, U, I, T, ur , s, p, c, f ; Y, A, ε) Arrêt : p ∉ Y x : = p ; C + : = {ur} ; C - : = Ø Tantque x ≠ s faire u : = A (x) si x = T(u) alors C + : = C + U {u} ; x : = I(u) Sinon /* dans ce cas, x = I(u) */ C - : = C - U {u} ; x : = T(u) Finsi Fintantque f(u) + ε si u ∈ C + f(u) : = f(u) - ε si u ∈ C - f(u) si u ∉ C + U C - Finitérer Finalgo Algorithme MARQUAGE (données : X, U, I, T, ur , s, p, c, f ; résultats : Y, A, ε) /* MARK est une variable logique qui vaut FAUX lorsqu’on ne peut plus marquer de nouveaux sommets*/ Y : = {s} ; MARK : = VRAI Tant que p ∉ Y et MARK faire Si il existe u = (xy) avec x ∈ Y, y ∉ Y et f(u) < c(u) alors /* cette étape est appelée « marquage direct ». L’arc u, s’il appartient à la chaîne décelée de s à p sera dans C +. Le flot sur u augmentera */ Y : = Y U {y} ; A (y) : = u ; δ(y) : = Min [δ(x) ; c(u) – f(u)] Sinon si il existe u = (yx) avec x ∈ Y, y ∉ Y et f(u) > 0 alors /* cette étape est appelée « marquage indirect ». L’arc u, s’il appartient à la chaîne décelée de s à p sera dans C -. Le flot sur u diminuera */ Y : = Y U {y} ; A (y) : = u ; δ(y) : = Min [δ(x) ; f(u)] Sinon MARK : = FAUX Finsi Finsi Fintantque Si MARK alors ε : = δ(p) finsi Finalgo 3) Flots canalisés Soit G=(X,U) un graphe. Considérons les deux applications suivantes : c : U R U {+∞} b : U R U {- ∞} u c(u) u b(u) tel que : b(u) ≤ c(u) ∀ u ∈ U Si S et P sont deux sommets et ur = (PS), le problème de recherche d’un flot maximum de S à P dans R =(X, U, c), revient à chercher un vecteur f ∈ R m+1 (m = |U|) tel que : i) f est un flot sur R U {ur } ii) b(u) ≤ f(u) ≤ c( u) ∀ u ∈ U iii) f(ur) maximum Procédure de marquage : Nature Marquage Avant marquage Après marquage Marquage Direct x* y f(u) < c(u) x* y* u ∈ C + Marquage Indirect x* y f(u) > b(u) x* y* u ∈ C - Algorithme FLOTMAXGENERAL (données : X, U, I, T, ur, s, p, b, c; résultats : Y, MODIF, FLOTBORNE) /* lorsque cette procédure est appelée, f est supposée être solution réalisable du problème de flot canalisé ; MODIF est une variable logique qui vaut VRAI ssi l’appel à cet algorithme conduit à un changement de flot ; FLOTBORNE est une variable logique qui uploads/Philosophie/ probleme-du-flot.pdf