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

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

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

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

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

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

9、的入度: 指向指向結點結點v的邊數的邊數. 記作記作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的所有結點的出度之的所有結點的出度之和等于入度之和和等于入度之和.證明證明: 因為圖中每條邊對應一個出度和一個入度因為圖中每條邊對應一個出度和一個入度. 所以所有結點的出度之和與所有結點的入度之和都等于所以所有結點的出度之和與所有結點的入度之和都等于有向邊數有向邊數.必然有所有結點的出度之和等于入度之和必

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

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

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

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

14、1相對相對G的補圖的補圖.可見可見G1是是G3相對相對G的補圖的補圖. G3也是也是G1相對相對G的補圖的補圖.而而G2不是不是G3相對相對G的補圖的補圖(多了一個結點多了一個結點).但是但是G3是是G2相對相對G的補圖的補圖.可見可見: 相對補圖無相互性相對補圖無相互性. ab cd eGG2 ab cd e cd b eG1 ab cd eG3十二十二. 圖的同構圖的同構設設G=和和G=是圖是圖,如果存在雙射如果存在雙射f:VV 且且任何任何vi,vjV,若邊若邊(vi,vj)E,當且僅當當且僅當 邊邊(f(vi),f(vj)E,(或或若邊若邊E,當且僅當當且僅當 邊邊E),則稱則稱G與與

15、G同構同構,記作記作G G. (同構圖要保持邊的同構圖要保持邊的“關聯關聯”關系關系)例如例如:右邊所示的兩個圖右邊所示的兩個圖:G= G=構造映射構造映射f:VV兩個圖同構的必要條件兩個圖同構的必要條件:1.結點個數相等結點個數相等. 2.邊數相等邊數相等.3.度數相同的結點數相等度數相同的結點數相等. 4. 對應結點的度數相等對應結點的度數相等.a bc d1 43 2a 1b 2c 3d 4下面是否同構的圖下面是否同構的圖?右面兩個圖不同構右面兩個圖不同構:左圖中四個左圖中四個3度結點度結點構成四邊形構成四邊形,而右圖而右圖則不然則不然.a fb ec d 3 51 62 4 31 2

16、ab c ab ec d 13 45 2 練習練習:請畫出請畫出K4的所有不同構的生成子圖的所有不同構的生成子圖.本節要求本節要求:準確掌握如下基本概念和定理準確掌握如下基本概念和定理:1.有向邊有向邊,無向邊無向邊,孤立結點孤立結點,平行邊平行邊,環環.2.有向圖有向圖,無向圖無向圖,零圖零圖,平凡圖平凡圖,簡單圖簡單圖,多重圖多重圖,完全圖完全圖,子圖子圖,生成子圖生成子圖,補圖補圖,相對補圖相對補圖3.四個定理四個定理(關于結點度關于結點度,以及結點度與邊數關系以及結點度與邊數關系)4.圖的同構圖的同構 (會判斷會判斷).作業作業: P279 (1) (2) (4) (5) 8-2. 路

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

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

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

20、路通路.如果一條如果一條回路回路中中,除起點和終點外除起點和終點外,其余其余結點都不同結點都不同,則稱則稱此回路為此回路為圈圈.例如右圖中例如右圖中: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個結點的圖中個結點的圖中,如果從結點如果從結點vi到到vj存存在一條路在一條路,則從則從vi到到vj必存在一條長度不多于必存在一

21、條長度不多于n-1的路的路.*證明證明: 設設vi到到vj存在一條路存在一條路: vivi+1vi+2,vj ,設此路的長度為設此路的長度為k.假設假設kn-1, 則此路中有則此路中有 k+1個結點個結點, k+1n, 而而G中只有中只有n個結點個結點, 所以此路中必有兩個結點相同所以此路中必有兩個結點相同, 假設假設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.兩個結點是連通的兩個結點是連通的: 在無向圖中在無向圖中,結點結點u和和v之間之間如果存在一條路如果存在一條路, 則稱則稱u與與v是連通的是連通的. 我們規定我們規定: 對任何結點對任何結點u, u與與u是連通的是連通的.2.結點之間的連通關系是個等價關系結點之間的連通關系是個等價關系. 令令G=

23、是無向圖是無向圖, R是是V上連通關系上連通關系, 即即 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上連通關系上連通關系, 設設R對對V的的商集商集中有等價類中有等價類V1,V2,V3, Vn ,這這n個個等價類等價類構成構成的的n個子圖

24、分別記作個子圖分別記作G(V1),G(V2),G(V3), G(Vn),并稱它并稱它們為們為G的連通分支的連通分支. 并用并用W(G)表示表示G中連通分支數中連通分支數.下邊例中下邊例中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, 在此路上必存在結點在此路上必存在結點u和和v,使得使得uV1, vV2 ,且且(u,v)是此路中是此路中的一條邊的一條邊. 充分性充分性:已知對已知對V的任何分成的任何分成V1、V2的劃分的劃分,恒存在一條邊恒存在一條邊,使它的兩個端點分別屬于使它的兩個端點分別屬于V1和和V2 (反證法反證法)假設假設G不是連通的不是連通的. 則則G

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

27、去的需要刪去的結點集合或邊的集合結點集合或邊的集合.1.點割集與割點點割集與割點:令令G=是是連通無向圖連通無向圖, 結點集合結點集合V1 , V1 V, 如果刪去如果刪去V1中所有結點后中所有結點后,G就變得不連通了就變得不連通了, 而刪而刪去去V1的任何真子集中的所有結點的任何真子集中的所有結點,得到的子圖仍然連通得到的子圖仍然連通.則則稱稱V1是是G的一個的一個點割集點割集. 如果點割集如果點割集V1中只有一個結點中只有一個結點, 則稱此結點為則稱此結點為割點割點.注注:在圖中刪除結點在圖中刪除結點u,是指把是指把u以及與以及與u關聯的邊都刪除關聯的邊都刪除.在圖中刪除某邊在圖中刪除某邊

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不連通不連通,至少要刪去的結點數至少要刪去的結點數. 上例中上例中 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 :一個連通圖中結點一個連通圖中結點v是是割點割點的充分且必要條件的充分且必要條件是存在兩個結點是存在兩個結點u和和w, 使得從使得從u到到w的任何路都通過的任何路都通過 v .證明證明:略略上邊是通過刪去結點的辦法使連通圖變得不連通的上邊是通過刪去結點的辦法使連通圖變得不連通的. 也可以通過刪去邊的辦法使連通圖變得不連通也可以通過刪去邊的辦法使連通圖變得不連通.3. 邊割集與割邊邊割集與割邊(橋橋)令令G=是是連通無向圖連通無向圖, 邊的集合邊的集合E1,E1 E, 如果刪去如果刪去E1中所有邊后中所有邊后,G就變得不連通了就變得不連通了, 而刪去

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

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

32、的長度的長度,稱之為從稱之為從u到到v的距離的距離.記作記作d. 上例中上例中 d=1 d=2 d=0 d= 3. 可達性的性質可達性的性質: 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. 強連通、單側連通和弱連通強連通、單側連通和弱連通 在在簡單有向

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

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

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

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

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

39、陣這里主要討論圖的三種矩陣.一一. 鄰接矩陣鄰接矩陣 這是以這是以結點結點與與結點結點之間的鄰接關系確定的矩陣之間的鄰接關系確定的矩陣.1.定義定義:設設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.從鄰接矩陣看圖的性質從鄰接矩陣看圖的性質: 無向圖無向圖:每行每行1的個數的個數=每列每列1的個數的個數=對應結點的度對應

40、結點的度 有向圖有向圖:每每行行1的個數的個數=對應結點的對應結點的出度出度 每每列列1的個數的個數=對應結點的對應結點的入度入度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設設G=是簡單圖是簡單圖,令令V=v1,v2,v3,vn, G的的鄰接矩陣鄰接矩陣(A(G)k中的第中的第 i行第行第j列元素列元素aijk=m, 表示在圖

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

43、 其它情況其它情況2.求可達矩陣求可達矩陣 可以根據鄰接矩陣可以根據鄰接矩陣A求可達矩陣求可達矩陣. 設設|V(G)|=n 令令A(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)轉置得轉置得PT=(pTij), 如果如果vi與與vj相互可達相互可達,則則 pij= pTij =1進而求進而求PPT對對PPT進行初等變換進行初等變換 第第2行與第行與第3行交換行交換,再第再第2列與第列與第3列交換列交換最后得兩個強分圖最后得兩個強分圖:v1,v3和和v2,v4,v5三三.完全關聯矩陣完全關聯矩陣 此矩陣是按照此矩陣是按照結點結點與與邊邊之間的關聯關系確定的矩陣之間的關聯關系確定的矩陣.1111101011111110101101011P=1010011111101001111111111PT=PPT=10100010111010001011

46、010111100011000001110011100111初等變換得v1v3v2v4v51.無向圖的完全關聯矩陣無向圖的完全關聯矩陣 1).定義定義:設設G=是個無向圖是個無向圖,V=v1,v2,v3,vm , E=e1,e2,e3,en ,一個一個mn階矩陣階矩陣M=(mij)稱為稱為G的完的完全關聯矩陣全關聯矩陣. 其中其中:2).從關聯矩陣看圖的性質從關聯矩陣看圖的性質: a)每列每列只有二個只有二個1. (因為每條邊只關聯兩個結點因為每條邊只關聯兩個結點) b)每行中每行中1的個數為對應的個數為對應 結點的度數結點的度數. c)如果兩列相同如果兩列相同,則說明對應的則說明對應的 兩條

