離散數(shù)學(xué)王元元習(xí)題解答

1、第三篇圖論第八章圖8.1 圖的基本知識內(nèi)容提要8.1.1 圖的定義及有關(guān)術(shù)語定義8.1圖(graph)G由三個部分所組成：(1)非空集合V(G)，稱為圖G的結(jié)點集，其成員稱為結(jié)點或頂點(nodesorvertices)。(2)集合E(G)，稱為圖G的邊集，其成員稱為邊(edges)。I(3)函數(shù)里；：E(G)f(V(G),V(G),稱為邊與頂點的關(guān)聯(lián)映射(associatvemapping)。這里(V(G)，V(G)稱為VG的偶對集，其成員偶對(pair)形如(u，v)，u，v為結(jié)點，它們未必不同。吆=(u,v)時稱邊e關(guān)聯(lián)端點u,v。當(dāng)(u,v)用作序偶時(V(G),V(G)=V(G)V(G

2、),e稱為有向邊，e以u為起點，以v為終點，圖G稱為有向圖(directedgraph);當(dāng)(u,v)用作無序偶對時，(u,v)=(v,u),稱e為無向邊(或邊)，圖G稱為無向圖(或圖)。圖G常用三元序組V(G),E(G),36,或V,巳W來表示。顯然，圖是一種數(shù)學(xué)結(jié)構(gòu)，由兩個集合及其間的一個映射所組成。定義8.2設(shè)圖6為V,E,3。(l)當(dāng)V和E為有限集時，稱G為有限圖，否則稱G為無限圖。本書只討論有限圖。(2)當(dāng)呸為單射時，稱G為單圖；當(dāng)Wg為非單射時，稱G為重圖，又稱滿足W(e1)=W(e2的不同邊e1,e2,為重邊，或平行邊。(3)當(dāng)W(e)=(v,v)(或v,v)時，稱e為環(huán)(loo

3、ps)。無環(huán)和重邊的無向單圖稱為簡單圖。當(dāng)G為有限簡單圖時，也常用(n,m)表示圖G,其中n=V,m=E。(4)W為雙射的有向圖稱為有向完全圖；對每一(u,v),uv,均有e使W(e)=(u,v)的簡單圖稱為無向完全圖，簡稱完全圖，n個頂點的完全圖常記作Kn。(5)在單圖G中，W(e)=(u,v)(或u,v)時，也用(u,v)(或u,v)表示邊e,這時稱u,v鄰接e,u,v是e的端點(或稱u為e的起點，v為e的終點)；也稱e關(guān)聯(lián)結(jié)點u,v。不是任何邊的端點的結(jié)點都稱為孤立結(jié)點，僅由孤立結(jié)點構(gòu)成的圖(E=)稱為零圖。(6)當(dāng)給G賦予映射f:V-W,或g:E-W,W為任意集合，常用實數(shù)集及其子集，

4、此時稱G為賦權(quán)圖，常用V,E,3,或/£,3,牙或V,E,W,f,g表示之。f(v)稱為結(jié)點v的權(quán)，g(e)稱為邊e的權(quán)。8.1.2 結(jié)點的度定義8.3在無向圖中，結(jié)點v的度(degree)d(v)是v作為邊的端點的數(shù)目。在有向圖中，結(jié)點的度d(v)是v的出度d+(v)(out-degree)與入度d-(v)(in-degree)的和；v的出度是v作為有向邊起點的數(shù)目，v的入度是v作為有向邊終點的數(shù)目。定理8.1對任意圖G,設(shè)其邊數(shù)為m,頂點集為vi,v2,，vn,那么nd(vi)2mi1定理8.2圖的奇數(shù)度頂點必為偶數(shù)個。定理8.3自然數(shù)序列(ai,a2,an)稱為一個度序列，如果

5、它是一個圖的頂點的度的序n列。(&,a2,an)為一度序列，當(dāng)且僅當(dāng)ai為一偶數(shù)。i1定義8.4一度的頂點稱為懸掛點(pendantnodes)。定義8.6各頂點的度均相同的圖稱為正則圖(regulargraph)。各頂點度均為k的正則圖稱為k-正則圖。8.1.3圖運算及圖同構(gòu)由于圖由結(jié)點集、邊集及關(guān)聯(lián)映射組成，因此對圖可作種種與集合運算相類似的運算。定義8.6設(shè)圖G1=<V1,E1,W1>,G2=<V2,E2,W2稱G1為G2的子圖(subgraph),如果V1V2,E1E2,32。稱G1為G2的真子圖，如果G1是G2的子圖，且G1G2。稱G1為G2的生成子圖(sp

6、anningsubgraph)，如果G1是G2的子圖，且V1=V2。定義8.7設(shè)圖G1=<V1,E1,WJG2=<V2,E2,W2>且W1與W2是相容的，即對任一x,若W1(x)=y1,W2(x=y2,則y1=y2,從而W2為一函數(shù)。(1)G1與G2的并，記為G1G2=G3=<V3,E3,W3>,其中V3=V1V2,E3=E1E2,W3=W2。(2) G1與G2的交，記為G1G2=G3=<V3,E3,W3刁其中V3=V1V2,E3=E1E2,W3=W2。(3)若G1為G2的子圖，則可定義G2對G1的差，記為G2-G1=G3=<V3,E3,¥3

7、>其中E3=E2-E1,V3=V2,W3=W2E3。(4)G1與G2的環(huán)和，記為G1G2，G1G2=(G1G2)(G1G2)(5)若G為簡單圖，則可定義G的補(bǔ)，記為G,若V(G)=n,則G=Kn一G定義8.8設(shè)圖G=<V,E,W>(1) Ge表示對G作刪除邊e的運算，G-e=<V,E',W'>,其中E'=Ee,W=WE，。(2) Gv表示對G作刪除頂點v的運算，G-v=<VE',W'>,其中V'=Vv,E'=Eee以v為端點,皿=we，。(3)邊e切割運算。設(shè)G中W(e)=(u,v),對G作邊e切

8、割得G'=<V',E',W'>,其中，V'=Vv'E'=(Ee)e1,e2,皿=(*e,(u,v)>)<e1,(u,v；<e2,(v',v)>(4)頂點v貫通運算。設(shè)G中頂點v恰為邊e1,e2的端點，且W(e1)=(u,v),W(e2)=(w,v)。對G作頂點v貫通得G'=<V',E',W'>,其中V'V-v,E'=(E-e1,e2)e,W'=(W<e1,(u,v)>,<e2,(w,v)>)<e,(

9、u,w)>。切割與貫通是互逆的，兩者常被稱為同胚運算。定義8.9設(shè)G1=<V1,E1,W1>,G2=<V2,E2,W2冽兩個圖，稱G1與G2同構(gòu)(isomorphic),如果存在雙射f:V1fV2,雙射g：E1fE2,使得對每一邊eE1,W1(e)=(u,v)(或<u,v>)當(dāng)且僅當(dāng)W2(g(e)=(f(u),f(v)(或<f(u),f(v)>)當(dāng)限于討論簡單圖時，可以用頂點的偶對表示邊，即當(dāng)W(e)=(u,v)時，邊e用(u,v)來表示。這時兩圖同構(gòu)的條件可以簡化為(u,v)E1當(dāng)且僅當(dāng)(f(u),f(v)E2習(xí)題解答練習(xí)8.11、想一想，一只

10、昆蟲是否可能從立方體的一個頂點出發(fā)，沿著棱爬行、它爬行過每條梭一次且僅一次，并且最終回到原地？為什么？解不可能。可將立方體的一個頂點看作圖的一個頂點，把立方體的棱看作圖的邊，那么該圖的四個頂點都是三度的，因此不可能從一個頂點出發(fā)，遍歷所有的邊一次且僅一次，并且最終回到原頂點。2、請設(shè)想一張圖，它的64個頂點表示國際象棋棋盤的64個方格，頂點間的邊表示：在這兩個頂點表示的方格之間可以進(jìn)行“馬步”的行走。試指出其頂點有哪幾類(依其度分類)，每類各有多少個頂點。解其頂點有5類：二度頂點合計4個,三度頂點合計8個，四度頂點,合1t20個，六度頂點,合方t16個頂點，八度頂點,合1t16個頂點。2344

11、443234616664314688886446888864468888644688886434666643234444323、(1)證明：n個頂點的簡單圖中不會有多于n(n1)條邊。2(2) n個頂點的有向完全圖中恰有n2條邊。證(1)n個頂點的簡單完全圖的邊數(shù)總和為(n1)(n2)21n(n1)2(2)n個頂點的有向完全圖的邊數(shù)總和為2nnnnnnn4、證明：在任何n(n>2)個頂點的簡單圖G中，至少有兩個頂點具有相同的度。證如果G有兩個孤立頂點，那么它們便是具有相同的度的兩個頂點。如果G恰有一個孤立頂點，那么我們可對有n-1個頂點但沒有孤立頂點的G'(它由G刪除孤立頂點后得

12、到)作下列討論。不妨設(shè)G沒有孤立頂點，那么G的n個頂點的度數(shù)應(yīng)是：1,2,3,，nT這n-1種可能之一，因此必定有兩個頂點具有相同的度。5、圖8.10是一個迷宮，其中數(shù)字表示通道、和死胡同(包括目標(biāo))。請用一個圖來表示這個迷宮(用結(jié)點表示通道、和死胡同(包括目標(biāo)),用邊表示它們之間的可直接到達(dá)關(guān)系。1圖 8.106、在晚會上有n個人，他們各自與自己相識的人握一次手。已知每人與別人握手的次數(shù)都是奇數(shù)，問n是奇數(shù)還是偶數(shù)。為什么？解n是偶數(shù)。用n個頂點表示n個人，頂點間的一條邊表示一次握手，可構(gòu)成一個無向圖。若n是奇數(shù)，那么該圖的頂點度數(shù)之和為奇數(shù)(奇數(shù)個奇數(shù)的和)，這是不可能的，因此n是偶數(shù)。(

13、n1)(n2)7、n個城市間有m條相互連接的直達(dá)公路。證明：當(dāng)m時，人們便能2通過這些公路在任何兩個城市間旅行。證用n個頂點表示n個城市，頂點間的邊表示直達(dá)公路，據(jù)題意需證這n個城市的公路網(wǎng)絡(luò)所構(gòu)成的圖G是連通的。反設(shè)G不連通，那么可設(shè)G由兩個不相關(guān)的子圖(沒有任何邊關(guān)聯(lián)分別在兩個子圖中的頂點)G1,G2組成，分別有ni,n2個頂點，從而，n=ni+n2,ni>1,n2>1oni(ni1)由于各子圖的邊數(shù)不超過-(見練習(xí)8.1之3),因此G的邊數(shù)m滿足：21 ni(ni2 i 1,、11)(似Q1)02(021)212(n1)(ni1)(n1)(h1)1，、,c、-(n1)(n1n

14、22)21(n1)(n2)2與已知m(n1)(n2)矛盾,故圖g是連通的。2(本題是定理8.8的特例，當(dāng)然也可以應(yīng)用這一定理和它的證明方法來解題。)*8、(1)證明：序列(7,6,5,4,3,3,2),(6,5,5,4,3,2,2)以及(6,6,5,4,3,3,1)都不是簡單圖的度序列。(2)若自然數(shù)序列(d1,d2,dn)滿足d1>d2>>dn,那么當(dāng)它為一簡單圖的度序列時必有n(a)di為偶數(shù)；1 1kn(b)對任一k,1<k<n,di&k(k-1)+min(k,di)。i1ik1證(1)由于7個頂點的簡單圖中不可能有7度的頂點，因此序列(7,6,5,

15、4,3,3,2)不是簡單圖的度序列。序列(6,5,5,4,3,2,2)中有三個奇數(shù)，因此它不是簡單圖的度序列。序列(6,6,5,4,3,3,1)中有兩個6,若它是簡單圖的度序列，那么應(yīng)有兩個頂點是6度頂點，于是它們都要與其它所有頂點鄰接，該圖就不會有一度的頂點，與序列中末尾的1沖突。故(6,6,5,4,3,3,1)也不是簡單圖的度序列。n證(2)di為偶數(shù)是顯然的。i1考慮圖中的k個頂點(k=1,2,n),這k個頂點的生成子圖的度數(shù)總和<k(k-1),而其余n-k個頂點Vk+1,Vk+2,vn,可使V1,V2,Vk增加的度數(shù)不會超過nmin(k,di)ik1kn因此我們有di&k

16、(k-1)+min(k,di)oi1ik19、畫出圖8.11中圖的補(bǔ)圖及它的一個生成子圖。22圖8.1110、一個簡單圖，如果同構(gòu)于它的補(bǔ)，則該圖稱為自補(bǔ)圖。(1)給出一個4個頂點的自補(bǔ)圖。(2)給出一個5個頂點的自補(bǔ)圖。(3)是否有3個頂點或6個頂點的自補(bǔ)圖？(4)證明一個自補(bǔ)圖一定有4k或4k+1個頂點(k為正整數(shù))。解(1) 4個頂點的自補(bǔ)圖:(2) 5個頂點的自補(bǔ)圖:(3)沒有。(4)證設(shè)G為自補(bǔ)圖，有n個頂點。我們已知因此G應(yīng)恰有n(n 1)條邊。故或者n是4的整數(shù)倍, 4有4k或4k + 1個頂點(k為正整數(shù))。n個頂點的完全圖有n(n 1)條邊,2或者n-1是4的整數(shù)倍，即圖G

17、一定11、證明圖 8.12中(a)與(b)同構(gòu)。A圖8.12(2)給出所有不同構(gòu)的4個結(jié)點的簡單圖的圖示。證在圖(a)圖(b)間建立雙射hvABDIJCEGHFh(v)可逐一驗證(不贅)(u,v)E(a)當(dāng)且僅當(dāng)(h(u),h(v)E(b)(2)所有不同構(gòu)的4個結(jié)點的簡單圖的圖示有如下11個:*12、Kn表示n個頂點的無向完全圖。(1)對K6的各邊用紅、藍(lán)兩色著色，每邊僅著一種顏色，紅、藍(lán)任選。證明：無論怎樣著色，圖上總有一個紅色邊組成的K3或一個藍(lán)色邊組成的K3。(2)用(1)證明下列事實：任意6個人之間或者有三個人相互認(rèn)識，或者有3個人相互都不認(rèn)識。證(1)考慮K6的頂點V,與之關(guān)聯(lián)的邊有

18、5條，其中至少有3條著同一顏色。不妨設(shè)均著紅色，這三邊的另一個端點分別是u1,u2,u3(如圖所示)。再考慮關(guān)聯(lián)u1,u2,u3的三條邊。如果它們中有一條著紅色的邊，那么我們就已經(jīng)得到一個紅色邊組成的K3,如果它們中沒有著紅色的邊，那么我們就能夠得到一個藍(lán)色邊組成的K3o證(2)用六個頂點表示6個人，頂點間紅色邊表示人員間相互認(rèn)識，頂點間藍(lán)色邊表示人員間相互不認(rèn)識，便產(chǎn)生一個邊著紅、藍(lán)兩色的完全圖K6o利用(1)的結(jié)論，可以斷定6個人之間或者有三個人相互認(rèn)識，或者有3個人相互都不認(rèn)識。8.2路徑、回路及連通性內(nèi)容提要8.2.1 路徑與回路定義8.10圖G的頂點V1到頂點vi的擬路徑(pseud

19、opath)是指如下頂點與邊的序列:V1,e1,V2,e2,V3，,vi-i,el-1,vi其中vi,v2,v3,，vi-i,vi為G的頂點e1,e2，e-1為G的邊，且e(i=1,2,l-1)以vi及vi+1為端點，(對有向圖G,ei以vi為起點，以vi+1為終點)，擬路徑的邊數(shù)l1稱為該擬路徑的長度。當(dāng)3(i=1,2,，l-1)各不相同時，該擬路徑稱為路徑(walk),又當(dāng)vi(i=1,2,，l)各不相同時(除vi與vi),則稱此路徑為通路(Path)。vi=vi的路徑稱為閉路徑(closedwalk)；vi=vi的通路稱為回路(circuit)。當(dāng)討論限于簡單圖或無平行邊的有向圖時，上述

20、擬路徑、路徑、通路等可用頂點序列來表不，例如用(Vi,V2,V3，,vi-i,vi)代替式vi,ei,V2,e2,V3，,v1-1,ei-i,vi。定理8.4在有n個頂點的圖G中，如果有從頂點u到v(uv)的擬路徑，那么從u到v必有路徑，并且必有長度不大于n-1的通路。定理8.5在具有n個頂點的圖G中，如果有從v到v的閉路徑，那么必定有一條從v到v的長度不大于n的回路。8.2.2連通性定義8.11稱圖中頂點u到v是可達(dá)的(accesible),如果u=v,或者有一條u到v的路徑。定義8.12稱無向圖G是連通的(connected),如果G的任何兩個頂點都是相互可達(dá)的。稱有向圖G是強(qiáng)連通的，如果

21、G的任何兩個頂點都是相互可達(dá)的；稱有向圖G是單向連通的，如果G的任何兩個頂點中，至少從一個頂點到另一個頂點是可達(dá)的；稱有向圖G是弱連通的，如果G的有向邊被看作無向邊時是連通的。定義8.13圖G'稱為圖G的連通分支(connectedcomponents),如果G'是G的子圖，G'是連通的，并且不存在G的真子圖G','使G'是連通的，且G'以G'為真子圖。定義8.14設(shè)G'為有向圖G的子圖，若G'是強(qiáng)連通的(單向連通的、弱連通的)，且G沒有真子圖G'使G'為其真子圖，而G'強(qiáng)連通(單向連通、弱

22、連通)，那么稱G'為G的一個強(qiáng)分圖(單向分圖、弱分圖)。定理8.6一個圖G是不連通的，當(dāng)且僅當(dāng)G的頂點集V可以分成兩個不交的非空子集V1和V2,使得任何邊都不以V1的一個頂點和V2一個頂點為其兩端點。定理8.7如果圖G恰有兩個不同的奇數(shù)度的頂點u,v,那么u到v必定是可達(dá)的。定理8.8若圖G為具有n個頂點、k個連通分支的簡單圖，那么G至多有(nk)(nk1)條邊。2A8.2.3連通度定義8.15設(shè)S為連通圖G的頂點集V的子集，稱S為G的點割集(cut-setofnodes),如果從G中刪除S中的所有頂點后得到的圖不連通，但S的任何真子集均無這一特性。當(dāng)點割集為單元素集合v時，v稱為割點

23、(cut-nodes)。定義8.16xG)稱為G的點連通度(node-connectivity),定義如下：0若G非連通圖(G)n1若G為KnminS:S為點割集若G連通，GKn定義8.17設(shè)S為連通圖G邊集E的子集，稱S為G的邊割集(cut-setofedges),或割集，如果從G中刪除S的所有邊后所得的圖是不連通的，但S的任何真子集均無這一特性。當(dāng)割集為單元素集e時，稱e為割邊(cut-edges)。定義8.18A(G)稱為圖G的邊連通度(edge-connectivity),定義如下：0當(dāng)G非連通圖時(G)0當(dāng)G為一孤立結(jié)點時minS:S為G的割集否則定理8.9對任何簡單無向圖G,xG)

24、<XG)<9(G)定理8.10設(shè)G為n個頂點、m條邊的簡單連通圖，那么XG)&2m習(xí)題解答練習(xí)8.21、證明定理8.5。證設(shè)n個頂點的圖G中，有從v到v的閉路徑，表示為(V,V1,V2,，Vk,V)如果v,vi,v2,vk中沒有相同頂點(因而不多于n個)，那么它便是一條從v到v的長度不大于n的回路。如果v,vi,v2,vk中有相同頂點vi=vj,例如(v,vi,，vi,，vj,vj+1,vk,v)那么刪除vi到vj的閉路徑，得到(v,v1,，vi,vj+1，,vk,v)仍然為從v到v的閉路徑。如此不斷刪除閉路徑內(nèi)相同頂點構(gòu)成的閉路徑，最終必可得到一條從v到v的長度不大于n的

25、回路。2、證明：在簡單無向圖G中，從結(jié)點u到結(jié)點v,如果既有奇數(shù)長度的通路又有偶數(shù)長度的通路，那么G中必有一奇數(shù)長度的回路。證設(shè)G中，從結(jié)點u到結(jié)點v的奇數(shù)長度的通路為O,偶數(shù)長度的通路為E。又。和E的除結(jié)點u和v的相交結(jié)點的數(shù)目歸納kok=0,那么。和E恰好構(gòu)成G的奇數(shù)長度的回路。設(shè)奇數(shù)長度的通路與偶數(shù)長度的通路的相交結(jié)點的數(shù)目少于k時，命題成立。設(shè)圖G中，從結(jié)點u到結(jié)點v的奇數(shù)長度的通路與偶數(shù)長度的通路有k個相交結(jié)點，如u圖所示：考慮結(jié)點u到結(jié)點k,如果從結(jié)點u到結(jié)點k,既有奇數(shù)長度的通路又有偶數(shù)長度的通路，那么據(jù)歸納假設(shè)，其中有一奇數(shù)長度的回路，因而G中必有一奇數(shù)長度的回路。如果從結(jié)點u

26、到結(jié)點k的兩條通路均為偶數(shù)長度，或均為奇數(shù)長度，那么結(jié)點k到結(jié)點v必然既有奇數(shù)長度的通路又有偶數(shù)長度的通路，因而構(gòu)成一奇數(shù)長度的回路。3、證明：若簡單無向圖G是不連通的，那么G一必定是連通的。證設(shè)簡單無向圖G是不連通的，那么G由兩個不相關(guān)的子圖(沒有任何邊關(guān)聯(lián)分別在兩個子圖中的頂點)G1,G2組成，分別有頂點，u1,u2,，uk和v1,v2,vi。由于邊(ui,vj)均不在G中(i=1,2,k,j=1,2,1)因此(ui,vj)全部在G一中，從而G一是連通的。4、有向圖可用于表示關(guān)系，圖8.18表示的二元關(guān)系是傳遞的嗎？說說如何由有向圖判定關(guān)系的傳遞性。求圖8.18表示的二元關(guān)系的傳遞閉包，說

27、說構(gòu)作有向圖傳遞閉包的方法。a圖 8.18解圖8.18表示的二元關(guān)系不是傳遞的。有向圖表示的關(guān)系是傳遞的，當(dāng)且僅當(dāng)對圖中任意兩個結(jié)點u,v,如果有從u到v的路徑，則必有從 u至1Jv的邊。圖8.18表示的二元關(guān)系的傳遞閉包如圖8.18 (b)所示。構(gòu)作有向圖傳遞閉包的方法是:對圖中任意兩個結(jié)點u,v,如果有從u到v的路徑，則添加從 u到v的邊。a5、給出圖8.19中有向圖的強(qiáng)分圖，單向分圖和弱分圖，作出它的凝聚圖。解圖8.19中有向圖的強(qiáng)分圖有:<v1,v2,<v1,v2>,<v2,v1>>,<v3,v4,v5,<v3,v5>,<v4

28、,v3>,<v4,v5>,<v5,v4>><v6,<v6,v6>>,<v7,v8,v9,<v7,v8>,<v8,v9>,<v9,v7>>,<v10，>圖8.19中有向圖的單向分圖有：<v1,v2,v3,v4,v5,v6,<v1,v2>,<v2,v1>,<v1,v4>,<v2,v3>,<v4,v3>,<v3,v5>,<v4,v5>,<v5,v4>,<丫3,丫6>&g

29、t;,<v7,v8,v9,v10,<v7,v8>,<v8,v9>,<v9,v7>,<v7,v10>>圖8.19的凝聚圖:v 1,V2 Q6、有 7 人 a, b, 要時借助他人作翻譯)一viov3,V4,V5vv7,V8,V9OV6c,d,e,f,g分別精通下列語言，問他們7人是否可以自由交談(必a精通英語。b精通漢語和英語。c精通英語、俄語和意大利語。d精通日語和英語。e精通德語和意大利語。f精通法語、日語和俄語。g精通法語和德語。解下圖中7個頂點表示7個人，關(guān)聯(lián)兩個頂點的邊表示兩個人同時精通某一種語言:由于該圖是連通的，因此他們7

30、人是可以自由交談(必要時借助他人作翻譯)7、證明：一個有向圖是單向連通的，當(dāng)且僅當(dāng)它有一條經(jīng)過每一結(jié)點的路徑。證充分性是顯然的。必要性：設(shè)有向圖G是單向連通的，P是G中的一條路徑，起點為Ui,終點為uko如下延長這一路徑：考慮路徑外的任意頂點w,若(1)有頂點w到ui的路徑，則我們?nèi)缭浮?2)有頂點Uk到w的路徑，則我們?nèi)缭?。否則，由于有向圖是單向連通的，(3)有頂點w到山的路徑，和頂點Uk-i到w的路徑，則我們?nèi)缭?。否則，由于有向圖是單向連通的，(4)有頂點w到Uk的路徑，和頂點Uk-2到w的路徑，則我們?nèi)缭?。否則,(5)如此等等一，有頂點w到Uk的路徑，和頂點ui到w的路徑，則我們?nèi)缭?。?/p>

