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


This page is not in its usual appearance because WIMS is unable to recognize your web browser.
In order to access WIMS services, you need a browser supporting forms. In order to test the browser you are using, please type the word wims here: and press ``Enter''.

Please take note that WIMS pages are interactively generated; they are not ordinary HTML files. They must be used interactively ONLINE. It is useless for you to gather them through a robot program.