離散數(shù)學(xué)圖論

1、第八章 圖論ABCD一一. . 圖的概念圖的概念 一個(gè)圖一個(gè)圖 G=, 其中其中 V(G): 是是G的結(jié)點(diǎn)的非空集合的結(jié)點(diǎn)的非空集合. (V(G),簡(jiǎn)記成簡(jiǎn)記成V. E(G): 是是G的邊的集合的邊的集合. 有時(shí)簡(jiǎn)記成有時(shí)簡(jiǎn)記成E.v 結(jié)點(diǎn)結(jié)點(diǎn)(Vertices): 用用 表示表示, 旁邊標(biāo)上該結(jié)點(diǎn)的名稱(chēng)旁邊標(biāo)上該結(jié)點(diǎn)的名稱(chēng).v 邊邊(Edges): 有向邊有向邊: 帶箭頭的弧線(xiàn)帶箭頭的弧線(xiàn).從從u到到v的邊表示成的邊表示成 無(wú)向邊無(wú)向邊:不帶箭頭的弧線(xiàn)不帶箭頭的弧線(xiàn).u和和v間的邊表示成間的邊表示成 (u,v)r w eV(G1)=r,e,wE(G1)=,A B C De1e5e7e6e3e

2、4e2G1 :G2 :V(G2)=A,B,C,DE(G2)=e1,e2,e3,e4,e5,e6,e7 8-1. 圖的基本概念在圖中在圖中, 結(jié)點(diǎn)的相對(duì)位置、邊的曲直、長(zhǎng)短無(wú)關(guān)緊要結(jié)點(diǎn)的相對(duì)位置、邊的曲直、長(zhǎng)短無(wú)關(guān)緊要.v鄰接點(diǎn)鄰接點(diǎn): 與一邊關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)與一邊關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn). v鄰接邊鄰接邊: 關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的兩條邊關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的兩條邊. v環(huán)環(huán):只關(guān)聯(lián)一個(gè)結(jié)點(diǎn)的邊只關(guān)聯(lián)一個(gè)結(jié)點(diǎn)的邊. v平行邊平行邊:在兩個(gè)結(jié)點(diǎn)之間關(guān)聯(lián)的多條邊在兩個(gè)結(jié)點(diǎn)之間關(guān)聯(lián)的多條邊. v二二. 有向圖與無(wú)向圖有向圖與無(wú)向圖 有向圖有向圖:只有有向邊的圖只有有向邊的圖. 無(wú)向圖無(wú)向圖:只有無(wú)向邊的圖只有無(wú)向邊的圖.三三

3、. 零圖與平凡圖零圖與平凡圖 孤立結(jié)點(diǎn)孤立結(jié)點(diǎn):不與任何邊關(guān)聯(lián)的結(jié)點(diǎn)不與任何邊關(guān)聯(lián)的結(jié)點(diǎn). 零圖零圖:僅由一些孤立結(jié)點(diǎn)構(gòu)成的圖僅由一些孤立結(jié)點(diǎn)構(gòu)成的圖. 即此圖的邊的集合即此圖的邊的集合E= 平凡圖平凡圖:僅由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的零圖僅由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的零圖. |V(G)|=1, |E(G)|=0 u uv abvabce1e2四四. 簡(jiǎn)單圖與多重圖簡(jiǎn)單圖與多重圖 簡(jiǎn)單圖簡(jiǎn)單圖:不含有環(huán)和平行邊的圖不含有環(huán)和平行邊的圖. 多重圖多重圖: 含有平行邊的圖含有平行邊的圖. 五五. 圖中結(jié)點(diǎn)圖中結(jié)點(diǎn)v的度的度: 1.定義定義:G是個(gè)圖是個(gè)圖, vV(G), 結(jié)點(diǎn)結(jié)點(diǎn)v所關(guān)聯(lián)邊數(shù)所關(guān)聯(lián)邊數(shù),稱(chēng)之為結(jié)稱(chēng)

4、之為結(jié)點(diǎn)點(diǎn)v的度的度. 記作記作 deg(v).(或或d(v).deg(a)=3 deg(b)=5 deg(c)=4 deg(d)=2 一個(gè)環(huán)給結(jié)點(diǎn)的度是一個(gè)環(huán)給結(jié)點(diǎn)的度是2. 2.圖的結(jié)點(diǎn)度序列圖的結(jié)點(diǎn)度序列:令令G=是圖是圖, V=v1,v2,v3,vn, 則稱(chēng)則稱(chēng): (der(v1), der(v2),der(v3), ,der(vn) 為圖為圖G的結(jié)點(diǎn)度序的結(jié)點(diǎn)度序列列.例如上圖的結(jié)點(diǎn)度序列為例如上圖的結(jié)點(diǎn)度序列為:(3,5,4,2) 3.圖的最大度圖的最大度(G)與最小度與最小度(G) :G=是圖是圖, (G) =maxdeg(v)|vG (G) =mindeg(v)|vGA B C

5、 De1e5e7e6e3e4e2 cb a c a b d4. 定理定理8-1.1 每個(gè)圖中所有結(jié)點(diǎn)度總和等于邊數(shù)的每個(gè)圖中所有結(jié)點(diǎn)度總和等于邊數(shù)的2倍倍.即即證明證明:因?yàn)閳D中每條邊關(guān)聯(lián)兩個(gè)結(jié)點(diǎn)因?yàn)閳D中每條邊關(guān)聯(lián)兩個(gè)結(jié)點(diǎn),因此每條邊給予它所因此每條邊給予它所關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)的度各是關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)的度各是1, 即一條邊對(duì)應(yīng)的度數(shù)是即一條邊對(duì)應(yīng)的度數(shù)是2, 所所以整個(gè)圖的度數(shù)總和為邊數(shù)的以整個(gè)圖的度數(shù)總和為邊數(shù)的2倍倍.定理定理8-1.2(握手定理握手定理)每個(gè)圖中每個(gè)圖中,奇數(shù)度的結(jié)點(diǎn)必為偶數(shù)奇數(shù)度的結(jié)點(diǎn)必為偶數(shù)個(gè)個(gè).(一次集會(huì)中一次集會(huì)中,與奇數(shù)個(gè)人握手的人與奇數(shù)個(gè)人握手的人,必是偶數(shù)個(gè)必是偶

6、數(shù)個(gè).)證明證明:令令G=是圖是圖,將將V分成兩個(gè)子集分成兩個(gè)子集V1 和和V2,其中其中 V1 -是度數(shù)是奇數(shù)的結(jié)點(diǎn)集合是度數(shù)是奇數(shù)的結(jié)點(diǎn)集合, V2 -是度數(shù)是偶數(shù)的結(jié)點(diǎn)集合是度數(shù)是偶數(shù)的結(jié)點(diǎn)集合 也是偶數(shù)也是偶數(shù), 于是奇數(shù)度的結(jié)點(diǎn)數(shù)是偶數(shù)于是奇數(shù)度的結(jié)點(diǎn)數(shù)是偶數(shù).deg(v)=2|E|vVdeg(v) + deg(v) =2|E|vV1 vV2而而deg(v)是偶數(shù)是偶數(shù)vV2所以所以deg(v)vV1六六. k-正則圖正則圖:一個(gè)無(wú)向簡(jiǎn)單圖一個(gè)無(wú)向簡(jiǎn)單圖G中中,如果如果(G)=(G)=k則稱(chēng)則稱(chēng)G為為k-正則圖正則圖.課堂練習(xí)課堂練習(xí):1.下面哪些數(shù)的序列下面哪些數(shù)的序列,可能是一個(gè)

7、圖的度數(shù)序列可能是一個(gè)圖的度數(shù)序列?如果可能如果可能,請(qǐng)?jiān)嚠?huà)出它的圖請(qǐng)?jiān)嚠?huà)出它的圖. 哪些可能不是簡(jiǎn)單圖哪些可能不是簡(jiǎn)單圖? a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4)2.已知無(wú)向簡(jiǎn)單圖已知無(wú)向簡(jiǎn)單圖G中中,有有10條邊條邊,4個(gè)個(gè)3度結(jié)點(diǎn)度結(jié)點(diǎn),其余結(jié)點(diǎn)的其余結(jié)點(diǎn)的度均小于或等于度均小于或等于2,問(wèn)問(wèn)G中至少有多少個(gè)結(jié)點(diǎn)中至少有多少個(gè)結(jié)點(diǎn)?為什么為什么? 1. a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4)解解:a)不是不是, 因?yàn)橛腥齻€(gè)數(shù)字是奇數(shù)因?yàn)橛腥齻€(gè)數(shù)字是奇數(shù). b) 可能是可能是,如下圖所示如下

