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