208
Recherche opérationnelle
Cette fois-ci, on ne peut plus marquer le sommet . On a donc obtenu le flot optimal,
avec un flot arrivant en égal à . En isolant les sommets marqués des sommets non
marqués, on fait apparaître la coupe de capacité minimale (cf. figure 5), qui est
constituée par les arcs
,
, . On vérifie que les arcs sortants sont saturés et que les
arcs entrants
et
portent un flot nul.
On démontre facilement que la complexité de l'algorithme de Ford-Fulkerson est du type
étant le nombre d'arcs et
la capacité maximale des arcs du
réseau. En ce sens, on n'a pas affaire à strictement parler à un algorithme polynomial,
puisque la complexité ne dépend pas de la taille du problème (spécifiée par
) mais
également d'une donnée du problème, heureusement entière. On dit que l'on a affaire à
un algorithme pseudo-polynomial. Il existe cela dit d'autres algorithmes voisins
polynomiaux.
9.3. PROBLEME DU FLOT COMPATIBLE
Soit maintenant un réseau
avec des contraintes de capacité différentes de celles
prises en charge auparavant, c'est-à-dire qu'on affecte à présent deux nombres entiers
positifs ou nuls
et
à chaque arc , et on impose aux flots
sur le
graphe
d'avoir toutes ses composantes
sur les arcs telles que
)
(
)
(
)
(
u
c
u
u
b
Ce type de contrainte intervient par exemple lorsqu'on doit impérativement satisfaire
certaines demandes. On peut sur ce type de graphe résoudre le problème du flot
maximal, mais l'initialisation de l'algorithme de Ford-Fulkerson ne se fait pas aussi
facilement qu'auparavant : il faut trouver un flot compatible avec les contraintes ciA
B
C
D
E
F
G
H
J
I
K
2
1
0
1
4
5
4
0
0
5
6
5
2
3
1
2
4
0
0
+A
+C
+A
+B
+B
+E
+F
+F
Sommets marqués
Sommets non marqués
COUPE