8、圖所示: c) 可能是可能是,如下圖所示如下圖所示:2.解解:已知邊數(shù)已知邊數(shù)|E|=10, deg(v)=2|E|=20其中有其中有4個(gè)個(gè)3度結(jié)點(diǎn)度結(jié)點(diǎn), 余下結(jié)點(diǎn)度之和為余下結(jié)點(diǎn)度之和為: 20-34=8因?yàn)橐驗(yàn)镚是簡(jiǎn)單圖是簡(jiǎn)單圖, 其余每個(gè)結(jié)點(diǎn)度數(shù)其余每個(gè)結(jié)點(diǎn)度數(shù)2, 所以至少還有所以至少還有4個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn). 所以所以G中至少有中至少有8個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn). 七七. 有向圖結(jié)點(diǎn)的出度和入度有向圖結(jié)點(diǎn)的出度和入度:(in degree out degree) G=是有向圖是有向圖,vV v的出度的出度: 從結(jié)點(diǎn)從結(jié)點(diǎn)v發(fā)出的邊數(shù)發(fā)出的邊數(shù). 記作記作deg+(v) 或或 dego(v) v的入度

9、的入度: 指向結(jié)點(diǎn)指向結(jié)點(diǎn)v的邊數(shù)的邊數(shù). 記作記作deg-(v) 或或 degi(v)degi(a)=2 degi(b)=2 degi(c)=1 degi(d)=1dego(a)=2 dego(b)=3 dego(c)=1 dego(d)=0定理定理8-1.3 G=是有向圖是有向圖, 則則G的所有結(jié)點(diǎn)的出度之的所有結(jié)點(diǎn)的出度之和等于入度之和和等于入度之和.證明證明: 因?yàn)閳D中每條邊對(duì)應(yīng)一個(gè)出度和一個(gè)入度因?yàn)閳D中每條邊對(duì)應(yīng)一個(gè)出度和一個(gè)入度. 所以所有結(jié)點(diǎn)的出度之和與所有結(jié)點(diǎn)的入度之和都等于所以所有結(jié)點(diǎn)的出度之和與所有結(jié)點(diǎn)的入度之和都等于有向邊數(shù)有向邊數(shù).必然有所有結(jié)點(diǎn)的出度之和等于入度之和必

10、然有所有結(jié)點(diǎn)的出度之和等于入度之和.a bc d八八. 完全圖完全圖1.無(wú)向完全圖無(wú)向完全圖 定義定義:G是個(gè)簡(jiǎn)單圖是個(gè)簡(jiǎn)單圖, 如果每對(duì)不同結(jié)點(diǎn)之間都有邊相連如果每對(duì)不同結(jié)點(diǎn)之間都有邊相連則稱(chēng)則稱(chēng)G是個(gè)完全圖是個(gè)完全圖. n個(gè)結(jié)點(diǎn)的無(wú)向完全圖個(gè)結(jié)點(diǎn)的無(wú)向完全圖G記作記作Kn.定理定理8-1.4 無(wú)向完全圖無(wú)向完全圖Kn, 有邊數(shù)有邊數(shù)證明證明: 因?yàn)橐驗(yàn)镵n中每個(gè)結(jié)點(diǎn)都與其余中每個(gè)結(jié)點(diǎn)都與其余n-1個(gè)結(jié)點(diǎn)關(guān)聯(lián)個(gè)結(jié)點(diǎn)關(guān)聯(lián) 即每個(gè)結(jié)點(diǎn)的度均為即每個(gè)結(jié)點(diǎn)的度均為n-1所以所以Kn的所有結(jié)點(diǎn)度數(shù)總和為的所有結(jié)點(diǎn)度數(shù)總和為n(n-1) 設(shè)邊數(shù)為設(shè)邊數(shù)為|E| 于是于是n(n-1)=2|E| 所以所以|

11、E|= K2K3K4K5) 1(21nn) 1(21nn2. 有向圖的完全圖有向圖的完全圖 (注注:這里的定義與教材不同這里的定義與教材不同) 1).有向簡(jiǎn)單完全圖有向簡(jiǎn)單完全圖:G是個(gè)是個(gè)有向簡(jiǎn)單圖有向簡(jiǎn)單圖,如果任何兩個(gè)如果任何兩個(gè)不不同同結(jié)點(diǎn)之間都有結(jié)點(diǎn)之間都有相互連接相互連接的邊的邊,則稱(chēng)它是有向簡(jiǎn)單完全則稱(chēng)它是有向簡(jiǎn)單完全圖圖.例如例如: 定理定理8-1.5: 有有n個(gè)結(jié)點(diǎn)的有向簡(jiǎn)單完全圖有邊數(shù)為個(gè)結(jié)點(diǎn)的有向簡(jiǎn)單完全圖有邊數(shù)為n(n-1).證明證明: 顯然它的邊數(shù)是顯然它的邊數(shù)是Kn邊數(shù)的邊數(shù)的2倍倍.所以是所以是n(n-1). 2).有向完全圖有向完全圖(有向全圖有向全圖) (它與

12、完全關(guān)系圖一致它與完全關(guān)系圖一致) G是個(gè)有向圖是個(gè)有向圖,如果如果任何兩個(gè)結(jié)點(diǎn)任何兩個(gè)結(jié)點(diǎn)之間都有相互連接的之間都有相互連接的邊邊,則稱(chēng)它是有向完全圖則稱(chēng)它是有向完全圖. 其圖形如下其圖形如下: 所以有所以有n個(gè)結(jié)點(diǎn)的有向完全圖個(gè)結(jié)點(diǎn)的有向完全圖, 有邊數(shù)有邊數(shù) n2.九九.子圖和生成子圖子圖和生成子圖1.子圖子圖:設(shè)設(shè)G=是圖是圖,如果如果G=且且V V, V, E E, 則稱(chēng)則稱(chēng)G是是G的子圖的子圖.可見(jiàn)可見(jiàn)G1,G2,G3都是都是K5的子圖的子圖. b cd e ab c ab cd eG1G2G3K5 ab cd e2. 生成子圖生成子圖設(shè)設(shè)G=是圖是圖, G=, G是是G的子圖的子

13、圖,如果如果V=V, 則稱(chēng)則稱(chēng)G是是G的生成子圖的生成子圖.上例中上例中, G1是是K5的生成子圖的生成子圖.十十. 補(bǔ)圖補(bǔ)圖由由G的的所有結(jié)點(diǎn)所有結(jié)點(diǎn)和為使和為使G變成完全圖變成完全圖,所需要添加的那些所需要添加的那些邊組成的圖邊組成的圖, 稱(chēng)之為稱(chēng)之為G相對(duì)完全圖的補(bǔ)圖相對(duì)完全圖的補(bǔ)圖,簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)G的補(bǔ)圖的補(bǔ)圖,記作記作 G K5 G Gb cd e ab c ab cd eG1G2G3K5 ab cd e十一十一.相對(duì)補(bǔ)圖相對(duì)補(bǔ)圖設(shè)設(shè)G1=是圖是圖G=的子圖的子圖,如果有如果有G2= 使得使得E2=E-E1且且V2中僅包含中僅包含E2中的邊所關(guān)聯(lián)的結(jié)點(diǎn)中的邊所關(guān)聯(lián)的結(jié)點(diǎn),則稱(chēng)則稱(chēng)G2是是G

