Cours sur les problèmes de flots

Chapitre 7Probl`emes de flots.7.1 Exemple.Un r´eseau electrique est form´e de lignes reliant des noeuds (transformateurs, centrede redistributions,...), chaque ligne a une capacit´e de transport maximale. On veut fairepasser une quantit´e de courant maximale entre le lieu de production (la source, suppos´eeunique) et le lieu de consommation (la cible, aussi suppos´ee unique).7.2 Notions de base sur les graphes– Un graphe orient´e G=(V,E) est form´e d’un ensemble de sommets V ={x ,...,x }1 net d’un ensemble d’arcs E ={1,2,...}. L’arc k reliant x `a x est aussi not´e (x ,x ).i j i j– un chemin est une suite x ,x ,...,x tel que (x ,x )∈ E pour i = 1,...,p−1.1 2 p i i+1– unechaineestunesuitex ,x ,...,x telque(x ,x )∈ E (arcavant)ou(x ,x )∈1 2 p i i+1 i+1 iE (arc arri`ere) pour i = 1,...,p−1.– Succ´esseurs de x∈ V c’est l’ensemble Suc(x) ={y | (x,y)∈ E}.– Pr´edecesseurs de x∈ V c’est l’ensemble Pred(x) ={y | (y,x)∈ E}.– A tout arc k (ou (x,y)) on associe sa capacit´e c (ou c(x,y)) un nombre > 0.kOn consid`erera uniquement des graphes tels que :1. il existe un sommet source s (c.a.d. que Pred(s) =∅).2. il existe un sommet cible t (c.a.d. que Suc(t) =∅).3. il existe un chemin de s `a t (sinon le probl`eme de flot n’a pas de solution).166`2 CHAPITRE 7. PROBLEMES DE FLOTS.7.3 Flots et coupe7.3.1 FlotUn flot f de valeur v est une fonction qui `a chaque arc (x,y) associe une valeur f(x,y)telle que :∀x∈ V,x = s,t Σ f(z,x) = Σ f(x,y)z∈Pred(x) y∈Suc(x)v = Σ ...