第八章圖論-東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院

1、第十四章　圖的基本概念,第四部分：圖論,七橋問題,問題尋找走遍哥尼斯堡（KÖnigsberg）城的7座橋，且只許走過每座橋一次，最后又回到原出發(fā)點(diǎn)求解1736年瑞士大數(shù)學(xué)家歐拉（Leonhard?Euler）發(fā)表了關(guān)于“哥尼斯堡七橋問題”的論文（圖論的第一篇論文）。他指出從一點(diǎn)出發(fā)不重復(fù)的走遍七橋，最后又回到原來出發(fā)點(diǎn)是不可能的。,圖論,圖論是近年來發(fā)展迅速而又應(yīng)用廣泛的一門新興學(xué)科。它最早起源于一些數(shù)學(xué)游戲的難題研究，

2、如1736年歐拉（L.Euler)所解決的哥尼斯堡七橋問題。以及在民間廣為流傳的一些游戲問題：例如迷宮問題、棋盤上馬的行走路線問題,棋盤上馬的行走路線問題,在中國象棋中，馬走“日”字，即每步從 1×2 矩形的一個頂點(diǎn)跳到相對的頂點(diǎn)。如圖，馬從M（3，2）一次只能跳到A、B、C、D、E、F、G、H中的任何一個位置。問題：馬能否從棋盤上任意一點(diǎn)出發(fā)，不重復(fù)、不遺漏地走遍整個棋盤（即每一點(diǎn)都走到并且只到一次）？,棋盤上馬的行走路線

3、問題,將馬目前所在位置涂成白色，用涂色的方法，將棋盤上的點(diǎn)分為黑、白相間的兩類,環(huán)游世界各國的問題,英國數(shù)學(xué)家哈密頓于1859年以游戲的形式提出：把一個正十二面體的二十個頂點(diǎn)看成二十個城市，要求找出一條經(jīng)過每個城市恰好一次而回到出發(fā)點(diǎn)的路線。這條路線就稱“哈密頓圈”。一百多年來，對哈密頓問題的研究，促進(jìn)了圖論的發(fā)展。,四色猜想,問題：任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色用數(shù)學(xué)語言表示，即：“將平面任意地細(xì)分為

4、不相重疊的區(qū)域，每一個區(qū)域總可以用1，2，3，4這四個數(shù)字之一來標(biāo)記，而不會使相鄰的兩個區(qū)域得到相同的數(shù)字”,圖論,圖論不斷發(fā)展，它在解決運(yùn)籌學(xué)，網(wǎng)絡(luò)理論，信息論，控制論，博奕論以及計(jì)算機(jī)科學(xué)等各個領(lǐng)域的問題時，顯示出越來越大的作用,第十四章　圖的基本概念,第一節(jié)：圖 第二節(jié)：通路、回路、圖的連通性　第三節(jié)：圖的矩陣表示和運(yùn)算,第一節(jié)：圖,無序積：設(shè)A，B為任意的兩個集合，稱 {{a,b}

5、 | a∈A且b∈B}為A與B的無序積，記做A&B無向圖：一個無向圖G是一個二重組, 其中V(G)為有限非空結(jié)點(diǎn)（或叫頂點(diǎn)）集合, E(G)是邊的集合，它是無序積V&V的多重子集，其元素為無向邊，簡稱邊。有向圖：一個有向圖G是一個二重組, 其中V(G)為有限非空結(jié)點(diǎn)（或叫頂點(diǎn)）集合, E(G)是邊的集合，它是笛卡兒乘積V×V的多重子集，其元素為有向邊，簡稱邊。,下面定義一些專門名詞：（１）通常用G表示無

6、向圖，D表示有向圖，但G也可以泛指圖。V(G)，E(G)分別表示G的頂點(diǎn)集和邊集。|V(G)|,|E(G)|分別表示G的頂點(diǎn)數(shù)和邊數(shù)， 若|V(G)|＝n，則稱G為n階圖。（２）若|V(G)|,|E(G)|均為有限數(shù)，則稱G為有限圖。（３）若圖G中，邊集為空，則稱之為零圖， 若G為n階圖，則稱之為n階零圖，記為Nn， N1稱為平凡圖。（4）頂點(diǎn)集為空的圖記為空圖。,第一節(jié)：圖,一些定義,（5）稱頂點(diǎn)或邊

