Chapitre 9 Problèmes de flots
9.1. FLOTS – DEFINTION
9.1.1. Flots
Soit un graphe
donné par ses sommets
et ses arcs
On appelle flot dans ce graphe un vecteur
tel que :
1) toute composante est un nombre entier que l'on appelle flux dans l'arc
2) la loi de Kirchhoff (loi aux nœuds) est vérifiée en tout sommet , c'est-à-dire que : si
représente l'ensemble des arcs incidents intérieurement à
(ayant
comme
extrémité terminale) et
l'ensemble des arcs incidents extérieurement à (ayant
comme extrémité initiale), on a :
9.1.2. Réseaux de transport
Pour relier la notion de flot à des phénomènes réels, il convient auparavant de définir ce
que l'on entend par réseau de transport.
Un réseau de transport est un
sans boucle où à chaque arc est associé un
nombre entier
(que l'on appellera capacité de l'arc ) et où :
1) il existe un sommet
et un seul tel que
( n'a pas de précédent) qu'on
appellera entrée du réseau.
2) il existe un sommet et un seul tel que
( n'a pas de suivant) qu'on
appellera sortie de réseau.
À un réseau de transport est donc associé le type de représentation suivant :
La notion de flots peut être associée, on le voit, à de multiples problèmes qui consistent à
faire passer des quantités de matières sur les arcs d'un réseau de transport tout en
essayant de faire respecter au mieux certains critères. Remarquons qu'elle est aussi très
utilisée dans d'autres disciplines que la recherche opérationnelle (hydraulique et
électricité par exemple).
Nous allons examiner le problème essentiel relatif à cette notion : celui du flot maximal.