c(x,y)
On supposera que la source et la destination ne sont pas limitées en ce qui concerne la "production" et la "consommation". La limite du système entier est constituée par la capacité des arcs à transporter le "liquide".
On définit une fonction de capacité c(x,y) où x et y sont des sommets du réseau comme :
| c(x,y)= | { | valeur de l'arc reliant x et y |
| 0 si aucun arc de x à ys |
On définit une fonction d'écoulement (ou flux) f(a,b) comme :
| f(a,b)= | { | 0 si pas d'arc entre a et b ou si pas d'écoulement |
| quantité de liquide s'écoulant de a vers b |
On aura donc :
f(x,y)
Soit v la quantité de liquide qui s'écoule de la source S vers la destination T, alors la quantité totale de liquide quittant S est égale à la quantité totale de liquide atteignant T, c'est-à-dire
f(S,x) = v
=f(x,T)
x
sommets
xsommets
Cela signifie qu'aucun autre sommet que S ne peut produire de liquide et qu'aucun sommet autre que T ne peut absorber de liquide.
donc :f(x,y)
=f(y,x)
x
S,T
ysommets
ysommets
On peut écrire ces relations en définissant des fonctions "entrée" et "sortie" pour chaque sommet du réseau comme:
sortie (S) = entrée (T) = v
entrée (x) = sortie (x)
Plusieurs fonctions d'écoulement peuvent exister pour un réseau don né.
12.2.
Représentation d'un réseau
Site Hosting: Bronco
Table des
matières.