7、用字母標(biāo)定的圖為標(biāo)定圖，否則成為非標(biāo)定圖。另外，將有向邊改為無向邊后的圖稱為原圖的基圖。（6）設(shè)G=為無向圖，ek=(vi,vj)∈E,則稱vi,vj為ek的端點(diǎn)， ek與vi或ek與vj是彼此關(guān)聯(lián)的。 若vi≠vj，則稱ek與vi或ek與vj的關(guān)聯(lián)次數(shù)為1， 若vi=vj，則稱ek與vi的關(guān)聯(lián)次數(shù)為2，并稱為環(huán)。任意的vl∈V，若vl≠vi且vl≠vj，則稱ek與vl的關(guān)聯(lián)次數(shù)為0。,一些定義,（7）設(shè)無向圖G=，v

8、i,vj∈V， ek,el∈E。若存在et∈E，使得et=(vi,vj)，則稱vi與vj是相鄰的。若ek與el至少有一個公共端點(diǎn)，則稱ek與el是相鄰的。 有向圖D=，vi,vj∈V，ek,el∈E 。若存在et∈E，使得et=，則稱vi為et的始點(diǎn)，vj為et的終點(diǎn)，并稱vi鄰接到vj，vj鄰接于vi，若ek的終點(diǎn)為el的始點(diǎn)，則稱ek與el相鄰。,一些定義,（8）設(shè)無向圖G=，對所有的v∈V稱為v的鄰域，記為NG(v)

9、，并稱NG(v) ∪{v}為v的閉鄰域，記為 。稱 為v的關(guān)聯(lián)集，記為IG(v) 。設(shè)有向圖G=，對所有的v∈V ，稱為v的后繼元素。稱為v的先驅(qū)元素。稱兩者之并為v的鄰域，記為ND(v) 。稱ND(v) ∪{v}，v的閉鄰域。,一些定義,定義14.3 在無向圖中，關(guān)聯(lián)一對頂點(diǎn)的無向邊如果多于一條，則稱這些邊為平行邊，平

10、行邊的條數(shù)稱為重?cái)?shù)。 在有向圖中，關(guān)聯(lián)一對頂點(diǎn)的有向邊如果多于一條，并且這些邊的始點(diǎn)和終點(diǎn)相同，則稱這些邊為平行邊。 含平行邊的圖稱為多重圖，即不含平行邊也不含環(huán)的圖稱為簡單圖。,一些定義,非多重圖稱為線圖。由定義可見，簡單圖是沒有環(huán)和平行邊的圖。,一些定義,定義14.4：在無向圖中，任意點(diǎn)其作為邊的端點(diǎn)次數(shù)之和稱為該點(diǎn)的度數(shù)，記為dG(v). 在有向圖中，對于任何結(jié)點(diǎn)v，以v為始點(diǎn)的邊的條數(shù)，稱為結(jié)點(diǎn)v的引出

11、次數(shù)(或出度)，記作d+(v)；以v點(diǎn)為終點(diǎn)的邊的條數(shù)稱為v的引入次數(shù)(或入度)，記作d－(v)；結(jié)點(diǎn)的v的引入次數(shù)和引出次數(shù)之和稱為v的次數(shù)（度數(shù)），用d (v)表示。由定義可見:度數(shù)d (v)＝d+(v)＋d－(v)。定義：最大度，最小度，最大出度，最大入度，最小入度，最小出度，懸掛點(diǎn)，懸掛邊,例　1,例：

12、 d (a)＝３(引入)+２(引出)=5 d（b）＝４ d（c）＝３ d（1）＝３ d（2）＝３ d（3）＝２,以后為了敘

