Problèmes de flots
199
Formellement, on peut écrire le problème du flot maximal ainsi : posons, pour simplifier
et
si l'arc
n'existe pas. Nous appellerons maintenant
le flux sur
l'arc reliant
on doit avoir :
et pour respecter la loi des noeuds :
m
a
x
i
i
j
i
n
j
....
1
=
1
=
n
b
x
j
j
j
i
m
i
....
1
=
1
=
Par ailleurs, il s'agit de maximiser sous ces contraintes la quantité :
1,0
= n
z
x
(flux sur l'arc de retour
)
On voit donc que l'on a affaire ici à un programme linéaire, mais qui risque d'être très
lourd à résoudre : en effet, si le réseau possède 20 sommets de part et d'autre par
exemple, le programme linéaire portera sur
inconnus et aura
contraintes. Or, un réseau de cette dimension est petit comparé à la majorité
de ceux que l'on traite dans les applications courantes. On peut évidemment le simplifier
en ne prenant qu'une variable - flux par arc existant, ce que nous n'avons pas fait pour
simplifier les notations, mais de toute façon, l'algorithme du simplexe est beaucoup trop
pénible pour ce type de problèmes, et nous allons donner une méthode de résolution plus
élégante : l'algorithme de Ford-Fulkerson.
Auparavant, mettons en évidence un certain nombre de résultats qui nous seront utiles.
a) Définition d'un cocycle.
Considérons un graphe orienté
Soit A un sous-ensemble de , on appellera
l'ensemble des arcs ayant leur extrémité initiale dans
et leur extrémité
terminale hors de . De même
sera l'ensemble des arcs ayant leur extrémité
initiale hors de A et leur extrémité terminale dans A. L'ensemble d'arcs
sera appelé un cocycle du graphe
Les arcs
seront dits orientés dans le sens « sortie ». Les arcs
seront
dits orientés dans le sens « entrée ».
A
A
)
(A
u
)
(A
u