OEF Réseaux et flots --- Introduction ---

Ce module regroupe pour l'instant 10 exercices sur les flots (définitions, flots complets).

Approvisionnement (modélisation)

Une société organise le transport de céréales des villes vers les villes .

La disponibilité en tonnes des villes est de

Les besoins en tonnes des villes sont de

Le tableau suivant donne les capacités de transport, en tonnes, entre les villes :

 
 

On désire modéliser le problème. Pour cela, on introduit un graphe valué avec des capacités. Quelles capacités doit-on mettre sur chaque arête ?

Approvisionnement (résolution)

Une société organise le transport de céréales des villes vers les villes .

La disponibilité en tonnes des villes est de

Les besoins en tonnes des villes sont de

Le tableau suivant donne les capacités de transport, en tonnes, entre les villes :

 
 

On a modélisé le problème par le graphe valué avec capacités suivantes. Déterminer les quantités à transporter de chaque ville d'origine vers chaque ville d'arrivée pour satisfaire au mieux la demande totale.

 
 

Saturation d'une chaîne

Voici un flot de à dans un graphe muni de capacités :

Arc
Flot
Capacité

Cliquer sur les chaînes qui ne sont pas des chemins :

.

On se demande si le flot peut être amélioré en utilisant . Pour cela, on calcule pour chacun des arcs la capacité résiduelle :

Peut-on améliorer le flot à l'aide de ? si oui, de combien ? sinon répondre 0.

Saturation d'un chemin

Voici un flot de à dans un graphe muni de capacités :

Arc
Flot
Capacité

Cliquer sur les chemins du graphe :

.

On se demande si le flot peut être amélioré en utilisant . Pour cela, on calcule pour chacun des arcs la capacité résiduelle :

Peut-on améliorer le flot à l'aide de ? si oui, de combien ? sinon répondre 0.

Construire un flot complet

Le dessin suivant représente un graphe muni de capacités. A vous de construire un flot complet en partant du flot nul. La méthode utilisée ici est de saturer tous les arcs allant de à . La liste de tels arcs est la suivante :

Arc
Flot
Capacité

L'arc Les arcs , a été saturé. ont été saturés. Il reste encore à examiner les arcs Il ne reste plus que l'arc à examiner.

L'arc est-il saturé ?

Répondre oui ou non. Saturez l'arc en donnant les nouvelles valeurs du flot :

Rendre complet un flot donné

Le dessin suivant représente un flot muni de capacités. Il n'est peut-être pas complet. A vous de le rendre complet. La méthode utilisée ici est de saturer tous les arcs allant de à . La liste de tels arcs est la suivante :

Arc
Flot
Capacité

L'arc Les arcs , a été saturé. ont été saturés. Il reste encore à examiner les arcs Il ne reste plus que l'arc à examiner.

L'arc est-il saturé ?

Répondre oui ou non. Saturez l'arc en donnant les nouvelles valeurs du flot :

Coupure d'un flot

Calculer la capacité de la coupure leftbrace1 rightbrace1 du flot valué de à représenté ci-dessous :

Arc
Flot
Capacité

Flot maximal et coupure

Le flot de à représenté ci-dessous est complet (saturé) pour les capacités indiquées :

Arc
Flot
Capacité

Sa valeur est de .

La capacité minimale des coupures est obtenue pour la coupure suivante (indiquer le sous-ensemble choisi contenant ) et vaut .

La valeur du flot maximal possible est de et le flot représenté

Définition d'un flot

Le dessin suivant représente un flot de à de valeur

à condition de bien compléter les valeurs manquantes :

Arc
Flot
Capacité

Valeur d'un flot

Le dessin suivant représente un flot de à .

à condition de bien compléter le tableau suivant :

Arc
Flot
Capacité

La valeur du flot est . The most recent version

Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.