INFO EX GRAPHE

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         0   1     0     1
B        0    0    0    0
C    1     0     0    1
D   0     0    0     0   

            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  =        

  /  0    1       0     1    \   
 |    0    0    0     0       |    
 |   1    0        0         1       |   
  \  0    0    0      0    /  
                   Calculer:           M² =

 /  0      0    0    0    \   
|   0    0   0    0      |    
|   0     1   0    1      |   
 \  0    0    0    0    /  

                     Calculer:     M3   =

 /    0     0   0    0    \   
|      0    0   0    0     |    
|     0   0   0        0    |   
 \    0    0    0    0     /  

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

   PREDECESSEURS   SOMMETS    SUCCESSEURS
  C            A    B     D
  A          B    
            C   A    D
  A    C           D   

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

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

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

   Y a-t-il un chemin de longueur 2  de B à D ?         NON       car  dans la matrice  M²

         ct-dessus  il y a     0       à l'intersection de la ligne de B avec la colonne de  D.

     Par contre il y a un chemin de longueur  2 de C à D  car il a un   1   

      à l'inersection de la ligne de C avec la colonne de D.  Ce chemin est :   C A 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        0   0   0   0
B       0   0   0   0  
C   0   0   0   0
D   0   0   0    0

 Y a-t-il un chemin de longueur 3  de B à D ?     NON     car  il y a un  0       

 

     à l'intersection de la ligne de B avec la colonne de D.

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