chapter單擊此處編輯母版標(biāo)題

1、圖論圖論簡介簡介圖論圖論是數(shù)學(xué)的一個(gè)分支是數(shù)學(xué)的一個(gè)分支, ,以圖為研究對(duì)象以圖為研究對(duì)象. .這種圖這種圖由若干給定的由若干給定的點(diǎn)點(diǎn)和連接兩點(diǎn)的和連接兩點(diǎn)的線線構(gòu)成構(gòu)成, ,借以描借以描述某些事物之間的關(guān)系述某些事物之間的關(guān)系. .用點(diǎn)代表事物用點(diǎn)代表事物, ,用連接用連接兩點(diǎn)的線表示兩個(gè)事物之間具有特定關(guān)系兩點(diǎn)的線表示兩個(gè)事物之間具有特定關(guān)系. .圖論起源于圖論起源于1818世紀(jì)世紀(jì), ,追朔到追朔到17361736年瑞士數(shù)學(xué)家年瑞士數(shù)學(xué)家L.EulerL.Euler出版第一本圖論著作出版第一本圖論著作, ,提出和解決著名提出和解決著名KonigsbergKonigsberg七橋問題七橋

2、問題. .從那時(shí)以來從那時(shí)以來, ,圖論不僅在圖論不僅在許多領(lǐng)域許多領(lǐng)域, ,如計(jì)算機(jī)科學(xué)如計(jì)算機(jī)科學(xué), ,運(yùn)籌學(xué)運(yùn)籌學(xué), ,心理學(xué)等方心理學(xué)等方面得到了廣泛的應(yīng)用面得到了廣泛的應(yīng)用, ,而且學(xué)科本身也獲得長而且學(xué)科本身也獲得長足發(fā)展足發(fā)展, ,形成了擬陣?yán)碚撔纬闪藬M陣?yán)碚? ,超圖理論超圖理論, ,代數(shù)圖論代數(shù)圖論, ,拓?fù)鋱D論等新分支拓?fù)鋱D論等新分支.(.(8.5,8.88.5,8.8二節(jié)不講二節(jié)不講) )圖圖的定義與記號(hào)的定義與記號(hào) 圖圖G G是一個(gè)二重組是一個(gè)二重組:G=:G= V V, ,E E , ,其中其中V V是非空是非空有限有限集集合合, ,它的元素稱為它的元素稱為結(jié)點(diǎn)結(jié)點(diǎn),

3、 E, E 也是也是( (可空可空) )有限有限集合集合, ,它的元素稱為它的元素稱為邊邊. . 圖圖G G的邊的邊e e是一個(gè)結(jié)點(diǎn)二重組是一個(gè)結(jié)點(diǎn)二重組: : a,ba,b ,a,b,a,b V,eV,e可可以是有序的以是有序的, ,稱為稱為有向邊有向邊, ,簡稱為弧簡稱為弧,a,a稱為弧稱為弧e e的的始點(diǎn)始點(diǎn),b,b稱為稱為e e的的終點(diǎn)終點(diǎn); e; e也可以是無序的也可以是無序的, ,稱稱為為無向邊無向邊.e=.e= a,ba,b 時(shí)時(shí), ,稱稱e e與與a,ba,b關(guān)聯(lián)關(guān)聯(lián), ,或或a,ba,b與與e e關(guān)聯(lián)關(guān)聯(lián), ,或或a a與與b b相相鄰接鄰接; ;關(guān)聯(lián)于同一結(jié)點(diǎn)的一條邊關(guān)聯(lián)于

4、同一結(jié)點(diǎn)的一條邊稱為稱為自回路自回路. . 每條邊都是無向邊的圖稱為每條邊都是無向邊的圖稱為無向圖無向圖; ;每條邊都每條邊都是有向邊的圖稱為是有向邊的圖稱為有向圖有向圖; ;我們我們僅僅討論無向圖討論無向圖和有向圖和有向圖. (. (看看圖圖8.1-18.1-1和和圖圖8.1-28.1-2) )圖圖的定義與記號(hào)的定義與記號(hào)續(xù)續(xù) 不與任何結(jié)點(diǎn)鄰接的結(jié)點(diǎn)稱為不與任何結(jié)點(diǎn)鄰接的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)孤立結(jié)點(diǎn), ,全為全為孤立結(jié)點(diǎn)組成的圖孤立結(jié)點(diǎn)組成的圖( (視為無向圖有向圖均可視為無向圖有向圖均可) )稱稱為為零圖零圖. . 在無向圖中兩結(jié)點(diǎn)間在無向圖中兩結(jié)點(diǎn)間( (包括結(jié)點(diǎn)自身包括結(jié)點(diǎn)自身) )若多于

5、一若多于一條邊，則稱這幾條邊為條邊，則稱這幾條邊為平行邊平行邊. .在有向圖中若在有向圖中若同始點(diǎn)和同終點(diǎn)的邊多于一條同始點(diǎn)和同終點(diǎn)的邊多于一條, ,則稱這幾條邊則稱這幾條邊為為平行邊平行邊, ,平行邊的條數(shù)稱為該邊的平行邊的條數(shù)稱為該邊的重?cái)?shù)重?cái)?shù). .含平含平行邊的圖稱為行邊的圖稱為多重圖多重圖, ,非多重圖稱為非多重圖稱為線圖線圖. .無自無自回路的線圖稱為回路的線圖稱為簡單圖簡單圖. .例子見圖例子見圖8.1-38.1-3. . 有向圖去掉方向所得無向圖稱為該圖的有向圖去掉方向所得無向圖稱為該圖的底圖底圖. .常用一個(gè)圖形來表示常用一個(gè)圖形來表示圖圖稱為稱為圖圖的的圖示圖示degdeg+

6、 +(1)=2,deg(1)=2,deg- -(1)=0, deg(1)=deg(2)=(1)=0, deg(1)=deg(2)=degdeg+ +(2)=deg(2)=deg- -(2)=1,(2)=1, =deg(6)=3. =deg(6)=3.deg(1)=deg(1)=deg(4)=2.=deg(4)=2.1234abcd123456abcdef結(jié)點(diǎn)的結(jié)點(diǎn)的度度( (次數(shù)次數(shù)) ) 有向圖中有向圖中, ,以結(jié)點(diǎn)以結(jié)點(diǎn)v v為始點(diǎn)的邊數(shù)稱為為始點(diǎn)的邊數(shù)稱為v v的的出度出度, ,記為記為degdeg+ +(v);(v);以結(jié)點(diǎn)以結(jié)點(diǎn)v v為終點(diǎn)的邊數(shù)稱為為終點(diǎn)的邊數(shù)稱為v v的的入入度度

