Calcul du débit maximal pour les réseaux

Question

pouvons-nous trouver un algorithme qui calcule (en temps linéaire) le débit maximum pour les réseaux arborescents, c'est-à-dire pour les réseaux tels que la suppression du puits (et de ses bords associés) laisse un arbre.

Answer 1

Ford-Fulkerson est O (E * f) où E est le nombre d'arêtes et f le flux maximum, ce qui serait considéré comme linéaire si vous avez une borne supérieure constante sur E ou f dans votre problème.

Answer 2

Oui, lancez simplement quelque chose comme ce qui suit:

maxf(s) { 
    if (s == sink) return s.in_capacity; 
    ret = 0; 
    foreach(c in children(s)) ret += maxf(c); 
    return min(ret, s.in_capacity); 
} 

Utilisez un premier appel avec s égal à la source (nous supposons que la source a une in_capacity de l'infini).