adjacency matrix 鄰接矩陣 簡介

Home >> Blog >> adjacency matrix 鄰接矩陣 簡介

adjacency matrix 鄰接矩陣 簡介

在圖論中，鄰接矩陣只不過是用於描述有限圖的方陣。矩陣的分量表示有限的一組頂點（也稱為節點）的對在圖中是否相鄰。在圖表示中，網絡是在節點和邊的幫助下表示的，其中節點是頂點，邊是有序對的有限集。

目錄：

• 定義
• 從圖表創建
• 特性
• 無向圖
• 有向圖
• 例子

圖也可以用矩陣的形式定義。為了在圖中執行路徑和循環的計算，使用矩陣表示。它是使用矩陣運算計算的。圖表的兩種最常見的表示是：

• 鄰接矩陣
• 鄰接表

我們將在這裡討論矩陣、它的形成及其性質。

鄰接矩陣定義

如果簡單圖沒有自環，那麼頂點矩陣的對角線應該有 0。對於無向圖是對稱的。連接矩陣被認為是一個方陣，其中每一行代表圖的出節點，每列代表圖的入節點。條目 1 表示兩個節點之間有一條邊。

無向圖的鄰接矩陣是對稱的。這表示第 i 行第 j 列的值與第 j 行第 i 列的值相同。此外，一個有趣的事實包括矩陣乘法。如果鄰接矩陣與自身相乘（矩陣乘法），如果在第 i 行第 j 列中存在非零值，則從 V i 到 V j 的路徑長度等於 2。儘管創建了路徑，但它沒有指定路徑。非零值表示存在的不同路徑的數量。

相關鏈接

正交矩陣

圖論

矩陣

矩陣的初等變換

如何創建鄰接矩陣？

如果圖 G 有 n 個頂點，則頂點矩陣 nxn 由下式給出

其中，a ij的值等於從頂點 i 到 j 的邊數。對於無向圖，所有 i, j 的值 a ij = a ji，因此鄰接矩陣變為 對稱矩陣。

在數學上，這可以解釋為：

設 G 為頂點集 {v 1 , v 2 , v 3 , . . . , v n }，則 G 的鄰接矩陣是 n × n 矩陣，如果在 G 中存在從 vi 到 v j的邊 並且在 ( i , j)-否則位置。

從給定的有向圖中， 鄰接矩陣 寫為

鄰接矩陣 =

特性

頂點矩陣是一個數字數組，用於表示有關圖的信息。圖的某些屬性對應於鄰接矩陣的屬性，反之亦然。屬性如下：

矩陣權力

定理：讓我們假設，A 是給定圖的連接矩陣。然後 A n的條目 i, j計數從頂點 i 到 j 的 n 步。

光譜

圖的連接矩陣的特徵值的研究在譜圖論中有明確的定義。假設 A 是 k 正則圖的連接矩陣， v 是 R n中的全1列向量。那麼Av的第i個條目等於A的第i行條目的總和。這表示從頂點i開始的邊數，恰好是k。 所以

同構

如果一個圖可以通過重新標記另一個圖的頂點從另一個圖獲得，則稱給定的兩個圖是同構的。注意，同構圖不需要具有相同的鄰接矩陣。因為這個矩陣取決於頂點的標籤。但是給定同構圖的鄰接矩陣是密切相關的。

定理：假設 G 和 H 是與鄰接矩陣 A 和 B 有 n 個頂點的圖。那麼 G 和 H 被稱為同構當且僅當存在置換矩陣 P 使得 B=PAP -1 .

鄰接矩陣無向圖

對於無向圖，遵循的協議將取決於線和循環。這意味著每條邊（即線）將 1 添加到矩陣中的相應單元格，並且每個循環都添加 2。因此，使用這種做法，我們可以很容易地找到一個頂點的度數，只需將兩者中的值相加即可它在鄰接矩陣中的相應行或列。這可以通過下面的例子來理解。

鄰接矩陣有向圖

如上一節所述，有向圖如下所示：

這種類型的圖的鄰接矩陣是使用前面示例中遵循的相同約定編寫的。

鄰接矩陣示例

問題：

寫下給定無向加權圖的鄰接矩陣

解決方案：

圖邊緣的權重在鄰接矩陣的條目中表示如下：

一個=

有關鄰接矩陣和其他矩陣相關主題的更多此類有趣信息，請註冊 BYJU'S -The Learning App 並觀看互動視頻以澄清疑問。