Analyser un graphe avec matrice de connexité

Énoncé

Soit M = pmatrix 0 & 1 & 0 1 & 0 & 1 0 & 1 & 0 pmatrix la matrice d'adjacence d'un graphe. Calculer la matrice de connexité C et déterminer si le graphe est fortement connexe. En déduire le diamètre du graphe.

Indice : Calcule C = M + M^2 + M^3. Le graphe est fortement connexe si tous les coefficients non diagonaux sont strictement positifs. Le diamètre est la distance maximale entre deux sommets.

Correction

  1. Étape 1 : Un détail à relever avant tout calcul : M est symétrique. Le graphe est donc NON orienté — c'est le chemin s_1 - s_2 - s_3, où chaque arête se parcourt dans les deux sens. Conséquence immédiate : la connexité et la forte connexité coïncident, puisque tout aller possède son retour.
  2. Étape 2 : Les puissances. La ligne 2 de M contient deux 1, donc la ligne 2 de M^2 est la SOMME des lignes 1 et 3 :

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

  3. Étape 3 : Les coefficients ne sont plus des 0 et des 1, et c'est instructif : (M^2)_{2,2} = 2 signifie qu'il existe deux chemins de longueur 2 de s_2 vers lui-même — l'aller-retour vers s_1 et l'aller-retour vers s_3.
  4. Étape 4 : La matrice de connexité :

    C = M + M^2 + M^3 = pmatrix 1&3&1 3&2&3 1&3&1 pmatrix

  5. Étape 5 : Tous les coefficients sont strictement positifs, donc le graphe est fortement connexe : chaque sommet atteint tous les autres.
  6. Étape 6 : Le diamètre est la plus grande des distances entre deux sommets. On les relève toutes : d(s_1, s_2) = 1 et d(s_2, s_3) = 1, car m_{1,2} = m_{2,3} = 1.
  7. Étape 7 : Pour le dernier couple : m_{1,3} = 0 mais (M^2)_{1,3} = 1, donc la distance vaut 2 — il faut passer par s_2. C'est la plus grande, d'où :

    diam(G) = 2

  8. Étape 8 : Le diamètre mesure la « largeur » du graphe : deux sauts suffisent pour aller n'importe où. Sur un chemin à trois sommets, c'est le maximum possible. Le diamètre est un maximum de MINIMUMS : On prend d'abord le plus COURT chemin entre chaque paire, puis le plus GRAND de ces nombres. Inverser les deux quantificateurs n'a aucun sens : le plus long chemin entre deux sommets est infini dès qu'il existe un circuit, puisqu'on peut tourner indéfiniment. La symétrie divise le travail par deux : Sur un graphe non orienté, d(s_i, s_j) = d(s_j, s_i) : il n'y a que trois distances à calculer ici au lieu de six. Et cela se vérifie sur C, qui est symétrique elle aussi — une matrice de connexité non symétrique sur un graphe non orienté signalerait une erreur de calcul.