7、, ,記為記為degdeg- -(v);(v);它們的和它們的和: : deg(v)=deg deg(v)=deg+ +(v)+deg(v)+deg- -(v) (v) 稱為稱為v v的的度度. . 無向圖中無向圖中, ,與結(jié)點(diǎn)與結(jié)點(diǎn)v v相關(guān)聯(lián)的邊數(shù)稱為相關(guān)聯(lián)的邊數(shù)稱為v v的的度度, ,記記為為deg(v).deg(v). 各結(jié)點(diǎn)的度都相等的圖稱為各結(jié)點(diǎn)的度都相等的圖稱為正則圖正則圖, ,或或k-k-正則正則圖圖, ,其中其中k k為結(jié)點(diǎn)度的公共值為結(jié)點(diǎn)度的公共值.(.(注注: :可以只考慮可以只考慮正則的無向圖正則的無向圖, ,然后再定義其底圖的無向圖是然后再定義其底圖的無向圖是正則圖的

8、有向圖為正則有向圖正則圖的有向圖為正則有向圖.).) 例子見上一張幻燈片和例子見上一張幻燈片和圖圖8.1-58.1-5. .關(guān)于有關(guān)于有 n n 結(jié)點(diǎn)結(jié)點(diǎn) m m 邊的邊的(n,m)(n,m)圖圖度的定理度的定理 定理定理8.1-18.1-1 令令 v v1 1, , ,v vn n為圖的所有結(jié)點(diǎn)為圖的所有結(jié)點(diǎn), ,則則 i=1i=1n n deg(vdeg(vi i)=2m. (1)=2m. (1)證證: :對(duì)于公式對(duì)于公式(1)(1)左邊的和式左邊的和式, ,圖的每條邊貢獻(xiàn)的圖的每條邊貢獻(xiàn)的度數(shù)恰為度數(shù)恰為2,2,從而結(jié)論成立從而結(jié)論成立. .注注: :對(duì)有向圖對(duì)有向圖(1)(1)可寫成可

9、寫成 i=1i=1n n degdeg+ +(v)+(v)+ i=1i=1n n degdeg- -(v)=2m.(v)=2m.定理定理8.1-28.1-2 任何圖中度為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)任何圖中度為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè). .證證: : 因偶度點(diǎn)度的和為偶數(shù)因偶度點(diǎn)度的和為偶數(shù), ,若奇度點(diǎn)為奇數(shù)個(gè)若奇度點(diǎn)為奇數(shù)個(gè), ,則奇度點(diǎn)度的和必為奇數(shù)則奇度點(diǎn)度的和必為奇數(shù). .但偶數(shù)加奇數(shù)得奇但偶數(shù)加奇數(shù)得奇數(shù)數(shù), ,便與便與(1)(1)式右邊為偶數(shù)相式右邊為偶數(shù)相矛盾矛盾. .8.1#4(c)8.1#4(c)簡單無向圖簡單無向圖 G G 必有必有2 2結(jié)點(diǎn)同度結(jié)點(diǎn)同度證證: :令令 G=vG=v1

10、 1, ,v,vn n.若若 G G 中中沒有孤立點(diǎn)沒有孤立點(diǎn), ,則則 G G 中中 n n個(gè)結(jié)點(diǎn)的度只取個(gè)結(jié)點(diǎn)的度只取 n-1n-1 個(gè)可能值個(gè)可能值: : 1,2,1,2,n-1,n-1,從而從而 G G 中至少有兩個(gè)結(jié)點(diǎn)的度相同中至少有兩個(gè)結(jié)點(diǎn)的度相同. .否則否則,G,G中有孤立點(diǎn)中有孤立點(diǎn), ,不妨設(shè)不妨設(shè)v vk k,v,vk+1k+1, ,v,vn n為全部為全部孤立點(diǎn)孤立點(diǎn), ,則則 v v1 1, ,v,vk-1k-1的度只取的度只取 k-2k-2個(gè)可能值個(gè)可能值: : 1,2,1,2,k-2,k-2,從而此從而此 k-1k-1個(gè)結(jié)點(diǎn)中至少有兩個(gè)個(gè)結(jié)點(diǎn)中至少有兩個(gè)同度點(diǎn)同度

11、點(diǎn). .圖的圖的同構(gòu)同構(gòu)定義定義: :對(duì)給定兩個(gè)圖對(duì)給定兩個(gè)圖 G=G= V,EV,E ,G,G = = V V ,E,E , ,若存在若存在雙射雙射 f:Vf:VV V 使對(duì)任意使對(duì)任意a,ba,b V, V, (a,b) (a,b) E E (f(a),f(b)(f(a),f(b) E E , ,并且并且(a,b)(a,b)與與(f(a),f(b)(f(a),f(b)有相同重?cái)?shù)有相同重?cái)?shù), ,則稱則稱 G G 與與 G G 同構(gòu)同構(gòu), ,記記為為 G G G G . .注注: : 兩圖同構(gòu)是相互的兩圖同構(gòu)是相互的: G: G G G G G G.G. 兩圖同構(gòu)時(shí)不僅結(jié)點(diǎn)之間要有一一對(duì)應(yīng)關(guān)系

12、兩圖同構(gòu)時(shí)不僅結(jié)點(diǎn)之間要有一一對(duì)應(yīng)關(guān)系, ,而且要求這種對(duì)應(yīng)關(guān)系而且要求這種對(duì)應(yīng)關(guān)系保持保持結(jié)點(diǎn)間的結(jié)點(diǎn)間的鄰接關(guān)鄰接關(guān)系系. .對(duì)有向圖同構(gòu)還要求對(duì)有向圖同構(gòu)還要求保持邊的方向保持邊的方向. . 尋求判斷圖同構(gòu)的簡單有效方法仍是圖論待尋求判斷圖同構(gòu)的簡單有效方法仍是圖論待解決的重要問題解決的重要問題. .同構(gòu)圖同構(gòu)圖舉例舉例 G G G G H H H H1 1a,2a,2b,3b,3c, c, 1 1a,2a,2b,3b,3c,c, 4 4d 4d 4d,5d,5e,6e,6f f1234abcd123456abcdefGGHH非同構(gòu)圖非同構(gòu)圖舉例舉例存在結(jié)點(diǎn)數(shù)及每個(gè)結(jié)點(diǎn)對(duì)應(yīng)度都相等的兩個(gè)

13、圖存在結(jié)點(diǎn)數(shù)及每個(gè)結(jié)點(diǎn)對(duì)應(yīng)度都相等的兩個(gè)圖仍然不同構(gòu)的情況仍然不同構(gòu)的情況. .一個(gè)例子是一個(gè)例子是圖圖8.1-88.1-8; ;另一另一例如下例如下:(:(注意注意: :兩個(gè)兩個(gè)4 4度點(diǎn)或鄰接或不相鄰接度點(diǎn)或鄰接或不相鄰接) )GG子圖的概念子圖的概念定義定義: :給定兩個(gè)無給定兩個(gè)無( (有有) )向圖向圖 G=G= V,EV,E ,G,G = = V V ,E,E . .若若 V VV V 和和 E EE E, ,則稱則稱 G G 是是G G的的子圖子圖; ;若若 V VV,EV,EE,E,且且 G G G G, ,則稱則稱 G G 是是 G G 的的真子圖真子圖; ;若若 V V =

