Flots

Question 1

Qu’est-ce qu’un flot ?.

Answer 1

Soit un graphe G(X,U) donné par ses sommets {1,2…,n} et
ses arcs {u1,u2…, um}, un flot est l’ensemble Φ des flux {Φ1,Φ2,…Φn} dans chacun des arcs. Φi est une valeur entière et tous les flux respectent la loi des « nœuds » (la somme des flux arrivant à un sommet est égale à la somme des flux qui en partent).

Question 2

Comment représenter un réseau de transport ?

Answer 2

Un réseau de transport est un 1-graphe sans boucle, avec une entrée et une sortie, où chaque arc u est associé à un nombre entier c(u) ≥ 0 (sa capacité)

Question 3

Comment appliquer l’algorithme de Ford-Fulkerson ?

Answer 3

• Si i marqué et Φ(uij)≤C(uij) on marque j
• Si j marqué et Φ(uij)>0) on marque i
• Si on trouve un cycle de sommets marqués on peut améliorer le flot en augmentant le flot sur les arcs parcourus dans le sens Entrée-Sortie et en diminuant le flot sur les arcs parcourus dans le sens contraire, et
  cela d’une même quantité. On retourne alors en 2.
• Sinon, le flot est maximal

Question 4

Quelle relation existe-t-il entre la capacité d’un graphe et une coupe de capacité maximale ?

Answer 4

La valeur maximale d’un flot de S (sortie) à E (entrée) dans un graphe G(X,U) muni de capacité c(u) est égale à la capacité d’une coupe de capacité minimale