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

1、第八章 圖論ABCD一一. . 圖的概念圖的概念 一個圖一個圖 G=, 其中其中 V(G): 是是G的結(jié)點的非空集合的結(jié)點的非空集合. (V(G),簡記成簡記成V. E(G): 是是G的邊的集合的邊的集合. 有時簡記成有時簡記成E.v 結(jié)點結(jié)點(Vertices): 用用 表示表示, 旁邊標上該結(jié)點的名稱旁邊標上該結(jié)點的名稱.v 邊邊(Edges): 有向邊有向邊: 帶箭頭的弧線帶箭頭的弧線.從從u到到v的邊表示成的邊表示成 無向邊無向邊:不帶箭頭的弧線不帶箭頭的弧線.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é)點的相對位置、邊的曲直、長短無關(guān)緊要結(jié)點的相對位置、邊的曲直、長短無關(guān)緊要.v鄰接點鄰接點: 與一邊關(guān)聯(lián)的兩個結(jié)點與一邊關(guān)聯(lián)的兩個結(jié)點. v鄰接邊鄰接邊: 關(guān)聯(lián)同一個結(jié)點的兩條邊關(guān)聯(lián)同一個結(jié)點的兩條邊. v環(huán)環(huán):只關(guān)聯(lián)一個結(jié)點的邊只關(guān)聯(lián)一個結(jié)點的邊. v平行邊平行邊:在兩個結(jié)點之間關(guān)聯(lián)的多條邊在兩個結(jié)點之間關(guān)聯(lián)的多條邊. v二二. 有向圖與無向圖有向圖與無向圖 有向圖有向圖:只有有向邊的圖只有有向邊的圖. 無向圖無向圖:只有無向邊的圖只有無向邊的圖.三三

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

4、之為結(jié)點點v的度的度. 記作記作 deg(v).(或或d(v).deg(a)=3 deg(b)=5 deg(c)=4 deg(d)=2 一個環(huán)給結(jié)點的度是一個環(huán)給結(jié)點的度是2. 2.圖的結(jié)點度序列圖的結(jié)點度序列:令令G=是圖是圖, V=v1,v2,v3,vn, 則稱則稱: (der(v1), der(v2),der(v3), ,der(vn) 為圖為圖G的結(jié)點度序的結(jié)點度序列列.例如上圖的結(jié)點度序列為例如上圖的結(jié)點度序列為:(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 每個圖中所有結(jié)點度總和等于邊數(shù)的每個圖中所有結(jié)點度總和等于邊數(shù)的2倍倍.即即證明證明:因為圖中每條邊關(guān)聯(lián)兩個結(jié)點因為圖中每條邊關(guān)聯(lián)兩個結(jié)點,因此每條邊給予它所因此每條邊給予它所關(guān)聯(lián)的兩個結(jié)點的度各是關(guān)聯(lián)的兩個結(jié)點的度各是1, 即一條邊對應(yīng)的度數(shù)是即一條邊對應(yīng)的度數(shù)是2, 所所以整個圖的度數(shù)總和為邊數(shù)的以整個圖的度數(shù)總和為邊數(shù)的2倍倍.定理定理8-1.2(握手定理握手定理)每個圖中每個圖中,奇數(shù)度的結(jié)點必為偶數(shù)奇數(shù)度的結(jié)點必為偶數(shù)個個.(一次集會中一次集會中,與奇數(shù)個人握手的人與奇數(shù)個人握手的人,必是偶數(shù)個必是偶

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

7、圖的度數(shù)序列可能是一個圖的度數(shù)序列?如果可能如果可能,請試畫出它的圖請試畫出它的圖. 哪些可能不是簡單圖哪些可能不是簡單圖? a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4)2.已知無向簡單圖已知無向簡單圖G中中,有有10條邊條邊,4個個3度結(jié)點度結(jié)點,其余結(jié)點的其余結(jié)點的度均小于或等于度均小于或等于2,問問G中至少有多少個結(jié)點中至少有多少個結(jié)點?為什么為什么? 1. a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4)解解:a)不是不是, 因為有三個數(shù)字是奇數(shù)因為有三個數(shù)字是奇數(shù). b) 可能是可能是,如下圖所示如下

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