14、V=V 和和 E EE E, ,則稱則稱 G G 是是 G G 的的生成子圖生成子圖; ;若子圖若子圖 G G 無孤立結(jié)點(diǎn)且無孤立結(jié)點(diǎn)且G G 由由E E 唯一確定唯一確定, ,則稱則稱G G 是是由由邊集邊集E E 導(dǎo)出的子圖導(dǎo)出的子圖; ;若對(duì)子圖若對(duì)子圖 G G = = V V ,E,E 中任二結(jié)點(diǎn)中任二結(jié)點(diǎn) u,v,(u,v)u,v,(u,v) E E (u,v)(u,v) E E , ,則稱則稱 G G 是由是由結(jié)點(diǎn)集結(jié)點(diǎn)集V V 導(dǎo)出的子圖導(dǎo)出的子圖( (易見易見:V:V 導(dǎo)出的子圖導(dǎo)出的子圖G G 是以是以V V 為其結(jié)點(diǎn)集為其結(jié)點(diǎn)集, ,所有所有在在G G中同時(shí)關(guān)聯(lián)于中同時(shí)關(guān)聯(lián)

15、于V V 中兩點(diǎn)的邊為其邊集中兩點(diǎn)的邊為其邊集).).有向圖子圖舉例有向圖子圖舉例( (圖圖8.1-108.1-10) ): :由由(1,2),(1,4),(5,1)(1,2),(1,4),(5,1)導(dǎo)出的子圖導(dǎo)出的子圖; ; : :由由(1,2),(3,2),(3,4),(1,4)(1,2),(3,2),(3,4),(1,4)導(dǎo)出的子圖導(dǎo)出的子圖( (也是此也是此4 4點(diǎn)導(dǎo)出的子圖點(diǎn)導(dǎo)出的子圖); ); : :由由1,2,4,51,2,4,5導(dǎo)出的子圖導(dǎo)出的子圖. . 11112222555334444完全圖完全圖與與補(bǔ)圖補(bǔ)圖 E=VE=V V V的有向圖的有向圖G=G= V,EV,E 稱為

16、稱為有向完全圖有向完全圖.n.n個(gè)結(jié)個(gè)結(jié)點(diǎn)的點(diǎn)的無向簡單圖無向簡單圖如果任二不同結(jié)點(diǎn)都相鄰時(shí)如果任二不同結(jié)點(diǎn)都相鄰時(shí), ,稱為稱為n n結(jié)點(diǎn)結(jié)點(diǎn)無向完全圖無向完全圖, ,記為記為 K Kn n. .完全圖的例子完全圖的例子見圖見圖8.1-118.1-11. . n n 結(jié)點(diǎn)線圖結(jié)點(diǎn)線圖G=G= V,EV,E 與與H=H= V,EV,E 稱稱互為補(bǔ)圖互為補(bǔ)圖( (記為記為G=HG=H或或H=GH=G),),如果如果E E是是n n結(jié)點(diǎn)完全圖的邊集與結(jié)點(diǎn)完全圖的邊集與E E的差集的差集. .下列二無向圖下列二無向圖G G與與H H互為補(bǔ)圖互為補(bǔ)圖. .GHK4 48.1#138.1#13的用紅的用

17、紅, ,蘭色給蘭色給 K K6 6邊著色邊著色命題命題: :對(duì)任意一種著色方案的著色結(jié)果對(duì)任意一種著色方案的著色結(jié)果, ,或者有一或者有一個(gè)紅個(gè)紅 K K3 3, ,或者有一個(gè)蘭或者有一個(gè)蘭 K K3 3. .證證: :令令a,b,c,d,e,fa,b,c,d,e,f為為K K6 6的的6 6結(jié)點(diǎn)結(jié)點(diǎn). .因過因過f f的的5 5條邊必條邊必有三邊著為同色有三邊著為同色, ,不失一般性不失一般性, ,設(shè)設(shè)(a,f),(b,f), (a,f),(b,f), (c,f)(c,f)已著紅色已著紅色. .若若(a,b),(a,c),(b,c)(a,b),(a,c),(b,c)已著蘭已著蘭色色, ,則則

18、a,b,ca,b,c導(dǎo)出的子圖是一個(gè)蘭導(dǎo)出的子圖是一個(gè)蘭K K3 3, ,從而結(jié)從而結(jié)論成立論成立. . 否則否則此三邊必有一邊此三邊必有一邊, ,例如例如(a,b)(a,b)已著已著紅色紅色, ,則則a,b,fa,b,f導(dǎo)出的的子圖是紅導(dǎo)出的的子圖是紅 K K3 3. .證畢證畢. .推論推論: :任何任何6 6人的人群中人的人群中, ,或者有或者有3 3人互相認(rèn)識(shí)人互相認(rèn)識(shí), ,或或者有者有3 3人彼此陌生人彼此陌生.(.(當(dāng)二人當(dāng)二人x,yx,y互相認(rèn)識(shí)互相認(rèn)識(shí), ,邊邊(x,y)(x,y)著紅色著紅色, ,否則著蘭色否則著蘭色. .則則6 6人認(rèn)識(shí)情況對(duì)應(yīng)人認(rèn)識(shí)情況對(duì)應(yīng)于于K K6 6

19、邊的一個(gè)二著色邊的一個(gè)二著色. .由上述命題知或者有紅由上述命題知或者有紅K K3 3或者有蘭或者有蘭K K3 3.).)fabcabc6改改5 5結(jié)論不成立結(jié)論不成立路徑與回路路徑與回路 圖圖 G=G= V,EV,E 的的點(diǎn)邊交替序列點(diǎn)邊交替序列 P=vP=v0 0e e1 1v v1 1e e2 2v v2 2 e en nv vn n稱為稱為 G G 的一條從的一條從v v0 0 到到v vn n的的長長為為 n n 的的路徑路徑, ,其其中中,e,ei i=(v=(vi-1i-1,v,vi i) ) E,i=1,E,i=1,n(,n(對(duì)有向圖要求對(duì)有向圖要求 v vi-1i-1,v,v

20、i i為為e ei i的的始始, ,終點(diǎn)終點(diǎn)).). P P 稱為稱為簡單路徑簡單路徑, ,如果如果 e e1 1, , ,e,en n 兩兩不同兩兩不同; ; P P 稱為稱為基本路徑基本路徑( (鏈鏈),),如果如果 v v0 0,v,v1 1, , ,v,vn n 兩兩不兩兩不同同( (易見易見鏈必為簡單路徑鏈必為簡單路徑); P); P 稱為稱為回路回路, ,如果如果 v v0 0= = v vn n; ; 回路回路 P P 稱為稱為簡單簡單( (基本基本) )回路回路, ,如果如果e e1 1, , ,e,en n(v(v1 1, , ,v,vn n) )兩兩不同兩兩不同. . 路徑

21、路徑 P P 可只用邊序列可只用邊序列 e e1 1e e2 2 e en n表示表示. .若若 G G 為為線圖線圖, ,則路徑則路徑 P P 也可只用結(jié)點(diǎn)序列也可只用結(jié)點(diǎn)序列 v v0 0v v1 1 v vn n 表示表示. . 例見例見圖圖8.2-18.2-1. . 任何圖任何圖 G G 中中有有從從 u u 到到 w w 的的路徑路徑( (回路回路) )必必有有從從 u u 到到 w w 的的基本路徑基本路徑( (回路回路) )由于由于G G有從有從u u到到w w的路徑的路徑,G,G必有一條長度最小的從必有一條長度最小的從u u到到w w的路徑的路徑:P.:P.如果如果P P不是基

22、本路徑不是基本路徑, ,則則 P=ueP=ue1 1v v1 1e e2 2 v vi ie ei+1i+1 v vj je ej+1 j+1 e en nw w 中中 v vi i=v=vj j, ,于是于是 P-eP-ei+1i+1, , ,e,ej j 仍是仍是G G的一條從的一條從u u到到w w的路徑的路徑, ,但長但長度比度比P P長度還要長度還要小小, ,得出得出矛盾矛盾. .v vi iv vj+1j+1v vj-1j-1v vi+1i+1v vn-1n-1uwv v1 1P在在 n n 結(jié)點(diǎn)的圖中任何結(jié)點(diǎn)的圖中任何鏈鏈的長度都的長度都不大于不大于 n-1n-1; ;任何任何基

