圖的矩陣表示_第1頁
圖的矩陣表示_第2頁
圖的矩陣表示_第3頁
圖的矩陣表示_第4頁
圖的矩陣表示_第5頁
已閱讀5頁,還剩86頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

關(guān)于圖的矩陣表示第一頁,共九十一頁,編輯于2023年,星期日圖的矩陣表示由于矩陣的行和列有固定的次序,因此在用矩陣表示圖時,先要將圖的結(jié)點(diǎn)進(jìn)行排序,若不具體說明排序,則默認(rèn)為書寫集合V時結(jié)點(diǎn)的順序。

用圖形表示圖是圖論的一種表示方法。它的優(yōu)點(diǎn)是形象直觀,但是這種表示在結(jié)點(diǎn)與邊的數(shù)目很多時是不方便的。在學(xué)習(xí)中常常需要分析圖并在圖上執(zhí)行各種過程和算法,也許必須用計算機(jī)來執(zhí)行這些算法,因此必須把圖的結(jié)點(diǎn)和邊傳輸給計算機(jī),由于集合與圖形都不適合計算機(jī)處理,所以要找到一種新的表示圖的方法,這就是圖的矩陣表示。利用這種方法,我們能把圖用矩陣存儲在計算機(jī)中,利用矩陣的運(yùn)算還可以了解到它的一些有關(guān)性質(zhì)。第二頁,共九十一頁,編輯于2023年,星期日第六章圖的矩陣表示一個圖可以按定義描述出來,也可以用圖形表示出來,還可以同二元關(guān)系一樣,用矩陣來表示。圖用矩陣表示有很多優(yōu)點(diǎn),既便于利用代表知識研究圖的性質(zhì)、構(gòu)造算法,也便于計算機(jī)處理。圖的矩陣表示常用的有兩種形式:鄰接矩陣和關(guān)聯(lián)矩陣。鄰接矩陣常用于研究圖的各種道路的問題,關(guān)聯(lián)矩陣常用于研究子圖的問題。由于矩陣的行列有固定的順序,因此在用矩陣表示圖之前,需將圖的結(jié)點(diǎn)和邊加以編號(定序),以確定與矩陣元素的對應(yīng)關(guān)系。3第三頁,共九十一頁,編輯于2023年,星期日

本章的教學(xué)內(nèi)容6.1關(guān)聯(lián)矩陣6.2圈矩陣6.3割集矩陣6.5圖的鄰接矩陣

第四頁,共九十一頁,編輯于2023年,星期日圖的矩陣表示計算機(jī)科學(xué)領(lǐng)域有許多算法涉及圖。計算機(jī)存儲圖的一種最簡單有效的方法就是矩陣。矩陣是由數(shù)字組成的矩陣表格,一般用大寫字母表示。(元素、行、列)。圖論有效地利用了矩陣,將其作為表達(dá)圖及其性質(zhì)的有效工具和手段。

第五頁,共九十一頁,編輯于2023年,星期日6.1無向圖的完全關(guān)聯(lián)矩陣定義

給定無向圖G,令v1,v2,…,vp,e1,e2,…,eq分別記為M(G)的頂點(diǎn)和邊,則矩陣M(G)=(mij)p×q,其中稱M(G)為圖G的完全關(guān)聯(lián)矩陣。第六頁,共九十一頁,編輯于2023年,星期日例

下圖G的完全關(guān)聯(lián)矩陣為:

v1v2v3v4v5e1e2e3e4第七頁,共九十一頁,編輯于2023年,星期日實例1例1求下圖的完全關(guān)聯(lián)矩陣。e1e2e3e4e5e6v1110011v2111000v3001101v4000110v5000000第八頁,共九十一頁,編輯于2023年,星期日無向圖的完全關(guān)聯(lián)矩陣有下列性質(zhì):(1)M(G)中每列恰有兩個1,即每條邊與兩個頂點(diǎn)關(guān)聯(lián);(2)每一行元素之和等于對應(yīng)頂點(diǎn)的度數(shù);(3)M(G)中元素之和等于G中頂點(diǎn)的度數(shù)總和;(4)多重邊對應(yīng)的列相同;(5)若G有w個連通分支G1,G2,?,Gw,則有準(zhǔn)分塊對角陣第九頁,共九十一頁,編輯于2023年,星期日e5e4e3e2e1e6v5v1v4v3v2第十頁,共九十一頁,編輯于2023年,星期日課堂思考題:一個圖的完全關(guān)聯(lián)矩陣是不是唯一的?完全關(guān)聯(lián)矩陣是不是唯一的確定一個圖?用完全關(guān)聯(lián)矩陣來表示圖有什么好處?圖的哪些性質(zhì)可以從完全關(guān)聯(lián)矩陣上一目了然?矩陣的運(yùn)算是否會有相應(yīng)的圖的變化?反過來,圖的哪些變化對應(yīng)著完全關(guān)聯(lián)矩陣的哪些變化?第十一頁,共九十一頁,編輯于2023年,星期日一般地說,我們把一個n階方陣A的某些列作一置換,再把相應(yīng)的行作同樣的置換,得到一個新的n階方陣A’,我們稱A和A’為置換等價。按不同次序所寫出來的鄰接矩陣是彼此置換等價的,今后我們略去這種元素次序的任意性,可取任何一個鄰接矩陣作為該圖的矩陣表示。第十二頁,共九十一頁,編輯于2023年,星期日課堂練習(xí)1

