Chapitre 6: Flots

Comment calculer le flot ?

Un flot dans un réseau de flot G = (V, A,c) est une fonction f :V ×V → R satisfaisant les deux propriétés suivantes : 1. contrainte de capacité : ∀ u,v ∈V : 0 ≤ f (u,v) ≤ c(u,v); 2. conservation des flots : ∀ u ∈V \\{s,t} : ∑v∈V f (v,u) = ∑v∈V f (u,v).