23、本回路基本回路的長度都的長度都不大于不大于 n n證證: :設(shè)任一鏈設(shè)任一鏈 P P 的長度為的長度為k,k,則則 P P穿程于穿程于 k+1k+1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn): :P P = = v v0 0e e1 1v v1 1e e2 2v v2 2 e ek kv vk kv vk k. . 因因 v v0 0,v,v1 1, , ,v,vk k 兩兩不同兩兩不同, ,故故 k+1k+1 n,n,從而從而 k k n-1.n-1.同理同理, ,長度為長度為k k的基本回路有的基本回路有 k k 個(gè)不同結(jié)點(diǎn)，從而個(gè)不同結(jié)點(diǎn)，從而 k k n. n. 距離距離的概念的概念 圖圖 G=G= V,EV,E

24、中中, ,從結(jié)點(diǎn)從結(jié)點(diǎn) u u 到到 w w 的的最短路徑最短路徑( (必為必為鏈鏈) )的的長度長度稱為稱為 G G 的從的從 u u 到到 w w 的的距離距離, ,記為記為 d(u,w)d(u,w). . 如果從如果從 u u 到到 w w沒有路徑?jīng)]有路徑, ,則令則令 d(u,w)=+d(u,w)=+ .(.(注意注意: :在無向圖中恒有在無向圖中恒有 d(u,w)=d(w,u),d(u,w)=d(w,u),而在有向圖中而在有向圖中可能出現(xiàn)可能出現(xiàn)d(u,w)d(u,w) d(w,u).)d(w,u).) 對(duì)任意對(duì)任意 u,v,wu,v,w V,d(u,v)V,d(u,v)是非負(fù)整數(shù)或

25、是非負(fù)整數(shù)或+ + ; ; d(u,v) d(u,v) 0;d(u,v)=00;d(u,v)=0 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) u=w;u=w; d(u,v)+d(v,w) d(u,v)+d(v,w) d(u,w)(d(u,w)(三角不等式三角不等式, ,距離特性距離特性) ) 三角不等式的證明三角不等式的證明: :若若 d(u,v)=+d(u,v)=+ 或或 d(v,w)=+d(v,w)=+ , ,結(jié)論顯然成立結(jié)論顯然成立. .否則否則, ,有從有從 u u 到到 v v 長長度為度為 d(u,v)d(u,v)的路徑和從的路徑和從v v到到w w長度為長度為d(v,w)d(v,w)的路的路徑徑, ,從而

26、有從從而有從u u到到w w長度為長度為d(u,v)+d(v,w)d(u,v)+d(v,w)的路徑的路徑. .無向圖無向圖的的連通性連通性 在無向圖在無向圖G G中中, ,若有從結(jié)點(diǎn)若有從結(jié)點(diǎn)u u到到w w的路徑的路徑( (或從或從u u到到w w的的鏈鏈, ,因有因有u-wu-w路必有路必有u-wu-w鏈鏈),),則稱從則稱從u u到到w w可達(dá)可達(dá). .約定約定每個(gè)結(jié)點(diǎn)到自身可達(dá)每個(gè)結(jié)點(diǎn)到自身可達(dá).(.(圖圖8.2-2(b)8.2-2(b) ) 無向圖稱為是無向圖稱為是連通連通的的, ,如果任二結(jié)點(diǎn)都可達(dá)如果任二結(jié)點(diǎn)都可達(dá). .易易見見: : G G 連通當(dāng)且僅當(dāng)連通當(dāng)且僅當(dāng) G G 有

27、一個(gè)生成子圖連通有一個(gè)生成子圖連通. . 無向圖結(jié)點(diǎn)間的無向圖結(jié)點(diǎn)間的可達(dá)關(guān)系是等價(jià)關(guān)系可達(dá)關(guān)系是等價(jià)關(guān)系( (滿足自滿足自反反, ,對(duì)稱和傳遞律對(duì)稱和傳遞律),),因此其因此其商集商集給出給出 G G 的結(jié)點(diǎn)集的結(jié)點(diǎn)集的一個(gè)的一個(gè)劃分劃分, ,屬于一個(gè)等價(jià)類的結(jié)點(diǎn)導(dǎo)出屬于一個(gè)等價(jià)類的結(jié)點(diǎn)導(dǎo)出 G G 的一的一個(gè)連通子圖個(gè)連通子圖, ,且不存在以此子圖為真子圖的連且不存在以此子圖為真子圖的連通子圖通子圖. .故把這些連通子圖稱為故把這些連通子圖稱為G G的的連通分支連通分支.G.G的任何二結(jié)點(diǎn)相互可達(dá)的任何二結(jié)點(diǎn)相互可達(dá)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)它們屬于同一它們屬于同一個(gè)連通分支個(gè)連通分支.G.G為連通

28、當(dāng)且僅當(dāng)它為連通當(dāng)且僅當(dāng)它恰有一個(gè)恰有一個(gè)連通連通分支分支. G. G的連通分支數(shù)記為的連通分支數(shù)記為 (G)(G). .有向圖有向圖的的連通性連通性 已知有向圖已知有向圖 G,G,若它的若它的底圖底圖是連通無向圖是連通無向圖, ,則則 G G 稱為是稱為是弱連通弱連通的的; ;若若 G G 的任二結(jié)點(diǎn)都相互可達(dá)的任二結(jié)點(diǎn)都相互可達(dá), ,則則G G稱為是稱為是強(qiáng)連通強(qiáng)連通的的; ;若若 G G 的任二結(jié)點(diǎn)至少從一的任二結(jié)點(diǎn)至少從一個(gè)到另一個(gè)可達(dá)個(gè)到另一個(gè)可達(dá), ,則則 G G 稱為是稱為是單向連通單向連通的的. . 易見易見: :強(qiáng)連通性強(qiáng)連通性 單向連通性單向連通性 弱連通性弱連通性; ;

29、但反之不真但反之不真. .反例如下反例如下: : 強(qiáng)連通強(qiáng)連通 單向連通非強(qiáng)連通單向連通非強(qiáng)連通 弱連通非單向連通弱連通非單向連通 從從a a到到b b不可達(dá)不可達(dá) 從從a a到到b b不可達(dá)且不可達(dá)且 從從b b到到a a不可達(dá)不可達(dá)aabbcd有向圖有向圖的強(qiáng)的強(qiáng)( (單向單向, ,弱弱) )連通分支連通分支 已知有向圖已知有向圖 G G 及其子圖及其子圖 G G . .若若 G G 是強(qiáng)是強(qiáng)( (單向單向, ,弱弱) )連通的連通的, ,并且并且 G G 中沒有以中沒有以 G G 為真子圖的強(qiáng)為真子圖的強(qiáng)( (單向單向, ,弱弱) )連通子圖連通子圖, ,則稱則稱 G G 為為 G G

