INFO EX1 TEST BTS1 B 11 février 2015

  INFO EX1    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é.

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

REPONSE:

1.a.Donnons la matrice adjacente M.

                   Mte

b. Représentation du graphe orienté.

Ewsde45 2

2. OUI. ll y a un chemin qui passe une seule fois par tous les sommets.

    Par exemple:  S1  S5  S4  S3  S2

    est un chemin hamiltonien

3. On a :

          Wee1ea4

4.a. Le nombre de chemins de longueur 2 dans le graphe est

         la somme des termes de M2.  

           1+2+1+1+1+1+1+1+3+1= 13

       Conclusion: Il y a 13 chemins de longueur 2

  b. Le nombre de chemins de longueur 2 qui partent de S1 est 

         la somme des termes de M2 sur la première ligne.

         1+2+1+1= 5

         Conclusion: Il y a 5 chemins de longueur 2issus de S1.

5. On admet que:

                  Weeee4578e

  a. Le pages accessibles depuis toutes les autres pages en quelques clics sont

      celles pour lesquelles arrive au moins un chemin ( de longueurs quelconque) .

      Il doit y avoir une colonne  de 1 dans M ' .

       Il y a au moins un chemin de chacun des sommetsqui arrive à S2.

       Il y a au moins un chemin de chacun des sommetsqui arive à S3.        

          Conclusion: Ce sont les sommets S2 et S3  .

           On peut aller aux pages P2 ou P3 à partir de n'importe quelle page.

      b. Les zéros de la première colonne de M ' signifie qu'il n'y a aucun chemin

          partant de  S2  ou  S2 ou S3 qui arrive à S1 .

          Conclusion: On ne peut pas des pages P2 , P3 ou P4 revenir à P1.

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