13、述方便，我們將具有n個結(jié)點(diǎn)和m條邊的圖簡稱為（n,m）圖,握手定理,定理14.1（握手定理）：設(shè)G是（n, m）無向圖，它的頂點(diǎn)集合Ｖ＝｛v1,v2,…,vn｝，于是有,證明：∵在無向圖中引入一條邊，總的次數(shù)增２，　　　∴若有m條邊，則總次數(shù)為2m。　?。ù硕ɡ硪部赏茝V到有向圖和混合圖）定理14.1 在有向圖中，則為：,例 2,d（a）＝４， d（b）＝３，

14、 d（c）＝４， d（d）＝３, 　 m＝７，2m＝１４＝Σd　 Σd ＝３+４+３+４ ＝１４,例 3,例：若圖Ｇ有n個頂點(diǎn),（n+1）條邊，則Ｇ中至少有一個頂點(diǎn)的度數(shù)≥３。證明：設(shè)Ｇ中有n個結(jié)點(diǎn)分別為v1,v2,…,vn，則由握手定理：　　 Σd（vi）＝２（n+1）而頂點(diǎn)

15、的平均度數(shù)為： d（vi）＝２(n+1)/n=2+1/n>2 　　　∴頂點(diǎn)中至少有一個頂點(diǎn)的度數(shù)≥３,握手定理的推論,推論：在圖中，度數(shù)為奇數(shù)的頂點(diǎn)必定有偶數(shù)個。 證明：設(shè)度數(shù)為偶數(shù)的頂點(diǎn)有n1個,記為vei(i=1,2,…n1),度數(shù)為奇數(shù)的頂點(diǎn)有n2個，記為voi(i=1,2,…,n2)。由上一定理得因?yàn)槎葦?shù)為偶數(shù)的各頂點(diǎn)次數(shù)之和為偶數(shù)。所以前一項(xiàng)度數(shù)為偶數(shù)；若n2為奇數(shù)，則第二項(xiàng)為奇數(shù)，兩項(xiàng)之和將為奇數(shù)，但這

16、與上式矛盾。故n2必為偶數(shù)。問題：是否在一個部門的25個人中間，由于意見不同，每個人恰好與5個人意見一致？,可圖化、可簡單圖化,設(shè)G=為一個n階無向圖，V＝｛v1,v2,…,vn｝，稱d(v1),d(v2)…d(vn) 為G的度數(shù)列。對于頂點(diǎn)標(biāo)定的無向圖，它的度數(shù)列是唯一的。 反之，對于給定的非負(fù)整數(shù)列d=(d1,d2,…,dn),若存在以V＝｛v1,v2,…,vn｝為頂點(diǎn)集的n階無向圖G，使得d(vi)=di，則稱d是可圖

17、化的。 特別的，如果所得圖是簡單圖，則稱d是可簡單圖化的。,可圖化的判斷定理,定理14.3 設(shè)非負(fù)整數(shù)列d=(d1,d2,…,dn), 則d是可圖化的當(dāng)且僅當(dāng) 證明：必要性顯然 充分性：構(gòu)造性證明定理14.4 設(shè)G為任意n階無向簡單圖，則△(G) ≤n-1,可圖化,例：判斷下列各非負(fù)整數(shù)列哪些是可圖化的？哪些是可簡單圖化的？(5,5,4,4,2,1)(5,4,3,2,2)

18、(3,3,3,1)(d1,d2,…,dn), d1>d2>…>dn≥1, 且 為偶數(shù)(4,4,3,3,2,2),同構(gòu)的定義,定義14.5：設(shè)Ｇ＝〈Ｖ，Ｅ〉和Ｇ’＝〈Ｖ’，Ｅ’〉是兩個圖，若存在從Ｖ到Ｖ’一雙射函數(shù)ｇ：Ｖ→Ｖ’，使得對任意的a,b∈V,[a,b] ∈E當(dāng)且僅當(dāng)[g(a),g(b)]∈Ｅ’ ，并且[a,b]和[g(a),g(b)]有相同的重?cái)?shù)，則稱Ｇ’和Ｇ同構(gòu)。討論定義：（1）Ｇ’

