Chapitre

III
Flots

Partie A. Définitions
Soit un graphe dont les arcs sont numérotés de 1 à . Un flot dans
est un vecteur à composantes réelles : Soit la matrice A
la transposée de A est notée AT (idem pour les vecteurs).[][]tel qu'en tout
sommet du graphe la loi de Kirchhoff soit vérifiée :

La composante est appelée la quantité de flux (ou le flux du vecteur et

peut-être assimilée par exemple à la quantité d'électricité (ou de "véhicules")
parcourant l'arc (dans le sens de l'arc si , dans le sens contraire si
). La capacité de l'arc ( ) est la borne supérieure du flux admissible sur
l'arc . Si on munit chaque arc d'un intervalle , un flot
tel que est un flot compatible.

On appelle réseau de transport un graphe dont les arcs sont

numérotés de 1 à et où chaque arc est muni d'un intervalle tel que
:
♦
♦
♦ l'arc est appelé arc de retour entre la sortie et
l'entrée telles que : et [ L'arc 1
est le seul arc incident à a vers l'intérieur et le seul arc incident à b vers
l'extérieur.].
 42 GEOMATIQUE

est appelée la valeur du flot (dans le réseau de transport).

En règle générale, un réseau de transport est un graphe antisymétrique.
On appelle coupe séparant deux sommets et de , un ensemble d'arcs de la
forme : avec , . La capacité de la coupe est :

Notations :
Par la suite, on oubliera la notation vectorielle d'un flot et on
écrira simplement .

Si est la matrice d'incidence sommets arcs du graphe (sans boucles) alors un flot
dans est tel que : du fait de la
conservation aux nœuds.
Si est un réseau de transport alors on le note parfois

Partie B. Recherche d'un flot maximum dans un

réseau de transport

