Identifier les arcs à partir de la matrice d'adjacence

Énoncé

Soit la matrice d'adjacence M = pmatrix 0 & 1 & 1 0 & 0 & 1 1 & 0 & 0 pmatrix d'un graphe orienté avec les sommets \{A, B, C\}. Lister tous les arcs de ce graphe.

Indice : Un coefficient m_{i,j} = 1 signifie qu'il existe un arc du sommet i vers le sommet j.

Correction

1. Étape 1 : L'exercice inverse le précédent : on part de la matrice et l'on retrouve les arcs. La convention est la même — ligne = départ, colonne = arrivée.
2. Étape 2 : On balaie ligne par ligne et l'on note chaque 1 rencontré : Ligne 1 (A) : des 1 en colonnes 2 et 3, donc les arcs (A, B) et (A, C).
3. Étape 3 : Ligne 2 (B) : un 1 en colonne 3, donc l'arc (B, C).
4. Étape 4 : Ligne 3 (C) : un 1 en colonne 1, donc l'arc (C, A).
5. Étape 5 : Le graphe possède donc quatre arcs :

   (A,B),\ (A,C),\ (B,C),\ (C,A)

6. Étape 6 : Contrôle : la matrice contient quatre 1, et l'on a listé quatre arcs. La matrice n'est pas symétrique, et c'est normal : Ici m_{1,2} = 1 mais m_{2,1} = 0 : on va de A vers B, jamais de B vers A. Le graphe est ORIENTÉ. Une matrice d'adjacence symétrique signale au contraire un graphe non orienté, où chaque arête se parcourt dans les deux sens. Balayer par lignes, jamais en zigzag : Une ligne = tous les arcs qui partent d'un même sommet. En parcourant ligne par ligne, on n'en oublie aucun et l'on obtient la liste déjà rangée.