1 FLOT COMPATIBLE
Soit G = (X, U ) un graphe connexe et sans boucles.
Soient b : U −→ R ∪ {−∞} et c : U −→ R ∪ {+∞} tels que b(u) ≤ c(u) pour tout arc u ∈ U .
Pour tout arc u, On appelle c(u) (respectivement b(u)) la capacité supérieure (respectivement
inférieure) de l’arc u. Soit M la matrice d’incidence sommets-arcs du graphe G.
Le problème du flot compatible consiste à trouver un vecteur f ∈ Rm tel que
1. f est un flot sur G (en d’autres termes M.f = 0)
2. b(u) ≤ f (u) ≤ c(u) pour tout u ∈ U .
Théorème 1 (Hoffman)
Une condition nécessaire et suffisante pour l’existence d’un flot compatible est que pour tout
P P
A ⊂ X, l’on ait : u∈ω− (A) b(u) ≤ u∈ω+ (A) c(u).
Preuve : La condition est nécessaire, en effet si f est un flot compatible sur G alors pour
tout A ⊂ X :
P P P P
u∈ω − (A) b(u) ≤ u∈ω − (A) f (u) = u∈ω + (A) f (u) ≤ u∈ω + (A) c(u).
Cette condition est aussi suffisante, nous allons le montrer :
Algorithme de recherche d’un flot compatible :
Soit f un flot quelconque surG.
0 si b(u) ≤ f (u) ≤ c(u)
Posons pour tout arc u, d(u) = b(u) − f (u) sif (u) < b(u)
f (u) − c(u) sif (u) > c(u)
P
d(f ) = u∈U d(u)
Le but est d’essayer de diminuer d(f )
Si d(f ) = 0 alors terminer le flot f est compatible
Si d(f ) > 0 alors il existe un arc v tel que f (v) < b(v) ou f (v) > c(v)
Si f (v) < b(v) alors on pose v = ps
Si f (v) > c(v) alors on pose v = sp
1. On marque le sommet s
2. S’il existe x un sommet marqué et y voisin de x non marqué alors on marque y si
– u = xy et f (u) < c(u) ou
– u = yx et f (u) > b(u)
Si l’on parvient à marquer p alors soit C la chaine élémentaire le long de laquelle p a été
marqué en partant de s.
µ = C ∪ {v} est un cycle élémentaire
Posons = min{1 , 2 } avec 1 = minu∈µ+ {c(u) − f (u)} et 1 = minu∈µ− {f (u) − b(u)}
On obtient un nouveau flot f 0 = f + µ qui vérifie d(f 0 ) < d(f )
1
Si l’on ne peut pas marquer p alors terminer, il n’existe pas de flot compatible (le problème
n’a pas de solution).
En effet, soit Y l’ensemble des sommets marqués. Dans ce cas, s ∈ Y et p ∈ /Y
−
– Si f (v) < b(v), v ∈ ω (Y )
– Soit u = yx ∈ ω − (Y ) − {v}. x est marqué et y non marqué donc f (u) ≤ b(u).
– Soit u = xy ∈ ω + (Y ), x est marqué et y non marqué donc f (u) ≥ c(u).
Donc
P P P P P
c(u) ≤ f (u) = f (u) = f (u) + f (v) < b(u)
u∈ω + (Y ) u∈ω + (Y ) u∈ω − (Y ) u∈ω − (Y )−{v} u∈ω − (Y )
Le cocycle ω(Y ) ne vérifie pas la condition nécessaire du théorème donc il n’existe pas
de flot compatible.
– Si f (v) > c(v), v ∈ ω + (Y )
on obtient les mêmes conclusions que le cas précédent.
2 TENSION COMPATIBLE
Soit G = (X, U ) un graphe connexe et sans boucles.
Soient b : U −→ R ∪ {−∞} et c : U −→ R ∪ {+∞} tels que b(u) ≤ c(u) pour tout arc u ∈ U .
Le problème de la tension compatible consiste à trouver un vecteur t ∈ Rm tel que
1. t est une tension G
2. b(u) ≤ t(u) ≤ c(u) pour tout u ∈ U .
Théorème 2 (Ghouila-Houri)
Une condition nécessaire et suffisante pour l’existence d’une tension compatible est que pour
P P
tout cycle µ, l’on ait : b(u) ≤ c(u).
u∈µ− u∈µ+
Preuve : La condition est nécessaire, en effet si t est une tension compatible sur G alors
pour tout cycle µ :
P P P P
b(u) ≤ t(u) = t(u) ≤ c(u).
u∈µ− u∈µ− u∈µ+ u∈µ+
Cette condition est aussi suffisante, nous allons le montrer :
Algorithme de recherche d’une tension compatible :
Soit t une tension quelconquesur G.
0 si b(u) ≤ t(u) ≤ c(u)
Posons pour tout arc u, d(u) = b(u) − t(u) sit(u) < b(u)
t(u) − c(u) sit(u) > c(u)
P
d(f ) = u∈U d(u)
1. – Si d(t) = 0 alors terminer la tension t est compatible.
– Si d(t) > 0 alors il existe un arc v tel que t(v) < b(v) ou t(v) > c(v)
2
– Si t(v) < b(v) alors on pose v = sp
– Si t(v) > c(v) alors on pose v = ps
On marque le sommet s, puis on applique la procédure suivante :
2. S’il existe un sommet x marqué et y voisin de x non marqué alors on marque y si
– u = xy et t(u) ≥ c(u) ou
– u = yx et t(u) ≤ b(u)
3. Si l’on parvient à marquer p alors terminer, G ne possède pas de tension compatible.
4. Sinon, soit Y l’ensemble des sommets marqués.
Posons = min{1 , 2 } avec 1 = minu∈ω+ (Y ) {c(u) − t(u)} et 1 = minu∈ω− (Y ) {t(u) − b(u)}
On obtient une nouvelle tension t0 = t + ω(Y ) qui vérifie d(t0 ) < d(t).
On retourne à (1).
Si on sort au pas (3), c’est à dire que le sommet p est marqué alors soit C la chaine qui a
permis son marquage en partant de s.
1er Cas t(v) > c(v) donc v = ps. On pose µ = C ∪ {v} et on a v ∈ µ+
– un arc u = xy ∈ C + , x et y sont marqués donc t(u) ≥ c(u)
– un arc u = xy ∈ C − , x et y sont marqués donc t(u) ≤ b(u)
On obtient
P P P P P P
b(u) ≥ t(u) = t(u) = t(u)+t(v) ≥ c(u)+t(v) > c(u)+c(v) =
u∈µ− u∈µ− u∈µ + u∈C + u∈C + u∈C +
P
c(u)
u∈µ+
Le cycle µ ne vérifie pas la condition nécessaire du théorème, donc G ne possède pas de
tension compatible.
2ème Cas t(v) < b(v) donc v = sp et en utilisant le même raisonnement que le cas précédent,
on aboutit à la même conclusion.
