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

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

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

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

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

5、它是一個(gè)圖的頂點(diǎn)的度的序n列。(&,a2,an)為一度序列，當(dāng)且僅當(dāng)ai為一偶數(shù)。i1定義8.4一度的頂點(diǎn)稱為懸掛點(diǎn)(pendantnodes)。定義8.6各頂點(diǎn)的度均相同的圖稱為正則圖(regulargraph)。各頂點(diǎn)度均為k的正則圖稱為k-正則圖。8.1.3圖運(yùn)算及圖同構(gòu)由于圖由結(jié)點(diǎn)集、邊集及關(guān)聯(lián)映射組成，因此對(duì)圖可作種種與集合運(yùn)算相類似的運(yù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是相容的，即對(duì)任一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對(duì)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為簡(jiǎn)單圖，則可定義G的補(bǔ)，記為G,若V(G)=n,則G=Kn一G定義8.8設(shè)圖G=<V,E,W>(1) Ge表示對(duì)G作刪除邊e的運(yùn)算，G-e=<V,E',W'>,其中E'=Ee,W=WE，。(2) Gv表示對(duì)G作刪除頂點(diǎn)v的運(yùn)算，G-v=<VE',W'>,其中V'=Vv,E'=Eee以v為端點(diǎn),皿=we，。(3)邊e切割運(yùn)算。設(shè)G中W(e)=(u,v),對(duì)G作邊e切

8、割得G'=<V',E',W'>,其中，V'=Vv'E'=(Ee)e1,e2,皿=(*e,(u,v)>)<e1,(u,v；<e2,(v',v)>(4)頂點(diǎn)v貫通運(yùn)算。設(shè)G中頂點(diǎn)v恰為邊e1,e2的端點(diǎn)，且W(e1)=(u,v),W(e2)=(w,v)。對(duì)G作頂點(diǎn)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)>。切割與貫通是互逆的，兩者常被稱為同胚運(yùn)算。定義8.9設(shè)G1=<V1,E1,W1>,G2=<V2,E2,W2冽兩個(gè)圖，稱G1與G2同構(gòu)(isomorphic),如果存在雙射f:V1fV2,雙射g：E1fE2,使得對(duì)每一邊eE1,W1(e)=(u,v)(或<u,v>)當(dāng)且僅當(dāng)W2(g(e)=(f(u),f(v)(或<f(u),f(v)>)當(dāng)限于討論簡(jiǎn)單圖時(shí)，可以用頂點(diǎn)的偶對(duì)表示邊，即當(dāng)W(e)=(u,v)時(shí)，邊e用(u,v)來(lái)表示。這時(shí)兩圖同構(gòu)的條件可以簡(jiǎn)化為(u,v)E1當(dāng)且僅當(dāng)(f(u),f(v)E2習(xí)題解答練習(xí)8.11、想一想，一只

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

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

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

13、n1)(n2)7、n個(gè)城市間有m條相互連接的直達(dá)公路。證明：當(dāng)m時(shí)，人們便能2通過(guò)這些公路在任何兩個(gè)城市間旅行。證用n個(gè)頂點(diǎn)表示n個(gè)城市，頂點(diǎn)間的邊表示直達(dá)公路，據(jù)題意需證這n個(gè)城市的公路網(wǎng)絡(luò)所構(gòu)成的圖G是連通的。反設(shè)G不連通，那么可設(shè)G由兩個(gè)不相關(guān)的子圖(沒(méi)有任何邊關(guān)聯(lián)分別在兩個(gè)子圖中的頂點(diǎn))G1,G2組成，分別有ni,n2個(gè)頂點(diǎn)，從而，n=ni+n2,ni>1,n2>1oni(ni1)由于各子圖的邊數(shù)不超過(guò)-(見(jiàn)練習(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)用這一定理和它的證明方法來(lái)解題。)*8、(1)證明：序列(7,6,5,4,3,3,2),(6,5,5,4,3,2,2)以及(6,6,5,4,3,3,1)都不是簡(jiǎn)單圖的度序列。(2)若自然數(shù)序列(d1,d2,dn)滿足d1>d2>>dn,那么當(dāng)它為一簡(jiǎn)單圖的度序列時(shí)必有n(a)di為偶數(shù)；1 1kn(b)對(duì)任一k,1<k<n,di&k(k-1)+min(k,di)。i1ik1證(1)由于7個(gè)頂點(diǎn)的簡(jiǎn)單圖中不可能有7度的頂點(diǎn)，因此序列(7,6,5,

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

16、(k-1)+min(k,di)oi1ik19、畫出圖8.11中圖的補(bǔ)圖及它的一個(gè)生成子圖。22圖8.1110、一個(gè)簡(jiǎn)單圖，如果同構(gòu)于它的補(bǔ)，則該圖稱為自補(bǔ)圖。(1)給出一個(gè)4個(gè)頂點(diǎn)的自補(bǔ)圖。(2)給出一個(gè)5個(gè)頂點(diǎn)的自補(bǔ)圖。(3)是否有3個(gè)頂點(diǎn)或6個(gè)頂點(diǎn)的自補(bǔ)圖？(4)證明一個(gè)自補(bǔ)圖一定有4k或4k+1個(gè)頂點(diǎn)(k為正整數(shù))。解(1) 4個(gè)頂點(diǎn)的自補(bǔ)圖:(2) 5個(gè)頂點(diǎn)的自補(bǔ)圖:(3)沒(méi)有。(4)證設(shè)G為自補(bǔ)圖，有n個(gè)頂點(diǎn)。我們已知因此G應(yīng)恰有n(n 1)條邊。故或者n是4的整數(shù)倍, 4有4k或4k + 1個(gè)頂點(diǎn)(k為正整數(shù))。n個(gè)頂點(diǎ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個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖的圖示。證在圖(a)圖(b)間建立雙射hvABDIJCEGHFh(v)可逐一驗(yàn)證(不贅)(u,v)E(a)當(dāng)且僅當(dāng)(h(u),h(v)E(b)(2)所有不同構(gòu)的4個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖的圖示有如下11個(gè):*12、Kn表示n個(gè)頂點(diǎn)的無(wú)向完全圖。(1)對(duì)K6的各邊用紅、藍(lán)兩色著色，每邊僅著一種顏色，紅、藍(lán)任選。證明：無(wú)論怎樣著色，圖上總有一個(gè)紅色邊組成的K3或一個(gè)藍(lán)色邊組成的K3。(2)用(1)證明下列事實(shí)：任意6個(gè)人之間或者有三個(gè)人相互認(rèn)識(shí)，或者有3個(gè)人相互都不認(rèn)識(shí)。證(1)考慮K6的頂點(diǎn)V,與之關(guān)聯(lián)的邊有

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

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

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

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

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

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

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

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

26、到結(jié)點(diǎn)k的兩條通路均為偶數(shù)長(zhǎng)度，或均為奇數(shù)長(zhǎng)度，那么結(jié)點(diǎn)k到結(jié)點(diǎn)v必然既有奇數(shù)長(zhǎng)度的通路又有偶數(shù)長(zhǎng)度的通路，因而構(gòu)成一奇數(shù)長(zhǎng)度的回路。3、證明：若簡(jiǎn)單無(wú)向圖G是不連通的，那么G一必定是連通的。證設(shè)簡(jiǎn)單無(wú)向圖G是不連通的，那么G由兩個(gè)不相關(guān)的子圖(沒(méi)有任何邊關(guān)聯(lián)分別在兩個(gè)子圖中的頂點(diǎn))G1,G2組成，分別有頂點(diǎn)，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)系是傳遞的嗎？說(shuō)說(shuō)如何由有向圖判定關(guān)系的傳遞性。求圖8.18表示的二元關(guān)系的傳遞閉包，說(shuō)

27、說(shuō)構(gòu)作有向圖傳遞閉包的方法。a圖 8.18解圖8.18表示的二元關(guān)系不是傳遞的。有向圖表示的關(guān)系是傳遞的，當(dāng)且僅當(dāng)對(duì)圖中任意兩個(gè)結(jié)點(diǎn)u,v,如果有從u到v的路徑，則必有從 u至1Jv的邊。圖8.18表示的二元關(guān)系的傳遞閉包如圖8.18 (b)所示。構(gòu)作有向圖傳遞閉包的方法是:對(duì)圖中任意兩個(gè)結(jié)點(diǎn)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, 要時(shí)借助他人作翻譯)一viov3,V4,V5vv7,V8,V9OV6c,d,e,f,g分別精通下列語(yǔ)言，問(wèn)他們7人是否可以自由交談(必a精通英語(yǔ)。b精通漢語(yǔ)和英語(yǔ)。c精通英語(yǔ)、俄語(yǔ)和意大利語(yǔ)。d精通日語(yǔ)和英語(yǔ)。e精通德語(yǔ)和意大利語(yǔ)。f精通法語(yǔ)、日語(yǔ)和俄語(yǔ)。g精通法語(yǔ)和德語(yǔ)。解下圖中7個(gè)頂點(diǎn)表示7個(gè)人，關(guān)聯(lián)兩個(gè)頂點(diǎn)的邊表示兩個(gè)人同時(shí)精通某一種語(yǔ)言:由于該圖是連通的，因此他們7

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

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

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

33、的割邊11、試用有向圖描述下列問(wèn)題的解：某人m帶一條狗d,一只貓c和一只兔子r過(guò)河。m每次游過(guò)河時(shí)只能帶一只動(dòng)物，而沒(méi)人管理時(shí)，狗與兔子不能共處，貓和兔子也不能共處。問(wèn)m怎樣把三個(gè)動(dòng)物帶過(guò)河去？(提示：用結(jié)點(diǎn)代表狀態(tài)，狀態(tài)用序偶<S1,S2>來(lái)表示，這里S1,S2分別是左岸和右岸的人及動(dòng)物集合，例如初始狀態(tài)為<m,d,c,r,>。解描述上述問(wèn)題的有向圖如下：<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、有向圖可以刻劃一個(gè)系統(tǒng)的狀態(tài)轉(zhuǎn)換，例如用圖8.21中的有向圖可以描述識(shí)別01010序列的狀態(tài)轉(zhuǎn)換系統(tǒng)。其中S為初始狀態(tài)，在此讀入序列，然后依序列中符號(hào)轉(zhuǎn)入后續(xù)狀態(tài)(讀到0進(jìn)入S1,讀到1進(jìn)入S2,如此等等)。S4表示讀完序列01010應(yīng)進(jìn)入的最后狀態(tài)，S5表示讀完一個(gè)非01010序列應(yīng)進(jìn)入的最后狀態(tài)。試自行構(gòu)作識(shí)別序列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)過(guò)G的所有頂點(diǎn)、所有邊的閉路徑。圖G稱為歐拉路徑（Eulerwalk）,如果圖G上有一條經(jīng)過(guò)G所有頂點(diǎn)、所有邊的路徑。定理8.11無(wú)向圖G為歐拉圖當(dāng)且僅當(dāng)G連通，并且所有頂點(diǎn)的度都是偶數(shù)。有向圖G為歐拉圖，當(dāng)且僅當(dāng)G是弱連通的，并且每個(gè)頂點(diǎn)的出度與入度相等。定理8.12如果G為歐拉圖，那么G可分成若干個(gè)（一個(gè)或幾個(gè)）回路。定理8.13無(wú)向圖G為歐拉路徑（非歐拉圖），當(dāng)且僅當(dāng)G連通，并且恰有兩個(gè)頂點(diǎn)的度是奇數(shù)。有向圖G為歐拉路徑（非歐拉圖），當(dāng)且僅當(dāng)G連通，

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

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

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

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

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

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

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

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

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