9、的入度: 指向結(jié)點指向結(jié)點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é)點的出度之的所有結(jié)點的出度之和等于入度之和和等于入度之和.證明證明: 因為圖中每條邊對應(yīng)一個出度和一個入度因為圖中每條邊對應(yīng)一個出度和一個入度. 所以所有結(jié)點的出度之和與所有結(jié)點的入度之和都等于所以所有結(jié)點的出度之和與所有結(jié)點的入度之和都等于有向邊數(shù)有向邊數(shù).必然有所有結(jié)點的出度之和等于入度之和必

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

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

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

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

14、1相對相對G的補圖的補圖.可見可見G1是是G3相對相對G的補圖的補圖. G3也是也是G1相對相對G的補圖的補圖.而而G2不是不是G3相對相對G的補圖的補圖(多了一個結(jié)點多了一個結(jié)點).但是但是G3是是G2相對相對G的補圖的補圖.可見可見: 相對補圖無相互性相對補圖無相互性. 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,當且僅當當且僅當 邊邊(f(vi),f(vj)E,(或或若邊若邊E,當且僅當當且僅當 邊邊E),則稱則稱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òu)造映射構(gòu)造映射f:VV兩個圖同構(gòu)的必要條件兩個圖同構(gòu)的必要條件:1.結(jié)點個數(shù)相等結(jié)點個數(shù)相等. 2.邊數(shù)相等邊數(shù)相等.3.度數(shù)相同的結(jié)點數(shù)相等度數(shù)相同的結(jié)點數(shù)相等. 4. 對應(yīng)結(jié)點的度數(shù)相等對應(yīng)結(jié)點的度數(shù)相等.a bc d1 43 2a 1b 2c 3d 4下面是否同構(gòu)的圖下面是否同構(gòu)的圖?右面兩個圖不同構(gòu)右面兩個圖不同構(gòu):左圖中四個左圖中四個3度結(jié)點度結(jié)點構(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í):請畫出請畫出K4的所有不同構(gòu)的生成子圖的所有不同構(gòu)的生成子圖.本節(jié)要求本節(jié)要求:準確掌握如下基本概念和定理準確掌握如下基本概念和定理:1.有向邊有向邊,無向邊無向邊,孤立結(jié)點孤立結(jié)點,平行邊平行邊,環(huán)環(huán).2.有向圖有向圖,無向圖無向圖,零圖零圖,平凡圖平凡圖,簡單圖簡單圖,多重圖多重圖,完全圖完全圖,子圖子圖,生成子圖生成子圖,補圖補圖,相對補圖相對補圖3.四個定理四個定理(關(guān)于結(jié)點度關(guān)于結(jié)點度,以及結(jié)點度與邊數(shù)關(guān)系以及結(jié)點度與邊數(shù)關(guān)系)4.圖的同構(gòu)圖的同構(gòu) (會判斷會判斷).作業(yè)作業(yè): P279 (1) (2) (4) (5) 8-2. 路

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

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

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

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

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

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

23、是無向圖是無向圖, R是是V上連通關(guān)系上連通關(guān)系, 即即 R=|u和和v是連通的是連通的 顯然顯然R具有自反、對稱和傳遞性具有自反、對稱和傳遞性.于是可以求商集于是可以求商集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=是無向圖是無向圖, R是是V上連通關(guān)系上連通關(guān)系, 設(shè)設(shè)R對對V的的商集商集中有等價類中有等價類V1,V2,V3, Vn ,這這n個個等價類等價類構(gòu)成構(gòu)成的的n個子圖

24、分別記作個子圖分別記作G(V1),G(V2),G(V3), G(Vn),并稱它并稱它們?yōu)閭優(yōu)镚的連通分支的連通分支. 并用并用W(G)表示表示G中連通分支數(shù)中連通分支數(shù).下邊例中下邊例中4.連通圖連通圖: 如果一個圖如果一個圖G只有一個連通分支只有一個連通分支(W(G)=1),則稱則稱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=是連通圖是連通圖,當且僅當當且僅當 對對V的任何分的任何分成成V1、V2的劃分的劃分,恒存在一條邊恒存在一條邊, 使得

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

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