14、1相對(duì)相對(duì)G的補(bǔ)圖的補(bǔ)圖.可見(jiàn)可見(jiàn)G1是是G3相對(duì)相對(duì)G的補(bǔ)圖的補(bǔ)圖. G3也是也是G1相對(duì)相對(duì)G的補(bǔ)圖的補(bǔ)圖.而而G2不是不是G3相對(duì)相對(duì)G的補(bǔ)圖的補(bǔ)圖(多了一個(gè)結(jié)點(diǎn)多了一個(gè)結(jié)點(diǎn)).但是但是G3是是G2相對(duì)相對(duì)G的補(bǔ)圖的補(bǔ)圖.可見(jiàn)可見(jiàn): 相對(duì)補(bǔ)圖無(wú)相互性相對(duì)補(bǔ)圖無(wú)相互性. ab cd eGG2 ab cd e cd b eG1 ab cd eG3十二十二. 圖的同構(gòu)圖的同構(gòu)設(shè)設(shè)G=和和G=是圖是圖,如果存在雙射如果存在雙射f:VV 且且任何任何vi,vjV,若邊若邊(vi,vj)E,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 邊邊(f(vi),f(vj)E,(或或若邊若邊E,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 邊邊E),則稱(chēng)則稱(chēng)G與與

15、G同構(gòu)同構(gòu),記作記作G G. (同構(gòu)圖要保持邊的同構(gòu)圖要保持邊的“關(guān)聯(lián)關(guān)聯(lián)”關(guān)系關(guān)系)例如例如:右邊所示的兩個(gè)圖右邊所示的兩個(gè)圖:G= G=構(gòu)造映射構(gòu)造映射f:VV兩個(gè)圖同構(gòu)的必要條件兩個(gè)圖同構(gòu)的必要條件:1.結(jié)點(diǎn)個(gè)數(shù)相等結(jié)點(diǎn)個(gè)數(shù)相等. 2.邊數(shù)相等邊數(shù)相等.3.度數(shù)相同的結(jié)點(diǎn)數(shù)相等度數(shù)相同的結(jié)點(diǎn)數(shù)相等. 4. 對(duì)應(yīng)結(jié)點(diǎn)的度數(shù)相等對(duì)應(yīng)結(jié)點(diǎn)的度數(shù)相等.a bc d1 43 2a 1b 2c 3d 4下面是否同構(gòu)的圖下面是否同構(gòu)的圖?右面兩個(gè)圖不同構(gòu)右面兩個(gè)圖不同構(gòu):左圖中四個(gè)左圖中四個(gè)3度結(jié)點(diǎn)度結(jié)點(diǎn)構(gòu)成四邊形構(gòu)成四邊形,而右圖而右圖則不然則不然.a fb ec d 3 51 62 4 31 2

16、ab c ab ec d 13 45 2 練習(xí)練習(xí):請(qǐng)畫(huà)出請(qǐng)畫(huà)出K4的所有不同構(gòu)的生成子圖的所有不同構(gòu)的生成子圖.本節(jié)要求本節(jié)要求:準(zhǔn)確掌握如下基本概念和定理準(zhǔn)確掌握如下基本概念和定理:1.有向邊有向邊,無(wú)向邊無(wú)向邊,孤立結(jié)點(diǎn)孤立結(jié)點(diǎn),平行邊平行邊,環(huán)環(huán).2.有向圖有向圖,無(wú)向圖無(wú)向圖,零圖零圖,平凡圖平凡圖,簡(jiǎn)單圖簡(jiǎn)單圖,多重圖多重圖,完全圖完全圖,子圖子圖,生成子圖生成子圖,補(bǔ)圖補(bǔ)圖,相對(duì)補(bǔ)圖相對(duì)補(bǔ)圖3.四個(gè)定理四個(gè)定理(關(guān)于結(jié)點(diǎn)度關(guān)于結(jié)點(diǎn)度,以及結(jié)點(diǎn)度與邊數(shù)關(guān)系以及結(jié)點(diǎn)度與邊數(shù)關(guān)系)4.圖的同構(gòu)圖的同構(gòu) (會(huì)判斷會(huì)判斷).作業(yè)作業(yè): P279 (1) (2) (4) (5) 8-2. 路

17、與回路 在實(shí)際應(yīng)用中在實(shí)際應(yīng)用中,比如在市內(nèi)乘出租車(chē)去參觀一個(gè)博覽會(huì)比如在市內(nèi)乘出租車(chē)去參觀一個(gè)博覽會(huì), 一定要司機(jī)選一條最短的路一定要司機(jī)選一條最短的路. 到博覽會(huì)后到博覽會(huì)后, 最好選一條這最好選一條這樣到路徑樣到路徑,使得每個(gè)展臺(tái)都參觀一次后使得每個(gè)展臺(tái)都參觀一次后,再回到原來(lái)存包再回到原來(lái)存包處處. 這就是路與回路的問(wèn)題這就是路與回路的問(wèn)題.一一. 路的概念路的概念 1.路的定義路的定義: 給定圖給定圖G=設(shè)設(shè)v0 ,v1,v2,vnV, e1,e2,enE 其中其中ei是關(guān)聯(lián)是關(guān)聯(lián)vi-1 ,vi的邊的邊, 則稱(chēng)則稱(chēng)結(jié)點(diǎn)和邊的交叉序列結(jié)點(diǎn)和邊的交叉序列v0 e1v1 e2v2envn

18、是連接是連接v0到到vn的路的路. v0是此路的起點(diǎn)是此路的起點(diǎn),vn是此路的終點(diǎn)是此路的終點(diǎn). 路中含有的路中含有的邊數(shù)邊數(shù) n稱(chēng)之為路的長(zhǎng)度稱(chēng)之為路的長(zhǎng)度.例如上圖中例如上圖中 v0 e2v3 e6v2是一條長(zhǎng)度為是一條長(zhǎng)度為2的路的路. v3 v2v1 v0e1e2e3e4e5e6如果圖是個(gè)如果圖是個(gè)簡(jiǎn)單圖簡(jiǎn)單圖, 則路可以只用結(jié)點(diǎn)序列表示則路可以只用結(jié)點(diǎn)序列表示. 如右圖中如右圖中, 路路:abcad如果圖是個(gè)如果圖是個(gè)有向圖有向圖, 則路可以則路可以只用邊序列表示只用邊序列表示. 如右邊有向圖中如右邊有向圖中 e1 e5e2e3 e6 是一條路是一條路.2. 回路回路:如果一條路的起

19、點(diǎn)和終點(diǎn)是一個(gè)結(jié)點(diǎn)如果一條路的起點(diǎn)和終點(diǎn)是一個(gè)結(jié)點(diǎn),則稱(chēng)此路是則稱(chēng)此路是一個(gè)回路一個(gè)回路. 如右圖中如右圖中 L1=v0 e1v1 e5v3 e6v2e4v0 L2= v0 e1v1 e5v3e2v03. 跡與閉跡跡與閉跡 如果一條路中如果一條路中,所有所有邊都不同邊都不同,則稱(chēng)此路為則稱(chēng)此路為跡跡. 如果一條如果一條回路回路中中,所有所有邊都不同邊都不同,則稱(chēng)此回路為則稱(chēng)此回路為閉跡閉跡. v3 v2v1 v0e1e2e3e4e5e6 cb a d v3 v2v1 v0e1e2e3e4e5e64. 通路與圈通路與圈如果一條路中如果一條路中,所有所有結(jié)點(diǎn)都不同結(jié)點(diǎn)都不同,則稱(chēng)此路為則稱(chēng)此路為通

20、路通路.如果一條如果一條回路回路中中,除起點(diǎn)和終點(diǎn)外除起點(diǎn)和終點(diǎn)外,其余其余結(jié)點(diǎn)都不同結(jié)點(diǎn)都不同,則稱(chēng)則稱(chēng)此回路為此回路為圈圈.例如右圖中例如右圖中:L1=v0 e1v1 e5v3 e6v2e4v0 L2= v0 e1v1 e5v3e2v0L3=v0 e1v1 e5v3 e2v0 e3v3 e6v2e4v0 L1和和L2是閉跡是閉跡, 也是圈也是圈.L3是閉跡是閉跡,而不是圈而不是圈. v3 v2v1 v0e1e2e3e4e5e6定理定理8-2.1 在一個(gè)有在一個(gè)有n個(gè)結(jié)點(diǎn)的圖中個(gè)結(jié)點(diǎn)的圖中,如果從結(jié)點(diǎn)如果從結(jié)點(diǎn)vi到到vj存存在一條路在一條路,則從則從vi到到vj必存在一條長(zhǎng)度不多于必存在一

21、條長(zhǎng)度不多于n-1的路的路.*證明證明: 設(shè)設(shè)vi到到vj存在一條路存在一條路: vivi+1vi+2,vj ,設(shè)此路的長(zhǎng)度為設(shè)此路的長(zhǎng)度為k.假設(shè)假設(shè)kn-1, 則此路中有則此路中有 k+1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), k+1n, 而而G中只有中只有n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), 所以此路中必有兩個(gè)結(jié)點(diǎn)相同所以此路中必有兩個(gè)結(jié)點(diǎn)相同, 假設(shè)假設(shè)vs=vt, (ts)于是此路為于是此路為:從圖看出從圖看出,此路中有一個(gè)從此路中有一個(gè)從vs到到vt的回路的回路, 此回路中此回路中,有有t-s條邊條邊( t-s1), 如果刪去這個(gè)回路如果刪去這個(gè)回路, 就得到一條就得到一條vi到到vj更更短的路短的路.如果新的路長(zhǎng)度還大于如

22、果新的路長(zhǎng)度還大于n-1, 說(shuō)明此路中還有回路說(shuō)明此路中還有回路,再刪去再刪去回路回路, 如此進(jìn)行下去如此進(jìn)行下去. 最后必可找到長(zhǎng)度小于最后必可找到長(zhǎng)度小于n-1的路的路. vs-1 vi+1 vt+1 vs = vt vs+1vi vt-1 vj vj-1.二二. 無(wú)向圖的連通性無(wú)向圖的連通性1.兩個(gè)結(jié)點(diǎn)是連通的兩個(gè)結(jié)點(diǎn)是連通的: 在無(wú)向圖中在無(wú)向圖中,結(jié)點(diǎn)結(jié)點(diǎn)u和和v之間之間如果存在一條路如果存在一條路, 則稱(chēng)則稱(chēng)u與與v是連通的是連通的. 我們規(guī)定我們規(guī)定: 對(duì)任何結(jié)點(diǎn)對(duì)任何結(jié)點(diǎn)u, u與與u是連通的是連通的.2.結(jié)點(diǎn)之間的連通關(guān)系是個(gè)等價(jià)關(guān)系結(jié)點(diǎn)之間的連通關(guān)系是個(gè)等價(jià)關(guān)系. 令令G=

