L’existence et le dénombrement de chemins de longueur k dans un graphe se fait en élevant à la puissance k la matrice booléenne aux arcs.

Matrice booléenne

On prend la matrice booléenne M, on l’élève successivement au carré, au cube, ..., à la puissance k pour déterminer le nombre de chemins de longueur 2,3,...,k

Calcul de

L’intersection de la ligne i et de la colonne j de la matrice donne le nombre de chemins de longueur 2 entre les sommets i et j

Plus généralement l’intersection de la ligne i et de la colonne j de la matrice donne le nombre de chemins de longueur k entre les sommets i et j

Matrice aux arcs

On prend la matrice aux arcs A, on l’élève successivement au carré, au cube, ..., à la puissance k pour déterminer le nombre de chemins de longueur 2,3,...,k ainsi que leur composition.

L’intérêt d’une telle représentation par rapport à la représentation par matrice booléenne est que l’on peut lire directement dans la composition des chemins de longueur k.

La méthode pour élever la matrice aux arcs au carré, au cube, etc, est d’adopter les lois de composition suivantes pour l’addition et la multiplication :

• La multiplication revient à concaténer 2 chemins
• L’addition est équivalente à la réunion ensembliste ils figurent dans la même case de la matrice aux arcs

L’intersection de la ligne i et de la colonne j de la matrice donne le nombre de chemins de longueur 2 entre les sommets i et j ainsi que leur composition.
Plus généralement, l’intersection de la ligne i et de la colonne j de la matrice donne le nombre de chemins de longueur k entre les sommets i et j ainsi que leur composition.

Chemins élémentaires - chemins hamiltoniens

L’existence et le dénombrement de chemins élémentaires de longueur k dans un graphe se fait en élevant à la puissance k la matrice aux arcs et en ne retenant que les chemins ne comportant pas de répérition de lettres.

Soit le graphe orienté comportant N sommets

Voir la figure Exemple de graphe orienté pour réaliser les matrices booléennes et aux arcs

• Chemins élémentaires de longueur 1
  Dans la matrice aux arcs A, on commence par supprimer tous les chemins qui ne sont pas élémentaires.
  boucle sur le sommet B
  Ce chemin est éliminé de A
  On obtient la matrice aux arcs A’ contenant les chemins élémentaires de longueur 1

• Chemins élémentaires de longueur 2
  On calcule à partir de en ne retenant que les chemins élémentaires.
  est un chemin de longueur 2 passant deux fois par le sommet A
  Ce chemin est éliminé de puisqu’il n’est pas élémentaire.
  On obtient la matrice aux arcs qui contient les chemins élémentaires de longueur 2
  

• Chemins élémentaires de longueur 3
  On calcule en ne retenant que les chemins élémentaires
  On obtient la matrice aux arcs contenant les chemins élémentaires de longueur 3

• Chemins élémentaires de longueur 4
  Dans la matrice apparaissent les chemins élémentaires de longueur 4
  

Ces chemins passent une fois et une seule par tous les sommets du graphe, ce sont donc des chemins Hamiltoniens. Si de plus les chemins Hamiltoniens ce referment sur eux-mêmes, ce sont des circuits Hamiltoniens.