27、去的需要刪去的結(jié)點集合或邊的集合結(jié)點集合或邊的集合.1.點割集與割點點割集與割點:令令G=是是連通無向圖連通無向圖, 結(jié)點集合結(jié)點集合V1 , V1 V, 如果刪去如果刪去V1中所有結(jié)點后中所有結(jié)點后,G就變得不連通了就變得不連通了, 而刪而刪去去V1的任何真子集中的所有結(jié)點的任何真子集中的所有結(jié)點,得到的子圖仍然連通得到的子圖仍然連通.則則稱稱V1是是G的一個的一個點割集點割集. 如果點割集如果點割集V1中只有一個結(jié)點中只有一個結(jié)點, 則稱此結(jié)點為則稱此結(jié)點為割點割點.注注:在圖中刪除結(jié)點在圖中刪除結(jié)點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是點割集是點割集.不存在割點不存在割點.2. 點連通度點連通度:若若G不是完全圖不是完全圖, 定義定義: k(G)=min | V1 | | V1是是G的點割集的點割集 為為G的的點連通度點連通度. 點連通度點連通度k(G)是表示為使是表示為使G不連通不連通,至少要刪去的結(jié)點數(shù)至少要刪去的結(jié)點數(shù). 上例中上例中 k(G)=2 具有割點圖的點連通度具有割點圖的點連通度 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 :一個連通圖中結(jié)點一個連通圖中結(jié)點v是是割點割點的充分且必要條件的充分且必要條件是存在兩個結(jié)點是存在兩個結(jié)點u和和w, 使得從使得從u到到w的任何路都通過的任何路都通過 v .證明證明:略略上邊是通過刪去結(jié)點的辦法使連通圖變得不連通的上邊是通過刪去結(jié)點的辦法使連通圖變得不連通的. 也可以通過刪去邊的辦法使連通圖變得不連通也可以通過刪去邊的辦法使連通圖變得不連通.3. 邊割集與割邊邊割集與割邊(橋橋)令令G=是是連通無向圖連通無向圖, 邊的集合邊的集合E1,E1 E, 如果刪去如果刪去E1中所有邊后中所有邊后,G就變得不連通了就變得不連通了, 而刪去

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

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

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