1. Définition
Flot maximum
Un flot maximum (dans un réseau de transport [1]) est un flot compatible de
valeur maximale.
[1 En rajoutant si besoin un arc et en les renumérotant, on arrive toujours à
définir un réseau de transport à partir d'un sous graphe partiel.]

2. Théorème de Ford-Fulkerson
Lemme
soient muni des intervalles , , . Pour tout
flot compatible, on a

Démonstration
Soient , l'arc , , avec ,
. La loi de conservation du flux impose :
 Flots 43

d'où et dans un réseau de transport

car .

Corollaire
si un flot et une coupe sont tels que la valeur du flot est égale à la capacité de la
coupe, alors le flot est un flot maximum et la coupe est de capacité minimale.

Évident

Corollaire
une condition nécessaire et suffisante pour que le problème du flot maximum de à
ait une solution de valeur finie est qu'il n'existe pas de chemin de capacité infinie
entre et

La condition est évidemment nécessaire ; elle est suffisante car s'il n'existe pas de
chemin de capacité infinie entre et , le graphe partiel engendré par les arcs de
capacité infinie ne peut pas être connexe et seuls les arcs de la coupe séparant et ,
contenant l'ensemble des sommets reliés à a par un chemin, sont de capacité finie.
Théorème :
dans un réseau de transport, la valeur maximale d'un flot compatible de l'entrée à la
sortie de est égale à la capacité d'une coupe de capacité minimale séparant et
.

Démonstration :
Soient l'arc ,
compatible maximum, avec , . On colorie l'arc 1 en noir et
les autres arcs comme suit :
♦ est coloré en noir si ;
♦ est coloré en rouge si ;
♦ est coloré en vert si .

Supposons que l'on soit dans le premier cas du "Lemme des arcs colorés de Minty", il
existe alors un cycle noir et rouge passant par 1 avec tous les arcs noirs dans le même
sens. Soit le vecteur associé au cycle passant par 1 dans le sens de 1 alors le cycle
de vecteur associé (avec suffisamment petit) serait compatible et
de valeur supérieure ce qui est impossible car le flot est maximum.
On est donc dans le deuxième cas du "Lemme des arcs colorés de Minty" : il existe un
cocycle noir et vert avec tel que tous les arcs de soient
verts et tous les arcs de soient noirs . On a alors :
44 GEOMATIQUE

Ce qui prouve que la valeur du flot est égale à la capacité de la coupe .

D'après le premier corollaire du lemme précédent, le flot est maximum et la coupe est
minimale.

3. Algorithme de Ford-Fulkerson
Principe de l'algorithme :
On part d'un flot compatible (dans un graphe a capacités entières) [1]. On augmente
de proche en proche la valeur de du flot à maximiser par plusieurs appels à une
procédure de marquage analogue à celle de la démonstration précédente.
[1 Dans un réseau de transport, il y a toujours un flot compatible : le flot nul.]

Initialisation du marquage :
On marque le sommet avec l'indice +1.

Itérations du marquage :
Si est marqué et n'est pas marqué alors :
♦ on marque si ;
♦ on marque si

Arrêt du marquage :
Si on a marqué alors on détermine un flot compatible . Soit un chaîne
allant de à de la forme . On définit le flot par :
♦
♦ si alors ;
♦ si alors ;
♦ dans les autres cas, on pose .

est compatible car on n'a modifié le flot que sur un cycle passant par l'arc 1 (dans le
sens de l'arc 1) et la loi de Kirchhoff est toujours vérifiée. On peut recommencer la
phase de détermination d'un flot en prenant au lieu de .

Si on n'a pas marqué alors le flot est maximum en vertu des résultats précédents.
 Flots 45

Partie C. Recherche d'un flot compatible

Si le graphe n'est pas un réseau de transport, l'existence d'un flot compatible n'est
pas assurée.
Lemme :
une condition nécessaire et suffisante pour l'existence d'un flot compatible est que l'on
ait pour tout cocycle :

Cette condition est nécessaire car si un flot compatible existe alors

.

Montrons qu'elle est suffisante grâce à l'algorithme de [Link] 1967 :

Principe de l'algorithme :
Comme pour l'algorithme de Ford Fulkerson, on va construire un flot à partir d'un
autre flot. On part d'un flot quelconque (peut-être non compatible). On appelle
distance du flux à l'intervalle la valeur :

et on va essayer de diminuer de proche en proche le nombre

(appelé distance du flot aux intervalles)

Initialisation du marquage :
Si , le flot est compatible donc c'est fini. Si , on numérote les arcs
de manière à avoir . On marque le sommet a extrémité finale de
l'arc .

Itérations du marquage : (analogue à celle utilisée précédemment)

Si est marqué et n'est pas marqué alors :
♦ on marque si ;
♦ on marque si
 46 GEOMATIQUE

Arrêt du marquage :
Si on a marqué alors on détermine un flot compatible qui vérifie
comme pour l'algorithme de Ford Fulkerson.
Sinon la condition nécessaire précédente nous indique qu'il n'existe pas de flot
compatible car l'ensemble des sommets marqués vérifie et par
construction :

Partie D. Application à la h-connexité

Théorème de Menger Dirac :
une condition nécessaire et suffisante pour qu'un graphe soit h connexe est que l'on
puisse relier deux sommet et par chemins intérieurement disjoints.

La condition est évidemment suffisante.

Cette condition est nécessaire car si et sont deux sommets non adjacents, on peut
construire un réseau de transport ayant pour entrée et sortie pour lequel un flot de
valeur maximum détermine chemins disjoints de entre et . On symétrise
puis on dédouble chaque sommet
. Tout arc incident
à vers l'intérieur est remplacé par un arc "entrant" de avec une capacité , de
même tout arc incident à vers l'extérieur est remplacé par un arc "sortant" de
avec une capacité . Il suffit alors d'appliquer le théorème de Ford Fulkerson.

Partie E. Application aux couplages

Étant donné un graphe simple, on appelle couplage un ensemble de d'arêtes
tel que deux arêtes quelconques sont non adjacentes. On dit qu'un sommet est
saturé par un couplage si un arc de est incident au sommet. Un couplage
parfait est un couplage qui sature tous les sommets du graphe.
Dans un réseau de transport biparti , on appelle demande en la
valeur : , demande de l'ensemble ,

et on note la quantité maximum de flot que l'on peut

faire entrer dans , c'est-à-dire la valeur maximum du flot pour un réseau de

transport obtenu à partir de en modifiant les capacités comme suit :
 Flots 47

Théorème :
dans un réseau de transport biparti , la valeur maximum dans l'arc 1
d'un flot compatible est :

Démonstration :
On considère un ensemble et on construit un réseau comme indiqué ci
dessus. Le théorème de Ford Fulkerson conduit à .
On peut se restreindre aux ensembles qui contiennent , car sinon on aurait
; en outre, on peut remplacer dans cette relation par sans
rien changer au second membre. Enfin, on peut se restreindre aux ensembles de la
forme , si l'on s'intéresse seulement au minimum. On a donc
.

Si et sont deux ensembles disjoints de sommets, on posera pour simplifier :

.

Considérons un ensemble qui contient la sortie et non l'entrée .

On pose :
On a alors

et
Donc d'après le théorème de Ford Fulkerson :

Théorème de König (1931) :

pour un multi graphe biparti , le nombre maximum d'arêtes d'un couplage
est égal à

Démonstration :
On construit le réseau de transport défini par les points de , ceux de , une entrée
et une sortie ; on joint à tout par un arc de capacité et tout
par un arc de capacité . On joint également
si .

Si , la demande totale de l'ensemble est ; la quantité maximum

48 GEOMATIQUE

de flot qu'on peut faire entrer dans est . Tout flot du réseau
définit un couplage du graphe, les points se correspondant lorsqu'une unité de
flot passe dans l'arc ; inversement tout couplage définit un flot.

La cardinalité maximum d'un couplage est donc égale à la valeur maximum du flot
entre et , c'est-à-dire, d'après le théorème précédent :

Théorème de König Hall (1934) :

pour un multi graphe biparti , on peut coupler et si et seulement si on
a .

Démonstration :
On peut coupler dans si et seulement si on a
d'après le théorème de König cela
équivaut à d'où .