47、邊是平行邊兩條邊是平行邊.mij = 1 vi與與ej關聯關聯 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.有向圖的完全關聯矩陣有向圖的完全關聯矩陣 1).定義定義:設設G=是個簡單有向是個簡單有向圖圖,V=v1,v2,v3,vm , E=e1,e2,e3,en , 一個一個mn階矩陣階矩陣M=(mij)稱為稱為G的完全關聯矩的完全關聯矩陣陣. 其中其中: 2)

48、.從關聯矩陣看圖的性質從關聯矩陣看圖的性質: a)每列只有一個每列只有一個1和一個和一個-1. (每條邊有一個起點一個終點每條邊有一個起點一個終點) b)每行中每行中1的個數為對應結點的個數為對應結點 的出度的出度.-1個數是結點入度個數是結點入度mij = 1 vi是是ej的起點的起點 -1 vi是是ej的終點的終點 0 vi與與ej不關聯不關聯 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本節重點掌握本節重點掌握: 圖的三個矩陣的求法圖的三個矩陣的求法 由圖的矩陣由圖的矩陣,看圖的性質看圖的性質. 作業作業 P300 (3)一一.歐拉圖歐拉圖: 1.歐拉路歐拉路:在無孤立結點的圖在無孤立結點的圖G中中,如果存在一條如果存在一條路路,它經過圖它經過圖中每條邊一次且僅一次中每條邊一次且僅一次, 稱此路為歐拉路稱此路為歐拉路. 2.歐拉回路歐拉回路:在無孤立結點的圖在無孤立結點的圖G中中,若存在一條若存在一條回路回路,它經過它經過圖中每條邊一次且僅一次圖中每條邊一次且僅一次,稱此回路為歐拉回路稱此回路為歐拉回路. 稱此圖為歐拉圖稱此圖為歐拉圖,或或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是連通的是連通的,且有且有零個零個或或兩個兩個奇數度的結點奇數度的結點.*證明證明:必要性必要性.(見教材見教材P302)充分性充分性,

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

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