23、是無(wú)向圖是無(wú)向圖, R是是V上連通關(guān)系上連通關(guān)系, 即即 R=|u和和v是連通的是連通的 顯然顯然R具有自反、對(duì)稱(chēng)和傳遞性具有自反、對(duì)稱(chēng)和傳遞性.于是可以求商集于是可以求商集V/R.例例1. 給定圖給定圖G1如右上圖所示如右上圖所示: V/R=a,b,g,c,d,e,f,h例例2.給定圖給定圖G2如右下圖所示如右下圖所示: V/R=1,3,5,2,4,6 gh a b ef c d 26 4 51 33.連通分支連通分支:令令G=是無(wú)向圖是無(wú)向圖, R是是V上連通關(guān)系上連通關(guān)系, 設(shè)設(shè)R對(duì)對(duì)V的的商集商集中有等價(jià)類(lèi)中有等價(jià)類(lèi)V1,V2,V3, Vn ,這這n個(gè)個(gè)等價(jià)類(lèi)等價(jià)類(lèi)構(gòu)成構(gòu)成的的n個(gè)子圖

24、分別記作個(gè)子圖分別記作G(V1),G(V2),G(V3), G(Vn),并稱(chēng)它并稱(chēng)它們?yōu)閭優(yōu)镚的連通分支的連通分支. 并用并用W(G)表示表示G中連通分支數(shù)中連通分支數(shù).下邊例中下邊例中4.連通圖連通圖: 如果一個(gè)圖如果一個(gè)圖G只有一個(gè)連通分支只有一個(gè)連通分支(W(G)=1),則稱(chēng)則稱(chēng)G是連通圖是連通圖. W(G3)=1 , G3是連通圖是連通圖 gh a b ef c dG1 26 4 51 3G2 G3W(G1)=3W(G2)=2W(G3)=1定理定理8-2.2: 圖圖G=是連通圖是連通圖,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 對(duì)對(duì)V的任何分的任何分成成V1、V2的劃分的劃分,恒存在一條邊恒存在一條邊, 使得

25、它的兩個(gè)端點(diǎn)分別使得它的兩個(gè)端點(diǎn)分別屬于屬于V1和和V2.*證明證明:必要性必要性. 已知已知G是連通的是連通的. 令令V1,V2是是V的一個(gè)劃分的一個(gè)劃分.任取任取v1V1, v2V2, 由于由于G是連通的是連通的, 必存在一條路必存在一條路 v1 . v2, 在此路上必存在結(jié)點(diǎn)在此路上必存在結(jié)點(diǎn)u和和v,使得使得uV1, vV2 ,且且(u,v)是此路中是此路中的一條邊的一條邊. 充分性充分性:已知對(duì)已知對(duì)V的任何分成的任何分成V1、V2的劃分的劃分,恒存在一條邊恒存在一條邊,使它的兩個(gè)端點(diǎn)分別屬于使它的兩個(gè)端點(diǎn)分別屬于V1和和V2 (反證法反證法)假設(shè)假設(shè)G不是連通的不是連通的. 則則G

26、至少有兩個(gè)連通分支至少有兩個(gè)連通分支G1、 G2,令令V1 =V(G1) V2=V-V(G1), 根據(jù)連通分支定義知根據(jù)連通分支定義知, 不不存在端點(diǎn)分別屬于存在端點(diǎn)分別屬于V1和和V2的邊的邊, 與已知矛盾與已知矛盾. 所以所以G是是連通的連通的.V1V2u vv1 v2.三三. 割集割集 (Cut Set) 割集在圖論中是個(gè)重要概念割集在圖論中是個(gè)重要概念, 在圖論的理論和應(yīng)用中在圖論的理論和應(yīng)用中, 都具有重要地位都具有重要地位. 比如有交通圖比如有交通圖:結(jié)點(diǎn)結(jié)點(diǎn)u, 邊邊e就是就是至關(guān)重要的至關(guān)重要的.割集就是使得原來(lái)連通的圖割集就是使得原來(lái)連通的圖, 變成不連通變成不連通, 需要?jiǎng)h

27、去的需要?jiǎng)h去的結(jié)點(diǎn)集合或邊的集合結(jié)點(diǎn)集合或邊的集合.1.點(diǎn)割集與割點(diǎn)點(diǎn)割集與割點(diǎn):令令G=是是連通無(wú)向圖連通無(wú)向圖, 結(jié)點(diǎn)集合結(jié)點(diǎn)集合V1 , V1 V, 如果刪去如果刪去V1中所有結(jié)點(diǎn)后中所有結(jié)點(diǎn)后,G就變得不連通了就變得不連通了, 而刪而刪去去V1的任何真子集中的所有結(jié)點(diǎn)的任何真子集中的所有結(jié)點(diǎn),得到的子圖仍然連通得到的子圖仍然連通.則則稱(chēng)稱(chēng)V1是是G的一個(gè)的一個(gè)點(diǎn)割集點(diǎn)割集. 如果點(diǎn)割集如果點(diǎn)割集V1中只有一個(gè)結(jié)點(diǎn)中只有一個(gè)結(jié)點(diǎn), 則稱(chēng)此結(jié)點(diǎn)為則稱(chēng)此結(jié)點(diǎn)為割點(diǎn)割點(diǎn).注注:在圖中刪除結(jié)點(diǎn)在圖中刪除結(jié)點(diǎn)u,是指把是指把u以及與以及與u關(guān)聯(lián)的邊都刪除關(guān)聯(lián)的邊都刪除.在圖中刪除某邊在圖中刪除某邊

28、,僅需把該邊刪除僅需把該邊刪除. u e左上圖中左上圖中:b,f, b,g, f,k,k,g以及以及a,d,i,l是點(diǎn)割集是點(diǎn)割集.不存在割點(diǎn)不存在割點(diǎn).2. 點(diǎn)連通度點(diǎn)連通度:若若G不是完全圖不是完全圖, 定義定義: k(G)=min | V1 | | V1是是G的點(diǎn)割集的點(diǎn)割集 為為G的的點(diǎn)連通度點(diǎn)連通度. 點(diǎn)連通度點(diǎn)連通度k(G)是表示為使是表示為使G不連通不連通,至少要?jiǎng)h去的結(jié)點(diǎn)數(shù)至少要?jiǎng)h去的結(jié)點(diǎn)數(shù). 上例中上例中 k(G)=2 具有割點(diǎn)圖的點(diǎn)連通度具有割點(diǎn)圖的點(diǎn)連通度 k(G)=1,如右圖如右圖 g ca i ej d h l k g ca b i ej f d h l k g c

29、b ej f h k u 定理定理8-2.3 :一個(gè)連通圖中結(jié)點(diǎn)一個(gè)連通圖中結(jié)點(diǎn)v是是割點(diǎn)割點(diǎn)的充分且必要條件的充分且必要條件是存在兩個(gè)結(jié)點(diǎn)是存在兩個(gè)結(jié)點(diǎn)u和和w, 使得從使得從u到到w的任何路都通過(guò)的任何路都通過(guò) v .證明證明:略略上邊是通過(guò)刪去結(jié)點(diǎn)的辦法使連通圖變得不連通的上邊是通過(guò)刪去結(jié)點(diǎn)的辦法使連通圖變得不連通的. 也可以通過(guò)刪去邊的辦法使連通圖變得不連通也可以通過(guò)刪去邊的辦法使連通圖變得不連通.3. 邊割集與割邊邊割集與割邊(橋橋)令令G=是是連通無(wú)向圖連通無(wú)向圖, 邊的集合邊的集合E1,E1 E, 如果刪去如果刪去E1中所有邊后中所有邊后,G就變得不連通了就變得不連通了, 而刪去

30、而刪去E1的任何真子集的任何真子集中的所有邊中的所有邊,得到的子圖仍然連通得到的子圖仍然連通.則稱(chēng)則稱(chēng)E1是是G的一個(gè)的一個(gè)邊割邊割集集. 如果邊割集如果邊割集E1中只有一條邊中只有一條邊, 則稱(chēng)此邊為則稱(chēng)此邊為割邊割邊, 也稱(chēng)之也稱(chēng)之 為為橋橋.如右圖中如右圖中e就是橋就是橋. e4.邊連通度邊連通度:若若G不是平凡圖不是平凡圖, 定義定義: (G)=min |E1| | E1是是G的邊割集的邊割集為圖為圖G的的邊連通度邊連通度. 邊連通度邊連通度(G)是表示為使是表示為使G不連通不連通,至少要?jiǎng)h去的邊數(shù)至少要?jiǎng)h去的邊數(shù).顯然顯然,如果如果G不是連通圖不是連通圖, 則則 k(G)=(G)=0

