Détecter un circuit dans un graphe

Énoncé

Soit M = pmatrix 0 & 1 & 0 0 & 0 & 1 1 & 0 & 0 pmatrix la matrice d'adjacence d'un graphe. Déterminer s'il existe un circuit et donner sa longueur.

Indice : Un circuit de longueur k passant par s_i existe si et seulement si (M^k)_{i,i} > 0.

Correction

1. Étape 1 : Un circuit est un chemin qui revient à son point de départ, donc un chemin de i à i. Le théorème des chemins le rend lisible immédiatement : Circuits et diagonale : (M^k)_{i,i} = nombre de circuits de longueur k passant par i. On cherche donc des coefficients diagonaux non nuls, en essayant k = 2, puis 3…
2. Étape 2 : Longueur 2 ? On lit la diagonale de M^2 :

   M^2 = pmatrix 0 & 0 & 1 1 & 0 & 0 0 & 1 & 0 pmatrix

3. Étape 3 : Les trois coefficients diagonaux sont nuls : aucun circuit de longueur 2. C'était prévisible, car un tel circuit demanderait un aller-retour i r i, donc deux arcs opposés — or la matrice n'est pas symétrique.
4. Étape 4 : Longueur 3 ? On multiplie encore une fois, en réutilisant la lecture par lignes :

   M^3 = M^2 M = pmatrix 1 & 0 & 0 0 & 1 & 0 0 & 0 & 1 pmatrix = I_3

5. Étape 5 : Les trois coefficients diagonaux valent 1 : il existe un circuit de longueur 3 par chaque sommet, et un seul.

   s_1 s_2 s_3 s_1

6. Étape 6 : M^3 = I_3 dit encore plus. Appliquer le graphe trois fois ramène tout à sa place : le graphe est un cycle pur. Donc M^4 = M, M^5 = M^2, et les puissances se répètent indéfiniment de trois en trois. Ne pas chercher au-delà de n sommets : Un circuit qui ne repasse pas deux fois par le même sommet a au plus n arcs. Avec 3 sommets, tester k = 2 et k = 3 suffit donc. Au-delà, on ne trouve que des circuits déjà vus, parcourus plusieurs fois. Un raccourci de lecture : Si une puissance de M redonne I, le graphe est un cycle et sa longueur est cet exposant. Repérer M^3 = I_3 répond donc à la question sans même lire la diagonale.