INFO EX III SUR LES GRAPHES

  INFO EX III SUR LES GRAPHES

 

EXERCICE EPREUVE    SUR LES GRAPHES        BTS    AVRIL 09

  EXERCICE       6 POINTS

        Partie A.

                       Dans l'ensemble des matrices  carrées d'ordre 3 on pose :                

 /  0   1  1  \

 /  1   0  0   \
A = |   0   1   0    | et I = |   0   1 0     |

 \  1   1  1  /

 \  0   0  1  /

                 On rappelle que :   A2   = A × A          A3   =   A2 × A     

                                   A4  =  A3    × A     

                   1. Calculer les produits matriciels     A2       et    A3   .

 

 / 1   2  1  \

 /  1   4  2   \
A²  = |   0   1   0    | et A3    = |   0   1 0     |

 \  1   3  2  /

 \ 2   6  3  /

                    2. Vérifier que :   A3   =  2 A²   - I.

                    Simple vérification.

           Partie B

                   Soit (G ) le graphe à trois sommets;   A , B , C .

                  1. Dessiner G.

                   2. Quelle est l'interprétation de 19  dans la matrice :

 

        /     3         
  12 5      \
A5     =   |      0  
  1   
0          |

       \    5           
  19   8      /

                       Il y a 19 chemins de longueur 5 allant de C à B.

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

                                longueur 5 dans le graphe de G

                                Quelles sont les probabilités des événements suivants:

                                C1 : "Le chemin se termine par A ".

                                C2 : " Le chemin commence par C et se termine par A ".

                                C3: " Le chemin est un circuit"

                                (On pourra arrondir les résultats au centième près )

                    L'univers des possibles Ω est l'ensemble des chemins de longueur  5.

                    Il y en a 53.    Donc Card( Ω) = 53.

                  (    53 est la somme de tous les termes de la matrice  )    

       Card( C1 ) = 3 + 0 + 5 =    8  

       Card( C2 ) =    5  

       Card( C3 ) =  3 +  1 + 8 = 12  (  Somme des termes de la diagonale principale )

            •   P(C1) = Card(C1 ) / Card( Ω)

                P( C1 ) = 8 / 53

              •   P(C2) = Card(C2 ) / Card( Ω)

                  P( C2 ) = 5 / 53

           •   P(C3) = Card(C ) / Card( Ω)

                P( C3 ) = 12 / 53

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