31、上不斷延長這一路徑，直至產(chǎn)生一條經(jīng)過每一結(jié)點的路徑。8、稱d(u,v)為圖G=<V,E,W中結(jié)點u,v間的距離:0當(dāng)uvd(u,v)當(dāng)u到v不可達(dá)u,v間最短路徑長度否則d稱為圖G的直徑，如果d=maxd(u,v)u,vV。試求圖8.20中圖的直徑，xG),XG),8(G),并指出一個點割集和一個邊割集。圖8.20解d=3,xG)=3,XG)=3,IG)=3。9、頂點v是簡單連通圖G的割點，當(dāng)且僅當(dāng)G中存在兩個頂點v1,v2,使v1到v2的通路都經(jīng)過頂點v。試證明之。證充分性是顯然的。必要性：設(shè)頂點v是簡單連通圖G的割點，如果不存在兩個頂點v1,v2,使v1到v2的通路都經(jīng)過頂點v,那么

32、對任意兩個頂點v1,v2,都有一條通路不經(jīng)過頂點v,因而刪除頂點v不能使G不連通，與v是簡單連通圖G的割點矛盾。故G中必存在兩個頂點v1,v2,使v1到v2的通路都經(jīng)過頂點v。10、邊e是簡單連通圖G的割邊，當(dāng)且僅當(dāng)e不在G的任一回路上。試證明之。證設(shè)e是簡單連通圖G的割邊，其端點為u,v。刪除邊e后，u,v應(yīng)在兩個不同的連通分支中。若e在G的一條回路上，那么刪除邊e后，u,v應(yīng)仍在一條通路上，矛盾。故e不在G的任一回路上。反之，設(shè)e不在G的任一回路上，而e不是簡單連通圖G的割邊。那么G-e仍是連通的，故還有u到v的一條通路，從而這條通路連同邊e構(gòu)成G中的一條回路，矛盾。因此邊e是簡單連通圖G

