Compter les chaînes de longueur $n$~2 min
Soit $A$ la matrice d'adjacence d'un graphe (orienté ou non). Pour tout $n\geq1$, le coefficient $(i,j)$ de $A^n$ est le nombre de chaînes de longueur $n$ allant du sommet $i$ au sommet $j$.
Par récurrence sur $n$. Notons $c_n(i,j)$ le nombre de chaînes de longueur $n$ de $i$ à $j$.
Initialisation. Une chaîne de longueur $1$ de $i$ à $j$ est une arête (ou un arc) de $i$ à $j$ : $c_1(i,j)=a_{ij}$, coefficient de $A^1$.
Hérédité. Supposons que, pour tout couple $(i,k)$, $c_n(i,k)$ soit le coefficient $(i,k)$ de $A^n$. Une chaîne de longueur $n+1$ de $i$ à $j$ est constituée d'une chaîne de longueur $n$ de $i$ à un sommet $k$, suivie d'une arête de $k$ à $j$. Pour $k$ fixé il y a $c_n(i,k)\times a_{kj}$ telles chaînes, et les différentes valeurs de $k$ donnent des chaînes distinctes. Donc $$c_{n+1}(i,j)=\sum_{k=1}^{N}c_n(i,k)\,a_{kj}=\sum_{k=1}^{N}(A^n)_{ik}\,a_{kj}=(A^nA)_{ij}=(A^{n+1})_{ij}.$$ La propriété est héréditaire, donc vraie pour tout $n\geq1$.
Dans $G$ : le coefficient $(A^2)_{AD}=2$ : deux chaînes de longueur $2$ de A à D (A-B-D et A-C-D). $(A^2)_{CC}=4$ : quatre chaînes fermées de longueur $2$ en C, une par voisin (aller-retour) : c'est le degré de C. $(A^3)_{AE}=3$ : A-B-C-E, A-C-D-E, A-B-D-E. On a utilisé np.linalg.matrix_power(A, 3).
Chaînes eulériennes (problème possible du programme). Une chaîne qui emprunte chaque arête exactement une fois est eulérienne. Théorème d'Euler : un graphe connexe admet une chaîne eulérienne si et seulement s'il a $0$ ou $2$ sommets de degré impair ; s'il en a $0$, la chaîne peut être fermée (cycle eulérien) ; s'il en a $2$, elle les a pour extrémités. Dans $G$, seuls B et D sont de degré impair : B-A-C-B-D-C-E-D convient. À Königsberg (sept ponts, quatre quartiers de degrés $3,3,3,5$) : impossible.