30、的的強(qiáng)強(qiáng)( (單向單向, ,弱弱) )連通分連通分支支. . 注注 一個(gè)有向圖的上述三種連通分支可能是一個(gè)有向圖的上述三種連通分支可能是互不相同的互不相同的, ,圖圖8.2-48.2-4中的圖就是這樣中的圖就是這樣. . 在有向圖中可用在有向圖中可用屬于同一強(qiáng)屬于同一強(qiáng)( (弱弱) )連通分連通分支支引入結(jié)點(diǎn)間的引入結(jié)點(diǎn)間的等價(jià)關(guān)系等價(jià)關(guān)系. .但對(duì)但對(duì)單向連通分單向連通分支支引入的關(guān)系不滿足引入的關(guān)系不滿足傳遞性傳遞性, ,從而不是等價(jià)關(guān)從而不是等價(jià)關(guān)系系( (圖圖8.2-58.2-5).).8.2#48.2#4無向圖無向圖 G G恰有的恰有的2 2個(gè)奇度結(jié)點(diǎn)個(gè)奇度結(jié)點(diǎn)可達(dá)可達(dá)解解1 1:

31、:令令u,wu,w為為G G恰有的恰有的2 2個(gè)奇度結(jié)點(diǎn)個(gè)奇度結(jié)點(diǎn). .考察考察u u所在的所在的連通分支連通分支G G. .因任何圖的因任何圖的奇度點(diǎn)為偶數(shù)奇度點(diǎn)為偶數(shù), ,故故G G至至少還有另一奇度點(diǎn)少還有另一奇度點(diǎn). .但但G G的每個(gè)點(diǎn)的每個(gè)點(diǎn)在在G G和和G G中有中有相同的度相同的度, ,所以所以G G恰有恰有2 2個(gè)奇度點(diǎn)而且就是個(gè)奇度點(diǎn)而且就是u u和和w.w.再由再由G G的的連通性連通性推出推出u u到到w w可達(dá)可達(dá). .解解2 2: :可一般地證明在可一般地證明在無向圖無向圖G G中從任一奇度點(diǎn)中從任一奇度點(diǎn)u u出出發(fā)的一條最長簡單路的另一端點(diǎn)必為一個(gè)奇度發(fā)的一條最

32、長簡單路的另一端點(diǎn)必為一個(gè)奇度點(diǎn)點(diǎn), ,原因是從原因是從u u出發(fā)的出發(fā)的最長最長簡單路不會(huì)終止在簡單路不會(huì)終止在u u處處( (否則否則d(u)d(u)為偶數(shù)為偶數(shù)););也不會(huì)終止在任一偶度也不會(huì)終止在任一偶度點(diǎn)點(diǎn)v v處處( (否則否則d(v)d(v)為奇數(shù)為奇數(shù)).).賦權(quán)圖賦權(quán)圖中的中的距離距離應(yīng)用廣泛的應(yīng)用廣泛的賦權(quán)圖賦權(quán)圖是三重組是三重組:G=:G= V,E,WV,E,W ,V,E,V,E 分別分別為為 G G 的結(jié)點(diǎn)集和邊集的結(jié)點(diǎn)集和邊集, ,W W是從是從 E E 到到 R R+ +的函數(shù)的函數(shù), ,邊邊e=(i,j)e=(i,j)的函數(shù)值的函數(shù)值 W(e)=W(i,j)W(

33、e)=W(i,j)稱為稱為 e e 的的權(quán)權(quán). . 賦權(quán)圖賦權(quán)圖 G G的一條路徑的一條路徑 P=(eP=(e1 1, ,e,ek k) )的的長度長度定義為定義為: : W(P)=W(eW(P)=W(e1 1)+)+W(e+W(ek k).).從結(jié)點(diǎn)從結(jié)點(diǎn)u u到到w w的的距離距離定義定義為為d(u,w)=d(u,w)=minminW(P)|PW(P)|P為為G G中從中從u u到到w w的路徑的路徑,約約定定:d(u,u)=0;d(u,w):d(u,u)=0;d(u,w) = = , ,當(dāng)從當(dāng)從u u到到w w不可達(dá)不可達(dá). .例如例如, ,對(duì)右邊的圖有對(duì)右邊的圖有d(a,c)=5;d(

34、a,c)=5; d(a,d)=9;d(a,d)=9;d(a,e)=7.d(a,e)=7.21073245abcde求已知求已知簡單連通賦權(quán)圖簡單連通賦權(quán)圖G G中從源點(diǎn)中從源點(diǎn)a a到到其它各點(diǎn)其它各點(diǎn)x x的最短距離的的最短距離的DijkstraDijkstra算法算法 步驟步驟 把結(jié)點(diǎn)集把結(jié)點(diǎn)集V V分割為二子集分割為二子集 S,T.S,T.開始時(shí)開始時(shí)S=a,T=S=a,T=V-SV-S. . 步驟步驟 對(duì)每結(jié)點(diǎn)對(duì)每結(jié)點(diǎn) t t T,T,求出求出 D(t)D(t)之后再定出之后再定出x x T T 使得使得 D(x)=D(x)= minD(x)|tminD(x)|t T.T. 步驟步驟

35、置置 S S 為為 S Sxx置置 T T為為T-x.T-x.若若 T=T=則則停止停止, ,否則轉(zhuǎn)步驟否則轉(zhuǎn)步驟作作下一次循環(huán)下一次循環(huán). .將證將證: :第第步求得的每一點(diǎn)步求得的每一點(diǎn)x x對(duì)應(yīng)有對(duì)應(yīng)有 D(x)=d(a,x)D(x)=d(a,x). . 開始時(shí)開始時(shí) 令令 D(t)=W(a,t),D(t)=W(a,t),結(jié)論顯然成立結(jié)論顯然成立: D(x)= : D(x)= minW(a,t)|tminW(a,t)|t T=d(a,x).T=d(a,x). 下一步對(duì)下一步對(duì)S S =S=Sx,Tx,T =T-x=T-x令令D D (t)(t)為為T T 中結(jié)中結(jié)點(diǎn)的點(diǎn)的D(t)D(t)

36、值值, ,則則 D D (t)(t)= = minD(t),D(x)+W(x,t)minD(t),D(x)+W(x,t). .DijkstraDijkstra算法的標(biāo)號(hào)法算法的標(biāo)號(hào)法舉例舉例21073645210736452210736452107364510 2 95225599990000用用DijkstraDijkstra算法的標(biāo)號(hào)法算法的標(biāo)號(hào)法解解8.2#11(b)8.2#11(b)11010141 05 326101555462233881063 EulerEuler路徑路徑與與EulerEuler圖圖 KonigsbergKonigsberg七橋問題七橋問題(1736(1736年年

37、).). 穿程于穿程于( (有向或無向有向或無向) )圖圖 G G 的每條邊一次且僅一的每條邊一次且僅一次的路徑次的路徑( (回路回路) )稱為稱為 EulerEuler 路徑路徑( (回路回路).). 具有具有 EulerEuler 回路的回路的連通連通圖稱為圖稱為EulerEuler圖圖. . EulerEuler定理定理 無向無向連通圖連通圖G G有一條有一條EulerEuler路徑當(dāng)且路徑當(dāng)且僅當(dāng)僅當(dāng) G G 有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)( (證明見教本證明見教本255255頁頁););有向有向連通圖連通圖G G有一條有一條EulerEuler路徑當(dāng)且僅路徑當(dāng)且僅當(dāng)當(dāng)

