第7章+圖論-3(圖的矩陣表示).ppt

1、第七章 圖論,引言 7.1 圖的基本概念 7.2 路與連通 7.3 圖的矩陣表示 7.4 最短路徑問題 7.5 圖的匹配 8.1 Euler圖和Hamilton圖 8.2 樹 8.3 生成樹 8.4 平面圖,7.3 圖的矩陣表示,圖的矩陣表示 圖的數(shù)學(xué)抽象是三元組，其形象直觀的表示即圖的圖形表示。為便于計(jì)算，特別為便于用計(jì)算機(jī)處理圖，下面介紹圖的第三種表示方法圖的矩陣表示。利用矩陣的運(yùn)算還可以了解到它的一些有關(guān)性質(zhì)。,內(nèi)容：關(guān)聯(lián)矩陣，鄰接矩陣，可達(dá)矩陣。,重點(diǎn)：1、有向圖，無向圖的關(guān)聯(lián)矩陣，,2、有向圖的鄰接矩陣。,了解：有向圖的可達(dá)矩陣。,7.3.1 圖的矩陣表示,鄰接矩陣,存儲(chǔ)原則: 存儲(chǔ)

2、結(jié)點(diǎn)集和邊集的信息.,（1）存儲(chǔ)結(jié)點(diǎn)集； （2）存儲(chǔ)邊集： 存儲(chǔ)每兩個(gè)結(jié)點(diǎn)是否有關(guān)系。,7.3.1 鄰接矩陣,1.無向圖的鄰接矩陣,定義 1.6.2設(shè) 的頂點(diǎn)集為 ，用 表示 中頂點(diǎn) 與 之間的邊數(shù)。稱矩陣 為 的鄰接矩陣。,從圖的鄰接矩陣的定義容易得出以下性質(zhì)： 是一個(gè)對(duì)稱矩陣； 若 為無環(huán)圖。則 中第 行(列)的元素之和等于頂點(diǎn) 的度數(shù)； (3) 兩個(gè)圖 與 同構(gòu)的充要條件是存在一個(gè)置換矩陣 ，使得 。,對(duì)應(yīng)的鄰接矩陣,例2下圖所示 的鄰接矩陣為：,A(G),A(G),A(G),A(G),A(G),A(G),相當(dāng)于將單位矩陣中相應(yīng)的行與行，或者列與列互換的矩陣,7.3.1 鄰接矩陣,同構(gòu)圖

3、 判別定理：圖G1 ，G2同構(gòu)的充要條件是：存在置換矩陣P，使得：A1PA2P。 其中A1，A2分別是G1 ，G2的鄰接矩陣。 如何判斷兩圖同構(gòu)是圖論中一個(gè)困難問題,7.3.1 鄰接矩陣,在鄰接矩陣A的冪A2， A3， 矩陣中， 每個(gè)元素有特定的含義。 定理 :設(shè)G是具有n個(gè)結(jié)點(diǎn)集v1， v2， ， vn 的圖， 其鄰接矩陣為A， 則Al（l1， 2， ）的（i， j）項(xiàng)元素a(l)ij是從vi到vj的長度等于l的路的總數(shù)。 證明 : 歸納法 當(dāng)l1時(shí)， A1A， 由A的定義， 定理顯然成立。 若lk時(shí)定理成立， 則當(dāng)lk1時(shí)， A k+1 A Ak ，,所以,aij (1)等于G中聯(lián)結(jié)vi與

4、vj的長度為1的路徑條數(shù)。,n aij (l+1) = aik akj (l) k=1,vk,vi,vj,長度=1,長度=l,共akj (l)條,7.3.1 鄰接矩陣,結(jié)論： (1) 如果對(duì)l1， 2， ， n-1， Al的（i， j）項(xiàng)元素（ij）都為零， 那么vi和vj之間無任何路相連接， 即vi和vj不連通。 因此， vi和vj必屬于G的不同的連通分支。 (2) 結(jié)點(diǎn)vi 到vj （ij）間的距離d（vi， vj）是使Al（l1， 2， ， n-1 ）的（i， j）項(xiàng)元素不為零的最小整數(shù)l。 (3) Al的（i， i）項(xiàng)元素a(l)ii表示開始并結(jié)束于vi長度為l的回路的數(shù)目。,7.3.

