Écrire la matrice d'adjacence d'un graphe orientéCalculer M² et M³Compter les chemins de longueur n
Le graphe orienté $\Gamma$ a pour sommets $1$, $2$, $3$, $4$ et pour arcs $$1\to 2,\quad 2\to 3,\quad 3\to 1,\quad 3\to 4,\quad 4\to 1.$$
- Écrire la matrice d'adjacence $M$ de $\Gamma$.
- Calculer $M^2$ et $M^3$.
- Combien existe-t-il de chemins de longueur $3$ allant de $1$ à $4$ ? Les écrire.
- Combien existe-t-il, au total, de chemins fermés de longueur $3$ dans $\Gamma$ ? Existe-t-il un chemin fermé de longueur $3$ partant de $4$ ?
Indice 1
Le coefficient $m_{ij}$ vaut $1$ s'il existe un arc de $i$ vers $j$ : la ligne est le départ, la colonne l'arrivée.
Indice 2
Pour calculer $M^3$, on peut multiplier $M^2$ par $M$.
Indice 3
Les chemins fermés de longueur $3$ se lisent sur la diagonale de $M^3$.
🔒 Corrigé Premium
Crée un compte gratuit : 5 corrigés Premium offerts chaque semaine
Créer mon compte gratuit