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 : On calcule M^2 pour chercher des circuits de longueur 2.

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

2. Étape 2 : Les coefficients diagonaux de M^2 sont tous nuls : (M^2)_{1,1} = 0, (M^2)_{2,2} = 0, (M^2)_{3,3} = 0. Il n'y a pas de circuit de longueur 2.
3. Étape 3 : On calcule M^3.

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

4. Étape 4 : Les coefficients diagonaux de M^3 sont tous égaux à 1. Il existe donc un circuit de longueur 3 passant par chaque sommet.
5. Étape 5 : Le circuit est : s_1 s_2 s_3 s_1 (ou toute permutation circulaire).