Notion de réseau

On appelle réseau un graphe sur lequel on va faire transiter un flot. Soit $G=(X,E)$ un graphe orienté avec $\vert X\vert=n$ et $\vert E\vert=m$. Chaque arc est doté de deux grandeurs positives ou nulles, $l$ et $u$, respectivement dénommées capacité minimale et capacité maximale et telles que :

$$\forall (\ivj) \: \in \: G \qquad 0 \leqslant l_{ij} \leqslant u_{ij}$$

Chaque nud est doté d'une contribution au flot $b(i)$. On appelle source tout sommet $i$ créant du flot, c'est à dire, tel que $b(i)>0$ et puits tout sommet $i,\; b(i)<0$ où le flot est `` consommé ''. Un flot sur le réseau $G$ est un vecteur $x \in \mathbb{R}^m$, indicé sur les arcs, tel que :

$$l_{ij} \leqslant x_{ij} \leqslant u_{ij}$$ (5.1)

$$\sum\limits_{k : (j,k) \in G} x_{jk} \;- \sum\limits_{i : (\ivj) \in G} x_{ij} = b(j) \quad \forall \: j \: \in \: X$$ (5.2)

1. La condition (5.1) spécifie que le flot est borné inférieurement et supérieurement par les capacités des arcs.
2. L'équation (5.2), qui n'est pas sans rappeler la première loi de Kirchoff (ou loi des nuds) en électricité, traduit la conservation du flot en chaque sommet du réseau. En effet, de façon plus littéraire, on peut la traduire par la phrase suivante :

   La quantité de flot sortant d'un sommet moins la quantité de flot entrant dans le même sommet est égale à la contribution de ce sommet.

Bien entendu, pour que le problème ait une solution, la somme des contributions doit être égale à 0, soit :

$$\sum\limits_{i \in X} b(i)=0$$

Exprimé ainsi, on voit immédiatement que les problèmes de flot permettent de modéliser directement les problèmes réels d'écoulement d'un liquide dans un ensemble de canalisations (le flot est alors le débit de liquide dans chaque tuyau) ou de circulation du courant électrique dans un réseau, le flot étant ici égal à l'intensité de courant passant dans un fil. La figure suivante illustre un réseau et un flot réalisable sur celui-ci. Les triplets figurant au dessus des arcs sont de la forme $(l,\,u,\,x)$.

Figure 5.1: Exemple de réseau portant un flot