Graphes orientés : matrice d'adjacence et nombre de chemins - Exercice 2

20 min

Dans un quartier, cinq carrefours

A

B

C

D

E

sont reliés par des rues à sens unique, représentées par le graphe orienté ci-dessous. On note

M

sa matrice d'adjacence (sommets rangés dans l'ordre alphabétique).

Question 1

Donner la matrice d'adjacence $M$ .

Correction

Le coefficient de la ligne

i

et de la colonne

j

vaut

1

s'il y a une rue allant du

i

-ième carrefour au

j

-ième carrefour, et

0

sinon.
Finalement :

M=\left(\begin{array}{ccccc} {0} & {1} & {0} & {0} & {0} \\ {0} & {0} & {1} & {0} & {1} \\ {0} & {0} & {0} & {1} & {0} \\ {0} & {1} & {0} & {0} & {1} \\ {1} & {0} & {1} & {0} & {0} \end{array}\right)

Question 2

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

Correction

D'après la calculatrice, on obtient :

M^{2}=\left(\begin{array}{ccccc} {0} & {0} & {1} & {0} & {1} \\ {1} & {0} & {1} & {1} & {0} \\ {0} & {1} & {0} & {0} & {1} \\ {1} & {0} & {2} & {0} & {1} \\ {0} & {1} & {0} & {1} & {0} \end{array}\right)

M^{3}=\left(\begin{array}{ccccc} {1} & {0} & {1} & {1} & {0} \\ {0} & {2} & {0} & {1} & {1} \\ {1} & {0} & {2} & {0} & {1} \\ {1} & {1} & {1} & {2} & {0} \\ {0} & {1} & {1} & {0} & {2} \end{array}\right)

Question 3

Combien y a-t-il de trajets empruntant exactement $2$ rues pour aller de $D$ à $C$ ? Les citer.

Correction

Soit

G

un graphe et

M

sa matrice d’adjacence.
Le nombre de chemins de longueur

n

joignant le sommet

i

au sommet

j

est donné par le terme d’indice

i,j

de la matrice

M^{n}

Nous allons prendre la valeur de l'intersection entre la quatrième ligne (en référence au sommet

D

) et la troisième colonne (en référence au sommet

C

)
Nous mettons

\red{\text{en rouge}}

cette valeur dans la matrice

M^{2}

M^{2}=\left(\begin{array}{ccccc} {0} & {0} & {1} & {0} & {1} \\ {1} & {0} & {1} & {1} & {0} \\ {0} & {1} & {0} & {0} & {1} \\ {1} & {0} & {{\color{red}{2}}} & {0} & {1} \\ {0} & {1} & {0} & {1} & {0} \end{array}\right)

Il y a donc

{\color{red}{2}}

trajets empruntant exactement

2

rues pour aller de

D

C

.
Ce sont :

D-B-C

D-E-C

Question 4

Un livreur part du carrefour $A$ pour aller au carrefour $D$ . Quel est le nombre minimal de rues qu'il doit emprunter ? Justifier à l'aide des puissances de $M$ , puis donner un tel trajet.

Correction

Le coefficient de la première ligne et de la quatrième colonne vaut

0

dans

M

et dans

M^{2}

: il n'existe aucun trajet de

1

2

rues allant de

A

D

.
Il vaut

1

dans

M^{3}

: il existe un trajet de

3

rues.
Finalement :

le livreur doit emprunter au minimum

3

rues, par le trajet

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

Graphes orientés : matrice d'adjacence et nombre de chemins - Exercice 2

Donner la matrice d'adjacence MMM .

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

Combien y a-t-il de trajets empruntant exactement 222 rues pour aller de DDD à CCC ? Les citer.

Un livreur part du carrefour AAA pour aller au carrefour DDD . Quel est le nombre minimal de rues qu'il doit emprunter ? Justifier à l'aide des puissances de MMM , puis donner un tel trajet.

Donner la matrice d'adjacence $M$ .

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

Combien y a-t-il de trajets empruntant exactement $2$ rues pour aller de $D$ à $C$ ? Les citer.

Un livreur part du carrefour $A$ pour aller au carrefour $D$ . Quel est le nombre minimal de rues qu'il doit emprunter ? Justifier à l'aide des puissances de $M$ , puis donner un tel trajet.