Pourquoi la matrice d’adjacence d’un graphe non orienté est-elle symétrique ?
Réponse courte
Dans un graphe non orienté, la relation entre deux sommets fonctionne dans les deux sens. Si une arête relie i à j, la matrice indique donc aussi bien l’adjacence de i vers j que de j vers i : les cases (i,j) et (j,i) sont égales.
Comprendre
La propriété vient des arêtes
Une arête d’un graphe non orienté relie deux sommets sans choisir de départ ni d’arrivée. Ainsi, si A est voisin de B, B est également voisin de A. Dans la matrice d’adjacence, la case de ligne A et colonne B indique cette relation ; la case de ligne B et colonne A indique la relation inverse. Les deux cases prennent alors la même valeur. Cette égalité pour chaque paire de sommets est précisément la symétrie de la matrice par rapport à sa diagonale.
Un exemple concret
Pour trois sommets A, B et C, supposons des arêtes A-B et B-C, mais pas A-C. Avec l’ordre A, B, C, la matrice binaire est : ligne A : 0, 1, 0 ; ligne B : 1, 0, 1 ; ligne C : 0, 1, 0. Les cases A,B et B,A valent toutes deux 1 ; les cases A,C et C,A valent toutes deux 0.
Ce que la symétrie ne dit pas
La diagonale concerne les boucles : elle vaut 0 si le graphe n’a pas d’arête d’un sommet vers lui-même, mais ce n’est pas la raison de la symétrie. Un graphe orienté peut avoir une matrice non symétrique, car A→B n’impose pas B→A. Vérifie aussi que les lignes et colonnes utilisent le même ordre de sommets, sinon la comparaison des cases n’a pas le sens attendu.
Exemples
- Si A-B est une arête, les cases (A,B) et (B,A) valent toutes deux 1.
- Sans arête entre A et C, les cases (A,C) et (C,A) valent toutes deux 0.
Pièges fréquents
- Attribuer la symétrie à l’absence de boucles : elle découle de la réciprocité de chaque arête, même si le graphe contient des boucles.
- Étendre la propriété aux graphes orientés : un arc A→B peut exister sans l’arc B→A.
