INFO EX 1 GRAPHE

INFO EXERCICE 1 SUR LES GRAPHES ORIENTES          MARS 2009        BTS1

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.  

 Le tableau commence de la façon suivante:

    Première étape:   Comme D est de niveau 0 car sans prédécesseur on barre D dans la colonne

                                des prédécesseurs.

                                Puis comme A et C n'ont plus de sommets dans la colonne des prédécesseurs

                                ils sont déclarés du niveau suivant c-à-d  1.

PREDECESSEURS SOMMETS   NIVEAUX
 On barre D  .    La case est vierge.                        D              A                 1      
                                        A      F           G          B      
 On barre D .   La case est vierge.                        D              C                       1    
Pas de prédecesseur pour D donc niveau 0             D                    0    
                                                                    B             E     
                                                                     C              F     
                                                                A     C                G       

       Seconde étape:        On barre A et C dans la colonne des prédécesseurs.

                                        Alors  les sommets F et G  n'ont plus de sommet dans la colonne des prédécesseurs.

                                        Ils sont donc déclarés du niveau suivant c-à-d  2.

       Troisième étape :     On barre  F et G dans la colonne des prédécesseurs.

                                        Alors  le sommet B  n'a plus de sommet dans la colonne des prédécesseurs.

                                        Il est donc déclaré du niveau suivant c-à-d  3.

         Quatrième étape:    On barre  B  dans la colonne des prédécesseurs.

                                         Alors  le sommet E  n'a plus de sommet dans la colonne des prédécesseurs.

                                         Il est donc déclaré du niveau suivant c-à-d  4.

    On obtient finalement le tableau suivant:

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

  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