1、寫出下圖所示無向圖的完全關(guān)聯(lián)矩陣v2v3e2v4e5e4e3e1v1第十三頁,共九十一頁,編輯于2023年,星期日有向圖的關(guān)聯(lián)矩陣定義

給定簡單有向圖D=<V,E>,V={v1,v2,…,vp},E={e1,e2,…,eq},p×q階矩陣M(D)=(mij)p×q,其中稱M(G)為D的完全關(guān)聯(lián)矩陣。第十四頁,共九十一頁,編輯于2023年,星期日v1v2v3v4e6e1e2e3e5e4第十五頁,共九十一頁,編輯于2023年,星期日例

求下圖的完全關(guān)聯(lián)矩陣e1e2e3e4e5e6e7v11000111v2-1100000v30-1100-10v400-1100-1v5000-1-100第十六頁,共九十一頁,編輯于2023年,星期日有向圖的完全關(guān)聯(lián)矩陣的性質(zhì)(4)平行邊對應(yīng)的列相同。(5)不能表示自環(huán)。第十七頁,共九十一頁,編輯于2023年,星期日v2v3e2v4e5e4e3e1v1第十八頁,共九十一頁,編輯于2023年,星期日完全關(guān)聯(lián)矩陣的秩定理

如果連通圖G有p個頂點(diǎn),則其完全關(guān)聯(lián)矩陣的秩為p-1,即rankM(G)=p-1。證明

對無向圖進(jìn)行證明

(1)因為M(G)中的每一列只有兩個1,若把M(G)的其余所有行加到最后一行上,則最后一行全為0(模2的運(yùn)算,相當(dāng)于各點(diǎn)鄰集的環(huán)合),故rankM(G)≤p-1。

第十九頁,共九十一頁,編輯于2023年,星期日(2)應(yīng)用行變換使得M(G)第1列(邊e)中的1個非零元在第1行第1列的位置,然后把第1行加到第1列另一個非零元所在行上,使得第1列中只有在首行上為1,其余全為0,得到矩陣M’(G)。第二十頁,共九十一頁,編輯于2023年,星期日v2v3e2v4e5e4e3e1v1v3v4e2e5e4e3V1,v2第二十一頁,共九十一頁,編輯于2023年,星期日由于G1是將M(G)的第1行與另一個首個元素為1的行加起來,對應(yīng)的是將圖的兩個頂點(diǎn)放在一起,因此G1必是連通圖,所以M’(G1)中沒有全零行。若M’(G1)的第1列全零,則將M’(G1)中的非零列與它對換,然后再用交換行和一行加到另一行,使M’(G1)中第1列首元素為1,其余元素為零,得到M’’(G),如圖所示第二十二頁,共九十一頁,編輯于2023年,星期日第二十三頁,共九十一頁,編輯于2023年,星期日繼續(xù)上述過程,并不改變矩陣秩,最終在經(jīng)過p-1次,將M(G)變換成M(p-1)(G),如上圖所示,顯然rankM(G)=rankM(p-1)(G)≥p-1。綜上所述,有rankM(G)=p-1。第二十四頁,共九十一頁,編輯于2023年,星期日例

計算完全關(guān)聯(lián)矩陣M(G)的秩。e1e2e3e4e5e6e7v10000011v20001110v30111000v41100000v51010101(4)(1)第二十五頁,共九十一頁,編輯于2023年,星期日(1)(5)(2)(3)(2)(5)(3)(4)第二十六頁,共九十一頁,編輯于2023年,星期日(3)(5)(4)(6)(4)(5)這個矩陣的秩為4,即rankM(G)=5-1=4。第二十七頁,共九十一頁,編輯于2023年,星期日推論推論