19、和Ｇ是同構(gòu)的,它們的頂點(diǎn)必須是一一對應(yīng)的；（2）且對無向圖而言，還要保持頂點(diǎn)之間的鄰接關(guān)系和邊的重?cái)?shù)；（3）且對有向圖而言，不但要保持頂點(diǎn)之間的鄰接關(guān)系，而且還應(yīng)保持邊的方向和邊的重?cái)?shù)。圖的同構(gòu)關(guān)系可以看作是全體圖集合上的二元關(guān)系，并且此關(guān)系是等價關(guān)系。,例4,例： 存在一雙射函數(shù)ｇ:{1,2,3,4}→｛a3,a4,a2,a1｝，其中：頂點(diǎn)的一一對應(yīng)： g(1)= a3; g(2)= a4; g

20、(3)= a2; g(4)= a1;邊的一一對應(yīng)：　　 g＝; g＝; g＝; g＝,例 5,例:下面給出二個無向圖，試求出同構(gòu)函數(shù),ｇ：｛1,2,3,4,5,6｝→｛ a1,a2,a3,a4,a5,a6｝邊的對應(yīng)為：g((i,j))＝(g(i),g(j))＝｛ai,aj｝,同構(gòu)的性質(zhì),兩圖同構(gòu)的必要條件：（1）頂點(diǎn)數(shù)相等；（2）邊數(shù)相等；（3）度數(shù)相同的頂點(diǎn)數(shù)相等。但這不是充分條件。如下圖,完全圖

21、,定義14.6：在ｎ個頂點(diǎn)的有向圖G=中，如果每個頂點(diǎn)都鄰接到其余的n-1個頂點(diǎn)，又鄰接于其余的n-1個頂點(diǎn)，則稱G為有向完全圖；在ｎ個頂點(diǎn)的無向圖G=中，每二個頂點(diǎn)之間均有一條邊連接，則稱G為無向完全圖。,特殊圖,定義14.7：所有頂點(diǎn)均具有同樣度數(shù)的簡單無向圖為正則圖，各頂點(diǎn)的度數(shù)均為k時稱為k－正則圖。,子圖的定義,定義14.8:設(shè)Ｇ=,Ｇ’=是二個圖， (a)若Ｖ’?Ｖ，Ｅ’?Ｅ，則稱Ｇ’是Ｇ的子圖； (b)若Ｖ’?Ｖ，

22、Ｅ’?Ｅ，并且Ｇ≠Ｇ’，則稱Ｇ’是Ｇ的真子圖； (c)若Ｖ’＝Ｖ，Ｅ’?Ｅ,則稱Ｇ’是Ｇ的生成子圖（支撐子圖）。 (d)若子圖G’中沒有孤立頂點(diǎn)，G’由E’唯一確定，則稱G’為由邊集E’導(dǎo)出的子圖。 (e)若在子圖G’中，對Ｖ’中的任意二頂點(diǎn)u,v，當(dāng)[u,v]∈E時有[u,v]∈E’，則G’由Ｖ’唯一確定，此時稱G’為由頂點(diǎn)集Ｖ’導(dǎo)出的子圖。,例 6,例：Ｇ圖如下 Ｇ的真子圖 生成子圖：,E’={,,,}導(dǎo)

23、出的子圖,由V’={a,b,d,e}導(dǎo)出的子圖,例 7,例 畫出4階3邊的所有非同構(gòu)的無向簡單圖。解：由握手定理可知，該無向簡單圖各頂點(diǎn)度數(shù)之和為6，最大度小于或等于3。于是所求無向簡單圖的度數(shù)列應(yīng)滿足的條件是，將6分成4個非負(fù)數(shù)，每個整數(shù)均大于等于0且小于等于3，并且奇數(shù)的個數(shù)為偶數(shù)。有三種情況3，1，1，1；2，2，1，1；2，2，2，0將每種度數(shù)列所有非同構(gòu)的圖都畫出來即可得所要求的全部非同構(gòu)圖。,補(bǔ)圖,定義14.9:設(shè)

