圖的矩陣表示課件

1、 圖的矩陣表示 計(jì)算機(jī)科學(xué)領(lǐng)域有許多算法涉及圖。計(jì)算機(jī)存儲(chǔ)圖的一種最簡(jiǎn)單有效的方法就是矩陣。矩陣是由數(shù)字組成的矩陣表格，一般用大寫(xiě)字母表示。（元素、行、列）。圖論有效地利用了矩陣，將其作為表達(dá)圖及其性質(zhì)的有效工具和手段。 定義10.18 設(shè) G(V, E) 為簡(jiǎn)單圖，它有 n 個(gè)結(jié)點(diǎn) Vv1, v2, , vn，則 n 階方陣 稱(chēng)為 G 的鄰接矩陣。 其中 v2v4v5v3v1v2v4v5v3v1無(wú)向圖有向圖 如果給定的圖是零圖，則其對(duì)應(yīng)的矩陣中所有的元素都為零，它是一個(gè)零矩陣，反之亦然，即鄰接矩陣為零矩陣的圖必是零圖。v1v2v4v3G1v2v1v4v3G2 用圖形表示圖的方法，關(guān)于結(jié)點(diǎn)間的

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

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

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

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

6、e4v11101v21110V30011v3從關(guān)聯(lián)矩陣中可以看出圖形的一些性質(zhì)： （1）圖中每一邊關(guān)聯(lián)兩個(gè)結(jié)點(diǎn)，故 M(G) 的每一列只有兩個(gè) 1。（2）每一行元素的和數(shù)對(duì)應(yīng)于結(jié)點(diǎn)的度數(shù)。（3）一行中的元素全為 0，其對(duì)應(yīng)的結(jié)點(diǎn)為孤立點(diǎn)。（4）兩個(gè)平行邊其對(duì)應(yīng)的兩列相同。（5）同一圖當(dāng)結(jié)點(diǎn)或邊的編序不同，其對(duì)應(yīng) M(G) 僅有行序、列序的差別。 當(dāng)一個(gè)圖是有向圖時(shí)，亦可用結(jié)點(diǎn)和邊的關(guān)聯(lián)矩陣來(lái)表示。定義10.21 給定簡(jiǎn)單有向圖 G，Vv1, v2, , vp，Ee1, e2, eq，pq 階矩陣 M(G)(mij)，其中稱(chēng) M(G) 為 G 的關(guān)聯(lián)矩陣。v2v1e3e4e2e1v3v4e5e1

7、e2e3e4e5v110101v2-11000v30-1-110v4000-1-1簡(jiǎn)單有向圖及其完全關(guān)聯(lián)矩陣 有向圖的完全關(guān)聯(lián)矩陣也有類(lèi)于無(wú)向圖的一些性質(zhì)。定義10.22 對(duì)圖 G 的完全關(guān)聯(lián)矩陣中的兩行相加如下：若記 vi 對(duì)應(yīng)的行為 ，將第 i 行與第 j 行相加，規(guī)定為：對(duì)有向圖是指對(duì)應(yīng)分量的加法運(yùn)算，對(duì)無(wú)向圖是指對(duì)應(yīng)分量的模 2 的加法運(yùn)算，把這種運(yùn)算記作 。 執(zhí)行這個(gè)運(yùn)算實(shí)際上是對(duì)應(yīng)于把圖 G 的結(jié)點(diǎn) vi 與結(jié)點(diǎn) vj 合并。 設(shè)圖 G 的結(jié)點(diǎn) vi 與結(jié)點(diǎn) vj 合并得到圖 G，那么 M(G) 是將 M(G) 中的第 i 行與第 j 行相加而得到。因?yàn)槿粲嘘P(guān)項(xiàng)中第 r 個(gè)對(duì)應(yīng)分量

8、有 ，則說(shuō)明 vi 與 vj 兩者之中只有一個(gè)結(jié)點(diǎn)是邊 er 的端點(diǎn)，且將這兩個(gè)結(jié)點(diǎn)合并后的結(jié)點(diǎn) vi,j 仍是 er 的端點(diǎn)。 若 則有兩種情況： （1）vi 與 vj 都不是邊 er 的端點(diǎn)，那么 vi, j 也不是 er 的端點(diǎn)。 （2）vi 與 vj 都是邊 er 的端點(diǎn)，那么合并后在 G中 er成為 vi, j 的自回路，按規(guī)則應(yīng)該被刪去。 此外，在 M(G) 中若有某些列，其元素全為 0，說(shuō)明 G 中的一些結(jié)點(diǎn)合并后，消失了一些對(duì)應(yīng)邊?！纠?0.9】有向圖(a)中合并結(jié)點(diǎn) v2 和 v3。解：合并時(shí)，刪去自回路得圖 (b)。其關(guān)聯(lián)矩陣 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 的完全關(guān)聯(lián)矩陣，而 G1 是由 G 的兩個(gè)結(jié)點(diǎn) vi 和 vj 合并而得到。由于 G 是連通的，故 G1 必為連通圖，M(G1) 也具有連通圖完全關(guān)聯(lián)矩陣的所有性質(zhì)，故 M(G1) 沒(méi)有全零的行。 如果 M(G1) 的第一列全為零，則可將 M(G1) 的非零列與第一列對(duì)調(diào)，不影響完全關(guān)聯(lián)矩陣的秩數(shù)。 因此必可以通過(guò)調(diào)整行序和把一行加到另一行上這兩種運(yùn)算，使 M(G1) 的第一列首項(xiàng)元素為 1，得到 繼續(xù)上述兩種運(yùn)算，并不改變矩陣的秩，經(jīng)過(guò) r1 次，最后將 M(G) 變換成如下矩陣。顯然 M(r1)(G) 有一個(gè)(r1) 階子陣，其行列式的值不為 0，故M(r1)(G) 的秩至少為 r1。由 和 可知 rankM(G)r1 10.6 本章小結(jié) 本章首先介紹了圖的基本概念，包括：點(diǎn)、邊、點(diǎn), 邊 序偶等，并根據(jù)點(diǎn)與點(diǎn)、邊與邊、邊與點(diǎn)之間的關(guān)系定義了鄰接點(diǎn)、鄰接邊、結(jié)點(diǎn)的度等概念，在這些概念基礎(chǔ)上定義了圖同構(gòu)。在圖分類(lèi)中，依據(jù)不同的標(biāo)準(zhǔn)可以將圖分為簡(jiǎn)單圖和多重圖、有向圖和無(wú)向圖等，學(xué)習(xí)主要以簡(jiǎn)單圖為主。 圖中的另一個(gè)基礎(chǔ)就是圖的連通性問(wèn)題，因?yàn)閳D結(jié)點(diǎn)之間是否有邊連通表明了結(jié)點(diǎn)所代表的對(duì)象之間是否存在關(guān)聯(lián)關(guān)系。路、