Matrice adjacente d'un graphe.

On considère un graphe non-orienté comportant n sommets que l'on numérote de 1 à n.
La matrice associée à ce graphe est composée de n lignes et n colonnes.
Le terme a_ij situé à l'intersection de la ligne i et de la colonne j est égal au nombre d'arêtes reliant le sommet i au sommet j.
La matrice est symétrique par rapport à la diagonale principale (allant de a₁₁ à a_nn). Ainsi, les termes a_ij = a_ji.

Dans le cas d'un graphe orienté, il faudra tenir compte de l'orientation des arêtes.
La matrice n'est généralement pas symétrique par rapport à la diagonale principale.

Exemple : On considère un graphe avec une boucle sur le sommet A, deux arêtes entre A et B, une seule arête de B à C.
On peut le symboliser par le shéma suivantOA⁐B―C; On numérote les sommets dans l'ordre alphabétique de 1 à 3.

i \ j	A 1	B 2	C 3
A   1	1	2	0	a11 = 1 car A relié à lui-même, a12 = 2 car deux arêtes entre A et B, a13 = 0 A et C ne sont pas reliés.
B   2	2	0	1	a21 = a12 = 2, a22 = 0 car pas de boucle sur B, a23 = 1 car B et C sont reliés par une seule arête.
C   3	0	1	0	a31 = a13 = 0, a32 = a23 = 1, a33 = 0 car pas de boucle sur C.

On notera cette matrice :	M =		1	2	0
			2	0	1
			0	1	0

Exemple : On reprend le graphe prédent en orientant les arêtes.
Une boucle sur le sommet A; Une arête de A vers B et une de B vers A. Une arête de B vers C.
On peut le symboliser par le shéma suivant : ⥀A ⇆ B→C;
On numérote toujours les sommets dans l'ordre alphabétique...

La nouvelle matrice adjacente est alors :	M =		1	1	0
			1	0	1
			0	0	0

Calculons M3 (avec la calculatrice !):	M =		3	2	1
			2	1	1
			0	0	0

Cherchons tous les chemins de longueur 3 possibles allant de B vers A. Il y B-A-B-A et B-A-A-A. Soit 2 chemins (valeurs de m₂₁).
Cherchons le nombre de circuits d'origne A et de longueur 3. On trouve A-B-A-A ; A-A-B-A et A-A-A-A. Soit 3 = m₁₁.

Nombre de chemins de longuer n.

Si on considère un graphe orienté et sa matrice adjacente M, alors le nombre de chemins de longueur n allant du sommet i au sommet j est donné par un coefficient m_ij de la matrice Mⁿ.

La démonstration se fait par récurrence... On note m_ij(n) le coefficient de ligne i et de colonne j dans la matrice Mⁿ.
Initialisation : Pour n = 1, Mⁿ = M. Par définition les coéfficients de la matrice adjacente représentent le nombre de chemins de longueur 1.
La propriété est vraie au rang 1. (ou La propriété est initialisée.)

Hérédité : On suppose la propriété vraie pour n ≥ 1. On veux montrer qu'elle est alors vraie au rang n+1.
Mⁿ⁺¹ = Mⁿ×M.
Le coefficient de la ligne i et de la colonne j de la matrice Mⁿ⁺¹ noté m_ij(n+1) s'obtient donc en multipliant la ligne i de la matrice Mⁿ
c'est-à-dire (m_i1(n) ... m_ik(n) ... ) par la colonne j de la matrice M soit (m_1j ... m_kj(n) ...) avec k = 1, ...
On a alors : m_ij(n+1) = m_i1(n)×m_1j + ... + m_ik(n)×m_kj + ...
Or d'après l'hypothèse de récurrence, m_i1(n) est le nombre de chemins de longueur n allant du sommet i au sommet 1 et m_1j le nombre de chemin de longueur 1 allant du sommet 1 au sommet j. Le produit m_i1(n)×m_1j représente donc le nombre de chemin de longueur n+1 allant du sommet i au sommet j en passant par le sommet 1. Ainsi de suite...
En faisant la somme de tous ce types de termes, on obtient le nombre de chemins possibles de longueur n+1 issue du sommet i finissant au sommet j en passant par tous les sommets intermédiaires du graphe.
Par conséquent, m_ij(n+1) reprèsente bien le nombre de chemins de longueur n+1 allant du sommet i au sommets j.
La propriété est donc vraie au rang n+1.

Conclusion : La propriété a été initialisée et est héréditaire donc d'après le principe de récurrence,
elle est vraie pour tout eniter n ≥ 1.