Remerciez-le!

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

Flot exercice supplementaire 1

Exercice supplémentaire On considère un réseau d ? adduction d ? eau potable modélisé par le graphe orienté valué G X U C suivant Les arcs correspondent à des conduites d ? eau et les valeurs sur les arcs désignent les capacités en m heure Le n ?ud correspond à une source limitée à m heure et le n ?ud à une station de pompage dans un euve limitée à m heure Les n ?uds et correspondent à villes dont les demandes respectives sont de et m heure A cause de la gravité l ? écoulement entre deux n ?uds se fait dans un seul sens sauf entre les n ?uds et o? une pompe permet si nécessaire de ramener de l ? eau du n ?ud au n ?ud a Déterminer un ot de débit maximal dans ce réseau en expliquant les di ?érentes étapes de la méthode utilisée Le réseau su ?ra-t-il à satisfaire les besoins des villes et b Donner la coupe minimale c Quelles sont les conduites qui doivent être élargies pour augmenter le débit Justi ?er d On crée une conduite du n ?ud au n ?ud de capacité m heure Que devient le ot maximal NB continuer le calcul à partir du ot maximal trouvé en a CCorrigé Pour tenir compte des capacités des sources et et des demandes des villes et on ajoute une super source et un super puits comme le montre le graphe suivant a La solution optimale est donnée par le graphe suivant o? sur chaque arc la première indique la capacité de l ? arc et la deuxième valeur indique la quantité de ot à faire passer à travers cet arc Le graphe d ? écart associé à cette solution est le suivant Le réseau ne su ?ra pas à satisfaire les besoins des villes et puisque le ot maximal est inférieur à la demande totale b La coupe minimale est la suivante XS S c Les conduites à élargir pour augmenter le débit sont et car elles appartiennent à la coupe minimale d La solution optimale devient C C