Construire la matrice d'adjacence d'un graphe

Énoncé

Soit un graphe orienté avec les sommets \{A, B, C\} et les arcs : (A, B), (B, C), (C, A). Construire la matrice d'adjacence de ce graphe.

Indice : Place 1 à la position (i,j) s'il existe un arc du sommet i vers le sommet j, et 0 sinon.

Correction

1. Étape 1 : Tout le chapitre repose sur une convention, et il faut la fixer une fois pour toutes : La convention de lecture : m_{i,j} = 1 signifie : il existe un arc de i vers j. Ligne = départ, colonne = arrivée. Certains ouvrages font l'inverse. Dans le doute, on le vérifie sur un arc connu de l'énoncé.
2. Étape 2 : On numérote d'abord, car les indices de la matrice sont des numéros, pas des lettres : s_1 = A, s_2 = B, s_3 = C.
3. Étape 3 : On place un 1 par arc, en lisant chaque couple comme (ligne, colonne) : arc (A, B) m_{1,2} = 1 · arc (B, C) m_{2,3} = 1 · arc (C, A) m_{3,1} = 1
4. Étape 4 : Tout le reste vaut 0, puisqu'il n'y a que trois arcs :

   M = pmatrix 0 & 1 & 0 0 & 0 & 1 1 & 0 & 0 pmatrix

5. Étape 5 : Deux contrôles gratuits. La somme de tous les coefficients vaut 3, soit le nombre d'arcs. Et la diagonale est nulle car aucun sommet ne boucle sur lui-même. Le piège de la transposée : Écrire m_{2,1} = 1 pour l'arc (A,B) donne la matrice TRANSPOSÉE, qui décrit le graphe avec tous les arcs retournés. Rien ne plante : la matrice reste une matrice d'adjacence valide, mais d'un autre graphe. Et toutes les questions suivantes deviennent fausses. Le contrôle par les sommes : Somme de la ligne i = nombre d'arcs qui PARTENT de i. Somme de la colonne j = nombre d'arcs qui ARRIVENT en j. Les deux totaux doivent donner le même nombre : celui des arcs.