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.

Et maintenant ?

Questions proches

← Toutes les questions-réponses