EX SUR LES GRAPHES

NOM: .....                        PRENOM:  ..............      DATE: Mars 09               CLASSE:  BTS1      

   INTRODUCTION SUR LES GRAPHES.      

          

              Sur la figure ci-contre se trouvent des points ABCD appelés sommets du graphe G.

             Des arcs orientés relient certains de ces sommets.

             1.Travail d'inventaire:

                 Compléter le tableau à double entrée qui indique les arcs en mettant 1

                 si l'arc existe  et en mettant 0 si l'arc n'existe pas.               

Départ      \     Arrivée      A        B            C           D         
A                 
B                 
C                 
D                 

            2. Soit M la matrice formée par les colonnes du tableau précédent.

                 (  On parle de matrice M d'adjacence du graphe G ou adjacente au graphe G . )

                         Donner :         M  =

        

 /                      \   
|                   |    
|                       |   
 \                   /  

                  Calculer:           M² =

 /                      \   
|                   |    
|                       |   
 \                   /  

                     Calculer:     M3   =

 /                      \   
|                   |    
|                       |   
 \                   /  

              3. Compléter le tableau des successeurs et des prédécesseurs.

   PREDECESSEURS   SOMMETS    SUCCESSEURS
   A     
   B    
   C   
   D   

              4. Remplir le tableau suivant avec les termes de la matrice M².

                ( La longueur d'un chemin est le nombre d'arcs orientés qui le compose.)

              Il indique le nombre de chemins de longueur 2 d'un sommet à un autre.

Départ      \     Arrivée      A        B            C           D         
A              
B              
C          
D           

   Y a-t-il un chemin de longueur 2  de B à D ? ...................          

   Y a-t-il un chemin de longueur 2  de C à D ? ...................                

 5.Remplir le tableau suivant avec les termes de la matrice M3.               

        Il indique le nombre de chemins de longueur 3 d'un sommet à un autre.

Départ      \     Arrivée      A        B            C           D         
A             
B            
C         
D         

 Y a-t-il un chemin de longueur 3  de B à D ? ...................      

 

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