33、圖簡單有向圖G中中,如果如果任何任何兩個結(jié)點間兩個結(jié)點間相互相互可達可達, 則稱則稱G是是強連通強連通. 如果任何一對結(jié)點間如果任何一對結(jié)點間, 至少至少有一個結(jié)點到另有一個結(jié)點到另一個結(jié)點可達一個結(jié)點可達, 則稱則稱G是是單側(cè)連通單側(cè)連通. 如果將如果將G看成無向圖后看成無向圖后(即把有向邊看成無向邊即把有向邊看成無向邊)是連通的是連通的,則稱則稱G是是弱連通弱連通.(a)強連通強連通.(b)a到到d, d到到a, 都不可達都不可達 是弱連通是弱連通.(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中有一個中有一個回路回路, 此回路至少包含每個結(jié)點一次此回路至少包含每個結(jié)點一次.證明證明:充分性充分性: 顯然成立顯然成立. 因為如果因為如果G中有一個回路中有一個回路, 它至少包含每個結(jié)點一次它至少包含每個結(jié)點一次就使得任何兩個結(jié)點間相互可達就使得任何兩個結(jié)點間相互可達 所以所以G是強連通的是強連通的. 必要性必要性:如果如果G是強連通的是強連通的,則任何兩個結(jié)點間相互可達則任何兩個結(jié)點間相互可達.所以可以構(gòu)造一個回路經(jīng)過所有結(jié)點所以可以構(gòu)造一個回路經(jīng)過所有結(jié)點. 否則必有一個回路不包含某個結(jié)點否則必有一個回路不包含某個結(jié)點v所以

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

36、圖. 這些這些分圖用結(jié)點的集合表示分圖用結(jié)點的集合表示. 例如例如,給定有向圖給定有向圖G,如圖所示如圖所示:求它的強分圖、單側(cè)分圖和求它的強分圖、單側(cè)分圖和弱分圖弱分圖.解解: 強分圖強分圖:由由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 在有向圖中在有向圖中,每個結(jié)點必位于一個且只位于一每個結(jié)點必位于一個且只位于一個個強分圖中強分圖中.證明證明:令令G=是有向圖是有向圖, 任取結(jié)點任取結(jié)點vV, 令令S是所有與是所

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

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

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

40、結(jié)點的度 有向圖有向圖:每每行行1的個數(shù)的個數(shù)=對應(yīng)結(jié)點的對應(yīng)結(jié)點的出度出度 每每列列1的個數(shù)的個數(shù)=對應(yīng)結(jié)點的對應(yīng)結(jié)點的入度入度v1 v5v4 v2 v3G1v3 v2 v4 v5v1 G20100010010010010100000100)(0110010010100110110100110)(21GAGA3.鄰接矩陣的乘積鄰接矩陣的乘積在在(A(G1)2 中中a342 =2 表示從表示從v3到到v4有長度為有長度為2的路有的路有2條條: 在在(A(G1)3中中a233 =6 表示從表示從v2到到v3有長度為有長度為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=是簡單圖是簡單圖,令令V=v1,v2,v3,vn, G的的鄰接矩陣鄰接矩陣(A(G)k中的第中的第 i行第行第j列元素列元素aijk=m, 表示在圖

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

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

44、P. v3 v2 v4 v5v1 G2 P=AA(2)A(3)A(4)A(5)3.用用可達矩陣可達矩陣求強分圖求強分圖. 以以G2為例為例 從圖看出有兩個強分圖從圖看出有兩個強分圖:v1,v3和和v2,v4,v5下面看怎樣用下面看怎樣用P求強分圖求強分圖.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相互可達相互可達,則則 pij= pTij =1進而求進而求PPT對對PPT進行初等變換進行初等變換 第第2行與第行與第3行交換行交換,再第再第2列與第列與第3列交換列交換最后得兩個強分圖最后得兩個強分圖:v1,v3和和v2,v4,v5三三.完全關(guān)聯(lián)矩陣完全關(guān)聯(lián)矩陣 此矩陣是按照此矩陣是按照結(jié)點結(jié)點與與邊邊之間的關(guān)聯(lián)關(guān)系確定的矩陣之間的關(guān)聯(lián)關(guān)系確定的矩陣.1111101011111110101101011P=1010011111101001111111111PT=PPT=10100010111010001011

46、010111100011000001110011100111初等變換得v1v3v2v4v51.無向圖的完全關(guān)聯(lián)矩陣無向圖的完全關(guān)聯(lián)矩陣 1).定義定義:設(shè)設(shè)G=是個無向圖是個無向圖,V=v1,v2,v3,vm , E=e1,e2,e3,en ,一個一個mn階矩陣階矩陣M=(mij)稱為稱為G的完的完全關(guān)聯(lián)矩陣全關(guān)聯(lián)矩陣. 其中其中:2).從關(guān)聯(lián)矩陣看圖的性質(zhì)從關(guān)聯(lián)矩陣看圖的性質(zhì): a)每列每列只有二個只有二個1. (因為每條邊只關(guān)聯(lián)兩個結(jié)點因為每條邊只關(guān)聯(lián)兩個結(jié)點) b)每行中每行中1的個數(shù)為對應(yīng)的個數(shù)為對應(yīng) 結(jié)點的度數(shù)結(jié)點的度數(shù). c)如果兩列相同如果兩列相同,則說明對應(yīng)的則說明對應(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=是個簡單有向是個簡單有向圖圖,V=v1,v2,v3,vm , E=e1,e2,e3,en , 一個一個mn階矩陣階矩陣M=(mij)稱為稱為G的完全關(guān)聯(lián)矩的完全關(guān)聯(lián)矩陣陣. 其中其中: 2)