33、的割邊11、試用有向圖描述下列問題的解：某人m帶一條狗d,一只貓c和一只兔子r過河。m每次游過河時只能帶一只動物，而沒人管理時，狗與兔子不能共處，貓和兔子也不能共處。問m怎樣把三個動物帶過河去？(提示：用結(jié)點代表狀態(tài)，狀態(tài)用序偶<S1,S2>來表示，這里S1,S2分別是左岸和右岸的人及動物集合，例如初始狀態(tài)為<m,d,c,r,>。解描述上述問題的有向圖如下：<d,r , m,c><c,m,d,r>< m,c,r,d ><r,m,c,<m, r,c,d><,m,d,c,r><m,d,c,r,>&

34、lt;d,c, m,r><m,d,c, r><d,m,c,r><m,d,rf,c><r,m,c,d)><c,r,m,d>12、有向圖可以刻劃一個系統(tǒng)的狀態(tài)轉(zhuǎn)換，例如用圖8.21中的有向圖可以描述識別01010序列的狀態(tài)轉(zhuǎn)換系統(tǒng)。其中S為初始狀態(tài)，在此讀入序列，然后依序列中符號轉(zhuǎn)入后續(xù)狀態(tài)(讀到0進(jìn)入S1,讀到1進(jìn)入S2,如此等等)。S4表示讀完序列01010應(yīng)進(jìn)入的最后狀態(tài)，S5表示讀完一個非01010序列應(yīng)進(jìn)入的最后狀態(tài)。試自行構(gòu)作識別序列01(10)10的有向圖刻劃的狀態(tài)轉(zhuǎn)換系統(tǒng)。圖 8.21(上文中w表示空字或重復(fù)任意多次

35、w所得的字。)8.3歐拉圖與哈密頓圖內(nèi)容提要8.3.1歐拉圖與歐拉路徑定義8.19圖G稱為歐拉圖(Eulergraph),如果圖G上有一條經(jīng)過G的所有頂點、所有邊的閉路徑。圖G稱為歐拉路徑（Eulerwalk）,如果圖G上有一條經(jīng)過G所有頂點、所有邊的路徑。定理8.11無向圖G為歐拉圖當(dāng)且僅當(dāng)G連通，并且所有頂點的度都是偶數(shù)。有向圖G為歐拉圖，當(dāng)且僅當(dāng)G是弱連通的，并且每個頂點的出度與入度相等。定理8.12如果G為歐拉圖，那么G可分成若干個（一個或幾個）回路。定理8.13無向圖G為歐拉路徑（非歐拉圖），當(dāng)且僅當(dāng)G連通，并且恰有兩個頂點的度是奇數(shù)。有向圖G為歐拉路徑（非歐拉圖），當(dāng)且僅當(dāng)G連通，

