algorithm - 対称行列と非対称行列の違い

Question

グラフと隣接行列を使って練習しています。しかし、対称行列と非対称行列を区別する良い例は見つかりませんでした。対称マトリックスと非対称マトリックスの違いを区別する方法を教えてください。

Answer 1

隣接行列は、無向グラフから導出された場合、対称です。

つまり、ノード A -> B からのパスは、ノードからのパスと同じコスト/重み/長さを持ちますB -> A。

隣接行列 を作成すると、Mそれは対称になります。より数学的には、行列はその転置と同じです。したがって、行列を転置すると、まったく同じに見えます。グラフィカルに、このようなマトリックスは次のようになります。ijM[i][j] == M[j]i]

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

対称性により、多くの場合、より少ないメモリで表現できます。無向グラフのFloyd-Warshallアルゴリズムのようなアルゴリズムの場合、行列の半分しか計算する必要がないため、計算量を 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. そのため、対角軸に沿ってマトリックスをミラーリングすることはできなくなりました。