31、*定理定理8-2.4 對(duì)于任何一個(gè)圖對(duì)于任何一個(gè)圖G,有有 k(G)(G)(G)證明證明: 略略(可參考書(shū)可參考書(shū)P283中定理中定理7-2.2)四四. 有向圖的連通性有向圖的連通性 1.結(jié)點(diǎn)間的可達(dá)性結(jié)點(diǎn)間的可達(dá)性: G=是有向圖是有向圖, u,vV, 如果從如果從 u到到v有一條路有一條路, 則稱(chēng)從則稱(chēng)從u到到v可達(dá)可達(dá). 右圖中右圖中 a可達(dá)可達(dá)b和和d, 但是但是a不可達(dá)不可達(dá)c. 顯然結(jié)點(diǎn)間的可達(dá)關(guān)系顯然結(jié)點(diǎn)間的可達(dá)關(guān)系,具有具有自反性和傳遞性自反性和傳遞性. 2. 結(jié)點(diǎn)結(jié)點(diǎn)u到到v的距離的距離: 如果如果u可達(dá)可達(dá)v, 可能從可能從u到到v有多條路有多條路,其其中中最短的路最短的路

32、的長(zhǎng)度的長(zhǎng)度,稱(chēng)之為從稱(chēng)之為從u到到v的距離的距離.記作記作d. 上例中上例中 d=1 d=2 d=0 d= 3. 可達(dá)性的性質(zhì)可達(dá)性的性質(zhì): 1). d0 2) d=0 3) d + dd (如上圖的如上圖的c,a,b) 4) 如果從如果從u到到v不可達(dá)不可達(dá),則則d= (如如b,c) 5)如從如從u可達(dá)可達(dá)v,從從v也可達(dá)也可達(dá)u, 但但d不一定等于不一定等于d. 例如例如 dd dc a b4. 圖的直徑圖的直徑: G是個(gè)圖是個(gè)圖, 定義定義 為圖為圖G的直徑的直徑.上圖中上圖中, 圖的直徑圖的直徑D= (因?yàn)橐驗(yàn)閐=)5. 強(qiáng)連通、單側(cè)連通和弱連通強(qiáng)連通、單側(cè)連通和弱連通 在在簡(jiǎn)單有向

33、圖簡(jiǎn)單有向圖G中中,如果如果任何任何兩個(gè)結(jié)點(diǎn)間兩個(gè)結(jié)點(diǎn)間相互相互可達(dá)可達(dá), 則稱(chēng)則稱(chēng)G是是強(qiáng)連通強(qiáng)連通. 如果任何一對(duì)結(jié)點(diǎn)間如果任何一對(duì)結(jié)點(diǎn)間, 至少至少有一個(gè)結(jié)點(diǎn)到另有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)可達(dá)一個(gè)結(jié)點(diǎn)可達(dá), 則稱(chēng)則稱(chēng)G是是單側(cè)連通單側(cè)連通. 如果將如果將G看成無(wú)向圖后看成無(wú)向圖后(即把有向邊看成無(wú)向邊即把有向邊看成無(wú)向邊)是連通的是連通的,則稱(chēng)則稱(chēng)G是是弱連通弱連通.(a)強(qiáng)連通強(qiáng)連通.(b)a到到d, d到到a, 都不可達(dá)都不可達(dá) 是弱連通是弱連通.(c)單側(cè)連通單側(cè)連通. dc a bD=maxd u,vV dc a b dc a b dc a b(a)(b)(c)定理定理8-2.5:一

34、個(gè)一個(gè)有向圖有向圖G是強(qiáng)連通的是強(qiáng)連通的,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G中有一個(gè)中有一個(gè)回路回路, 此回路至少包含每個(gè)結(jié)點(diǎn)一次此回路至少包含每個(gè)結(jié)點(diǎn)一次.證明證明:充分性充分性: 顯然成立顯然成立. 因?yàn)槿绻驗(yàn)槿绻鸊中有一個(gè)回路中有一個(gè)回路, 它至少包含每個(gè)結(jié)點(diǎn)一次它至少包含每個(gè)結(jié)點(diǎn)一次就使得任何兩個(gè)結(jié)點(diǎn)間相互可達(dá)就使得任何兩個(gè)結(jié)點(diǎn)間相互可達(dá) 所以所以G是強(qiáng)連通的是強(qiáng)連通的. 必要性必要性:如果如果G是強(qiáng)連通的是強(qiáng)連通的,則任何兩個(gè)結(jié)點(diǎn)間相互可達(dá)則任何兩個(gè)結(jié)點(diǎn)間相互可達(dá).所以可以構(gòu)造一個(gè)回路經(jīng)過(guò)所有結(jié)點(diǎn)所以可以構(gòu)造一個(gè)回路經(jīng)過(guò)所有結(jié)點(diǎn). 否則必有一個(gè)回路不包含某個(gè)結(jié)點(diǎn)否則必有一個(gè)回路不包含某個(gè)結(jié)點(diǎn)v所以

35、所以v與回路上的各結(jié)點(diǎn)都不相互可達(dá)與回路上的各結(jié)點(diǎn)都不相互可達(dá).這與這與G是強(qiáng)連通條件矛盾是強(qiáng)連通條件矛盾.所以所以G必有回路至少包含每個(gè)結(jié)點(diǎn)一次必有回路至少包含每個(gè)結(jié)點(diǎn)一次. 可以應(yīng)用此定理判斷可以應(yīng)用此定理判斷G是否為強(qiáng)連通是否為強(qiáng)連通, 就是看它是否有包就是看它是否有包含每個(gè)結(jié)點(diǎn)的回路含每個(gè)結(jié)點(diǎn)的回路.6. 強(qiáng)分圖、單側(cè)分圖和弱分圖強(qiáng)分圖、單側(cè)分圖和弱分圖在在簡(jiǎn)單有向圖簡(jiǎn)單有向圖中中,具有強(qiáng)連通性質(zhì)的最大子圖具有強(qiáng)連通性質(zhì)的最大子圖,稱(chēng)為稱(chēng)為強(qiáng)分圖強(qiáng)分圖.具有單側(cè)連通的最大子圖具有單側(cè)連通的最大子圖,稱(chēng)為稱(chēng)為單側(cè)分圖單側(cè)分圖. 具有弱連通的具有弱連通的最最大子圖大子圖,稱(chēng)為稱(chēng)為弱分圖弱分

36、圖. 這些這些分圖用結(jié)點(diǎn)的集合表示分圖用結(jié)點(diǎn)的集合表示. 例如例如,給定有向圖給定有向圖G,如圖所示如圖所示:求它的強(qiáng)分圖、單側(cè)分圖和求它的強(qiáng)分圖、單側(cè)分圖和弱分圖弱分圖.解解: 強(qiáng)分圖強(qiáng)分圖:由由a,g,hbc def導(dǎo)出的子圖導(dǎo)出的子圖.單側(cè)分圖單側(cè)分圖:由由a,g,h,b,f,d,eb,c,f,d,e導(dǎo)出的子圖導(dǎo)出的子圖.弱分圖弱分圖:G本身是弱分圖本身是弱分圖. ef c d gh a b定理定理8-2.6 在有向圖中在有向圖中,每個(gè)結(jié)點(diǎn)必位于一個(gè)且只位于一每個(gè)結(jié)點(diǎn)必位于一個(gè)且只位于一個(gè)個(gè)強(qiáng)分圖中強(qiáng)分圖中.證明證明:令令G=是有向圖是有向圖, 任取結(jié)點(diǎn)任取結(jié)點(diǎn)vV, 令令S是所有與是所

37、有與v 相互可達(dá)的結(jié)點(diǎn)集合相互可達(dá)的結(jié)點(diǎn)集合, 當(dāng)然當(dāng)然vS S, 而而S是一個(gè)是一個(gè)強(qiáng)分圖強(qiáng)分圖, 所以所以v必位于一個(gè)強(qiáng)分圖中必位于一個(gè)強(qiáng)分圖中. 如果如果v位于兩個(gè)不同的強(qiáng)分圖位于兩個(gè)不同的強(qiáng)分圖S1、S2中中, 于是于是 v與與S1中中每個(gè)結(jié)點(diǎn)相互可達(dá)每個(gè)結(jié)點(diǎn)相互可達(dá), v也與也與 S2中每個(gè)結(jié)點(diǎn)相互可達(dá)中每個(gè)結(jié)點(diǎn)相互可達(dá), 所所以以S1中每個(gè)結(jié)點(diǎn)都與中每個(gè)結(jié)點(diǎn)都與S2中每個(gè)結(jié)點(diǎn)通過(guò)中每個(gè)結(jié)點(diǎn)通過(guò)v相互可達(dá)相互可達(dá), 這這說(shuō)明說(shuō)明S1與與S2是一個(gè)強(qiáng)分圖是一個(gè)強(qiáng)分圖, 與已知與已知S1、S2是兩個(gè)不同的是兩個(gè)不同的強(qiáng)分圖矛盾強(qiáng)分圖矛盾. 所以每個(gè)結(jié)點(diǎn)必位于一個(gè)且只位于一個(gè)強(qiáng)分圖中所以每

