Flot maximum
Le flot maximum de modéliser une très large classe de problèmes. Leur interprétation correspond à la circulation de flux physiques sur un réseau : distribution électrique, réseau d’adduction, acheminement de paquets sur Internet, etc. Il s’agit d’acheminer la plus grande quantité possible de matière entre une source s et une destination t.
Définition d’un réseau
Un réseau est un graphe orienté N=(V,A) avec une valuation positive de ses arcs. La valuation c(x,y) d’un arc (x,y) est appelée la capacité de l’arc. N possède deux sommets particuliers : une source s et une destination t. Les autres sommets sont appelés nœuds intermédiaires.
Un flot représente l’acheminement d’un flux de matières depuis une source s vers une destination t. Le flot est ainsi décrit par la quantité de matière transitant sur chacun des arcs du réseau. Cette quantité doit être inférieure à la capacité de l’arc, qui limite ainsi le flux pouvant transiter par lui. De plus il n’est pas possible de stocker ou de produire de la matière aux nœud intermédiaires : un flot vérifie localement une loi de conservation analogue aux lois de Kirchhoff en électricité.
Un flot F sur un réseau N est une valuation positive des arcs qui vérifie les deux propriétés suivantes :
- Pour tout arc a ∈ A, 0 ≤ F(a)≤c(a)
- Pour tout sommet intermédiaire x∈V \ { s,t }, ∑y F(y,x) = ∑y F(x,y)
La somme F–(x) =∑yF(y,x) est le flot entrant au sommet x
La somme F+(x) =∑yF(x,y) est le flot sortant du sommet x
La valeur | F | d’un flot F est définie comme le flot sortant moins le flot entrant en s : | F | = F+(s) – F–(s).
Problème du flot maximum
Le problème de flot maximum classique est un problème linéaire. Nous supposons que le réseau possède des arêtes entre tout couple de sommets. S’il n’y a pas de capacité, elle est fixée à 0. La fonction objectif est la somme des flots sortant de la source ou entrant dans le puits. La fonction objectif peut varier en fonction de l’objectif.
Les contraintes de base sont identiques quelle que soit la fonction objectif :
- Contraintes de capacité : f(u,v) ≤ c(u,v)
- Symétrie : f(u,v) = – f(v,u)
- Conservation de flots : la somme des flots entrants est égale à la somme des flots sortants sauf pour la source et le puits, on appelle le degré d(u) la différence entre le flot sortant et entrant du sommet u : d(u)=0 sauf pour u=s et u=t.
- autres
Beaucoup de problèmes peuvent être rapporté à un problème de flot maximum. Un algorithme naïf consiste à répéter le processus suivant jusqu’à ce que vous soyez bloqué. Trouver un chemin s-t où chaque arc a f(e)<u(e) et augmenter le débit le long du chemin par le minimum de u(e)-f(e). Cette méthode ne donne pas une valeur optimale, nous devons être en mesure de revenir en arrière.
Réduction de problèmes
Problème du flot multi-source multi-puits : une source fictive est reliée à toutes les sources, la capacité des arêtes dépend de divers critères (capacité des sommets, contraintes flot entrant-flot sortant). Les puits sont reliés à un puits fictif. Ce type de problème est généralement un problème de couplage.
Problème de flot avec capacité aux sommets : les sommets sont dupliqué en sommet entrant et sommet sortant avec un arc les reliant. La capacité de cet arc est égale à la capacité du sommet.
Problème du plus court chemin : la source est l’origine du chemin et le puits avec d(s)=1 et d(t)=-1. Il n’y a pas de contraintes de capacité. Le coût de passage dans tous les arcs est de 1. Nous recherchons le flot à cout minimal.
Coupe d’un réseau et capacité résiduelle
Une coupe (E,T) d’un réseau de transport N=(V,A) est une partition de V en E et T=V-E telle que s ∈E et t∈T. On définit la capacité c(E,T) de la coupe la somme des capacités des arcs (u,v) avec u dans E et v dans T. Pour toute coupe (E,T) et tout flot f, |f| est majorée par la capacité de la coupe c(E,T).
Supprimer un ensemble d’arêtes pour déconnecter t de s. Trouver un ensemble pour minimiser la somme des capacités des arcs. Une coupe min est une partition de noeuds (S, T) telle que s est dans S et t dans T où c(E,T) est minimal. Par définition, le problème de min-cut a le même résultat qu’un problème de flot maximum.
Étant donné un réseau N=(V,A) et un flot f sur N, on appelle capacité résiduelle cf (u,v) = c(u,v) – f(u,v). De plus, si la capacité de (v,u) est nulle, cf (v,u) = f(u,v). La capacité résiduelle est toujours positive ou nulle.
Le graphe résiduel est le réseau N’=(V,A) avec les capacités résiduelles pour chaque arc de A. Un chemin augmentant est un chemin entre s et t dans le graphe résiduel.
A partir du graphe résiduel d’un flot max, il est possible de trouver la solution du problème min-cut (et vice versa). Dans le graphe suivant, si vous recherchez un ensemble de sommets connectés à partir du sommet s, vous trouvez l’ensemble {s,3,4,7} qui est l’ensemble S pour le problème de min-cut.
Trouver un flot augmentant
Trouver un chemin s-t dans le graphe résiduel, il est appelé chemin augmentant. Une fois le chemin sélectionné, augmentez le débit le long des arcs dans la même direction que le graphe standard, diminuez le débit le long des arcs allant dans le sens arrière.
FR 
EN 
ES