36、并且恰有兩個頂點的入度與出度不等，它們中一個的出度比入度多1,另一個入度比出度多1。8.3.2哈密頓圖及哈密頓通路定義8.20無向圖G稱為哈密頓圖（Hamiltongraph）,如果G上有一條經(jīng)過所有頂點的回路（也稱這一回路為哈密頓回路）。稱無向圖有哈密頓通路（非哈密頓圖），如果G上有一條經(jīng)過所有頂點的通路（非回路）。定理8.14設(shè)圖G為具有n個頂點的簡單無向圖，如果G的每一對頂點的度數(shù)之和都不小于n-1，那么G中有一條哈密頓通路；如果G的每一對頂點的度數(shù)之和不小于n,且n>3,那么G為一哈密頓圖。n1定理8.15當(dāng)n為不小于3的奇數(shù)時，Kn上恰有條互相均無任何公共邊的哈皆頓2回路。定義

37、8.21圖G稱為可2-著色（2-chromatic）,如果可用兩種顏色給G的所有頂點著色，使每個頂點著一種顏色，而同一邊的兩個不同端點必須著不同顏色。定理8.16設(shè)圖G是可2-著色的。如果G是哈密頓圖，那么著兩種顏色的頂點數(shù)目相等；如果G有哈密頓通路，那么著兩種顏色的頂點數(shù)目之差至多為一。習(xí)題解答練習(xí)8.31、試作出四個圖的圖示，使第一個既為歐拉圖又為哈密頓圖；第二個是歐拉圖而非哈密頓圖；第三個是哈密頓圖卻非歐拉圖；第四個既非歐拉圖也非哈密頓圖。解（a）既為歐拉圖又為哈密頓圖；（b）是歐拉圖而非哈密頓圖；（c）是哈密頓圖卻非歐拉圖；（d）既非歐拉圖也非哈密頓圖。2、像第一題要求的那樣對歐拉路徑

