圖的矩陣表示課件

1、 圖的矩陣表示 計算機科學領域有許多算法涉及圖。計算機存儲圖的一種最簡單有效的方法就是矩陣。矩陣是由數字組成的矩陣表格，一般用大寫字母表示。（元素、行、列）。圖論有效地利用了矩陣，將其作為表達圖及其性質的有效工具和手段。 定義10.18 設 G(V, E) 為簡單圖，它有 n 個結點 Vv1, v2, , vn，則 n 階方陣 稱為 G 的鄰接矩陣。 其中 v2v4v5v3v1v2v4v5v3v1無向圖有向圖 如果給定的圖是零圖，則其對應的矩陣中所有的元素都為零，它是一個零矩陣，反之亦然，即鄰接矩陣為零矩陣的圖必是零圖。v1v2v4v3G1v2v1v4v3G2 用圖形表示圖的方法，關于結點間的

2、通路很容易在圖形中看出來，但在鄰接矩陣中就需經過計算。設有向圖 G 的結點集 Vv1, v2, , vn，它的鄰接矩陣為： A(G)(aij)nn，現在我們來計算從結點 vi 到結點 vj 的長度為 2 的路的數目。注意到每條從結點 vi 到結點 vj 的長度為2的路的中間必經過一個結點vk，即vivkvj (1kn)，如果圖中有路 vivkvj 存在，那么 aikakj1，即 aikakj1，反之如果圖 G 中不存在路 vivkvj，那么 aik0 或 akj0，即 aikakj0，于是從結點 vi 到結點 vj 的長度為 2 的路的數目等于： 按照矩陣的乘法規(guī)則，這恰好是矩陣中的第 i 行

