Разница между симметричной и асимметричной матрицей

Question

Я занимаюсь графиками и смежными матрицами. Но я не мог найти хороший пример, который отличает симметричную и асимметричную матрицу. Может ли кто-нибудь сказать мне, как отличить разницу между симметричной или асимметричной матрицей.

Answer 1

Матрица смежности симметрична, если она получена из неориентированного графа.

Это означает, что путь от узла A -> B имеет ту же стоимость/вес/длину, что и путь от узла B -> A.

Если создать матрицу смежности M, это будет симметричным, а это означает, что для любого i и j, M[i][j] == M[j]i]. Математически матрица идентична его транспозиции. Поэтому, если вы перенесете свою матрицу, она будет выглядеть точно так же. Графически такая матрица выглядит следующим образом:

0 2 3 4 
2 0 5 6 
3 5 0 7 
4 6 7 0 

В силу симметрии, часто можно представить его, используя меньше памяти. Для алгоритмов, таких как Floyd-Warshall-algorithm на неориентированных графах, вы можете уменьшить объем вычислений на 50%, так как вам нужно всего лишь вычислить половину матрицы:

0 2 3 4 
    0 5 6 
    0 7 
     0 

Для сравнения, асимметричные матрицы:

0 2 3 9 <-- 
2 0 5 6 
3 5 0 7 
4 6 7 0 

Обратите внимание, что он почти идентичен предыдущему примеру, но в правом верхнем углу находится 9. Таким образом, невозможно больше зеркалировать матрицу вдоль ее диагональной оси.