Vérifier la connexité forte d'un graphe

Énoncé

Soit M = pmatrix 0 & 1 & 0 0 & 0 & 1 1 & 0 & 0 pmatrix la matrice d'adjacence d'un graphe avec 3 sommets. Vérifier si ce graphe est fortement connexe.

Indice : Un graphe est fortement connexe si pour tout couple (i,j), il existe un chemin de i à j ET de j à i. Calcule M + M^2 + M^3 pour obtenir la matrice de connexité.

Correction

  1. Étape 1 : Fortement connexe veut dire : de n'importe quel sommet, on peut atteindre n'importe quel autre en suivant les arcs dans leur sens. Comme la longueur du chemin n'est pas imposée, on somme les puissances. Matrice de connexité : C = M + M^2 + + M^{\,n-1} pour un graphe à n sommets. c_{i,j} > 0 signifie qu'il existe au moins un chemin de i vers j.
  2. Étape 2 : Pourquoi s'arrêter à M^{\,n-1} ? Un chemin qui ne repasse jamais par le même sommet traverse au plus n sommets, donc au plus n-1 arcs. S'il existe un chemin de i à j, il en existe un de cette longueur au plus, et les puissances suivantes n'apportent rien de nouveau. Ici n = 3, donc M et M^2 suffiraient — on ajoute M^3 par confort de lecture.
  3. Étape 3 : On additionne coefficient par coefficient :

    C = pmatrix 0&1&0 0&0&1 1&0&0 pmatrix + pmatrix 0&0&1 1&0&0 0&1&0 pmatrix + pmatrix 1&0&0 0&1&0 0&0&1 pmatrix = pmatrix 1&1&1 1&1&1 1&1&1 pmatrix

  4. Étape 4 : Tous les coefficients sont strictement positifs, donc il existe un chemin entre tout couple de sommets, dans les deux sens. Le graphe est fortement connexe.
  5. Étape 5 : Le résultat était prévisible : le graphe est le cycle s_1 s_2 s_3 s_1, et sur un cycle on atteint tout le monde en tournant. Un seul zéro suffit à tout casser : La forte connexité exige que TOUS les coefficients hors diagonale soient non nuls. Un unique c_{i,j} = 0 signifie que j est inatteignable depuis i, et le graphe n'est pas fortement connexe — voir l'exercice 39013, où C est triangulaire. Ne pas confondre les deux connexités : Fortement connexe : on circule dans le sens des arcs. Faiblement connexe : le graphe est d'un seul tenant si l'on oublie les orientations. Un graphe peut être faiblement connexe sans être fortement connexe, jamais l'inverse.