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

Compter les chemins de longueur donnée

Informatique et algorithmique · Graphes · ★★★ niveau 3 (difficile)

Énoncé

Soit $A$ la matrice d'adjacence d'un graphe non orienté à $n$ sommets. Le coefficient $(i,j)$ de $A^k$ compte les chemins de longueur $k$ de $i$ à $j$. Écrire puissance(A, k) avec np.dot, puis vérifier $A^2$ à la main sur le graphe d'arêtes $\{0,1\}$, $\{1,2\}$, $\{1,3\}$, $\{2,3\}$.

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