24、無向簡單圖G= 有n個頂點(diǎn)，無向簡單圖H= 也有同樣的頂點(diǎn)，而E’是由n個頂點(diǎn)的完全圖的邊刪去E所得，則圖H稱為圖G的補(bǔ)圖。 自補(bǔ)圖：H與G同構(gòu),例 8,例：試畫出5個頂點(diǎn)三條邊和5個頂點(diǎn)七條邊的簡單無向圖。解： 5個頂點(diǎn)三條邊的圖,5個頂點(diǎn)七條邊的圖（為5頂點(diǎn)三條邊的補(bǔ)圖）,圖的操作,關(guān)于圖的四種操作：（1）刪去Ｇ中的一條邊e；（2）刪去Ｇ中的一個頂點(diǎn)（即是刪去頂點(diǎn)ｖ和與ｖ有關(guān)聯(lián)的所有邊）。（3）設(shè)邊e=(

25、u,v)∈E，用G\e表示從G中刪除e后，將e的兩個端點(diǎn)u,v用一個新的頂點(diǎn)w代替，使w關(guān)聯(lián)e以外u,v關(guān)聯(lián)的所有邊，稱為e的收縮。（4）設(shè)u,v∈V，用G∪(u,v)表示在u,v之間加一條邊(u,v)，稱為新加邊。,第十四章　圖的基本概念,第二節(jié)：通路、回路、圖的連通性,14.2 通路和回路,定義14.11: 在有向圖中，從某一頂點(diǎn)出發(fā)經(jīng)過某些點(diǎn)邊交替序列到達(dá)終點(diǎn)，此序列稱為通路。而經(jīng)過的各條邊之間沒有相同的通路稱為簡單通路。

26、如果通路中頂點(diǎn)各不相同且邊也各不相同，則稱為初級通路或路徑。如果通路的起點(diǎn)和終點(diǎn)重合，稱此通路為回路。沒有相同邊的回路稱為簡單回路，沒有相同邊也沒有相同點(diǎn)（除起始點(diǎn)和終止點(diǎn)外）的回路稱為圈。,14.2 通路和回路,討論：（1）從一個頂點(diǎn)到某一頂點(diǎn)的通路（若有的話）不一定是唯一的；（2）通路的表示方法：(a)邊點(diǎn)序列表示法： 設(shè)Ｇ＝＜Ｖ，Ｅ＞為一有向圖，vi∈V，則通路可以表示成：（v1,e1,v2,e2,v3,……vk-1

27、,en,vk）(b)也可僅用邊的序列表示(c)頂點(diǎn)表示法(在簡單圖中)：（ v1, v2 ,… vk） (3)無向圖中的以上術(shù)語的定義完全類似，不再重復(fù)。,例 1,例：給出有向圖Ｇ,求起始于１,終止于３的通路。 P1=(1,2,3)=(,) P2=(1,2,3,4,3)

28、 P3=(1,4,3) P4=(1,2,4,1,2,3) P5=(1,2,4,1,4,3) P6=(1,…,1,2,3),…可見：（1）從1到3有無限條通路，∵中間有回路；（2）上例中的P1 ，P2， P3， P5為簡單通路。,通路的性質(zhì),定義:

29、通路P中邊的條數(shù)稱為通路P的長度（路長）。長度為0的通路定義為一個單獨(dú)的頂點(diǎn)。定理14.5:設(shè)圖Ｇ＝＜Ｖ，Ｅ＞，ｎ是Ｖ中的頂點(diǎn)數(shù)（即｜Ｖ｜＝ｎ），如果從v1到v2(v1≠v2)有一條通路，則從v1到v2有一條長度不大于n-1的通路。 推論:設(shè)圖Ｇ＝＜Ｖ，Ｅ＞，ｎ是Ｖ中的頂點(diǎn)數(shù)（即｜Ｖ｜＝ｎ），如果從v1到v2(v1≠v2)有一條通路，則從v1到v2有一條長度不大于n-1的初級通路（路徑）。,通路和回路的性質(zhì),定理14.6：在ｎ階圖中

30、，從vi到vi如果存在一條回路的話，則從vi到vi一定存在一條長度小于或等于ｎ的回路。推論：在ｎ階圖中，從vi到vi如果存在一條簡單回路的話，則從vi到vi一定存在一條長度小于或等于ｎ的初級回路。,通路和回路,例： 1. 無向完全圖Kn（n≥3）中有幾種非同構(gòu)的圈？ 2. 無向完全圖K3的頂點(diǎn)依次標(biāo)定為a，b，c. 在定義意義下K3中有多少 不同的長度為3的圈？,14.3 圖的連通性,定義14.1

