Théorie des graphes et algorithmes

On considère un graphe G_o=(X_o,E_o) qui représente le réseau et les arcs orientés sur lesquels de la matière peut être acheminée. L'arc (x,y) et l'arc (y,x) existent tous les deux lorsque la matière peut circuler indifféremment dans un sens ou dans l'autre.

Selon les exemples, on a vu qu'il pouvait exister une ou plusieurs sources par lesquelles la matière peut arriver et un ou plusieurs puits par lesquels la matière peut sortir.

Pour résoudre ce problème, on préfère n'avoir qu'une seule source et qu'un seul puits.

Aussi on ajoute une source unique que l'on désigne par la lettre s et un puits unique que l'on désigne par la lettre t.

On ajoute également des arcs orientés allant de l'unique source s vers l'ensemble des sources et des arcs orientés allant des différents puits vers le puits unique t.

On obtient alors le graphe G=(X,E).

En général, la matière que l'on peut faire circuler sur un arc est limité par des contraintes physiques.

C'est le maximum que peut fournir une source s_i sur l'arc (s,s_i).

C'est le maximum que l'on peut envoyer dans un puits t_j sur l'arc (t,t_j).

C'est le maximum qui peut passer de x vers y pour l'arc (x,y) correspondant à un arc général du réseau.

Dans tous les cas, on note cette capacité C(x,y), sachant qu'elle peut être égale à +∞ lorsqu'il n'y a pas de contrainte de capacité.

Dans tous les exemples présentés, il est évident que les quantités qui circulent sur les arcs sont toutes positives ou nulles.

Dans d'autres exemples plus complexes, il peut arriver que les quantités qui circulent sur les arcs soient supérieures à des capacités minimales. Cela complique peu la modélisation du problème, mais cela rend plus difficile sa résolution.

Nous ne nous intéressons ici qu'à la résolution des problèmes où les capacités inférieures sont toutes nulles.

Les inconnues du problème sont les quantités qui circulent sur tout arc (x,y), on les note F(x,y), où F peut signifier flux ou flot.

Pour tout arc (x,y) de E, on a :

0 ≤ F(x,y) ≤ C(x,y)

Pour tout point x différent de s et de t,

soient z₁, z₂, ... , z_m les m prédécesseurs de x et y₁, y₂, ... , y_q les q successeurs de x,

la contrainte de conservation du flot au point x s'écrit :

F(z₁,x) + F(z₂,x) + ... + F(z_m,x) = F(x,y₁) + F(x,y₂) + ... + F(x,y_q)

Soient y₁, y₂, ... , y_q les q successeurs de la source s,

soient z₁, z₂, ... , z_m les m prédécesseurs du puits t,

soit v la valeur du flot qui entre dans la source,

les contraintes de conservation du flot à travers le graphe conduisent aux équations suivantes :

v = F(s,y₁) + F(s,y₂) + ... + F(s,y_q) = F(z₁,t) + F(z₂,t) + ... + F(z_m,t)

Le flot qui entre dans la source est égal au flot qui sort du puits.