Graphe - Exercice Flot Maximal

Exercice 36: Ecrire 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=FordFulkeson(G=(V,E,c,s,t))
    si f=M
        retourne Vrai
    sinon
        retourne Faux

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

En entrée, les capacités sont entières et on considère un chemin élémentaire de s à t et le flot maximal à travers ce chemin. Ce flot maximal a une valeur entière. Quand on construit le graphe résiduel correspondant, les capacités sont entières.