Problème de flot

Les flots permettent 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 :

  1. Pour tout arc a ∈ A, 0F(a)c(a)
  2. Pour tout sommet intermédiaire xV \ { 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

Le problème de flot 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.

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

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).

Capacité résiduelle

É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.

residuel

Publicités