La matrice d'un graphe orienté

La matrice. Le coefficient $a_{ij}$ vaut $1$ s'il existe un arc de $i$ vers $j$, et $0$ sinon. Les arcs partant de $1$ vont vers $2$ et $3$ ; celui partant de $2$ va vers $3$ ; celui partant de $3$ va vers $1$ : $$A=\left(\begin{array}{ccc}0& 1& 1\\ 0& 0& 1\\ 1& 0& 0\end{array}\right).$$

Symétrique ? Non. Par exemple $a_{12}=1$ alors que $a_{21}=0$ : il y a un arc de $1$ vers $2$, mais aucun de $2$ vers $1$. C'est précisément ce que l'orientation permet, et la dissymétrie de la matrice le dit.

Le cas non orienté. Si l'on oubliait les sens, chaque arc deviendrait une arête reliant les deux sommets dans les deux sens. Les paires reliées seraient $\{1,2\}$, $\{2,3\}$ et $\{1,3\}$ — noter que $3\to 1$ et $1\to 3$ donnent la même arête $\{1,3\}$, qu'on ne compte qu'une fois. La matrice deviendrait $$A^{\prime }=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right),$$ qui est celle du graphe complet $K_3$, symétrique comme il se doit.

À retenir. Une matrice d'adjacence est symétrique si et seulement si le graphe est non orienté : la symétrie n'est pas une propriété de calcul, c'est la traduction de « si $i$ est relié à $j$, alors $j$ est relié à $i$ ».