Démontrer le nombre de chemins de longueur n avec la matrice d'adjacence - Exercice 2

20 min

On considère le graphe

G

non orienté représenté ci-dessous et sa matrice d'adjacence

M

(sommets rangés dans l'ordre alphabétique).

Question 1

Donner la matrice $M$ .

Correction

Le coefficient de la ligne

i

et de la colonne

j

vaut

1

si les

i

-ième et

j

-ième sommets sont adjacents, et

0

sinon.
Finalement :

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

Question 2

Démontrer que, dans un graphe simple non orienté, le coefficient de la ligne $i$ et de la colonne $i$ de $M^{2}$ est égal au degré du sommet $i$ . Le vérifier avec le sommet $D$ à l'aide de la calculatrice.

Correction

Un chemin de longueur

2

allant de

i

i

s'écrit

i-l-i

, où

l

est un sommet adjacent à

i

(il n'y a pas de boucle). Comme le graphe est simple, il y a exactement un tel chemin pour chaque sommet

l

adjacent à

i

, donc autant que d'arêtes issues de

i

.
Ainsi :

le coefficient de la ligne

i

et de la colonne

i

M^{2}

est le degré du sommet

i

D'après la calculatrice, on obtient :

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

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

4

, et le sommet

D

est bien de degré

4

(il est adjacent à

B

C

E

F

Question 3

À l'aide de la calculatrice, donner le coefficient de la première ligne et de la septième colonne de $M$ , $M^{2}$ , $M^{3}$ et $M^{4}$ . En déduire la distance entre $A$ et $G$ , ainsi que le nombre de chaînes de longueur $4$ reliant $A$ à $G$ .

Correction

Les coefficients de la première ligne et de la septième colonne de

M

M^{2}

M^{3}

M^{4}

valent respectivement

0

0

0

4

.
Il n'existe donc aucune chaîne de longueur

1

2

3

reliant

A

G

, mais il en existe

4

de longueur

4

.
Finalement :

la distance entre

A

G

est

4

, et

4

chaînes de longueur

4

relient

A

G

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.

Démontrer le nombre de chemins de longueur n avec la matrice d'adjacence - Exercice 2

Donner la matrice MMM .

Démontrer que, dans un graphe simple non orienté, le coefficient de la ligne iii et de la colonne iii de M2M^{2}M2 est égal au degré du sommet iii . Le vérifier avec le sommet DDD à l'aide de la calculatrice.

À l'aide de la calculatrice, donner le coefficient de la première ligne et de la septième colonne de MMM , M2M^{2}M2 , M3M^{3}M3 et M4M^{4}M4 . En déduire la distance entre AAA et GGG , ainsi que le nombre de chaînes de longueur 444 reliant AAA à GGG .

Donner la matrice $M$ .

Démontrer que, dans un graphe simple non orienté, le coefficient de la ligne $i$ et de la colonne $i$ de $M^{2}$ est égal au degré du sommet $i$ . Le vérifier avec le sommet $D$ à l'aide de la calculatrice.

À l'aide de la calculatrice, donner le coefficient de la première ligne et de la septième colonne de $M$ , $M^{2}$ , $M^{3}$ et $M^{4}$ . En déduire la distance entre $A$ et $G$ , ainsi que le nombre de chaînes de longueur $4$ reliant $A$ à $G$ .