48、.從關(guān)聯(lián)矩陣看圖的性質(zhì)從關(guān)聯(lián)矩陣看圖的性質(zhì): a)每列只有一個每列只有一個1和一個和一個-1. (每條邊有一個起點一個終點每條邊有一個起點一個終點) b)每行中每行中1的個數(shù)為對應(yīng)結(jié)點的個數(shù)為對應(yīng)結(jié)點 的出度的出度.-1個數(shù)是結(jié)點入度個數(shù)是結(jié)點入度mij = 1 vi是是ej的起點的起點 -1 vi是是ej的終點的終點 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é)重點掌握本節(jié)重點掌握: 圖的三個矩陣的求法圖的三個矩陣的求法 由圖的矩陣由圖的矩陣,看圖的性質(zhì)看圖的性質(zhì). 作業(yè)作業(yè) P300 (3)一一.歐拉圖歐拉圖: 1.歐拉路歐拉路:在無孤立結(jié)點的圖在無孤立結(jié)點的圖G中中,如果存在一條如果存在一條路路,它經(jīng)過圖它經(jīng)過圖中每條邊一次且僅一次中每條邊一次且僅一次, 稱此路為歐拉路稱此路為歐拉路. 2.歐拉回路歐拉回路:在無孤立結(jié)點的圖在無孤立結(jié)點的圖G中中,若存在一條若存在一條回路回路,它經(jīng)過它經(jīng)過圖中每條邊一次且僅一次圖中每條邊一次且僅一次,稱此回路為歐拉回路稱此回路為歐拉回路. 稱此圖為歐拉圖稱此圖為歐拉圖,或或E圖圖.(Euler)

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

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

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

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

54、:= Cj) E1包含所有邊包含所有邊. k)打印打印E1 =52345612635 l)停止停止. 16 25 3 4 16 25 3 4歐拉路與歐拉回路問題歐拉路與歐拉回路問題, 也稱一筆畫問題也稱一筆畫問題.*5.歐拉圖的應(yīng)用歐拉圖的應(yīng)用-計算機鼓輪的設(shè)計計算機鼓輪的設(shè)計早期向計算機輸入數(shù)據(jù)早期向計算機輸入數(shù)據(jù), 為簡單為簡單,以輸入八進制數(shù)為例以輸入八進制數(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. 有三個觸點分別與三個有三個觸點分別與三個部分接觸部分接觸,以讀取三個數(shù)字以讀取三個數(shù)字. 如圖所示如圖所示:轉(zhuǎn)動鼓輪轉(zhuǎn)動鼓輪,分別輸出分別輸出8個數(shù)個數(shù):000,001,010,011,100,101,110,111 下面介紹此鼓輪的設(shè)計過程下面介紹此鼓輪的設(shè)計過程:00001111 此輪的設(shè)計此輪的設(shè)計:以兩位二進制數(shù)以兩位二進制數(shù)V=00,01,10,11為結(jié)點為結(jié)點,畫帶權(quán)圖畫帶權(quán)圖(即邊上標有數(shù)字即邊上標有數(shù)字-稱為邊的權(quán)稱為邊的權(quán)), 從任何從任何a1a2V結(jié)點畫有向邊結(jié)點畫有向邊,標的權(quán)標的權(quán)0(或或1), 該邊指向結(jié)點該邊指向結(jié)點a20(或或a2

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

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

58、密爾頓路漢密爾頓路:通過通過G中每個結(jié)點恰好一次的路中每個結(jié)點恰好一次的路. 漢密爾頓回路漢密爾頓回路(H回路回路):通過通過G中每個結(jié)點恰好一次的回中每個結(jié)點恰好一次的回路路. 漢密爾頓圖漢密爾頓圖(H圖圖):具有漢密爾頓回路具有漢密爾頓回路(H回路回路)的圖的圖.例如右圖中例如右圖中,就是就是H圖圖因為它有因為它有H回路回路:12345612.漢密爾頓圖的判定漢密爾頓圖的判定: 到目前為止并到目前為止并沒有沒有判定判定H圖的充要條件圖的充要條件.定理定理8-4.2 (充分條件充分條件):G是完全圖是完全圖,則則G是是H圖圖.證明證明:略略定理定理8-4.3(充分條件充分條件)設(shè)設(shè)G是有是有

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

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