Accueil du site > MOCA > Flot maximal sur un réseau de transport
Aller à ...
OMFG
Informations
Dans la rubrique MOCA , cet article a été écrit par b3nj et publié le 6 avril 2006.
11626 personnes ont affiché cette page et sa popularité est de 100.
Pebkac
Mots clefs
I see dead pixels.
Outils
SYN
Flot maximal sur un réseau de transport

Définitions

1. Réseau de transport

Un réseau de transport est un graphe G=<X,U> dans lequel les deux conditions suivantes sont respectées :

  • Il existe deux sommets uniques :
    • Le sommet source S tel que \Gamma^{-1}_{S} = \oslash
    • Le sommet puits T tes que \Gamma_{S} = \oslash
  • Chaque arc doit être muni d’un nombre C_u \geq 0 appelé capacité de l’arc [1]

Exemple

PNG - 12.4 ko
Exemple de réseau de transport

2. Flot dans un réseau de transport

Soit G=<X,U> un réseau de transport, et G_{0}=<X, U^{0}> un graphe déduit de G avec un arc du sommet puits vers le sommet source.

Exemple

PNG - 13.9 ko
Exemple de réseau de transport avec arc retour

\varphi' = [ \varphi_{0}, \varphi_{1}, \varphi_{2}, \ldots, \varphi_{m} ] est un flot sur G^{0} si et seulement si :

  1. La somme des flots sortants est égale à la somme des flots entrants [2] \sum\limits_{u \in \omega^{+}(i)} \varphi{u} = \sum\limits_{u \in \omega^{-}(i)} \varphi{u}
  2. Aux sommets S et T la somme des flots sortants sur S est égale à la somme des flots entrants sur T : \sum\limits_{u \in \omega^{+}(i)} \varphi{u} = \sum\limits_{u \in \omega^{-}(i)} \varphi{u} avec \varphi_{u} = \varphi_{0}\qquad [3]

Exemple

PNG - 15.1 ko
Exemple de réseau de transport avec arc retour et flots

\varphi' = [ \varphi_{0}, \varphi_{1}, \ldots, \varphi_{8}] = [9,3,6,0,3,3,3,3,6]

\varphi' est un flot sur G^{0} car il respecte les règles.

Faire les exercices Exercice 14 et Exercice 15

pages : 1 2 3 4 >>

[1] Noté entre crochets sur les graphes
[2] Cette propriété doit être vérifiée pour chaque sommet de G^{0} exception faite des sommets S et T
[3] Phi u est le flot sur l’arc retour

Poster un message