EX 2 TEST BTS1 B 11 février 2015

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.
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.
b. Déterminer la matrice M4    ;
    cette matrice peut être obtenue à la calculatrice.
   Interpréter le résultat dans le contexte du jeu.
3. Existe-t-il un chemin hamiltonien ? Si oui, le donner.
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].
   b. Donner la représentation géométrique du graphe G′
     dont la matrice d’adjacence est M′.
c. Interpréter dans le contexte du jeu la dernière ligne de la matrice M′.

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