38、和哈密頓通路作出四個圖。解（a）既有歐拉路徑又有哈密頓通路；（b）有歐拉路徑而無哈密頓通路；（c）有哈密頓通路卻無歐拉路徑；（d）既無歐拉路徑也無哈密頓通路。(a)(b)(c)(d)3、問n為何種數(shù)值時，Kn既是歐拉圖又是哈密頓圖。問k為何值時，k-正則圖既是歐拉圖又是哈密頓圖。解n為奇數(shù)時，Kn既是歐拉圖又是哈密頓圖。k為大于或等于n/2的偶數(shù)時，k-正則圖既是歐拉圖又是哈密頓圖。4、證明：恰有兩個奇數(shù)度頂點u,v的無向圖G是連通的，當(dāng)且僅當(dāng)在G上添加邊（u,v）后所得的圖G*是連通的。證必要性是顯然的。設(shè)G*是恰有兩個奇數(shù)度頂點u,v的無向圖G添加邊（u,v）后所得，且是連通的，那么圖G*

39、是一個歐拉圖（每一個頂點都是偶數(shù)度的連通圖），因此G*中刪除邊（u,v）后所得的圖G仍是連通的。5、參閱練習(xí)8.1第2題。問馬可否從某處出發(fā)完成所有可能的跳步一次且僅一次后回到原地。解練習(xí)8.1第2題中的圖不是歐拉圖（它有三個3度的頂點），因此馬不可能從某處出發(fā)完成所有可能的跳步一次且僅一次后回到原地。6、參閱練習(xí)8.1第2題。問馬可否從某處出發(fā)跳遍棋盤的所有方格一次且僅一次后回到原地。解馬可以從某處出發(fā)跳遍棋盤的所有方格一次且僅一次后回到原地。具體跳步如下圖所示：幻方中數(shù)字n表示第n個跳步的起點。下圖則表示跳步的圖示。5011246314372635236251122534153810496

