Skip to content

Flot

Objectifs

  • Définir le problème du flot maximum
  • Appliquer l'algorithme de Ford-Fulkerson
  • Définir une coupe dans un réseau de flot
  • Connaître le théorème flot-max/coupe-min
  • Trouver la coupe minimum d'un réseau de flot

Cours

Appuyez sur F pour passer en plein écran.
Version plein écran ou imprimable.

Exercices

Exercice : Ford-Fulkerson

Appliquer l'algorithme de Ford-Fulkerson et trouver la coupe minimum sur les graphes suivants :

Correction

Flot maximum : 5 + 5 + 5 = 15

Coupe minimum : {S, U, V} / {T} ou {S} / {T, U, V}

Correction

Flot maximum : 2 + 3 + 2 = 7

Coupe minimum : {S, A} / {B, C, D, T} ou {S} / {A, B, C, D, T}

Sources