Graphes et chaînes de Markov

À retenir. Dans un graphe non orienté, la somme des degrés est le double du nombre d'arêtes. Matrice d'adjacence $A$ : $a_{ij}$ est le nombre d'arêtes (ou d'arcs) de $i$ vers $j$. Le coefficient $(i,j)$ de $A^n$ est le nombre de chaînes de longueur $n$ reliant $i$ à $j$.

À retenir. La matrice de transition $P$ est stochastique : chaque ligne a une somme égale à $1$. Si $\pi_n$ est la ligne des probabilités à l'étape $n$ : $\pi_{n+1}=\pi_nP$. Un état stable $\pi$ vérifie $\pi=\pi P$ et la somme de ses coefficients vaut $1$.

À retenir. Le graphe complet $K_n$ a $\dfrac{n(n-1)}{2}$ arêtes ; chaque sommet est de degré $n-1$. Un graphe connexe admet une chaîne eulérienne s'il a $0$ ou $2$ sommets de degré impair, et un cycle eulérien si tous les degrés sont pairs.