EXERCICE SUR LES GRAPHES

                                     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   

                                    Grapheetchmini23

   3. Marquer  la longueur de chaque arc.

           Il suffit de lire le tableau des durées qui est donné dans l'énoncé.

                                Grapheetchmini2

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.

  Tbmoore 3

                 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.

                                           Grapheetchmini234

 ------------------------------------------------------------------------------------------------------------------------------------------