3、，第 j 列的元素。表示從結點 vi 到結點 vj 的長度為 2 的路的數目。表示從結點 vi 到結點 vi 的長度為 2 的回路的數目。一般地有上述這個結論對無向圖也成立。定理10.10 設 A(G) 為圖 G 的鄰接矩陣，則 (A(G)l 中的 i 行 j 列元素 等于 G 中連接結點 vi 與 vj 的長度為 l 的路的數目。證明：歸納法證明。 (1) 當 l2 時，由上得知是顯然成立。 (2) 設命題對 l 成立，由 故 【例10.6】給定一圖 G(V, E) 如下圖所示。v3v1v2v4v5解：從矩陣中可以看到，v1 與 v2 之間有兩條長度為 3 的路，結點 v1 與 v3 之間有

4、一條長度為 2 的路，在結點 v2 有四條長度為 4 的回路。 在許多問題中需要判斷有向圖的一個結點 vi 到另一個結點 vj 是否存在路的問題。如果利用圖 G 的鄰接矩陣 A，則可計算 A，A2，A3，An，當發(fā)現其中的某個 Al 的 aij(l)1，就表明結點 vi 到 vj 可達。但這種計算比較繁瑣，且 Al 不知計算到何時為止。從前面得知，如果有向圖 G 有 n 個結點Vv1, v2, , vn vi 到 vj 有一條路，則必有一條長度不超過 n 的通路，因此只要考察 aij(l) 就可以了，其中 1ln。對于有向圖 G 中任意兩個結點之間的可達性，亦可用可達矩陣。定義10.19 令

5、G 是一個簡單有向圖， ，假定 V 的結點已編序，即 Vv1, v2, , vn，定義一個 nn 矩陣 。其中 稱矩陣 P 是圖 G 的可達性矩陣。 【例10.7】求下圖的可達性矩陣。p2p1p3p5p4解：同理可證：由此看出，如果把鄰接矩陣看作是結點集 V 上關系 R 的關系矩陣，則可達性矩陣 P 即為 ，因此可達矩陣亦可用 Warshall 算法計算。 定義10.20 給定無向圖 G，令 v1, v2, , vp 和 e1, e2, , eq 分別記為 G 的結點和邊，則矩陣 M(G)(mij)，其中稱 M(G) 為完全關聯矩陣。無向圖及其完全關聯矩陣 v2v1e3e4e2e1e1e2e3

6、e4v11101v21110V30011v3從關聯矩陣中可以看出圖形的一些性質： （1）圖中每一邊關聯兩個結點，故 M(G) 的每一列只有兩個 1。（2）每一行元素的和數對應于結點的度數。（3）一行中的元素全為 0，其對應的結點為孤立點。（4）兩個平行邊其對應的兩列相同。（5）同一圖當結點或邊的編序不同，其對應 M(G) 僅有行序、列序的差別。 當一個圖是有向圖時，亦可用結點和邊的關聯矩陣來表示。定義10.21 給定簡單有向圖 G，Vv1, v2, , vp，Ee1, e2, eq，pq 階矩陣 M(G)(mij)，其中稱 M(G) 為 G 的關聯矩陣。v2v1e3e4e2e1v3v4e5e1

7、e2e3e4e5v110101v2-11000v30-1-110v4000-1-1簡單有向圖及其完全關聯矩陣 有向圖的完全關聯矩陣也有類于無向圖的一些性質。定義10.22 對圖 G 的完全關聯矩陣中的兩行相加如下：若記 vi 對應的行為 ，將第 i 行與第 j 行相加，規(guī)定為：對有向圖是指對應分量的加法運算，對無向圖是指對應分量的模 2 的加法運算，把這種運算記作 。 執(zhí)行這個運算實際上是對應于把圖 G 的結點 vi 與結點 vj 合并。 設圖 G 的結點 vi 與結點 vj 合并得到圖 G，那么 M(G) 是將 M(G) 中的第 i 行與第 j 行相加而得到。因為若有關項中第 r 個對應分量

8、有 ，則說明 vi 與 vj 兩者之中只有一個結點是邊 er 的端點，且將這兩個結點合并后的結點 vi,j 仍是 er 的端點。 若 則有兩種情況： （1）vi 與 vj 都不是邊 er 的端點，那么 vi, j 也不是 er 的端點。 （2）vi 與 vj 都是邊 er 的端點，那么合并后在 G中 er成為 vi, j 的自回路，按規(guī)則應該被刪去。 此外，在 M(G) 中若有某些列，其元素全為 0，說明 G 中的一些結點合并后，消失了一些對應邊?！纠?0.9】有向圖(a)中合并結點 v2 和 v3。解：合并時，刪去自回路得圖 (b)。其關聯矩陣 M(G) 是由 M(G) 中將第 2 行加到第

9、 3 行上面得到的。e1e2e3e4e5e6E7e8e9v1110000000v2-101000100v300-11000-11v40-10001-110v500001-100-1v6000-1-10000v1e9e4e2e1v2,3v4e5v5e7e6v6e8v2v1e9e4e2e1v3v4e5v5e7e6v6e8e3e1e2e3e4e5e6E7e8e9v1110000000v2-101000100v300-11000-11v40-10001-110v500001-100-1v6000-1-10000e1e2e3e4e5e6E7e8e9v1110000000V2,3-1001001-11v4

10、0-10001-110v500001-100-1v6000-1-10000 由于 M(G1) 是 G1 的完全關聯矩陣，而 G1 是由 G 的兩個結點 vi 和 vj 合并而得到。由于 G 是連通的，故 G1 必為連通圖，M(G1) 也具有連通圖完全關聯矩陣的所有性質，故 M(G1) 沒有全零的行。 如果 M(G1) 的第一列全為零，則可將 M(G1) 的非零列與第一列對調，不影響完全關聯矩陣的秩數。 因此必可以通過調整行序和把一行加到另一行上這兩種運算，使 M(G1) 的第一列首項元素為 1，得到 繼續(xù)上述兩種運算，并不改變矩陣的秩，經過 r1 次，最后將 M(G) 變換成如下矩陣。顯然 M(r1)(G) 有一個(r1) 階子陣，其行列式的值不為 0，故M(r1)(G) 的秩至少為 r1。由 和 可知 rankM(G)r1 10.6 本章小結 本章首先介紹了圖的基本概念，包括：點、邊、點, 邊 序偶等，并根據點與點、邊與邊、邊與點之間的關系定義了鄰接點、鄰接邊、結點的度等概念，在這些概念基礎上定義了圖同構。在圖分類中，依據不同的標準可以將圖分為簡單圖和多重圖、有向圖和無向圖等，學習主要以簡單圖為主。 圖中的另一個基礎就是圖的連通性問題，因為圖結點之間是否有邊連通表明了結點所代表的對象之間是否存在關聯關系。路、