INFO EX2 TEST BTS1 B 11 février 2015

INFO    TEST   Graphes    février 2015   BTS1 

Exercice 2                  6 points
Au cours d’un stage, un étudiant en BTS SIO a développé un jeu

pour téléphone portable.Le jeu comprend quatre étapes, notées A, B, C, D.

Le joueur commence à l’étape A puis, selon l’indice découvert, passe

à une autre étape. Les possibilités de passage d’une étape à l’autre

sont données par le graphe orienté G ci-contre, dont les
sommets A, B, C, D modélisent les étapes, et les
flèches les possibilités de passage d’une étape à                 
une autre.
                 Eeweer54                                  
                                                                      
1. Donner la matrice d’adjacence M de ce graphe orienté, en considérant les
    quatre sommets A, B, C, D dans cet ordre.

        REPONSE:

          On a:

        Conclusion:

                Ewwe45 
2. On donne:

               /   0 1 0 1     \
             /     0 0 0 0      \
 M2    =   \     0 0 0 1      /
               \   0 0 0 0     /

a. Citer tous les chemins de longueur 2.

           REPONSE:

         Dans la matrice M2 la somme des coefficients est : 1 + 1 + 1 = 3

         Il y a donc trois chemins de longueur 2:

         Conclusion:

               ACB

               ABD

               CBD 
b. Déterminer la matrice M4    ;
    cette matrice peut être obtenue à la calculatrice.
    Interpréter le résultat dans le contexte du jeu.

     REPONSE:

       On a :   M4 =  0

         Conclusion :     M4    est la matrice nulle

      Il n'existe pas de chmin de longueur 4.

         Donc:

       Conclusion: dans le jeu il n'est pas possible     

     de faire 4 passages d'une étape à l'autre. 

3. Existe-t-il un chemin hamiltonien ? Si oui, le donner.

        Conclusion:

       ACBD est un chemin hamiltonien

  (  Il passe par tous les sommets une et une seule fois )

4. On note M[n]  la n-ième puissance booléenne
   de la matrice M, et ⊕ l’addition booléenne de deux matrices.

   a. Déterminer la matrice M′  = M ⊕M[2]⊕M[3]⊕M[4].

       REPONSE:

     Ici    M[2] =  M2   

             M[4]   = M4 = 0

        et 

 Wweer4987

    Donc:       M[3]    =  M3   

      On obtient:

     M′  = M ⊕M[2]⊕M[3]⊕M[4]

           Conclusion:

          Ewwww4378 1

 b. Donner la représentation géométrique du graphe G′
     dont la matrice d’adjacence est M′.

       REPONSE:

              Il y a juste un raccourcis.

                   Eeweer541
c. Interpréter dans le contexte du jeu la dernière ligne de la matrice M′.

            REPONSE:

          Il n'a pas de chemin partant de D quelque soit sa longueur.

           Le joueur ne peut pas partir de l'étape D

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