EXERCICE SUR LES GRAPHES ORIENTES SIMPLES DE 2000N MARS 2009
EXERCICE 1 5 POINTS
Une entreprise veut créer un site Internet comportant 5 pages A , B , C , D , E .
La structure des pages vérifie les conditions suivantes:
• La page A est la page d'accueil et sur chacune des autres pages figure un bouton
permettant de revenir directement à la page d'accueil.
• On peut passer directement de la page A aux autres pages sauf à la page E.
• On peut passer directement de la page B à la page E et de la page E à la page C.
1. Dessiner une représentation du graphe orienté associé au site.
2. Vérifier que la matrice d'adjacence M du graphe est :
| / 0 | 1 | 1 | 1 | 0 \ | |
| / 1 | 0 | 0 | 0 | 1 \ | |
| M = | | 1 | 0 | 0 | 0 | 0 | |
| \ 1 | 0 | 0 | 0 | 0 / | |
| \ 1 | 0 | 1 | 0 | 0 / |
3. Calculer les deux matrices booléennes M[ 2 ] et M[ 3 ] . Quelle est la signification
des " 1 " présents dans la matrice M[ 3 ] ?
4. On admet que la matrice M 3 = M × M ×M , où × désigne la multiplication des matrices, peut
s'écrire :
| / 1 | 3 | 4 | 3 | 0 \ | |
| / 4 | 1 | 1 | 1 | 1 \ | |
| M3 = | | 3 | 0 | 0 | 0 | 1 | |
| \ 3 | 0 | 0 | 0 | 1 / | |
| \ 3 | 1 | 1 | 1 | 1 / |
a. Déterminer le nombre de chemins de longueur 3 ayant pour origine B et pour extrémité A.
Ecrire ces chemins.
b. Ecrire les trois circuits de longueur 3
-------------------------------------------------------------------------------------------------------------------------------