38、個(gè)結(jié)點(diǎn)必位于一個(gè)且只位于一個(gè)強(qiáng)分圖中.在給定的簡(jiǎn)單有向圖中找強(qiáng)分圖在給定的簡(jiǎn)單有向圖中找強(qiáng)分圖-回路中的結(jié)點(diǎn)構(gòu)成回路中的結(jié)點(diǎn)構(gòu)成一個(gè)強(qiáng)分圖一個(gè)強(qiáng)分圖, 不在回路中的結(jié)點(diǎn)不在回路中的結(jié)點(diǎn),自己構(gòu)成一個(gè)強(qiáng)分圖自己構(gòu)成一個(gè)強(qiáng)分圖. 作業(yè)作業(yè) P286 (3) (5) (8)8-3. 圖的矩陣表示圖的矩陣表示不僅是給出圖的一種表示方法圖的矩陣表示不僅是給出圖的一種表示方法, 還可以通過(guò)還可以通過(guò)這些矩陣討論有關(guān)圖的若干性質(zhì)這些矩陣討論有關(guān)圖的若干性質(zhì), 更重要的是可以用矩陣更重要的是可以用矩陣形式將圖存入計(jì)算機(jī)中形式將圖存入計(jì)算機(jī)中, 在計(jì)算機(jī)中對(duì)圖作處理在計(jì)算機(jī)中對(duì)圖作處理. 這里主要討論圖的三種矩

39、陣這里主要討論圖的三種矩陣.一一. 鄰接矩陣鄰接矩陣 這是以這是以結(jié)點(diǎn)結(jié)點(diǎn)與與結(jié)點(diǎn)結(jié)點(diǎn)之間的鄰接關(guān)系確定的矩陣之間的鄰接關(guān)系確定的矩陣.1.定義定義:設(shè)設(shè)G=是個(gè)簡(jiǎn)單圖是個(gè)簡(jiǎn)單圖,V=v1,v2,v3,vn , 一個(gè)一個(gè)nn階矩陣階矩陣A=(aij)稱(chēng)為稱(chēng)為G的鄰接矩陣的鄰接矩陣. 其中其中:aij =1 vi與與vj鄰接鄰接, 即即(vi,vj)E 或或 E0 vi與與vj不鄰接或不鄰接或i=j例如例如, 給定無(wú)向圖給定無(wú)向圖G1和有向圖和有向圖G2如圖所示如圖所示:2.從鄰接矩陣看圖的性質(zhì)從鄰接矩陣看圖的性質(zhì): 無(wú)向圖無(wú)向圖:每行每行1的個(gè)數(shù)的個(gè)數(shù)=每列每列1的個(gè)數(shù)的個(gè)數(shù)=對(duì)應(yīng)結(jié)點(diǎn)的度對(duì)應(yīng)

40、結(jié)點(diǎn)的度 有向圖有向圖:每每行行1的個(gè)數(shù)的個(gè)數(shù)=對(duì)應(yīng)結(jié)點(diǎn)的對(duì)應(yīng)結(jié)點(diǎn)的出度出度 每每列列1的個(gè)數(shù)的個(gè)數(shù)=對(duì)應(yīng)結(jié)點(diǎn)的對(duì)應(yīng)結(jié)點(diǎn)的入度入度v1 v5v4 v2 v3G1v3 v2 v4 v5v1 G20100010010010010100000100)(0110010010100110110100110)(21GAGA3.鄰接矩陣的乘積鄰接矩陣的乘積在在(A(G1)2 中中a342 =2 表示從表示從v3到到v4有長(zhǎng)度為有長(zhǎng)度為2的路有的路有2條條: 在在(A(G1)3中中a233 =6 表示從表示從v2到到v3有長(zhǎng)度為有長(zhǎng)度為3的路有的路有6條條:v2v1v2v3 , v2v4v2v3 , v2v3

41、v2v3 , v2v3v1v3 , v2v3v5v3 , v2v4v5v3 .2002102201023112013111112)(0110010010100110110100110)(211GAGAv1 v5v4 v2 v3G1045124015251264156242244201100100101001101101001102002102201023112013111112)(31GAv3 v2v4 , v3 v5v4定理定理8-3.1設(shè)設(shè)G=是簡(jiǎn)單圖是簡(jiǎn)單圖,令令V=v1,v2,v3,vn, G的的鄰接矩陣鄰接矩陣(A(G)k中的第中的第 i行第行第j列元素列元素aijk=m, 表示在圖

42、表示在圖G中從中從vi到到vj長(zhǎng)度為長(zhǎng)度為k的路有的路有m條條.可以用歸納法證明可以用歸納法證明.(見(jiàn)教材見(jiàn)教材P290)在實(shí)際應(yīng)用中在實(shí)際應(yīng)用中,有時(shí)只關(guān)心從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否有時(shí)只關(guān)心從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否有路有路,而不關(guān)心路有多長(zhǎng)而不關(guān)心路有多長(zhǎng),比如電話(huà)網(wǎng)絡(luò)比如電話(huà)網(wǎng)絡(luò). 這就促使我們定這就促使我們定義可達(dá)矩陣義可達(dá)矩陣.二二.可達(dá)性矩陣可達(dá)性矩陣1.定義定義:設(shè)設(shè)G=是個(gè)簡(jiǎn)單圖是個(gè)簡(jiǎn)單圖,V=v1,v2,v3,vn , 一個(gè)一個(gè)nn階矩陣階矩陣P=(pij)稱(chēng)為稱(chēng)為G的可達(dá)性矩陣的可達(dá)性矩陣. 其中其中:pij =1 vi到到vj可達(dá)可達(dá), (至少有一條路至少有一條路) 0

43、 其它情況其它情況2.求可達(dá)矩陣求可達(dá)矩陣 可以根據(jù)鄰接矩陣可以根據(jù)鄰接矩陣A求可達(dá)矩陣求可達(dá)矩陣. 設(shè)設(shè)|V(G)|=n 令令A(yù)(k)是將是將Ak中的非中的非0元素都寫(xiě)成元素都寫(xiě)成1,而得到的只含有而得到的只含有0和和1的的0-1矩陣矩陣.于是可達(dá)矩陣于是可達(dá)矩陣P為為: P=AA(2)A(3).A(n) 其中其中是邏輯或是邏輯或. 有兩種方法求有兩種方法求P 方法方法1. 按照矩陣相乘分別求出按照矩陣相乘分別求出A(k) (k2), 然后再然后再. 方法方法2.用求傳遞閉包的用求傳遞閉包的Warshall算法算法,見(jiàn)見(jiàn)P124.例如例如,G2如圖所示如圖所示, 求它的求它的可達(dá)矩陣可達(dá)矩陣

44、P. v3 v2 v4 v5v1 G2 P=AA(2)A(3)A(4)A(5)3.用用可達(dá)矩陣可達(dá)矩陣求強(qiáng)分圖求強(qiáng)分圖. 以以G2為例為例 從圖看出有兩個(gè)強(qiáng)分圖從圖看出有兩個(gè)強(qiáng)分圖:v1,v3和和v2,v4,v5下面看怎樣用下面看怎樣用P求強(qiáng)分圖求強(qiáng)分圖.0010000010100100100100010A=1001001011011010001001001A(2) =0110101011100100100000010A(3) =1001001011011010001001001A(4) =A(2)A(5)=A(3)1111101011111110101101011P=v3 v2 v4 v5v

45、1 G2先將先將P=(pij)轉(zhuǎn)置得轉(zhuǎn)置得PT=(pTij), 如果如果vi與與vj相互可達(dá)相互可達(dá),則則 pij= pTij =1進(jìn)而求進(jìn)而求PPT對(duì)對(duì)PPT進(jìn)行初等變換進(jìn)行初等變換 第第2行與第行與第3行交換行交換,再第再第2列與第列與第3列交換列交換最后得兩個(gè)強(qiáng)分圖最后得兩個(gè)強(qiáng)分圖:v1,v3和和v2,v4,v5三三.完全關(guān)聯(lián)矩陣完全關(guān)聯(lián)矩陣 此矩陣是按照此矩陣是按照結(jié)點(diǎn)結(jié)點(diǎn)與與邊邊之間的關(guān)聯(lián)關(guān)系確定的矩陣之間的關(guān)聯(lián)關(guān)系確定的矩陣.1111101011111110101101011P=1010011111101001111111111PT=PPT=10100010111010001011

46、010111100011000001110011100111初等變換得v1v3v2v4v51.無(wú)向圖的完全關(guān)聯(lián)矩陣無(wú)向圖的完全關(guān)聯(lián)矩陣 1).定義定義:設(shè)設(shè)G=是個(gè)無(wú)向圖是個(gè)無(wú)向圖,V=v1,v2,v3,vm , E=e1,e2,e3,en ,一個(gè)一個(gè)mn階矩陣階矩陣M=(mij)稱(chēng)為稱(chēng)為G的完的完全關(guān)聯(lián)矩陣全關(guān)聯(lián)矩陣. 其中其中:2).從關(guān)聯(lián)矩陣看圖的性質(zhì)從關(guān)聯(lián)矩陣看圖的性質(zhì): a)每列每列只有二個(gè)只有二個(gè)1. (因?yàn)槊織l邊只關(guān)聯(lián)兩個(gè)結(jié)點(diǎn)因?yàn)槊織l邊只關(guān)聯(lián)兩個(gè)結(jié)點(diǎn)) b)每行中每行中1的個(gè)數(shù)為對(duì)應(yīng)的個(gè)數(shù)為對(duì)應(yīng) 結(jié)點(diǎn)的度數(shù)結(jié)點(diǎn)的度數(shù). c)如果兩列相同如果兩列相同,則說(shuō)明對(duì)應(yīng)的則說(shuō)明對(duì)應(yīng)的 兩條

