EXERCICE SUR LES GRAPHES
EXERCICE
Le tableau ci-dessous est extrait d'une grille présentant les différents points d'une ville reliés par
des lignes de transport en commun avec la durée des trajets en minutes .
A ce tableau est associé un graphe dont les sommets sont A , B , C , D , F et G .
→ | A | B | C | D | E | F | G |
A | 8 | 3 | |||||
B | 4 | ||||||
C | 6 | 4 | |||||
D | 10 | 9 | |||||
E | |||||||
F | 3 | ||||||
G | 7 |
Par exemple, dans le tableau, la cellule contenant le nombre 9 correspond à la durée ( 9 minutes)
du trajet du bus reliant le point de départ D au point d'arrivée C.
1.Réaliser le tableau des prédécesseurs de ce graphe, et déterminer le niveau de chacun des sommets.
PREDECESSEURS | SOMMETS | NIVEAUX |
A | ||
B | ||
C | ||
D | ||
E | ||
F | ||
G |
2. Dessiner le graphe en ordonnant les sommets par niveaux .
3. Marquer la longueur de chaque arc.
4. Déterminer le ou les trajets de durée minimale permettant d'aller de D à E.
( On détaillera la méthode utilisée.)
------------------------------------------------------------------------------------------------------------------
1. Donons le tableau des prédécesseurs et des niveaux.
• Quand on a un arc ( A,B) on dit que A est un prédécesseur de B et que
B est un successeur de A.
Il n'y a donc aucune difficulté à remplir la première colonne du tableau.
• Pour les niveaux on procède de la façon suivante:
( Il faut que le graphe n'ai ni boucle ni circuit).
Première étape: D est de niveau 0 car sans prédécesseur.
On barre alors D partout dans la colonne des prédécesseurs.
Seconde étape:
Dans la colonne des prédécesseurs deux nouvelles cases sont vides.
Pour les sommets A et C il n'y a plus rien dans la colonne des prédécesseurs
A et C sont déclarés alors de niveau suivant c-à-d 1.
On barre alors tous les A et C dans la colonne des prédécesseurs.
Troisième étape :
Dans la colonne des prédécesseurs deux nouvelles cases sont vides.
Pour les sommets F et G il n'y a plus rien dans la colonne des prédécesseurs
F et G sont déclarés alors de niveau suivant c-à-d 2.
On barre alors tous les F et G dans la colonne des prédécesseurs.
Quatrième étape:
Dans la colonne des prédécesseurs une nouvelle case est vide.
Pour le sommet B il n'y a plus rien dans la colonne des prédécesseurs.
B est déclaré alors de niveau suivant c-à-d 3.
On barre alors B dans la colonne des prédécesseurs.
Cinqième étape :
Dans la colonne des prédécesseurs une nouvelle case est vide.
Pour le sommet E il n'y a plus rien dans la colonne des prédécesseurs.
E est déclaré alors de niveau suivant c-à-d 4.
Le processus s'arrête puisque tous les sommets ont un niveau déterminé.
PREDECESSEUR | SOMMETS | NIVEAUX |
D |
A | 1 |
A F G | B | 3 |
D | C | 1 |
D | 0 | |
B | E | 4 |
C | F | 2 |
A C | G | 2 |
2. Dessiner le graphe en ordonnant les sommets par niveaux.
Les sommets de même niveau sont mis sur une même verticale.
On commence par le niveau 0 puis niveau 1 , etc
3. Marquer la longueur de chaque arc.
Il suffit de lire le tableau des durées qui est donné dans l'énoncé.
4. Déterminer le ou les trajets de durée minimale permettant d'aller de D à E.
( On détaillera la méthode utilisée.)
• Méthode empirique.
On fait un inventaire:
DCFBE : 9 + 6 + 3 + 4 = 22 minutes
DCGBE : 9 + 4 + 7 + 4 = 24 minutes
DAGBE : 10 + 3 + 7 + 4 = 24 minutes
DABE : 10 + 8 + 4 = 22 minutes
Conclusion: Il y a deux trajets de D à E de durée minimale: 22 minutes
DCFBE et DABE
•Méthode de Moore-Dijstra.
Alors à reculons:
E ← B( 22) ← F( 18 ) ← C( 15 ) ← D( 9) ← D
ou " " ← A(18) ←D(10) ← D
c-à-d D C F B E
ou
DABE
Finalement: On trouve les deux chemins de longueur minimale.
------------------------------------------------------------------------------------------------------------------------------------------