mathématiques appliquées (ECG 1re année) · Chapitre 3 · Exercice d'entraînement

Le cycle à quatre sommets

Théorie des graphes · Chemins et puissances de la matrice · ★★ niveau 2

Énoncé

On considère le graphe non orienté de sommets $1,2,3,4$ et d'arêtes $\{1,2\}$, $\{2,3\}$, $\{3,4\}$, $\{4,1\}$. Écrire sa matrice d'adjacence $A$, calculer $A^2$ et $A^3$. Combien y a-t-il de chaînes de longueur $3$ de $1$ vers $1$ ? de $1$ vers $3$ ? de $1$ vers $2$ ? Expliquer le motif observé.

Un exercice à chercher : son corrigé n'est pas publié. Sur Adloun, le tuteur guide par questions, sans donner la réponse.