Détecter un circuit dans un graphe
Énoncé
Soit M = (0 , 1 , 0 ; 0 , 0 , 1 ; 1 , 0 , 0) 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ᵢ existe si et seulement si (Mᵏ)ᵢ,ᵢ > 0.
Correction
- É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ᵏ)ᵢ,ᵢ = nombre de circuits de longueur k passant par i.
On cherche donc des coefficients diagonaux non nuls, en essayant k = 2, puis 3…
- Étape 2 : Longueur 2 ? On lit la diagonale de M² :
M² = (0 , 0 , 1 ; 1 , 0 , 0 ; 0 , 1 , 0)
- É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.
- Étape 4 : Longueur 3 ? On multiplie encore une fois, en réutilisant la lecture par lignes :
M³ = M² × M = (1 , 0 , 0 ; 0 , 1 , 0 ; 0 , 0 , 1) = I₃
- Étape 5 : Les trois coefficients diagonaux valent 1 : il existe un circuit de longueur 3 par chaque sommet, et un seul.
s₁ → s₂ → s₃ → s₁
- Étape 6 : M³ = I₃ dit encore plus. Appliquer le graphe trois fois ramène tout à sa place : le graphe est un cycle pur. Donc M⁴ = M, M⁵ = M², 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³ = I₃ répond donc à la question sans même lire la diagonale.