TD 6 : flot maximal

Exercice 36 : Écrire un algorithme décidant si un flot d'un réseau est maximal dans ce réseau.

fonction is_maximal(G=(V,E,c,s,t):réseau, M:flot):booléen
    f = FordFulkerson(G=(V,E,c,s,t))
    si valeur(f) = valeur(M)
        retourne Vrai
    sinon
        retourne Faux

Plus directement, un flot $M$ est maximal si et seulement s'il n'existe pas de chemin améliorant de $s$ à $t$ dans le graphe résiduel $G_M$ : un seul parcours (en largeur ou en profondeur) de $G_M$ depuis $s$ suffit, en $O(|V| + |E|)$.

Exercice 37 : Démontrer que tout réseau à capacités entières admet un flot maximal qui associe à tout arc une valeur entière.

On applique l'algorithme de Ford-Fulkerson en partant du flot nul, qui est entier. Par récurrence sur le nombre d'itérations : si le flot courant est entier, les capacités du graphe résiduel sont entières (différences d'entiers), donc la capacité résiduelle d'un chemin améliorant (minimum de ces capacités) est un entier strictement positif. Le flot augmenté reste donc entier sur chaque arc.

La valeur du flot augmente d'au moins 1 à chaque itération et est bornée par la capacité d'une coupe : l'algorithme termine. À la terminaison, il n'existe plus de chemin améliorant, donc le flot obtenu est maximal (théorème flot maximal / coupe minimale), et il associe à tout arc une valeur entière.