TEST GRAPHE BTS1

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

  Soit A , B , C  les trois sommets d'un graphe orienté G de matrice d'adjacence

 la matrice M ci-dessous:     

  /  1 0      1  \
   M   = |    1 0    0   |
 \   0 1    1  /

  AIDE:  289140.htmRPl   

•  Laquelle des matrice suivantes est la matrice M²  ?  ( Barrer les deux mauvaises matrices . )  

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

            

 

        •  Construire le graphe G.      AIDE:  289140.htmRPl       

               ...............

 

 

• Faire le tableau des prédécesseurs et des successeurs.           

PREDECESSEURS  SOMMETS SUCCESSEURS
              A     
              B      
               C     
 

           •  Combien de chemins de longueur  2 de A à C  y a -t- il ?          ...................  

              Citer ces chemins:            ......................

           • Combien de chemins allant à C et de longueur 2  y a - t- il ?     .................

 

 

             •  On admet que :    AIDE:  289140.htmRPl   

  /        2             2        3      \
  M3    =    |         1             1        2       |
    \        2             1        2      /

  Combien de chemins de longueur 3 y a-t-il ? ....................    ,

  Combien  de chemins de longueur 3  d'origine A et d'extrémité C  y a-t-il ? ,

                   ............................

 

      Citer ces chemins.

 

              ...................................

 

  On choisit au hasard ( avec  équiprobabilité ) un chemein de longueur 3 dans le graphe de G.

    Quelle est la probabilité de l'événement E " Le chemin se termine par A" ?  AIDE:  289140.htmRPl   

               ..........................................

 

 

 

    Quelle est la probabilité de l'événement F " Le chemin est un circuit" ? 

   ( Un circuit étant un chemin qui revient au mêm sommet )    

 

                    ............................

 

              On admet que la matrice booléenne M[2]   est:

  /  1    1  \
M[2]   = |    1 0    1   |
 \   1 1    1  /

     http,289140.htmRP

        Elle est obtenue en remplaçant tous les termes non nuls de M²  par 1.

   Calculer la somme booléenne M' =  M (+)   M[2]    (+) M[3] .          AIDE:  289140.htmRPl   

                                 ......................... 

 

 

 

           Faire le graphe de matrice d'adjacence M'. Que remarquez-vous?    

 

              ...................................