INFO Matrices et Graphes 2 BTS
EXERCICE 1
Soit G un graphe orienté simple de sommets ABCDEF dont
la matrice adjacente est :
Les réponses attendues ne sont pas OUI , NON simplement.
Ce qui entraîne votre conviction doit figurer sur la copie.
1. a. Y a-t-il des arcs qui "arrivent" en A ou C ou F ?
Réponse: NON. La première colonne , la troisième colonne et
la sixième colonne n'ont que des zéros.
b. Comment interprétez-vous la présence de deux lignes de zéros dans M ?
Réponse: Les deuxième et cinquième lignes n'ont que des 0.
Aucun arc ne part donc du sommet E ni du sommet B.
2. Le graphe G comporte-t-il des boucles ?
Réponse: NON . Il n'y a que des 0 dans la diagonale principale
de la matrice M.
3. a. Combien d'arcs G comporte-t-il ?
Réponse: Il y a 6 fois le 1 dans la matrice M.
Il y a donc 6 arcs.
b. Donner le tableau des prédécesseurs et des successeurs.
Prédécesseurs | Sommets | successeurs |
A | D E | |
C D | B | |
C | B E | |
A | D | B |
A C F | E | |
F | E |
4. Compléter le tableau par une colonne pour les niveaux des sommets.
Prédécesseurs | Sommets | Niveaux |
A | 0 | |
C D | B | 2 |
C | 0 | |
A | D | 1 |
A C F | E | 1 |
F | 0 |
5. Proposer une représentation de G en l'ordonnant suivant les niveaux.
Réponse:
6. Trouver les matrices M2 , M3 , M4 , M5 ,M6 .
Réponse:
Les matrices M3 , M4 , M5 ,M6 sont les matrices nulles
7.a. Combien y a-t-il un chemin de longueur 2 qui arrive à E ?
Réponse: NON car la cinquième colonne de M2 est faite de 0.
b. Combien y a-t-il en tout de chemins de longueur 2 ?
Citez ce ou ces chemins.
Réponse: La somme des termes de la matrice M2 est 1.
Il y a donc un seul chemin de longueur 2.
C'est ADB
8. a. Y a-t-il des chemins de longueur 3.
Réponse : NON car M3 est la matrice nulle
b. Existe-t-il des chemins de longueur supérieure à 3.
Réponse: NON car toutes les matrices , M4 , M5 ,M6 , ... sont nulles.
9. a.Reproduire le graphe précédent en rajoutant les raccourcis.
( Un raccoucis étant un arc entre deux sommets
qui sont déjà joignable par un chemin existant. )
On obtient un nouveau graphe G ' appelé:
<< fermeture transitive de G >>.
Réponse: G ' est :
b. Donner la matrice adjacente M ' de ce nouveau graphe G '.
Réponse:
10. a . Dans chacune des matrices M2 , M3 , M4 , M5 ,M6
on laisse les 0 et on remplace les termes autres que 0 par des 1.
On obtient ainsi des matrices booléennes , n'ayant que des 0 ou des 1.
On les note respectivement :
M [ 2 ] , M[ 3] , M[ 4 ] , M[ 5 ] ,M[ 6 ] .
Préciser ces cinq matrices booléennes :
Réponse: On retrouve ici les matrices M2 , M3 , M4 , M5 ,M6
car elles étaient déjà booéennes.
b. Calculez la matrice A somme booléenne des matrices
booléennes M , M [ 2 ] , M[ 3] , M[ 4 ] , M[ 5 ] ,M[ 6 ]
( Rappel: 0 + 0 = 0 1 + 0 = 0 + 1 = 1 1 + 1 = 1 )
Comparer M ' et A.
Réponse: Comme les matrices M[ 3] , M[ 4 ] , M[ 5 ] ,M[ 6 ] sont nulles
cela revient à considérer la somme booléenne
D'où : A = M '
----------------------------------------------------------------------------------------------------------------------------
EXERCICE 2
L'entreprise Nevets and Sirhc Society doit créer un site
internet pour un particulier.
Ce site site internet doit comporter 5 pages notées B , C , D, E
et la page d'accueil A.
De chacune des pages B, C, D, E en cliquant on doit pouvoir
revenir à la page d'accueil.
On doit pouvoir à partir de la page d'accueil A, en cliquant, obtenir l'accès
directement aux pages B et C.
Depuis la page C on doit pouvoir en cliquant obtenir la page B et la page E.
On doit pouvoir depuis la page E en cliquant obtenir la page D.
En fin à partir de la page C en cliquant on doit pouvoir obtenir la page D.
Il n'est pas prévu de bouton sur lequel en cliquant on reste sur la même page.
1. Faire la représentation du site en considérant le graphe G dont les
sommets sont A, B, C, D, E et en considérant les "clic " comme des arcs.
Réponse:
2. Donner sa matrice adjacente M.
Réponse: On a :
3. Trouver la matrice M2 .
Combien de double " clic" peut-on faire pour aller d'une page à une autre?
Réponse: On a :
Donc :
Il suffit d'ajouter tous les termes de la matrice M2
il y en a donc : 18
4. Est-il possible, en cliquant plusieurs fois, de partir de la page d'accueil A
pour y revenir seulement à la fin en ayant pu consulter successivement
toutes les pages du site ?
Réponse: NON car si on part de A pour B on doit revenir en A.
et si l'on part de A pour C on ne peut pas atteindre B
sans repasser par A entre temps.
-----------------------------------------------------------------------------------------------------
EXERCICE 3 ( Si vous avez le temps )
1. Trouver le ou les trajets de durée minimale de A à F du graphe G suivant.
( La pondération est en minutes )
F ← 16(C) ← 11(A) ← A
Donc le chemin le plus court est : ACF de 16 mn
2. Donner les niveaux des sommets.
Réponse:
Prédécesseurs | Sommets | Niveaux |
A | 0 | |
A | B | 1 |
AB | C | 2 |
B | D | 2 |
CD | E | 3 |
EC | F | 4 |
----------------------------------------------------------------------------------------------------------------