對稱矩陣與不對稱矩陣的區別

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。所以不可能沿着它的對角軸鏡像矩陣。