38、G G的每點(diǎn)出的每點(diǎn)出, ,入度相等入度相等, ,只有兩點(diǎn)例外只有兩點(diǎn)例外, ,并且它并且它們出們出, ,入度之差一為入度之差一為1,1,一為一為-1.-1. 推論推論 無向連通圖無向連通圖 G G 是是EulerEuler圖當(dāng)且僅當(dāng)圖當(dāng)且僅當(dāng) G G 的的結(jié)結(jié)點(diǎn)度數(shù)都是偶數(shù)點(diǎn)度數(shù)都是偶數(shù). . 應(yīng)用應(yīng)用: Konigsberg: Konigsberg七橋問題不可解七橋問題不可解, ,因?qū)?yīng)圖因?qū)?yīng)圖( (見見圖圖8.2-8(b)8.2-8(b) )都是都是 3 3 度結(jié)點(diǎn)度結(jié)點(diǎn). .用定理用定理8.2-48.2-4的證明方法的證明方法構(gòu)造構(gòu)造EulerEuler回路回路11555222334

39、441112341 1351 5245=12341 1352451=12341352451無向圖無向圖 G G 能否能否一筆畫一筆畫的問題等價(jià)于的問題等價(jià)于 G G 是是否有一條否有一條EulerEuler路徑路徑( (回路回路) )的問題的問題 若圖只有若圖只有兩個(gè)兩個(gè)奇結(jié)點(diǎn)奇結(jié)點(diǎn), ,則任何則任何EulerEuler路徑必路徑必從其中一點(diǎn)開始到另一點(diǎn)結(jié)束從其中一點(diǎn)開始到另一點(diǎn)結(jié)束. .利用這條規(guī)律利用這條規(guī)律, ,先在此先在此2 2奇點(diǎn)之間加條邊使之變成奇點(diǎn)之間加條邊使之變成EulerEuler圖并畫圖并畫出一條出一條EulerEuler回路回路, ,然后再去掉所加的邊即得一然后再去掉所加

40、的邊即得一條條EulerEuler路徑路徑. .ab123456789HamiltonHamilton路徑路徑與與HamiltonHamilton圖圖 無向連通圖無向連通圖G G穿程于穿程于G G 的每一結(jié)點(diǎn)的每一結(jié)點(diǎn)一次且僅一一次且僅一次次的路徑的路徑( (回路回路) )稱為稱為G G 的一條的一條HamiltonHamilton 路徑路徑( (回路回路););具有具有HamiltonHamilton回路的無向連通圖稱為回路的無向連通圖稱為HamiltonHamilton圖圖. .由定義知由定義知HamiltonHamilton 路徑路徑( (回路回路) )必必為為基本基本路徑路徑( (回路

41、回路).). 18591859年年IrelandIreland數(shù)學(xué)家數(shù)學(xué)家HamiltonHamilton提出環(huán)游世界提出環(huán)游世界游戲給出游戲給出HamiltonHamilton圖的一個(gè)經(jīng)典例子圖的一個(gè)經(jīng)典例子( (圖圖8.2-8.2-1111).). 可以證明可以證明: :對(duì)任意正整數(shù)對(duì)任意正整數(shù) n n 3 3 完全圖完全圖 K Kn n 恒有恒有HamiltonHamilton回路回路( (不難從任一點(diǎn)開始作出一條不難從任一點(diǎn)開始作出一條HamiltonHamilton回路回路, ,每一步都通到一個(gè)新結(jié)點(diǎn)每一步都通到一個(gè)新結(jié)點(diǎn), ,最后最后回到起點(diǎn)回到起點(diǎn)).().(推廣到賦權(quán)圖的情形推

42、廣到賦權(quán)圖的情形, ,求有最小權(quán)求有最小權(quán)的的HamiltonHamilton回路問題就是有名的回路問題就是有名的貨郎問題貨郎問題) )HamiltonHamilton圖圖的一個(gè)必要條件的一個(gè)必要條件 定理定理 若若G=G= V,EV,E 為為HamiltonHamilton圖圖, ,則對(duì)每個(gè)則對(duì)每個(gè)S S V V有有 (G-S)(G-S) |S|S|, ,其中其中 (G-S)(G-S)表示子圖表示子圖G-SG-S的連通分支數(shù)的連通分支數(shù). .證證: :設(shè)設(shè)C C是是G G的一條的一條HamiltonHamilton回路回路( (必為必為基本基本回路回路),),則對(duì)則對(duì)V V的任意真子集的任意

43、真子集S S都有都有 (C-S)(C-S) |S|, (1)|S|, (1)( (S=aS=a1 1 時(shí)時(shí),(1),(1)式成立等式式成立等式; ; S=aS=a1 1,a,a2 2 時(shí)時(shí),C,C1 1=C-=C-aa1 1 是鏈?zhǔn)擎? ; 而而 C-S=CC-S=C1 1-a-a2 2 是鏈?zhǔn)擎? ,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)a a2 2為為C C1 1端點(diǎn)端點(diǎn), ,否則否則 (C-S)=2.(C-S)=2.總之總之, , (C-S)(C-S) 2=|S|. 2=|S|. S=aS=a1 1, ,a,ak k,a,ak+1k+1 時(shí)時(shí), ,由歸納法得由歸納法得 (C-S)(C-S) (C-a(C-a1

44、 1, ,a,ak k)+1 )+1 |a|a1 1, ,a,ak k|+1=k+1=|a|+1=k+1=|a1 1, ,a,ak+1k+1|.|.) )因生成子圖的連通分支數(shù)不比母圖的多因生成子圖的連通分支數(shù)不比母圖的多和和C-SC-S是是G-SG-S的生成子圖的生成子圖, ,故得證故得證 (G-S)(G-S)(C-S)(C-S) |S|.|S|.a a1 1a a2 2Ca a1 1Ca a2 28.2#158.2#15求簡單無向圖求簡單無向圖G:(G:(b b)G)G有有E-E-回路但回路但無無H-H-回路回路;(;(d d)G)G無無E-E-回路也無回路也無H-H-回路回路 左圖左圖G

45、 G無奇度點(diǎn)故有無奇度點(diǎn)故有EulerEuler回路回路; ;易見易見G G無無HamiltonHamilton回路回路( (取取S=a,bS=a,b時(shí)時(shí), ,有有 (G-S)=32=|S|).(G-S)=32=|S|). 右圖右圖H H有奇度點(diǎn)故無有奇度點(diǎn)故無EulerEuler回路回路; ;易見易見H H無無HamiltonHamilton回路回路( (證明同上或用證明同上或用窮舉法窮舉法驗(yàn)證驗(yàn)證).).GHabab非非HamiltonHamilton圖圖舉例舉例例例 圖圖8.2-128.2-12不是不是HamiltonHamilton圖圖, ,原因是原因是: :取取S S為為3 3個(gè)黑點(diǎn)

