Matrice d'adjacence d'un graphe

Soit $G$ un graphe non-orienté qui possède $n$ sommets numérotés de $1$ à $n.$ On appelle matrice d'adjacence du graphe la matrice $A=(a_{i,j})$ où $a_{i,j}$ est le nombre d'arêtes joignant le sommet $i$ au sommet $j.$ Pour les graphes ayant au plus une arête entre deux sommets, on a $a_{i,j}\in\{0,1\}.$

Exemple : Voici un graphe, et la matrice d'adjacence correspondante :

On peut remarque que cette matrice est symétrique. C'est le cas pour toutes les matrices d'adjacence d'un graphe non-orienté.

Le résultat principal concernant les matrices d'adjacence est le théorème suivant :

On peut également définir la matrice d'adjacence d'un graphe orienté. Cette fois, le coefficient $a_{i,j}$ désigne le nombre d'arcs d'origine $i$ et d'extrémité $j.$

Exemple : Pour le graphe suivant,

on trouve la matrice d'adjacence $$\left( \begin{array}{cccc} 0& 0& 1& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 1& 0& 0 \end{array} \right).$$ Cette matrice n'est plus symétrique. En revanche, le terme d'indice $(i,j)$ de la matrice $A^n$ compte toujours le nombre de chemins allant de $i$ vers $j.$