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

第七章圖論引言7.1圖的基本概念7.2路與連通7.3圖的矩陣表示7.4最短路徑問題7.5圖的匹配8.1Euler圖和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ǔ)結(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)的鄰接矩陣?yán)?下圖所示的鄰接矩陣為：A(G)A(G)A(G)A(G)A(G)A(G)相當(dāng)于將單位矩陣中相應(yīng)的行與行，或者列與列互換的矩陣7.3.1鄰接矩陣同構(gòu)圖判別定理：圖G1，G2同構(gòu)的充要條件是：存在置換矩陣P，使得：A1＝PA2P。其中A1，A2分別是G1，G2的鄰接矩陣。如何判斷兩圖同構(gòu)是圖論中一個(gè)困難問題v1v2v3v4圖G1vavbvcvd圖G20111101111011110A1＝12340111101111011110A2＝abcdv1<->vav2<->vbv3<->vcv4<->vd7.3.1鄰接矩陣在鄰接矩陣A的冪A2，A3，…矩陣中，每個(gè)元素有特定的含義。定理:設(shè)G是具有n個(gè)結(jié)點(diǎn)集｛v1，v2，…，vn｝的圖，其鄰接矩陣為A，則Al（l＝1，2，…）的（i，j）項(xiàng)元素a(l)ij是從vi到vj的長度等于l的路的總數(shù)。

證明:歸納法

當(dāng)l＝1時(shí)，A1＝A，由A的定義，定理顯然成立。

若l＝k時(shí)定理成立，

則當(dāng)l＝k＋1時(shí)，Ak+1＝A

·Ak

，所以aij(1)等于G中聯(lián)結(jié)vi與vj的長度為1的路徑條數(shù)。n

aij

(l+1)=aik

×

akj

(l)

k=1vkvivj長度=1長度=l共akj

(l)條7.3.1鄰接矩陣結(jié)論：

(1)如果對(duì)l＝1，2，…，n-1，Al的（i，j）項(xiàng)元素（i≠j）都為零，那么vi和vj之間無任何路相連接，即vi和vj不連通。因此，vi和vj必屬于G的不同的連通分支。

(2)結(jié)點(diǎn)vi

到vj

（i≠j）間的距離d（vi，vj）是使Al（l＝1，2，…，n-1）的（i，j）項(xiàng)元素不為零的最小整數(shù)l。

(3)Al的（i，i）項(xiàng)元素a(l)ii表示開始并結(jié)束于vi長度為l的回路的數(shù)目。7.3.1鄰接矩陣?yán)?圖G＝（V，E）的圖形如圖，求鄰接矩陣A和A2，A3，A4，并分析其元素的圖論意義。解7.3.1鄰接矩陣

(1)由A中a(1)12＝1知，v1和v2是鄰接的；由A3中a(3)12＝2知，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（１）34＝a（２）34＝a（３）34＝a（４）34＝０，所以結(jié)點(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ù)就是行中相應(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.有向圖的鄰接矩陣1、設(shè)有向圖，，的鄰接矩陣，，其中指鄰接到的邊的條數(shù)(非負(fù)整數(shù))。7.3.1圖的矩陣表示有向圖的鄰接矩陣7.3.2鄰接矩陣?yán)?

有向圖(下圖所示)，求。解：7.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)矩陣?yán)?下圖所示的關(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)矩陣1、設(shè)有向圖，，，的關(guān)聯(lián)矩陣，其中7.3.2關(guān)聯(lián)矩陣?yán)?有向圖(下圖所示)，求。解：A(D)A(D)7.3.3有向圖的可達(dá)性矩陣有向圖的可達(dá)性矩陣。(了解)設(shè)為有向圖，，令，可達(dá)性矩陣其中元素可由求得：7.3.3有向