Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cor exercice s 6 Le problème du ot maximal ?? Exercices -corrigé I Déterminer sur le réseau suivant reprendre le graphe sur l'énoncé On procède successivement aux marquages suivants d'autres suites sont possibles ici on prend systématiquement le premier s

Le problème du ot maximal ?? Exercices -corrigé I Déterminer sur le réseau suivant reprendre le graphe sur l'énoncé On procède successivement aux marquages suivants d'autres suites sont possibles ici on prend systématiquement le premier sommet susceptible d'être marqué Première itération de l'algorithme de Ford Fulkerson Procédure de marquage s a b e- car le ux sur e b est c f p p est marqué Modi ?cation du ot arc a b - arc e b on peut donc envoyer un ot de valeur le long de la cha? ne s a b e c f p le ux augmente de sur tous les arcs sauf sur e b o? il diminue de La valeur du ot passe à a b c - s d e- ? p f g h i u Deuxième itération Procédure de marquage s a b on ne peut aller plus loin on repart de s On marque alors g h d- e c f p p est marqué Modi ?cation du ot arc e c - arc d h on peut donc envoyer un ot de le long de la cha? ne s g h d e c f p le ux augmente de sur tous les arcs sauf sur d h o? il diminue de La valeur du ot passe à Le problème du ot maximal exercices corrigé p Ca b c - - s d p e f - g h i u Troisième itération Procédure de marquage s a b puis à nouveau à partir de s g h d- e maximal on ne peut rien marquer d'autres le ot est ? ? a b c - - s d p e f - ? g h i u L'ensemble des sommets marqués est s a b d e g h La coupe associée est constituée des arcs dont l'origine est marquée et l'extrémité non marquée b c e c e f h f h i La capacité de cette coupe est Ceci con ?rme que le ot précédent est optimal Le problème du ot maximal exercices corrigé p CII Une ra ?nerie de pétrole a On complète le graphe par une supersource s et les arcs s S s S s S que l'on munit d'une capacité supérieure égale à la quantité qui peut être délivrée par chacun des puits La conservation des ux aux sommets S S S permet de limiter ce qui part de chacun des puits à ce qu'ils peuvent fournir S T S s T T R ra ?nerie p T S T Actuellement il arrive une quantité de à la ra ?nerie Pour voir si cette quantité est maximale on recherche s'il existe une cha? ne améliorante qui permettrait d'augmenter la valeur du ot Marquage s S S S - T T T p Le long de cette cha? ne on peut envoyer un ot de la limitation est due à l'arc T T S T S s - T T T R ra