Réseau ( s source, t puits) : s → A ( 5 ) , s → B ( 3 ) , A → B ( 1 ) , A → t ( 4 ) , B → t ( 4 ) . Trouver le flot maximum par chemins augmentants. Identifier une coupe minimum et vérifier flot-max = coupe-min.

Flot maximum dans un réseau

Difficile Inspiré BAC France

Exercice inspiré d'un BAC France

Énoncé et solution adaptés au programme français. Voir crédits.

Énoncé

Réseau ( $s$ source, $t$ puits) : $s \to A (5)$ , $s \to B (3)$ , $A \to B (1)$ , $A \to t (4)$ , $B \to t (4)$ .

Trouver le flot maximum par chemins augmentants.
Identifier une coupe minimum et vérifier flot-max = coupe-min.

Indices

— clique pour révéler

1 Indice 1

Commence par chercher un premier chemin de $s$ vers $t$ qui n'utilise pas encore de capacite, et note le flot maximal que tu peux y faire passer sans depasser aucune capacite d'arete.

2 Indice 2

Cherche ensuite un deuxieme chemin different de $s$ a $t$ qui a encore de la capacite disponible, puis un troisieme si possible, en verifiant a chaque fois que tu ne depasses pas la capacite restante de chaque arete traversee.

3 Indice 3

Pour la coupe minimum, separe les sommets en deux groupes, l'un contenant $s$ et l'autre contenant $t$, et additionne les capacites des aretes qui vont d'un groupe vers l'autre ; essaie plusieurs partitions pour trouver celle qui donne la plus petite somme.

Bloqué sur cet exercice ?

Léo peut t'expliquer pas à pas, en s'adaptant à ton niveau.

Demander à Léo

Exercice Terminé? 🎉

Validez votre réponse pour enregistrer votre progression et gagner des points

Application : réseau de communication et fiabilité Retour au chapitre Coloration de cartes et théorème des 4 couleurs

Flot maximum dans un réseau

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Flot maximum dans un réseau

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Valider votre réponse

Tu as vu 5 exercices aujourd'hui 🎯