設(shè)圖G有p個結(jié)點(diǎn),k個連通分支,則圖G完全關(guān)聯(lián)矩陣的秩為p-k。證明

設(shè)圖G有p個結(jié)點(diǎn),k個連通分支,則通過對M(G)進(jìn)行行交換和列交換,總能得到如下分塊矩陣。第二十八頁,共九十一頁,編輯于2023年,星期日其中M(Gi)是連通子圖Gi的關(guān)聯(lián)矩陣,其對應(yīng)的結(jié)點(diǎn)個數(shù)設(shè)為pi。rank

M(Gi)=pi-1,則rank

M(G)=(p1-1)+(p2-1)+…+(pk-1)=p-k第二十九頁,共九十一頁,編輯于2023年,星期日v2v3e2v4e5e4e3e1v1圖的完全關(guān)聯(lián)矩陣可以去掉一行,改稱關(guān)聯(lián)矩陣,去掉那一行所對應(yīng)的點(diǎn)稱為參考點(diǎn)。完全關(guān)聯(lián)矩陣v1為參考點(diǎn)關(guān)聯(lián)矩陣第三十頁,共九十一頁,編輯于2023年,星期日定義:連通圖G=(p,q)的一個階為min{p,q}的方陣稱為p×q矩陣的一個大子陣,大子陣的行列式稱為大行列式。第三十一頁,共九十一頁,編輯于2023年,星期日定理:連通圖G的關(guān)聯(lián)矩陣M的一個大子陣是非奇異的充要條件是與這個大子陣的列相應(yīng)的邊,組成G的一顆生成樹.第三十二頁,共九十一頁,編輯于2023年,星期日v2v3e2v4e5e4e3e1v1第三十三頁,共九十一頁,編輯于2023年,星期日v2v3e2v4e5e4e3e1v1生成樹的邊數(shù)為頂點(diǎn)數(shù)4-1=3,因此若對應(yīng)的邊是一棵生成樹(連通圖的秩為頂點(diǎn)數(shù)減1)其秩必為3(樹中有4個頂點(diǎn)3條邊且是連通圖,)第三十四頁,共九十一頁,編輯于2023年,星期日第三十五頁,共九十一頁,編輯于2023年,星期日6.5圖的鄰接矩陣第三十六頁,共九十一頁,編輯于2023年,星期日鄰接矩陣

定義

設(shè)G=<V,E>是一個無向簡單圖,它有p個頂點(diǎn)V={v1,v2,…,vp},則p階方陣A(G)=(aij)稱為G的鄰接矩陣,其中第三十七頁,共九十一頁,編輯于2023年,星期日v1v4v2v3第三十八頁,共九十一頁,編輯于2023年,星期日e2e5v1v2v3v4e1e4e3

第三十九頁,共九十一頁,編輯于2023年,星期日例已知無向圖的鄰接矩陣如下,試畫出相應(yīng)的無向圖。v1v6v5v4v3v2第四十頁,共九十一頁,編輯于2023年,星期日

10.已知圖G的鄰接矩陣如下請畫出G的圖形。第四十一頁,共九十一頁,編輯于2023年,星期日v1v6v5v4v3v2解:畫法:先確定結(jié)點(diǎn)再用行確定邊。第四十二頁,共九十一頁,編輯于2023年,星期日有向圖的鄰接矩陣

設(shè)有向圖D=<V,E>的頂點(diǎn)集V={v1,v2,…,vp}則n階方陣A(D)=(aij)p×p稱為D的鄰接矩陣,其中第四十三頁,共九十一頁,編輯于2023年,星期日v4v3v2v1第四十四頁,共九十一頁,編輯于2023年,星期日v1v4v3v2第四十五頁,共九十一頁,編輯于2023年,星期日課堂練習(xí):寫出下圖所示有向圖的鄰接矩陣v2v3e2v4e5e4e3e1v1第四十六頁,共九十一頁,編輯于2023年,星期日鄰接矩陣的性質(zhì)無向簡單圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣不一定對稱。鄰接矩陣與結(jié)點(diǎn)的標(biāo)定順序有關(guān),不同標(biāo)定順序?qū)?yīng)的鄰接矩陣是彼此置換等價的。在無向圖的鄰接矩陣中,第i行中非零元的個數(shù)等于vi的度,第i列中非零元的個數(shù)等于vi的度。在有向圖的鄰接矩陣中,第i行中所有元素之和等于vi的出度,第i列中所有元素之和等于vi的入度。第四十七頁,共九十一頁,編輯于2023年,星期日