47、邊是平行邊兩條邊是平行邊.mij = 1 vi與與ej關(guān)聯(lián)關(guān)聯(lián) 0 否則否則e1e2e3e5e7e6e4v1 v5v4 v2 v3 e1 e2 e3 e4 e5 e6 e7v1 1 1 0 0 0 0 0 v2 1 0 1 1 1 0 0 v3 0 1 1 1 0 1 0v4 0 0 0 0 1 0 1v5 0 0 0 0 0 1 1M=2.有向圖的完全關(guān)聯(lián)矩陣有向圖的完全關(guān)聯(lián)矩陣 1).定義定義:設(shè)設(shè)G=是個(gè)簡(jiǎn)單有向是個(gè)簡(jiǎn)單有向圖圖,V=v1,v2,v3,vm , E=e1,e2,e3,en , 一個(gè)一個(gè)mn階矩陣階矩陣M=(mij)稱(chēng)為稱(chēng)為G的完全關(guān)聯(lián)矩的完全關(guān)聯(lián)矩陣陣. 其中其中: 2)

48、.從關(guān)聯(lián)矩陣看圖的性質(zhì)從關(guān)聯(lián)矩陣看圖的性質(zhì): a)每列只有一個(gè)每列只有一個(gè)1和一個(gè)和一個(gè)-1. (每條邊有一個(gè)起點(diǎn)一個(gè)終點(diǎn)每條邊有一個(gè)起點(diǎn)一個(gè)終點(diǎn)) b)每行中每行中1的個(gè)數(shù)為對(duì)應(yīng)結(jié)點(diǎn)的個(gè)數(shù)為對(duì)應(yīng)結(jié)點(diǎn) 的出度的出度.-1個(gè)數(shù)是結(jié)點(diǎn)入度個(gè)數(shù)是結(jié)點(diǎn)入度mij = 1 vi是是ej的起點(diǎn)的起點(diǎn) -1 vi是是ej的終點(diǎn)的終點(diǎn) 0 vi與與ej不關(guān)聯(lián)不關(guān)聯(lián) e1 e2 e3 e4 e5 e6 e7v1 -1 1 0 0 0 0 0 v2 1 0-1 0-1 0 0 v3 0-1 1-1 0-10v4 0 0 0 1 1 0 1v5 0 0 0 0 0 1-1M=v1 v5v4 v2 v3e1e2e3e

49、5e7e6e4本節(jié)重點(diǎn)掌握本節(jié)重點(diǎn)掌握: 圖的三個(gè)矩陣的求法圖的三個(gè)矩陣的求法 由圖的矩陣由圖的矩陣,看圖的性質(zhì)看圖的性質(zhì). 作業(yè)作業(yè) P300 (3)一一.歐拉圖歐拉圖: 1.歐拉路歐拉路:在無(wú)孤立結(jié)點(diǎn)的圖在無(wú)孤立結(jié)點(diǎn)的圖G中中,如果存在一條如果存在一條路路,它經(jīng)過(guò)圖它經(jīng)過(guò)圖中每條邊一次且僅一次中每條邊一次且僅一次, 稱(chēng)此路為歐拉路稱(chēng)此路為歐拉路. 2.歐拉回路歐拉回路:在無(wú)孤立結(jié)點(diǎn)的圖在無(wú)孤立結(jié)點(diǎn)的圖G中中,若存在一條若存在一條回路回路,它經(jīng)過(guò)它經(jīng)過(guò)圖中每條邊一次且僅一次圖中每條邊一次且僅一次,稱(chēng)此回路為歐拉回路稱(chēng)此回路為歐拉回路. 稱(chēng)此圖為歐拉圖稱(chēng)此圖為歐拉圖,或或E圖圖.(Euler)

50、 在在G1中中:有歐拉路有歐拉路:acbefgdcfh在在G2中中:有歐拉回路有歐拉回路:v1v2v3v4v5v2v4v6v5v3v1如何判定一個(gè)圖中是否有歐拉路如何判定一個(gè)圖中是否有歐拉路,或有歐拉回路或有歐拉回路?a ge b d hc f G1v1 v5v4 v2 v3 v6G28-4. 歐拉圖與漢密爾頓圖歐拉圖與漢密爾頓圖3.有歐拉路與有歐拉回路的判定有歐拉路與有歐拉回路的判定:定理定理8-4.1:無(wú)向圖無(wú)向圖G具有具有歐拉路歐拉路,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G是連通的是連通的,且有且有零個(gè)零個(gè)或或兩個(gè)兩個(gè)奇數(shù)度的結(jié)點(diǎn)奇數(shù)度的結(jié)點(diǎn).*證明證明:必要性必要性.(見(jiàn)教材見(jiàn)教材P302)充分性充分性,

51、(證明的過(guò)程就是一個(gè)構(gòu)造歐拉路的過(guò)程證明的過(guò)程就是一個(gè)構(gòu)造歐拉路的過(guò)程) 如果如果G有兩個(gè)奇數(shù)度結(jié)點(diǎn)有兩個(gè)奇數(shù)度結(jié)點(diǎn):就從一個(gè)奇數(shù)度結(jié)點(diǎn)出發(fā)就從一個(gè)奇數(shù)度結(jié)點(diǎn)出發(fā),每每當(dāng)?shù)竭_(dá)一個(gè)偶數(shù)度結(jié)點(diǎn)當(dāng)?shù)竭_(dá)一個(gè)偶數(shù)度結(jié)點(diǎn),必然可以再經(jīng)過(guò)另一條邊離開(kāi)此必然可以再經(jīng)過(guò)另一條邊離開(kāi)此結(jié)點(diǎn)結(jié)點(diǎn),如此重復(fù)下去如此重復(fù)下去,經(jīng)過(guò)所有邊后到達(dá)另一個(gè)奇數(shù)度結(jié)點(diǎn)經(jīng)過(guò)所有邊后到達(dá)另一個(gè)奇數(shù)度結(jié)點(diǎn) 如果如果G無(wú)奇數(shù)度結(jié)點(diǎn)無(wú)奇數(shù)度結(jié)點(diǎn),則可以從任何一個(gè)結(jié)點(diǎn)出發(fā)則可以從任何一個(gè)結(jié)點(diǎn)出發(fā),去構(gòu)去構(gòu)造一條歐拉路造一條歐拉路.推論推論:無(wú)向圖無(wú)向圖G具有具有歐拉回路歐拉回路,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G是連通的是連通的,且所有且所有結(jié)點(diǎn)的度都是偶

52、數(shù)結(jié)點(diǎn)的度都是偶數(shù).用此推論判斷用此推論判斷,七橋問(wèn)題的圖是不是歐拉圖七橋問(wèn)題的圖是不是歐拉圖?4.求歐拉回路的算法求歐拉回路的算法:A B C De1e5e7e6e3e4e2G有有E回路回路?停止停止N選結(jié)點(diǎn)選結(jié)點(diǎn)v 以以v為起點(diǎn)找閉跡為起點(diǎn)找閉跡E1 E1包含所有包含所有 邊邊Y打印打印 E1在在G-E1中找一個(gè)閉跡中找一個(gè)閉跡E2 使使 E1與與 E2至少有一個(gè)公共點(diǎn)至少有一個(gè)公共點(diǎn)N以某以某公共點(diǎn)公共點(diǎn)為起、末點(diǎn)為起、末點(diǎn),對(duì)對(duì) E1E2中的邊重新排序得中的邊重新排序得 新的閉跡新的閉跡C E1:=CY不是不是用上述算法求右圖中歐拉回路用上述算法求右圖中歐拉回路.此圖中所有結(jié)點(diǎn)度均為偶