46、時(shí)有個(gè)黑點(diǎn)時(shí)有 (G-S)=4(G-S)=4 3=|S|.3=|S|.例例 圖圖8.1-58.1-5的的PetersonPeterson圖圖不是不是HamiltonHamilton圖圖, ,但它滿足但它滿足對(duì)一切非空子集對(duì)一切非空子集S S V V有有 (G-S)(G-S) |S|,|S|,所以所以, ,定理定理8.2-68.2-6的條件的條件不是充分的不是充分的. .例例 圖圖8.2-138.2-13不是不是HamiltonHamilton圖圖( (用一種符號(hào)標(biāo)用一種符號(hào)標(biāo)記法證明記法證明).).結(jié)點(diǎn)符號(hào)標(biāo)記法結(jié)點(diǎn)符號(hào)標(biāo)記法補(bǔ)充補(bǔ)充圖標(biāo)記結(jié)束后圖標(biāo)記結(jié)束后, ,可能出現(xiàn)可能出現(xiàn)相鄰結(jié)點(diǎn)標(biāo)記符

47、號(hào)相同相鄰結(jié)點(diǎn)標(biāo)記符號(hào)相同的情況的情況, ,此時(shí)應(yīng)先在該對(duì)結(jié)點(diǎn)之間增加一個(gè)新此時(shí)應(yīng)先在該對(duì)結(jié)點(diǎn)之間增加一個(gè)新結(jié)點(diǎn)結(jié)點(diǎn)( (此點(diǎn)必為此點(diǎn)必為2 2度點(diǎn)度點(diǎn)),),同時(shí)將它標(biāo)以不同的符同時(shí)將它標(biāo)以不同的符號(hào)號(hào). .設(shè)所有有相同標(biāo)記的鄰點(diǎn)都做上述處理之設(shè)所有有相同標(biāo)記的鄰點(diǎn)都做上述處理之后得到的圖記為后得到的圖記為G G . .則則 G G 有有HamiltonHamilton路當(dāng)且僅當(dāng)路當(dāng)且僅當(dāng)G G 有有HamiltonHamilton路路. .故若故若 G G 的不同標(biāo)記結(jié)點(diǎn)數(shù)不的不同標(biāo)記結(jié)點(diǎn)數(shù)不同時(shí)同時(shí)( (如下圖如下圖) )即可斷定即可斷定 G G 不是不是HamiltonHamilton

48、圖圖. .AAABBBAAABBBBGG n(n( 3)3)結(jié)點(diǎn)無向簡單圖結(jié)點(diǎn)無向簡單圖G G為為HamiltonHamilton圖圖的一個(gè)充分條件的一個(gè)充分條件: :n/2,n/2, 記記最小度數(shù)最小度數(shù)證證: :用用反證法反證法. .若結(jié)論不成立若結(jié)論不成立, ,則必有則必有n n結(jié)點(diǎn)的結(jié)點(diǎn)的最大最大( (邊數(shù)邊數(shù)最多最多) )非非HamiltonHamilton圖圖G=G= V,EV,E . .因因G G K Kn n, ,故故G G有結(jié)點(diǎn)有結(jié)點(diǎn)u,v, u,v, (u,v)(u,v) E,E,且且G+(u,v)G+(u,v)為為HamiltonHamilton圖圖, ,同時(shí)同時(shí)G+(u

49、,v)G+(u,v)中任中任一一HamiltonHamilton回路都含邊回路都含邊(u,v).(u,v).于是于是G G有從有從u u到到v v的的HamiltonHamilton路徑路徑(u=v(u=v1 1,v,v2 2, ,v,vn n=v)(=v)(見下圖見下圖).).令令S S=v=vi i|(u,v|(u,vi+1i+1) ) E,E,T T=v=vi i|(v|(vi i,v),v) E,E,則則 v vn n S ST, T, |S|ST|n.T|n.又又 S ST=T=( (否則設(shè)某否則設(shè)某v vi i S ST,T,則如下圖所則如下圖所示示G G有有HamiltonHam

50、ilton回路矛盾回路矛盾).).因此因此d(u)+d(v)=|S|+|T|=|Sd(u)+d(v)=|S|+|T|=|ST|+|ST|+|ST|n,T|n,與假設(shè)矛與假設(shè)矛盾盾. .u=v v1 1v v2 2v vi-1i-1v vi+1i+1v vi iv vn n=v=v注注與與例例 注注 由上面的證明可得更一般結(jié)論由上面的證明可得更一般結(jié)論:n:n結(jié)點(diǎn)無向結(jié)點(diǎn)無向簡單圖簡單圖G G為為HamiltonHamilton 圖圖, ,如果如果G G的的任任2 2結(jié)點(diǎn)度數(shù)結(jié)點(diǎn)度數(shù)之和都不小于之和都不小于 n/2n/2. . 例例 n n結(jié)點(diǎn)無向結(jié)點(diǎn)無向k-k-正則圖正則圖必為必為Hamilt

51、onHamilton圖只要圖只要 k k n/2. (n/2. (因因 =k=k n/2)n/2)HamiltonHamilton圖圖的一個(gè)應(yīng)用的一個(gè)應(yīng)用( (習(xí)題習(xí)題8.2#68.2#6) )BCDEFG7 7位客人入席位客人入席,A,A只會(huì)講英語只會(huì)講英語,B,B會(huì)講英會(huì)講英, ,漢語漢語,C,C會(huì)講會(huì)講英英, ,意大利意大利, ,俄語俄語,D,D會(huì)講日會(huì)講日, ,漢語漢語,E,E會(huì)講德會(huì)講德, ,意大意大利語利語,F,F會(huì)講法會(huì)講法, ,日日, ,俄語俄語,G,G會(huì)講法會(huì)講法, ,德語德語. .能否安能否安排圓桌席位使每位客人與其左右鄰不用翻譯便排圓桌席位使每位客人與其左右鄰不用翻譯便可

52、交談可交談? ?建立無向圖模型建立無向圖模型: :結(jié)點(diǎn)為結(jié)點(diǎn)為客人客人; ;會(huì)共同語言的會(huì)共同語言的2 2結(jié)結(jié)點(diǎn)相鄰接點(diǎn)相鄰接. .則問題則問題歸結(jié)為歸結(jié)為求此圖的一條求此圖的一條HamiltonHamilton回路回路. .不難驗(yàn)證不難驗(yàn)證, ,此圖有此圖有一條一條HamiltonHamilton回路是回路是: :(A,B,D,F,G,E,C,A).(A,B,D,F,G,E,C,A).按此按此回路安排席位可滿足要求回路安排席位可滿足要求. .A英英法德俄意日漢HamiltonHamilton圖圖對(duì)編碼的一個(gè)應(yīng)用對(duì)編碼的一個(gè)應(yīng)用把圓周等分成把圓周等分成2 2n n個(gè)扇形個(gè)扇形, ,每一扇形代表

53、一個(gè)每一扇形代表一個(gè)n n位二進(jìn)制串位二進(jìn)制串用以表示旋轉(zhuǎn)指針的位置用以表示旋轉(zhuǎn)指針的位置( (不難設(shè)計(jì)指針上的不難設(shè)計(jì)指針上的n n個(gè)觸點(diǎn)個(gè)觸點(diǎn)來實(shí)現(xiàn)這個(gè)數(shù)來實(shí)現(xiàn)這個(gè)數(shù)).).當(dāng)當(dāng)n=3n=3時(shí)右下圖是一例時(shí)右下圖是一例. .由于交界附近由于交界附近會(huì)出現(xiàn)誤差會(huì)出現(xiàn)誤差, ,自然要求自然要求相鄰二數(shù)盡可能接近相鄰二數(shù)盡可能接近, ,即要求即要求ijkijk與與uvwuvw相鄰必須滿足相鄰必須滿足|i,j,k|i,j,ku,v,w|=2 (1) u,v,w|=2 (1) 此問題可歸結(jié)為求此問題可歸結(jié)為求立方圖立方圖G=G= V,EV,E ,V=000,001,V=000,001, , 111,

54、111, ijk,uvwijk,uvwE E當(dāng)且僅當(dāng)條件當(dāng)且僅當(dāng)條件(1)(1)成立成立, ,的一條的一條HamiltonHamilton路路.(.(解存在但不唯一解存在但不唯一) )111110101100000010011 001000001011111110100101010有向線圖有向線圖的的鄰接矩陣鄰接矩陣 定義定義 將有向線圖將有向線圖G=G= V,EV,E 的結(jié)點(diǎn)集的結(jié)點(diǎn)集強(qiáng)行命名強(qiáng)行命名( (標(biāo)標(biāo)定次序定次序) )為為 V=1,2,V=1,2,n,n,則則n n階階(0,1)(0,1)方陣方陣A=(aA=(aijij) )稱為的稱為的G G鄰接矩陣鄰接矩陣, ,其中其中當(dāng)當(dāng)(i

55、,j)(i,j) E,aE,aijij=1;=1;否則否則,a,aijij=0.=0. 注注 鄰接矩陣與結(jié)點(diǎn)的鄰接矩陣與結(jié)點(diǎn)的標(biāo)定次序有關(guān)標(biāo)定次序有關(guān), ,不同的不同的標(biāo)定次序?qū)?yīng)的鄰接矩陣不同標(biāo)定次序?qū)?yīng)的鄰接矩陣不同, ,但這兩個(gè)矩陣但這兩個(gè)矩陣置換相似置換相似, ,即適當(dāng)?shù)亟粨Q行和列的次序能從一即適當(dāng)?shù)亟粨Q行和列的次序能從一個(gè)鄰接矩陣變到另一個(gè)個(gè)鄰接矩陣變到另一個(gè). .或者說或者說, ,它們對(duì)應(yīng)的有它們對(duì)應(yīng)的有向線圖同構(gòu)向線圖同構(gòu). . 有向線圖在標(biāo)定次序后得到唯一鄰接矩陣有向線圖在標(biāo)定次序后得到唯一鄰接矩陣; ;一個(gè)一個(gè)n n階階(0,1)(0,1)方陣對(duì)應(yīng)唯一標(biāo)定次序的有向線方陣對(duì)應(yīng)