由鄰接矩陣的定義可知,鄰接矩陣是表示圖的頂點(diǎn)之間相鄰關(guān)系的矩陣,無向圖的鄰接矩陣是對稱矩陣,而有向圖的鄰接矩陣則未必是對稱矩陣;當(dāng)G為有k個連通分支G1,G2,?,Gk的分離圖時,適當(dāng)調(diào)整頂點(diǎn)的順序,則鄰接矩陣為準(zhǔn)分塊對角陣。第四十八頁,共九十一頁,編輯于2023年,星期日例試寫出下圖所示圖G的鄰接矩陣。v1v2v5v4v3v6分析首先將圖中的6個結(jié)點(diǎn)排序,然后利用定義9.2.2寫出其鄰接矩陣。初學(xué)時可先在矩陣的行與列前分別按結(jié)點(diǎn)排序標(biāo)上結(jié)點(diǎn),若第i行前的結(jié)點(diǎn)到第j列前的結(jié)點(diǎn)有邊相連,則在鄰接矩陣的第i行第j列元素為1,否則為0。若結(jié)點(diǎn)排序為v1v2v3v4v5v6,則可標(biāo)記如下:解若結(jié)點(diǎn)排序為v1v2v3v4v5v6,則其鄰接矩陣第四十九頁,共九十一頁,編輯于2023年,星期日說明由例題可看出,圖G=<V,E>的鄰接矩陣依賴于V中元素的次序。對于V中各元素不同的排序,可得到同一圖G的不同鄰接矩陣。但是,G的任何一個鄰接矩陣可以從G的另一鄰接矩陣中通過交換某些行和相應(yīng)的列而得到,其交換過程與將一個排序中的結(jié)點(diǎn)交換位置變?yōu)榱硪粋€排序是一致的。如果我們略去由結(jié)點(diǎn)排序不同而引起的鄰接矩陣的不同,則圖與鄰接矩陣之間是一一對應(yīng)的。因此,我們略去這種由于V中元素的次序而引起的鄰接矩陣的任意性,只選V中元素的任一種次序所得出的鄰接矩陣,作為圖G的鄰接矩陣。第五十頁,共九十一頁,編輯于2023年,星期日如圖所示G,其鄰接矩陣A為顯然無向圖的鄰接矩陣必是對稱的。

下面的定理說明,在鄰接矩陣A的冪A2,A3,…等矩陣中,每個元素有特定的含義。第五十一頁,共九十一頁,編輯于2023年,星期日利用鄰接矩陣計算兩點(diǎn)間途徑的數(shù)目定理

設(shè)A(G)是圖G的鄰接矩陣,則(A(G))l中的i行,j列元素aij(l)等于G中聯(lián)結(jié)vi與vj的長度為l的途徑的數(shù)目。

分析:(1)A(G)中所有元素之和為G中長度為1的路的數(shù)目。

第五十二頁,共九十一頁,編輯于2023年,星期日(2)G中有長度為2的路vivkvj存在aik=akj=1,所以從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj的長度為2的路的數(shù)目等于第五十三頁,共九十一頁,編輯于2023年,星期日v2v3e2v4e5e4e3e1v1v1v3v2v4第五十四頁,共九十一頁,編輯于2023年,星期日v2v3e2v4e5e4e3e1v1第五十五頁,共九十一頁,編輯于2023年,星期日第五十六頁,共九十一頁,編輯于2023年,星期日v2v3e2v4e5e4e3e1v1第五十七頁,共九十一頁,編輯于2023年,星期日v2v3e2v4e5e4e3e1v1v1v3v2v4v1v3v2v4第五十八頁,共九十一頁,編輯于2023年,星期日利用鄰接矩陣計算途徑的數(shù)目從vi到vj的長度為l的路,可以看成是由vi到vk的一條長度為1的路和vk到vj的一條長度為l-1的路合成,所以vi到vj的長度為l的路的數(shù)目為:第五十九頁,共九十一頁,編輯于2023年,星期日

由定理可得出以下結(jié)論:

1)如果對l=1,2,…,n-1,Al的(i,j)項元素(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)項元素不為零的最小整數(shù)l。

3)Al的(i,i)項元素a(l)ii表示開始并結(jié)束于vi長度為l的回路的數(shù)目。第六十頁,共九十一頁,編輯于2023年,星期日例8.8

圖G=<V,E>的圖形如圖8.17所示,求鄰接矩陣A和A2,A3,A4,并分析其元素的圖論意義。解:寫出A的鄰接矩陣,并求出A2,A3,A4如下,第六十一頁,共九十一頁,編輯于2023年,星期日第六十二頁,共九十一頁,編輯于2023年,星期日