5、1 鄰接矩陣,例1 圖G（V， E）的圖形如圖， 求鄰接矩陣A和A2， A3， A4， 并分析其元素的圖論意義。 解,7.3.1 鄰接矩陣,(1) 由A中a(1)121知， v1和v2是鄰接的； 由A3中a(3)122知， v1到v2長度為3的路有兩條， 從圖中可看出是v1 v2 v1 v2和v1 v2 v3 v2 。 (2) 由A2的主對(duì)角線上元素知， 每個(gè)結(jié)點(diǎn)都有長度為的回路， 其中結(jié)點(diǎn)v2有兩條： v2 v1 v2和v2 v3 v2 ， 其余結(jié)點(diǎn)只有一條。 (3) 由于A3的主對(duì)角線上元素全為零， 所以G中沒有長度為的回路。 (4) 由于a（）34a（）34a（）34a（）34， 所以結(jié)

6、點(diǎn)v3和v4間無路， 它們屬于不同的連通分支。 (5) d（v1， v3）。 對(duì)其他元素讀者自己可以找出它的意義。,7.3.1 鄰接矩陣,設(shè)圖，如下圖所示,討論 （1）圖G的鄰接矩陣中的元素為0和1，又稱為布爾矩陣； （2）圖G的鄰接矩陣中的元素的次序是無關(guān)緊要的，進(jìn)行行和行、列和列的交換，則得到相同矩陣。 若有二個(gè)簡單有向圖，則可得到二個(gè)對(duì)應(yīng)的鄰接矩陣，若對(duì)某一矩陣進(jìn)行行和行、列和列之間的交換后得到和另一矩陣相同的矩陣，則此二圖同構(gòu)。 （3）當(dāng)有向圖中的有向邊表示關(guān)系時(shí)，鄰接矩陣就是關(guān)系矩陣； （4）零圖的鄰接矩陣稱為零矩陣，即矩陣中的所有元素均為0； （5）在圖的鄰接矩陣中， 行中1的個(gè)數(shù)

7、就是行中相應(yīng)結(jié)點(diǎn)的引出次數(shù) 列中1的個(gè)數(shù)就是列中相應(yīng)結(jié)點(diǎn)的引入次數(shù),7.3.1 鄰接矩陣,矩陣的計(jì)算：,主對(duì)角線上的數(shù)表 示結(jié)點(diǎn)i（或j）的 引出次數(shù)。,主對(duì)角線上的數(shù)表示結(jié)點(diǎn)i（或j）的引入次數(shù)。,7.3.1 鄰接矩陣,表示i和j之間具有長度為2的通路數(shù)， 表示i和j之間具有長度為3的通路數(shù)， 表示i和j之間具有長度為4的通路數(shù)，,7.3.1 鄰接矩陣,bij表示從結(jié)點(diǎn)vi到vj有長度分別為1，2，3，4的不同通路總數(shù)。 此時(shí)， bij0，表示從vi到vj是可達(dá)的。,7.3.1 鄰接矩陣,2.有向圖的鄰接矩陣,7.3.1 圖的矩陣表示,有向圖的鄰接矩陣,7.3.2 鄰接矩陣,例1,解：,7.

8、3.2 關(guān)聯(lián)矩陣,關(guān)聯(lián)矩陣多用于簡單無向圖 無向圖的關(guān)聯(lián)矩陣,一個(gè)圖 由它的頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系唯一確定；,定義 1.6.1 設(shè) 的頂點(diǎn)集和邊集分別為 ， 。用 表示頂點(diǎn) 與邊 關(guān)聯(lián)的次數(shù)(0，1或2)，稱矩陣 為 的關(guān)聯(lián)矩陣。,7.3.2 關(guān)聯(lián)矩陣,例1,下圖所示 的關(guān)聯(lián)矩陣為：,對(duì)應(yīng)的關(guān)聯(lián)矩陣,從圖的關(guān)聯(lián)矩陣的定義容易得出以下性質(zhì)： 的每一列元素之和均為2； 的每一行元素之和等于對(duì)應(yīng)頂點(diǎn)的度數(shù)。 若某行元素全為0，則對(duì)應(yīng)的頂點(diǎn)為孤立點(diǎn)。 重邊所對(duì)應(yīng)的列完全相同。,=,7.3.2 關(guān)聯(lián)矩陣,有向圖的關(guān)聯(lián)矩陣,其中,7.3.2 關(guān)聯(lián)矩陣,例2,解：,A(D),A(D),7.3.3 有向圖的可達(dá)性矩陣,有向圖的可達(dá)性矩陣。(了解),可達(dá)性矩陣,7.3.3 有向圖的可達(dá)性矩陣,根據(jù)可達(dá)性矩陣， 可知圖中任意兩個(gè)結(jié)點(diǎn)之間