31、2：設(shè)無向圖Ｇ=，且vi,vj∈V，若從vi到vj存在一條通路的話，則稱vi，vj是連通的。一般認(rèn)為vi到自身是連通的。由定義可見：連通的概念與vi到vj之間的通路多少、通路長度、是什么樣的通路沒有任何關(guān)系。,14.3 圖的連通性,連通性一定滿足：（１）自反性：∵ vi到vi一定是連通的。（２）可傳遞性： vi到vj連通，vj到vk連通，那么vi到vk連通。（３）對于有向圖而言，既不一定對稱，也不一定反對稱。 ∵若vi到vj

32、存在一條通路的話，則vj到vi未必存在一條通路。（連通性對無向圖滿足自反、對稱和可傳遞性）,連通圖,定義14.12：對于無向圖中的任何頂點(diǎn)來講，若任何二個頂點(diǎn)是相互連通的，則稱此圖是連通的，否則稱為非連通圖或分離圖。,連通分支,定義14.13：設(shè)無向圖G=，V關(guān)于頂點(diǎn)之間的連通關(guān)系～的商集V/～={V1,V2,…, Vk}，Vi為等價類，稱導(dǎo)出子圖G[Vi](i=1,2,…,k)為G的連通分支，連通分支數(shù)k常記為p(G)。一個無向

33、圖或者是一個連通圖，或者是由若干個連通分支組成,距離,定義14.14: 在無向圖G=中，從頂點(diǎn)vi到vj最短通路（短程線）的長度，叫做從vi到vj的距離，記為d(vi, vj) 。若從vi到vj不存在通路，則d(vi, vj) =∞注意：在無向圖中，有以下性質(zhì)：1) d(vi, vj) ≥0 2) d(vi, vi) = 03) d(vi, vj)=d(vj, vi) 4) d(vi, vj) +d(vj,

34、 vk) ≥ d(vi, vk),點(diǎn)割集、割點(diǎn),定義14.15 設(shè)無向圖 G= 。若存在 使得p(G-V’) >p(G)，且有任意的　　　　均有p(G-V’’) =p(G)，則稱V’為G的點(diǎn)割集。若是單個點(diǎn)，則稱割點(diǎn)。定義14.16 設(shè)無向圖 G= 。若存在 使得p(G-E’) >p(G)，且有任意的　　　　均有p(G-E’’) =p(G)，則稱E’為G的邊割集。若是單個邊，則稱

35、割邊或者橋。點(diǎn)連通度　k-連通圖 注意：若G是k-連通圖，則在G中刪除任何k-1個頂點(diǎn)后，所得圖一定還是連通的邊連通度 r邊-連通圖,點(diǎn)連通度、邊連通度的關(guān)系,對于任何無向圖G，有,距離,定義14.19：設(shè)有向圖Ｇ=，且vi,vj∈V，若從vi到vj存在一條通路的話，則稱vi可達(dá)vj。一般認(rèn)為vi到自身是可達(dá)的。若vi可達(dá)vj并且vj可達(dá)vi，則稱vi,vj相互可達(dá)。定義14.20: 在有向圖G=中，從頂點(diǎn)v

36、i到vj最短通路（短程線）的長度，叫做從vi到vj的距離，記為d(vi, vj) 。若從vi到vj不存在通路，則d(vi, vj) =∞。,連通性,定義14.22：在有向圖中，它的基圖若是連通的，則稱此有向圖為弱連通的；若圖中任何頂點(diǎn)偶對中至少有一點(diǎn)到另一頂點(diǎn)是可達(dá)的，則稱此圖是單向連通的；如果任兩頂點(diǎn)均是互相可達(dá)的，則稱是強(qiáng)連通的。討論定義：（1）強(qiáng)連通的一定是單向連通的和弱連通的；（2）單向連通的一定是弱連通的；（3）弱連