1)由A中a(1)12=1知,v1和v2是鄰接的;由A3中a(3)12=2知,v1到v2長度為3的路有兩條,從圖中可看出是v1v2v1v2和v1v2v3v2。

2)由A2的主對角線上元素知,每個結(jié)點(diǎn)都有長度為2的回路,其中結(jié)點(diǎn)v2有兩條:v2v1v2和v2v3v2,其余結(jié)點(diǎn)只有一條。

第六十三頁,共九十一頁,編輯于2023年,星期日4)由于

所以結(jié)點(diǎn)v3和v4間無路,它們屬于不同的連通分支。

5)d(v1,v3)=2。

由于A3的主對角線上元素全為零,所以G中沒有長度為3的回路。

第六十四頁,共九十一頁,編輯于2023年,星期日e2e5v1v2v3v4e1e4e3

例1設(shè)G=(V,E)為簡單有無圖,如下圖,確定v1到v2有多少條長度為3的途徑?v1到v3有多少條長度為2的路?v2到自身長度為3回路各多少條?第六十五頁,共九十一頁,編輯于2023年,星期日e2e5v1v2v3v4e1e4e3第六十六頁,共九十一頁,編輯于2023年,星期日例2

給定圖G=<V,E>,求v1到v3的長度為1,2,3,4的路的數(shù)目。經(jīng)過v2的回路共有多少條?第六十七頁,共九十一頁,編輯于2023年,星期日v1到v3的長度為1的路有0條v1到v3的長度為2的路有1條v1到v3的長度為3的路有0條v1到v3的長度為4的路有2條經(jīng)過v2的回路共有a22(2)+a22(3)+a22(4)=2+0+4=6第六十八頁,共九十一頁,編輯于2023年,星期日基于鄰接矩陣的其它矩陣第六十九頁,共九十一頁,編輯于2023年,星期日1.賦權(quán)圖的鄰接矩陣

定義

設(shè)G=<V,E>是一個賦權(quán)圖,它有p個頂點(diǎn)V={v1,v2,…,vp},則p階方陣A(G)=(aij)稱為賦權(quán)圖G的鄰接矩陣,其中其中wij是邊(vi,vj)

上的權(quán)值,∞表示頂點(diǎn)i和j之間沒有邊相連.第七十頁,共九十一頁,編輯于2023年,星期日25v1v2v3v4436第七十一頁,共九十一頁,編輯于2023年,星期日

定義

G=<V,E>是一個簡單有向圖,假定V的頂點(diǎn)已編序,即V={v1,v2,…,vp},定義一個

p×p

矩陣P=P(pij)。其中

稱矩陣P是圖G

的可達(dá)性矩陣。

2.可達(dá)性矩陣第七十二頁,共九十一頁,編輯于2023年,星期日在定義中,規(guī)定了有向圖的任何結(jié)點(diǎn)自己和自己可達(dá)。所以可達(dá)性矩陣P(G)的主對角線元素全為1??蛇_(dá)性矩陣用來描述有向圖的一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)是否有路,即是否可達(dá)。無向圖也可以用矩陣描述一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)是否有路。在無向圖中,如果結(jié)點(diǎn)之間有路,稱這兩個結(jié)點(diǎn)連通。由可達(dá)性矩陣的定義知,當(dāng)i≠j時,如果vi到vj有路,則=1;如果vi到vj無路,則=0;又可知,如果vi到vj有路,則必存在長度小于等于p–1的路。第七十三頁,共九十一頁,編輯于2023年,星期日用圖G的鄰接矩陣A(G)的冪矩陣來求圖G的可達(dá)性矩陣P:先計算Bp–1=A+A2+…+Ap–1,設(shè)Bp–1=()p×p。若≠0,則令=1,若=0,則令pij=0,i,j=1,…,p。第七十四頁,共九十一頁,編輯于2023年,星期日Vv1v3v1v2v3v4第七十五頁,共九十一頁,編輯于2023年,星期日v1v2v3v4第七十六頁,共九十一頁,編輯于2023年,星期日3.度對角矩陣的定義設(shè)G是一個簡單圖,頂點(diǎn)集合V={v1,v2,…,vp},定義p階方陣稱為G的度對角矩陣,其中,第七十七頁,共九十一頁,編輯于2023年,星期日圖G和它的度對角矩陣v2v3e2v4e5e4e3e1v1第七十八頁,共九十一頁,編輯于2023年,星期日e2e5v1v2v3v

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論