40、4214013362761229523328391648760120415429594458533217426472574419305535854631564318幻方0407夕72X。A/攵VA0/V飛夕夕A夕發(fā)V乙0000707、試計算Kn（n>3）中不同的哈密頓回路共有多少條。解不同的哈密頓回路共有（n1）!條?？梢杂靡来芜x取每一條邊來生成哈密頓回路。因2為組成回路的第一條邊的選擇可能是n種，組成回路的第二條邊的選擇可能是n-1種，組成回路的第n-1條邊的選擇可能是2種，組成回路的第n條邊的選擇可能是1種，而每一哈密頓回路由此生成兩次，因此不同的哈密頓回路共有（n1）!條。28、十

41、一個學(xué)生在一張圓桌旁共進(jìn)晚餐，要求在每次晚餐上每個學(xué)生的鄰座都與其它各次晚餐的鄰座不同。問這樣共進(jìn)晚餐能安排多少次。種（根2據(jù)定理8.15。）9、判別圖8.31中各圖是否為哈密頓圖，若不是，請說明理由，并回答它是否有哈密頓(c)通路。圖 8.31解每次晚餐上每個學(xué)生的鄰座都與其它各次晚餐的鄰座不同的安排方式有解（a）,（b）是為哈密頓圖。（c）不是哈密頓圖，也沒有哈密頓通路。在圖（c）中增加頂點k,并對其頂點做二著色，構(gòu)成圖（d）（如下）。圖（d）不是哈密頓圖，也沒有哈密頓通路。因為圖中白色頂點比黑色頂點多兩個。故（c）不是哈密頓圖，也沒有哈密頓通路。否則它的哈密頓回路或哈密頓通路必定經(jīng)過頂點