53、數(shù)此圖中所有結(jié)點(diǎn)度均為偶數(shù),所以有歐拉回路所以有歐拉回路.a) 選以選以1為起點(diǎn)的閉跡為起點(diǎn)的閉跡E1:1261b) E1不包含所有邊不包含所有邊.c) 在在G- E1中找新閉跡中找新閉跡E2: 6356 ( 6是是E1與與E2的公共點(diǎn)的公共點(diǎn))d)以公共點(diǎn)以公共點(diǎn)6為起點(diǎn)為起點(diǎn),對(duì)對(duì)E1E2中的邊排序中的邊排序:C=6356126e) E1 := Cf) E1不包含所有邊不包含所有邊.g) 在在G- E1中找新閉跡中找新閉跡E2: 52345 ( 5是是E1與與E2的公共點(diǎn)的公共點(diǎn))h)以公共點(diǎn)以公共點(diǎn)5為起點(diǎn)為起點(diǎn),對(duì)對(duì)E1E2中的邊排序中的邊排序: C=52345612635i) E1

54、:= Cj) E1包含所有邊包含所有邊. k)打印打印E1 =52345612635 l)停止停止. 16 25 3 4 16 25 3 4歐拉路與歐拉回路問(wèn)題歐拉路與歐拉回路問(wèn)題, 也稱(chēng)一筆畫(huà)問(wèn)題也稱(chēng)一筆畫(huà)問(wèn)題.*5.歐拉圖的應(yīng)用歐拉圖的應(yīng)用-計(jì)算機(jī)鼓輪的設(shè)計(jì)計(jì)算機(jī)鼓輪的設(shè)計(jì)早期向計(jì)算機(jī)輸入數(shù)據(jù)早期向計(jì)算機(jī)輸入數(shù)據(jù), 為簡(jiǎn)單為簡(jiǎn)單,以輸入八進(jìn)制數(shù)為例以輸入八進(jìn)制數(shù)為例 (0,1,2,3,4,5,6,7,即即000,001,010,011,100,101,110,111)鼓輪表面分成鼓輪表面分成23等分等分,每一等分分別用絕緣體或?qū)w組成每一等分分別用絕緣體或?qū)w組成,絕緣部分輸出絕緣部分輸出

55、0,導(dǎo)體部分輸出導(dǎo)體部分輸出1. 有三個(gè)觸點(diǎn)分別與三個(gè)有三個(gè)觸點(diǎn)分別與三個(gè)部分接觸部分接觸,以讀取三個(gè)數(shù)字以讀取三個(gè)數(shù)字. 如圖所示如圖所示:轉(zhuǎn)動(dòng)鼓輪轉(zhuǎn)動(dòng)鼓輪,分別輸出分別輸出8個(gè)數(shù)個(gè)數(shù):000,001,010,011,100,101,110,111 下面介紹此鼓輪的設(shè)計(jì)過(guò)程下面介紹此鼓輪的設(shè)計(jì)過(guò)程:00001111 此輪的設(shè)計(jì)此輪的設(shè)計(jì):以?xún)晌欢M(jìn)制數(shù)以?xún)晌欢M(jìn)制數(shù)V=00,01,10,11為結(jié)點(diǎn)為結(jié)點(diǎn),畫(huà)帶權(quán)圖畫(huà)帶權(quán)圖(即邊上標(biāo)有數(shù)字即邊上標(biāo)有數(shù)字-稱(chēng)為邊的權(quán)稱(chēng)為邊的權(quán)), 從任何從任何a1a2V結(jié)點(diǎn)畫(huà)有向邊結(jié)點(diǎn)畫(huà)有向邊,標(biāo)的權(quán)標(biāo)的權(quán)0(或或1), 該邊指向結(jié)點(diǎn)該邊指向結(jié)點(diǎn)a20(或或a2

56、1),于是構(gòu)成邊于是構(gòu)成邊a1a20, (或或a1a21),這八條邊分別表示這八條邊分別表示八個(gè)二進(jìn)制數(shù)八個(gè)二進(jìn)制數(shù):000,001,010,011,100,101,110,111從此圖上取一個(gè)回路從此圖上取一個(gè)回路: e0e1e2e5 e3e7e6e4將上述各邊的末位數(shù)字寫(xiě)成序列將上述各邊的末位數(shù)字寫(xiě)成序列:01011100,于是就按照此序列將鼓輪進(jìn)行加工于是就按照此序列將鼓輪進(jìn)行加工,標(biāo)標(biāo)0部分部分用絕緣體用絕緣體,標(biāo)標(biāo)1部分用導(dǎo)體部分用導(dǎo)體.001001111e0 =000e1 =001e3 =011e4 =100e5 =101e2 =010110 = e6e7 =11100001111

57、 二二. 漢密爾頓圖漢密爾頓圖(H圖圖) (Hamilton圖圖)Hamilton是英國(guó)數(shù)學(xué)家是英國(guó)數(shù)學(xué)家,在在1959年年,他提出他提出Hamilton回路回路.H圖起源于一種游戲圖起源于一種游戲,這個(gè)游戲就是所謂周游世界問(wèn)題這個(gè)游戲就是所謂周游世界問(wèn)題. 例如例如,某個(gè)城市的街道如圖所示某個(gè)城市的街道如圖所示:該城市的所有交叉路口都有形象各該城市的所有交叉路口都有形象各異的精美的雕塑異的精美的雕塑,吸引著許多游客吸引著許多游客,人人都想找到這樣的路徑人人都想找到這樣的路徑:游遍各游遍各個(gè)景點(diǎn)再回到出發(fā)點(diǎn)個(gè)景點(diǎn)再回到出發(fā)點(diǎn)-H回路回路.1.定義定義:設(shè)設(shè)G=是個(gè)無(wú)向有限圖是個(gè)無(wú)向有限圖, 漢

58、密爾頓路漢密爾頓路:通過(guò)通過(guò)G中每個(gè)結(jié)點(diǎn)恰好一次的路中每個(gè)結(jié)點(diǎn)恰好一次的路. 漢密爾頓回路漢密爾頓回路(H回路回路):通過(guò)通過(guò)G中每個(gè)結(jié)點(diǎn)恰好一次的回中每個(gè)結(jié)點(diǎn)恰好一次的回路路. 漢密爾頓圖漢密爾頓圖(H圖圖):具有漢密爾頓回路具有漢密爾頓回路(H回路回路)的圖的圖.例如右圖中例如右圖中,就是就是H圖圖因?yàn)樗幸驗(yàn)樗蠬回路回路:12345612.漢密爾頓圖的判定漢密爾頓圖的判定: 到目前為止并到目前為止并沒(méi)有沒(méi)有判定判定H圖的充要條件圖的充要條件.定理定理8-4.2 (充分條件充分條件):G是完全圖是完全圖,則則G是是H圖圖.證明證明:略略定理定理8-4.3(充分條件充分條件)設(shè)設(shè)G是有是有

59、n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,若對(duì)若對(duì)G中中每對(duì)結(jié)點(diǎn)度數(shù)之和大于等于每對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n-1(n),則則G有一條有一條H路路(H回路回路)證明證明: 先證明先證明G是連通的是連通的.(反證法反證法) 見(jiàn)書(shū)見(jiàn)書(shū)P307 再構(gòu)造再構(gòu)造H路路(H回路回路) 16 25 3 4 K2K3K4K5在圖在圖G1中中滿(mǎn)足充分條件滿(mǎn)足充分條件(G)=4 (G)=2任意兩個(gè)結(jié)點(diǎn)度數(shù)之和大于任意兩個(gè)結(jié)點(diǎn)度數(shù)之和大于5,所以是所以是H圖圖. 注意注意:上述條件只是充分條件上述條件只是充分條件,而不是必要條件而不是必要條件即不滿(mǎn)足這個(gè)條件的即不滿(mǎn)足這個(gè)條件的, 也可能有也可能有H路路.例如例如:在圖在圖G2中

60、中并不滿(mǎn)足任意兩個(gè)結(jié)點(diǎn)度數(shù)之和大于并不滿(mǎn)足任意兩個(gè)結(jié)點(diǎn)度數(shù)之和大于3, 但是卻有但是卻有H路路. 15 24 3G1d c a b G2定理定理8-4.4:(必要條件必要條件) 若圖若圖G=有有H回路回路,則對(duì)則對(duì)V的任何非空的任何非空子有限集子有限集S, 均有均有W(G-S)|S|, 其中其中W(G-S)是從是從G中刪去中刪去S中所中所有結(jié)點(diǎn)及與這些結(jié)點(diǎn)關(guān)聯(lián)的邊所得到的子圖的連通分支數(shù)有結(jié)點(diǎn)及與這些結(jié)點(diǎn)關(guān)聯(lián)的邊所得到的子圖的連通分支數(shù).證明證明:設(shè)設(shè)C是圖是圖G的一條的一條H回路回路,則對(duì)于則對(duì)于V的任何非空子集的任何非空子集S,在在C中刪去中刪去S中任意一個(gè)結(jié)點(diǎn)中任意一個(gè)結(jié)點(diǎn)v1后后, 則