Vidéo (5 min): Idées clefs sur l'optimalité de l'algorithme de Ford et Fulkerson


Cette vidéo suppose que vous avez déjà fait un effort de lecture du polycopié et notamment des définitions de réseaux de flot, flot, graphe résiduel, chemin augmentants, coupe.

Essayons de comprendre pourquoi l'algorithme de Ford-Fulkerson termine avec un flot maximum. Autrement dit, pourquoi l'absence de chemin de s à t dans le graphe résiduel final garantit l'optimalité du flot.

 

La vidéo ci-dessus présente les idées clefs, voilà une rédaction formelle de la preuve:

Notation

Etant donné un réseau de flot G=(V,A)  et un flot f, on notera f^{out}(u) pour tout sommet u \in V la quantité de flot totale sortant de u. Plus précisément:

f^{out}(u) = \sum\limits_{v | (u,v) \in A} f(u,v)

De façon similaire, on notera  f^{in}(u) la quantité de flot totale entrant dans u c'est à dire:

f^{in}(u) = \sum\limits_{v | (v,u) \in A} f(v,u) 

 

Optimalité de l'algorithme de Ford et Fulkerson

Proposition: Si f est un flot tel qu'il n'y a plus de chemin augmentant dans G_f (le graphe résiduel pour f) alors il existe une coupe (S^*,T^*) telle que v(f) = c(S^*,T^*) (on dira que (S^*,T^*) est une coupe minimale de G).

Preuve: Identifions la coupe (S^*,T^*). On définit S^* comme l'ensemble des noeuds atteignables depuis s dans G_f et T^* = V - S^*. C'est bien une coupe (partition de V et s \in S^*, t \in T^*). Observons les arcs qui traversent une telle coupe:

  1. Les arcs e=(u,v) tels que u \in S^* et v \in T^* sont saturés i.e f(e) = c_e (sinon e serait un arc en avant dans G_f et on aurait v \in S^*)
  2. Les arcs e'=(u',v') tels que u' \in T^* et v' \in S^* ne portent pas de flot i.e f(e') = 0 (sinon (v',u') serait un arc en arrière dans G_f et on aurait u' \in S^*) .

Donc tous les arcs de S^* vers T^* sont saturés de flot et les arcs de retour de T^* vers S^* ne portent pas de flot.

Notons de plus que v(f) = f^{out}(s) ce qu'on peut aussi écrire v(f) = \sum\limits_{u \in S^*} (f^{out}(u) - f^{in}(u)) car par conservation du flot tous les termes autres que u = s sont nuls et il n'y a pas de flot entrant dans s (f^{in}(s) = 0). On peut ré-écrire cette somme en faisant la sommation sur les arcs cette fois et en éliminant les arcs apparaissant à la fois avec un signe + et un signe -:

v(f) = \sum_{u \in S^*} (f^{out}(u) - f^{in}(u)) = \sum\limits_{e=(u,v) \in A | u \in S^* \textrm{ et } v \in T^*} f(e) - \sum\limits_{e=(u,v) \in A | u \in T^* \textrm{ et } v \in S^*} f(e)


Or on vient de voir que les arcs de T^* vers S^* ne portent pas de flot donc :

v(f) = \sum\limits_{e=(u,v) \in A | u \in S^* \textrm{ et } v \in T^*} f(e)


Comme les arcs de S^* vers T^* sont saturés de flot, on obtient bien:


v(f) = \sum\limits_{(u,v) \in A| u \in S^* \textrm{ et } v \in T^*} c_e = c(S^*,T^*)

 

Contacts: Nicolas Catusse et Hadrien Cambazard

Last modified: Thursday, 12 September 2019, 9:49 AM