Exercice 3, § 1

Soit $Q = (S,F, o, t)$ un carquois localement fini. On définit la matrice $M_Q= (m_{i,j})$, de type $(S,S)$ à éléments dans $\mathbf{Z}$, par

$m_{i,j}=$ Card$\{f\in F|o(f) =i$ et $t(f) =j\}$. La matrice $M_Q$ est appelée la matrice d’adjacence de Q.

a) Étant donnés des carquois Q et $Q'$, donner une condition nécessaire et suffisante sur leurs matrices d’adjacence pour que les carquois Q et $Q'$ soient isomorphes.

b) Exprimer en termes de la matrice d’adjacence $M_Q$ le nombre de chemins de longueur $n$ dans Q dont l’origine et le terme sont donnés.

c) Démontrer que la matrice d’adjacence du carquois sous-jacent à un graphe est symétrique.