NOM; ............ PRENOM: .............. DATE: Mars 09 CLASSE: BTS1 GRAPHE
EXERCICE 1 6 POINTS
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 et en marquant la longueur de chaque arc.
3. Déterminer le ou les trajets de durée minimale permettant d'aller de D à E.
( On détaillera la méthode utilisée.)