EX GRAPHE 1

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.)