EX 1 TEST BTS1 B 11 février 2015

            TEST    BTS1 B     mercredi 11 février 2015  Polynésie  

EXERCICE 1   (  donné à la session de mai 2014     7 POINTS )

Un amateur a publié un site internet avec 5 pages, notées P1, P2, P3, P4 et P5.
La page d’accueil du site est la page P1.
Chaque page contient des liens permettant de naviguer vers d’autres pages,
Pour améliorer la navigation sur son site, il demande conseil à un informaticien, qui
modélise le site par un graphe.

Les 5 sommets S1, S2, S3, S4 et S5 de ce graphe représentent les 5 pages,
Un lien d’une page vers une autre est représenté par un arc orienté allant du sommet
associé à la page de départ vers celui associé à la page d’arrivée,
Le tableau des successeurs obtenu par l’informaticien est le suivant :

Sommets  S1 S2  S3  S4  S5
Successeurs S2, S3, S5 S3  S2  S3  S1, S2, S4

 


1. a. Déterminer la matrice d’adjacence M de ce graphe.

    b. Donner une représentation géométrique de ce graphe orienté.

2. Existe-t-il un chemin hamiltonien dans ce graphe ?

     ( c-à-d passant par tous les sommets une seule fois) 

    Si oui, en indiquer un.

3. Calculer la matrice M2.
4. a. Combien existe-t-il de chemins de longueur 2 dans le graphe ?
    b. Combien existe-t-il de chemins de longueur 2 issus du sommet S1 ?
5. On rappelle que la matrice M′  de fermeture transitive du graphe est donnée
    par l’addition booléenne :      M′ = M ⊕M[2]⊕M[3]⊕M[4]⊕M[5].
    On admet que

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

a. Quelles sont les pages du site qui sont accessibles depuis toutes les autres
    pages en quelques clics ? Justifier.
b. Interpréter les 0 de la première colonne de la matrice M′
    dans le contexte de l’énoncé.

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