37、通的既可能不是單向連通的，更可能不是強(qiáng)連通的。,連通性,強(qiáng)連通的 　 單向連通的　　弱連通的,圖的連通性,定理14.8 設(shè)有向圖D=，V＝｛v1,v2,…,vn｝ 。D是強(qiáng)連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點(diǎn)至少一次的回路。證明：充分性顯然　　　必要性（構(gòu)造性證明）定理14.9 設(shè)D是n階有向圖。D是單向連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點(diǎn)至少一次的通路。,二部圖,定義14.23:如果無向圖的頂點(diǎn)集V分成兩個子集X,Y,(即滿

38、足X∩Y=Φ,X∪Y=V),使得G中任意一邊的兩個端點(diǎn)分屬于X和Y,則稱G為二部圖,X和Y稱為互補(bǔ)頂點(diǎn)子集,常記圖為G=。 定義:若二部圖G=中X的每個頂點(diǎn)與Y的每個頂點(diǎn)都有且只有一條邊相關(guān)聯(lián),稱G為完全二部圖,記為Km,n,其中|X|=m,|Y|=n。,例　4,,子集X={a,b},Y={x,y,z},這是一個二部圖。,這是完全二部圖K2,3。,二部圖,此兩圖均是K3,3因而是同構(gòu)的 定理14.10:無向圖G是二部圖的充要條件

39、是G的所有回路的長度均為偶數(shù)。,第十四章　圖的基本概念,第三節(jié)：圖的矩陣表示和運(yùn)算,圖的矩陣表示,矩陣是研究圖的有關(guān)性質(zhì)的最有效的工具之一，可運(yùn)用圖的矩陣運(yùn)算求出圖的通路、回路和其它一些性質(zhì)。前面討論圖的圖解表示法的優(yōu)點(diǎn)是直觀，但缺點(diǎn)是：（1）在結(jié)點(diǎn)較多時，用圖表示十分繁雜，甚至沒法表示；（2）計(jì)算機(jī)中難以貯存。本節(jié)討論用矩陣表示圖能較好的克服以上二大缺點(diǎn)。,圖的矩陣表示,定義14.23 設(shè)無向圖G＝，V={v1,v2,…,vn

40、}，E={e1,e2,…,em}，令mij為頂點(diǎn)vi與邊ej的關(guān)聯(lián)次數(shù)，則稱(mij)n×m為G的關(guān)聯(lián)矩陣，記做M(G)。1） M(G)每列元素之和均為2。2） M(G)第i行元素之和為vi的度數(shù)。3）各頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍4）第j列與第k列相同當(dāng)且僅當(dāng)邊ej和ek是平行邊。5） 　　當(dāng)且僅當(dāng)vi是孤立點(diǎn),圖的矩陣表示,定義14.24 設(shè)有向圖D＝中無環(huán)，V={v1,v2,…,vn}，E={e

41、1,e2,…,em}，令mij＝ 1 vi為ej的始點(diǎn) 0 vi與ej不關(guān)聯(lián) －1 vi為ej的終點(diǎn)則稱(mij)n×m為G的關(guān)聯(lián)矩陣，記做M(D)。1）M(D)中所有元素之和為0。2）M(D)中，-1的個數(shù)等于+1的個數(shù)，都等于邊數(shù)m。3）第i行中，+1的個數(shù)等于d+(vi)，-1的個數(shù)等于d-(vi)。4）平行邊所對應(yīng)的列相同。

42、,圖的矩陣表示,定義14.25：設(shè)D＝＜Ｖ，Ｅ＞是有向圖，其中V={v1,v2,…,vn}，并假定各結(jié)點(diǎn)已經(jīng)有從v1到vn的排列次序。定義一個n×n的矩陣A，并把其中各元素aij表示成： aij = vi鄰接到 vj 邊的條數(shù)則稱矩陣A為圖G的鄰接矩陣。例：設(shè)圖D＝＜Ｖ，Ｅ＞如下圖所示，其中 V={v1,v2, v3,v4},圖的矩陣表示,討論定義：（1）若圖D的鄰接矩陣中的元素為0和1，又稱為布爾矩陣。（2）圖

