Scribd
Importer
419 vues2 pages

Optimisation des Réseaux de Graphes

Le document présente cinq exercices sur la théorie des graphes. Les exercices portent sur la recherche de plans d'installation, d'arbres de coût minimal, de plus courts chemins et l'application de l'algorithme de Ford.

Transféré par

Ahmed Mahjoub
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
419 vues2 pages

Optimisation des Réseaux de Graphes

Le document présente cinq exercices sur la théorie des graphes. Les exercices portent sur la recherche de plans d'installation, d'arbres de coût minimal, de plus courts chemins et l'application de l'algorithme de Ford.

Transféré par

Ahmed Mahjoub
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Théorie deS grapheS Série n:03

Exercice 01:

Un projet d'installation de conduits d'eau alimentant les localités: A, B, C, D, E, F est


représenté par le graphe G=(X,U) suivant. Les valeurs portées sur les arêtes représentent la longueur
des conduits utilisés pour l'installation.
2
3 B C 2

A 1 2 4 D
1 4
3 F E

Donner un plan d'installation minimisant la longueur totale des conduits d'eau utilisés?

Exercice 02:
On considère le graphe G=(X,U) dont les valeurs des arcs représentent des coûts.
4
3 A
E
2
B 4 3 3
2
2 C D

Déterminer un arbre de coût minimal?

Exercice 03:
Pour un voyage de la ville A à la ville G, on considère la matrice suivante donnant les liaisons
possibles entre ces villes ainsi que la durée de chaque voyage en heurs.

A B C D E F G
A - 1 3 - - - -
B - - 1 2 2 - -
C - - - 1 1 - -
D - - - - - 9 -
E - - - - - - 3
F - - - - 3 - 4
G - - - - - - -

1) Représenter sous forme de graphe ordonné les différentes liaisons existant entre ces villes.
2) Déterminer une solution permettant d'aller de A à G pour une durée de voyage minimum. Si on
démarre de A à 9h du matin, à quelle heure on arrivera à G sachant que le temps d'attente entre
deux voles est de 15 minutes.

1
Théorie deS grapheS Série n:03

Exercice 04:

Considérons le réseau de transport R=(X,U,d) suivant, dont les évaluations des arcs
représentent le coût de transport entre deux sommets.
2
B D 4
2
2
H 4
A
3
E I
C 1
5
G 1

2
1 F
1) Quel est l'algorithme à appliquer pour déterminer le chemin le moins coûteux pour aller de A à I?
2) Déterminer un plan de transport permettant de minimiser le coût total de transport.

Exercice 05:
Appliquer l'algorithme général de Ford au graphe ci-dessous, pour définir une arborescence des
plus courts chemins, issue de s.
7
2 ** 5
2 x4
** x1 1
3
s ** 5 4 9
5 ** x6 5
**3 x2 10
3 4 **2
x3 x8
7
7 **
** 4 x7 3
7
x5 3

Vous aimerez peut-être aussi