42、k(k在兩個二度頂點之間的邊上)，從而圖(d)也是哈密頓圖，也有哈密頓通路，矛盾。(d)10、證明：對哈密頓圖G=<V,E,刪除S(V)中的所有頂點后，所得圖G'的連通分支數(shù)不大于S。證設(shè)G1是G中的哈密頓回路，顯然在G1中刪除S(V)中的所有頂點后，所得圖G1'的連通分支數(shù)k1,不小于在G中刪除S(V)中的所有頂點后，所得圖G'的連通分支數(shù)k,即k<k1o由于G1是一條回路，在G1中刪除S(V)中的所有頂點后，所得圖G1'的連通分支數(shù)k1不大于S是顯然的，即k1wS。因此kwkiwS211、設(shè)G為(n,m)圖。證明：如果mCn12,那么G為哈密頓圖

43、(提不：運用定理8.14)。證設(shè)G中有兩個頂點v1和v2的度數(shù)之和不大于n-1，那么以v1和v2為端點的邊不多于n-1條。而其余頂點之間的邊的數(shù)目不多于(n2)(n3)條。故G的總邊數(shù)m滿足21mn1-(n2)(n3)12-(2n2n25n6)12-(n3n4)12(n1)(n2)1C；11與mC212矛盾，故G中任意兩個頂點的度數(shù)之和大于n。根據(jù)定理8.14,G為哈密頓圖。12、設(shè)有n個圍成一圈跳舞的孩子，每個孩子都至少與其中n個是朋友。試證明，總2可安排得使每個孩子的兩邊都是他的朋友。證設(shè)n個孩子為n個頂點，用邊表示頂點間的朋友關(guān)系構(gòu)成一個圖G。由于每個孩子都至少與其中n個是朋友，因此G的

