GRAPHES THÉORIE DES

Flots et tensions

Voici un problème bien formalisé, et pour lequel la formalisation est utile.

Le problème des affectations, des transports, des flots et des tensions révèle sous ses différents noms les multiples facettes d'une même réalité algébrique rencontrée historiquement dans des cadres très différents. Empruntons deux exemples caractéristiques à Claude Berge.

Affectation optimale du personnel (D. Votaw et A. Orden). Considérons p ouvriers a₁, a₂, ..., a_p que l'on veut répartir sur q machines b₁ , ..., b_q. Le rendement de l'ouvrier a_i sur la machine b_j est donné par un nombre kij. Comment affecter les ouvriers aux machines pour maximiser le rendement total ?

Problème des trajets maritimes à vide (B. O. Koopmans). Considérons le trafic des cargos en 1913 : certains ports, comme Lisbonne, San Francisco, Athènes, Yokohama, exportent peu et importent beaucoup ; d'autres ports, tels New York, La Plata, Odessa, Rotterdam, exportent beaucoup et importent peu. Il faudra donc envoyer les cargos à vide le long des lignes maritimes usuelles, de façon à satisfaire les demandes en navires vides de New York, La Plata, etc. Connaissant la longueur l_i de la traversée sur la ligne maritime i, on veut minimiser le coût de ce rapatriement.

La formalisation mathématique de ces problèmes nécessite une série de définitions.

On appelle graphe de transport un graphe orienté où l'on distingue deux sommets, la sortie et l'entrée, et un arc qui les relie. Dans un tel graphe, à tout couple de sommets quelconques (x_i, x_j) liés par un arc, on affecte deux nombres b_ij et c_ij (b_ij ≤ c_ij) appelés capacités inférieure et supérieure de l'arc.

Supposons que les arcs désignent des chemins à sens unique le long desquels on fait circuler des personnes en nombre supérieur à b_ij et inférieur à c_ij, les débits étant conservés en chaque sommet du graphe. Si la capacité supérieure de l'arc qui relie l'entrée à la sortie est infinie et sa capacité inférieure nulle, on se propose de trouver les débits entiers des différents arcs tels que le débit de l'arc s soit maximal (resp. minimal).

Un ensemble de débits satisfaisant à cette question est appelé un flot maximal (resp. flot minimal). On peut munir l'ensemble de ces problèmes de structures algébriques linéaires sur lesquelles on sait raisonner.

Numérotons les arêtes du graphe de 1 à n. À chaque flot on peut associer un n-uple dont les éléments sont les n débits du flot. Ces n-uples constituent le module des flots (cf. algèbre linéaire et multilinéaire).

Si l'on associe à chaque sommet du graphe un entier quelconque, on dit que l'on a muni le graphe d'un potentiel. Ce potentiel induit sur les arcs du graphe un ensemble de tensions. Ces tensions forment un autre module, orthogonal au module des flots.

Une chaîne d'un graphe est une suite de sommets et d'arcs commençant et finissant par un sommet, et telle qu'entre deux sommets consécutifs il y ait un arc allant du premier vers le second ou du second vers le premier. Un cycle est un ensemble de chaînes fermées. Un cocycle est un ensemble d'arcs dont une extrémité est dans un sous-ensemble A de X et l'autre dans le complémentaire de A.

Les modules des flots et tensions vérifient eux-mêmes d'intéressantes propriétés d'orthogonalité avec les vecteurs-cycles et les vecteurs-cocycles. Ces « vecteurs » interprètent, dans le langage du calcul linéaire, les propriétés des cycles et des cocycles. Les propriétés des modules permettent alors de démontrer avec élégance l'existence des flots. Deux définitions supplémentaires sont indispensables à l'expression d'une telle condition nécessaire et suffisante d'existence.

Si ω_A désigne le cocycle de A, on note ω_A⁺ l'ensemble des arcs du cocycle qui ont leur origine dans A, et ω_A⁻ l'ensemble des[...]