43、D的鄰接矩陣中的元素的次序是無關(guān)緊要的，只要進(jìn)行行和行、列和列的交換，則可得到相同的矩陣。,圖的矩陣表示,（3）當(dāng)有向圖中的有向邊表示關(guān)系時，鄰接矩陣就是關(guān)系矩陣；若圖是自反的，則主對角線的元素均為1；若圖是對稱的，則對于i和j有aij=aji，主對角線的元素不論。,圖的矩陣表示,（4）零圖的鄰接矩陣稱為零矩陣，即矩陣中的所有元素均為0；（5）在有向圖的鄰接矩陣中：①行中1的個數(shù)就是行中相應(yīng)頂點(diǎn)的出度②列中1的個數(shù)就是列中相應(yīng)

44、頂點(diǎn)的入度,d+(1)=1,d-(1)=2 d+(2)=2,d-(2)=2 d+(3)=3,d-(3)=1 d+(4)=1,d-(4)=2,A(D)中所有元素之和為D中長度為1的通路的條數(shù)對角線元素之和為D中長度為1的回路的條數(shù)考慮：A(D)的n次冪表示什么？,圖的矩陣表示,圖的矩陣表示,*矩陣的計(jì)算（有向圖中）： 設(shè)：,令,其含義為：①若ai1×a1j＝1，則表示有i→1→j長度為2的通路；②A2表示i

45、和j之間具有長度為2的不同通路的條數(shù)，,A3表示i和j之間具有長度為3的不同通路的條數(shù)，A4表示i和j之間具有長度為4的不同通路的條數(shù)。,,例,從2→1有二條長度為2的通路；,從3→1有二條長度為3的通路;,從2→1有二條長度為4的通路；,圖的矩陣表示,定理14.11：設(shè)Ｇ＝＜Ｖ，Ｅ＞，|V|=ｎ，A為G的鄰接矩陣，則Am的元素表示（i ,j）之間具有長度為m的不同通路數(shù)，（i ,j）表示矩陣Am中的一個記入值。（長度為m的路徑條數(shù)）

46、推論：設(shè)Ｇ＝＜Ｖ，Ｅ＞，|V|=ｎ，二個頂點(diǎn)之間的距離d(vi,vj)可以從A1,A2,…, An中去求得，當(dāng)（i ,j）記入值不為零且矩陣的冪次最小時，這個冪次即是d(vi,vj) 。由推論1可以求得一個圖的距離矩陣。,例,圖的矩陣表示,推論：Bn = A1＋A2＋…＋An表示i到j(luò)之間的長度小于等于n的所有通路數(shù)， A1表示長度為1的通路數(shù)。 …… An表示長度為n的通路數(shù)。（注意：Bn是A1,A2,…, An中各對應(yīng)

47、位數(shù)字相加之和）,圖的矩陣表示,定義14.27：設(shè)D＝＜Ｖ，Ｅ＞是有向圖，其中|V|=ｎ，假定D中各結(jié)點(diǎn)是有序的，定義一個n×n矩陣P，它的元素為：,則P稱為圖D的可達(dá)性矩陣。,圖的矩陣表示,討論定義：①可達(dá)性矩陣中的元素為0和1，∴它是布爾矩陣；②可達(dá)性矩陣只能表示vi到vj有無通路，而不能指明存在的所有通路，這和鄰接矩陣是不相同的；③可達(dá)性矩陣P并沒有表達(dá)出每一個元素自身可達(dá)的概念，若實(shí)際情況需要，可規(guī)定：主對角線上

48、的元素均用1表示（∵自己到自己是可達(dá)的）,圖的矩陣表示,下面介紹可達(dá)性矩陣的求法：其方法是：若Bn-1中（i ,j）是非“0”元素，則對應(yīng)的Pi,j=1，否則Pi,j =0。 例：,圖的矩陣表示,由定義：若,由B3可得：,表示任何結(jié)點(diǎn)之間是可達(dá)的。,圖的運(yùn)算,定義14.29：設(shè)圖G1=和圖G2=（１）G1和G2的并，定義為圖G3= ，其中E3＝E1∪E2, V3為E1∪E2中邊關(guān)聯(lián)的頂點(diǎn)集，記為G3＝G1∪G2。（２）G1