44、每一頂點的度數(shù)至少是-,從而G的任何兩個頂點的度22數(shù)之和至少是no根據(jù)定理8.14,G為哈密頓圖。即G有哈密頓回路，這表明，總可安排n個孩子圍成一圈跳舞，使每個孩子的兩邊都是他的朋8.4圖的矩陣表示內(nèi)容提要8.4.1 關(guān)聯(lián)矩陣定義8.22設(shè)G為(n,m)圖，那么nm矩陣A=aj,1當(dāng)邊0以頂點vi為端點aij0否則稱為G的關(guān)聯(lián)矩陣(incidencematrix),記為A(G)。定理8.17若G為(n,m)連通簡單圖。那么A的秩為n-l(即其最大非零行列式的階數(shù)為n-l)o8.4.2鄰接矩陣定義8.23設(shè)G=<V,E,為一無重邊的有向圖。其中V=v2,vn,那么nn矩陣A=aij,1當(dāng)vi,vjE(或(my)E)ij0當(dāng)vi,vjE(或(vi,vj)E)稱為圖G的鄰接矩陣(adjacencymatrix),記為AG用Al表示l個矩陣A的乘積。(1)令A(yù)l=a：，那么a的意義是：G中從頂點vi到vj的長度為l的擬路徑恰為a條。(2)令A(yù)CA=bj,那么bj的意義是：有bj個頂點v,使得vi到v,vj到v都有邊(兩邊交于v)。因而bii表示頂點vi的出度。(3)令A(yù)，CA=bij,