56、唯一標(biāo)定次序的有向線圖圖. .換句話說換句話說, ,不計(jì)圖的同構(gòu)和矩陣的置換相似不計(jì)圖的同構(gòu)和矩陣的置換相似有向線圖與一個(gè)有向線圖與一個(gè)n n階階(0,1)(0,1)方陣一一對(duì)應(yīng)方陣一一對(duì)應(yīng). .有限集有限集V V上的關(guān)系上的關(guān)系R R的的圖示圖示是以為是以為V V結(jié)結(jié)點(diǎn)集的一個(gè)點(diǎn)集的一個(gè)有向線圖有向線圖 易見易見: :關(guān)系關(guān)系R R的的關(guān)系矩陣關(guān)系矩陣正是正是R R的圖示作為有向的圖示作為有向線圖的線圖的鄰接矩陣鄰接矩陣. . 一個(gè)有向線圖一個(gè)有向線圖G=G= V,EV,E 對(duì)應(yīng)的關(guān)系對(duì)應(yīng)的關(guān)系R R的逆關(guān)系的逆關(guān)系R R 對(duì)應(yīng)的有向線圖對(duì)應(yīng)的有向線圖G G = = V,EV,E 稱為稱為G

57、 G的的逆圖逆圖.G.G與與G G 有有相同相同( (的強(qiáng)行命名的強(qiáng)行命名) )的結(jié)點(diǎn)集的結(jié)點(diǎn)集, ,并且并且(i,j)(i,j) E E (j,i)(j,i) E E . . 逆圖逆圖G G 的鄰接矩陣的鄰接矩陣A A 與原圖的鄰接矩陣與原圖的鄰接矩陣A A之間的之間的關(guān)系是關(guān)系是: : A A =A=AT T. .無向線圖無向線圖與與賦權(quán)圖賦權(quán)圖的的鄰接矩陣鄰接矩陣 定義定義 無向線圖無向線圖G=G= V,EV,E ,V=1,2,V=1,2,n,n的鄰接矩的鄰接矩陣是陣是n n階階(0,1)(0,1)方陣方陣A=(aA=(aijij),),其中其中當(dāng)當(dāng)(i,j)(i,j) E,aE,aij

58、ij=a=ajiji=1;=1;否則否則,a,aijij=a=ajiji=0.=0.由此可見由此可見, ,無向線圖的鄰接矩陣是對(duì)稱矩陣無向線圖的鄰接矩陣是對(duì)稱矩陣: : A=AA=AT T. .例如例如, ,零圖的鄰接矩陣是零矩陣零圖的鄰接矩陣是零矩陣; ; 完全圖完全圖K Kn n的鄰接的鄰接矩陣是恰有矩陣是恰有n n個(gè)個(gè)0 0并全在對(duì)角線上的并全在對(duì)角線上的n n階階(0,1)(0,1)方方陣陣. . 定義定義 賦權(quán)圖賦權(quán)圖G=G= V,E,WV,E,W ,V=1,2,V=1,2,n,n的鄰接矩的鄰接矩陣是陣是n n階階(0,1)(0,1)方陣方陣A=(aA=(aijij),),其中其中當(dāng)

59、當(dāng)(i,j)(i,j) E,aE,aijij=W(i,j);=W(i,j);否則否則,a,aijij=0.=0.鄰接矩陣鄰接矩陣的圖論意義的圖論意義設(shè)設(shè)A A為有向線圖為有向線圖G G的鄰接矩陣的鄰接矩陣. . A A的第的第i i行行( (列列) )和和等于第等于第i i結(jié)點(diǎn)結(jié)點(diǎn)的出的出( (入入) )度度, ,i=1,i=1,n.n. B=AA B=AAT T= =( (b bijij) )的元素的元素 b bijij=a=ai1i1a aj1j1+ +a+ainina ajnjn=k=k表示有表示有k k個(gè)點(diǎn)個(gè)點(diǎn), ,它們都是從它們都是從i,ji,j引引出的有向邊的公共交點(diǎn)出的有向邊的公

60、共交點(diǎn). .特別特別, ,b biiii是第是第i i結(jié)點(diǎn)的出度結(jié)點(diǎn)的出度. .對(duì)偶地對(duì)偶地可討論可討論A AT TA A的元素的圖論意義的元素的圖論意義. . A A2 2=AA=AA=(a(aijij(2)(2) )的元素的元素a aijij(2)(2)=a=ai1i1a a1j1j+ +a+ainina anjnj=k=k表示有表示有k k個(gè)點(diǎn)個(gè)點(diǎn), ,它們都是從它們都是從i i到到j(luò) j長為長為2 2的有向路的有向路徑的中點(diǎn)徑的中點(diǎn), ,即從即從i i到到j(luò) j長為長為2 2的路徑恰有的路徑恰有k k條條. .一般一般地地, ,從從i i到到j(luò) j長為長為m m的路徑恰有的路徑恰有a