INFO TEST

 INFO TEST

  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  /

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

       C'est la troisième.

 /     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.                     RETOUR     http://www.mathemaths.com/rubrique,test-graphe-bts1,289113.html  

          

  

 

 

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

         

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

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

              Citer ces chemins:          AAC                       ACC

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

                   2+ 1+ 1 = 4

             Il suffit de sommer les termes de la colonne de C  dans la matrice M².

              

             •  On admet que :                        http://www.mathemaths.com/rubrique,test-graphe-bts1,289113.html  

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

            • • Combien de chemins de longueur 3  y a-t-il ?  SEIZE

                   2 + 2 + 3 + 1 +1 + 2 + 2 + 1 + 2    = 16       Somme des termes de la matrice  M3         

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

                          3 

               • • Citer ces chemins.

                            AAAC                   ACCC             AACC

                             

    • • On choisit au hasard ( avec équiprobabilité ) un chemin de longueur 3

                     dans le graphe G .              http://www.mathemaths.com/rubrique,test-graphe-bts1,289113.html  

       • • •  Quelle est la probabilité de l'événement E " Le chemin se termine par A " ?

                     Soit Ω l'univers ds possibles. Il contient les 16 chemins de longueur 3.

                    Card( Ω ) = 16

                     E est l'ensemble des chemins de longueurs 3 qui se terminent par A.

                    Card( E ) = 2 + 1 + 2 = 5

                    Il suffit d'ajouter les termes de la première colonne de  M3  . 

                    Comme P( E ) = Card( E ) / Card( Ω  )     on a :

                    Conclusion :  P( E ) = 5 / 16

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

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

                      F est l'ensemble des circuits de longueur 3.

                      Card( F ) =2 + 1 + 3 = 5

                      Il suffit d'ajouter les termes de la diagonale principale de la matrice  M3  . 

                      Comme P( F ) = Card( F ) / Card( Ω  )   on a :

                    Conclusion : P( F ) = 5 / 16

      • On admet que l'on a la matrice booléenne  :        RETOUR   289113.htmRPl  

      

  /  1 1      1  \
   M[2]    = |    1 0    1    |
 \   1 1    1  /
                 obtenue à partir de la matrice M²  , en remplaçant les termes non nuls par 1.

               •  •   Calculer la somme booléenne suivante :  M ' = M (+)  M[2]    (+)  M[3]    .

 /  1 0  1   \  / 1 1 1   \  / 1 1  1  \
M (+)  M[2]    (+)  M[3] = |   1 0  0    | (+) |  1 0 1    | (+) |  1 1  1   |
 \  0 1  1   /  \ 1 1 1   /  \ 1 1  1   /

                On obtient :

  /  1   1       1  \
   M '   = |     1   1      1    |
 \   1   1    1  /

             •  • Faire le graphe de matrice d'adjacence M'. Que remarque-t-on ?

 

  On a les 4 raccourcis.                                       RETOUR   289113.htmRPl  

 On remarque M' est la matrice d'adjacence de la fermeture transitive de G.