Devoir type n°2 (2 h) - Exercice 2

30 min
50
Cinq serveurs informatiques AA , BB , CC , DD et EE sont reliés par des liaisons à sens unique, représentées par le graphe orienté ci-dessous. On note MM sa matrice d'adjacence (sommets rangés dans l'ordre alphabétique).

Barème : 8 points
Question 1

Donner la matrice d'adjacence MM .

Correction
Le coefficient de la ligne ii et de la colonne jj vaut 11 s'il y a une liaison allant du ii-ième serveur au jj-ième serveur, et 00 sinon.
Finalement :
M=(0100000101100100000110100)M=\left(\begin{array}{ccccc} {0} & {1} & {0} & {0} & {0} \\ {0} & {0} & {1} & {0} & {1} \\ {1} & {0} & {0} & {1} & {0} \\ {0} & {0} & {0} & {0} & {1} \\ {1} & {0} & {1} & {0} & {0} \end{array}\right)

Question 2

À l'aide de la calculatrice, donner M2M^{2} et M3M^{3} .

Correction
D'après la calculatrice, on obtient :
M2=(0010120110010011010011010)M^{2}=\left(\begin{array}{ccccc} {0} & {0} & {1} & {0} & {1} \\ {2} & {0} & {1} & {1} & {0} \\ {0} & {1} & {0} & {0} & {1} \\ {1} & {0} & {1} & {0} & {0} \\ {1} & {1} & {0} & {1} & {0} \end{array}\right)
M3=(2011012011102011101001102)M^{3}=\left(\begin{array}{ccccc} {2} & {0} & {1} & {1} & {0} \\ {1} & {2} & {0} & {1} & {1} \\ {1} & {0} & {2} & {0} & {1} \\ {1} & {1} & {0} & {1} & {0} \\ {0} & {1} & {1} & {0} & {2} \end{array}\right)
Question 3

Combien y a-t-il de chemins de longueur 22 allant de BB à AA ? Les citer.

Correction
Soit GG un graphe et MM sa matrice d’adjacence.
Le nombre de chemins de longueur nn joignant le sommet ii au sommet jj est donné par le terme d’indice i,ji,j de la matrice MnM^{n}
Nous allons prendre la valeur de l'intersection entre la deuxième ligne (en référence au sommet BB) et la première colonne (en référence au sommet AA)
Nous mettons en rouge\red{\text{en rouge}} cette valeur dans la matrice M2M^{2}
M2=(0010120110010011010011010)M^{2}=\left(\begin{array}{ccccc} {0} & {0} & {1} & {0} & {1} \\ {{\color{red}{2}}} & {0} & {1} & {1} & {0} \\ {0} & {1} & {0} & {0} & {1} \\ {1} & {0} & {1} & {0} & {0} \\ {1} & {1} & {0} & {1} & {0} \end{array}\right)
Il y a donc 2{\color{red}{2}} chemins de longueur 22 allant du sommet BB au sommet AA .
Ce sont :
B−C−AB-C-A et B−E−AB-E-A

Question 4

Justifier que, depuis chaque serveur, un message peut revenir à son point de départ en exactement 33 liaisons. Citer un tel chemin partant de DD .

Correction
Les coefficients diagonaux de M3M^{3} valent 2,2,2,1,22 , 2 , 2 , 1 , 2 : ils sont tous non nuls, donc pour chaque sommet il existe au moins un chemin de longueur 33 allant de ce sommet à lui-même.
Pour DD , le coefficient vaut 11 :
le seul chemin est D−E−C−DD-E-C-D

Question 5

Quel est le nombre minimal de liaisons pour envoyer un message de AA à DD ? Justifier.

Correction
Le coefficient de la première ligne et de la quatrième colonne vaut 00 dans MM et dans M2M^{2} , et 11 dans M3M^{3} .
Finalement :
il faut au minimum 33 liaisons, par le chemin A−B−C−DA-B-C-D

Signaler une erreur

Aide-nous à améliorer nos contenus en signalant les erreurs ou problèmes que tu penses avoir trouvés.

Connecte-toi ou crée un compte pour signaler une erreur.