53、數此圖中所有結點度均為偶數,所以有歐拉回路所以有歐拉回路.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.歐拉圖的應用歐拉圖的應用-計算機鼓輪的設計計算機鼓輪的設計早期向計算機輸入數據早期向計算機輸入數據, 為簡單為簡單,以輸入八進制數為例以輸入八進制數為例 (0,1,2,3,4,5,6,7,即即000,001,010,011,100,101,110,111)鼓輪表面分成鼓輪表面分成23等分等分,每一等分分別用絕緣體或導體組成每一等分分別用絕緣體或導體組成,絕緣部分輸出絕緣部分輸出

55、0,導體部分輸出導體部分輸出1. 有三個觸點分別與三個有三個觸點分別與三個部分接觸部分接觸,以讀取三個數字以讀取三個數字. 如圖所示如圖所示:轉動鼓輪轉動鼓輪,分別輸出分別輸出8個數個數:000,001,010,011,100,101,110,111 下面介紹此鼓輪的設計過程下面介紹此鼓輪的設計過程:00001111 此輪的設計此輪的設計:以兩位二進制數以兩位二進制數V=00,01,10,11為結點為結點,畫帶權圖畫帶權圖(即邊上標有數字即邊上標有數字-稱為邊的權稱為邊的權), 從任何從任何a1a2V結點畫有向邊結點畫有向邊,標的權標的權0(或或1), 該邊指向結點該邊指向結點a20(或或a2

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

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

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

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

60、中并不滿足并不滿足任意兩個結點度數之和大于任意兩個結點度數之和大于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中所中所有結點及與這些結點關聯的邊所得到的子圖的連通分支數有結點及與這些結點關聯的邊所得到的子圖的連通分支數.證明證明:設設C是圖是圖G的一條的一條H回路回路,則對于則對于V的任何非空子集的任何非空子集S,在在C中刪去中刪去S中任意一個結點中任意一個結點v1后后, 則