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

第三篇圖論第八章圖圖的基本知識內(nèi)容提要圖的定義及有關(guān)術(shù)語定義圖(graph)G由三個部分所組成：非空集合V(G)，稱為圖G的結(jié)點集，其成員稱為結(jié)點或頂點(nodesorvertices)。集合E(G)，稱為圖G的邊集，其成員稱為邊(edges)。I函數(shù)屮:E(G)f(V(G),V(G)),稱為邊與頂點的關(guān)聯(lián)映射(associatveGmapping)。這里(V(G),V(G))稱為VG的偶對集，其成員偶對(pair)形如(u,v),u，v為結(jié)點，它們未必不同。屮(e)=(u,v)時稱邊e關(guān)聯(lián)端點u，v。G當(dāng)(u,v)用作序偶時(V(G),V(G))=V(G)?V(G)，e稱為有向邊，e以u為起點，以v為終點，圖G稱為有向圖(directedgraph)；當(dāng)(u,v)用作無序偶對時，(u,v)=(v,u)，稱e為無向邊(或邊)，圖G稱為無向圖(或圖)。圖G常用三元序組＜V(G),E(G),W＞,或〈V,E,W＞來表示。顯然，G圖是一種數(shù)學(xué)結(jié)構(gòu)，由兩個集合及其間的一個映射所組成。定義8?2設(shè)圖G%〈V,E,屮〉。當(dāng)V和E為有限集時，稱G為有限圖，否則稱G為無限圖。本書只討論有限圖。當(dāng)屮為單射時，稱G為單圖；當(dāng)屮為非單射時，稱G為重圖，GG又稱滿足屮(el)=屮(e2)的不同邊el,e2,為重邊，或平行邊。當(dāng)屮(e)=(v,v)(或〈v,v>)時，稱e為環(huán)(loops)。無環(huán)和重邊的無向單圖稱為簡單圖。當(dāng)G為有限簡單圖時，也常用(n,m)表示圖G,其中n二??,m=?E?o屮為雙射的有向圖稱為有向完全圖；對每一(u,v),u?v,均有e使W(e)=(u,v)的簡單圖稱為無向完全圖，簡稱完全圖，n個頂點的完全圖常記作Kon在單圖G中，屮(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,vo不是任何邊的端點的結(jié)點都稱為孤立結(jié)點，僅由孤立結(jié)點構(gòu)成的圖(E=?)稱為零圖。當(dāng)給G賦予映射f：V-W,或g：E-W,W為任意集合，常用實數(shù)集及其子集,此時稱G為賦權(quán)圖，常用<V,E,W,f>或〈V,E,W,g>或〈V,E,W,f,g>表示之。f(v)稱為結(jié)點v的權(quán)，g(e)稱為邊e的權(quán)。結(jié)點的度定義在無向圖中，結(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ù)目。定理對任意圖G,設(shè)其邊數(shù)為m,頂點集為{v,v,…，v},那么l2n工d(v)二2mii=1定理圖的奇數(shù)度頂點必為偶數(shù)個。定理自然數(shù)序列(a,a,…,a)稱為一個度序列，如果它是一個圖的12n頂點的度的序列。(a,a,…,a)為一度序列，當(dāng)且僅當(dāng)工a為一偶數(shù)。12nii=1定義一度的頂點稱為懸掛點(pendantnodes)。定義各頂點的度均相同的圖稱為正則圖(regulargraph)。各頂點度均為k的正則圖稱為k-正則圖。圖運算及圖同構(gòu)由于圖由結(jié)點集、邊集及關(guān)聯(lián)映射組成，因此對圖可作種種與集合運算相類似的運算。定義設(shè)圖G1=〈V1,El,屮1>,G2=<V2,E2,屮2>，稱G1為G2的子圖(subgraph),如果V1?V2,E1?E2,W1?屮2。稱G1為G2的真子圖，如果G1是G2的子圖，且G1?G2。稱G1為G2的生成子圖(spanningsubgraph),如果G1是G2的子圖，且V1=V2。定義設(shè)圖G1=<V1,E1,W1>,G2=<V2,E2,W2>，且屮1與屮2是相容的，即對任一x,若屮1(x)=y1,屮2(x)=y2,則y1二y2，從而W1?W2為一函數(shù)。G1與G2的并，記為G1?G2=G3=<V3,E3,屮3>,其中V3=V1?V2,E3=E1?E2,W3=W1?W2OG1與G2的交，記為G1?G2=G3=<V3,E3,屮3>,其中V3二V1?V2,E3=E1?E2,W3=屮1?屮2。若G1為G2的子圖，則可定義G2對G1的差，記為G2—G1=G3=<V3,E3,W3>，其中E3=E2-E1,V3=V2,W3=屮2?。E3G1與G2的環(huán)和，記為G1?G2,G1?G2=(G1?G2)—(G1?G2)若G為簡單圖，貝何定義G的補，記為G_,若?V(G)?=n,則G一二K—Gn定義設(shè)圖G=<V,E,W>G—e表示對G作刪除邊e的運算，G—e=<V,E',W>，其中E'=E—{e},屮'二屮？。E'G—v表示對G作刪除頂點v的運算，G—v=<V',E',W>,其中V'二V—{v},E'=E—{e?e以v為端點},W'=W?oE'邊e切割運算。設(shè)G中屮(e)=(u,v),對G作邊e切割得G'=<V',E',屮'>，其中，V'=V?{v'},E'=(E—{e})?{e1,e2},屮'二(屮一{<e,(u,v)>})?{<e1,(u,v')>,〈e2,(v',v)>}頂點v貫通運算。設(shè)G中頂點v恰為邊e1,e2的端點，且屮(e1)=(u,v),W(e2)=(w,v)。對G作頂點v貫通得G'=<V',E',W>,其中V'=V—{v},E'=(E—{e1,e2})?{e},屮'=(屮一{<e1,(u,v)>,<e2,(w,v)>})?{<e,(u,w)>}o切割與貫通是互逆的，兩者常被稱為同胚運算。定義設(shè)G1=<V1,E1,W1>,G2=<V2,E2,W2>為兩個圖，稱G1與G2同構(gòu)(isomorphic),如果存在雙射f：V1-V2，雙射g：E1-E2，使得對每一邊e?E1,屮l(e)=(u,v)(或〈u,v>)當(dāng)且僅當(dāng)屮2(g(e))=(f(u),f(v))(或<f(u),f(v)>)當(dāng)限于討論簡單圖時，可以用頂點的偶對表示邊，即當(dāng)屮(e)=(u,v)時，邊e用(u,v)來表示。這時兩圖同構(gòu)的條件可以簡化為(u,v)?El當(dāng)且僅當(dāng)(f(u),f(v))?E2習(xí)題解答練習(xí)1、想一想，一只昆蟲是否可能從立方體的一個頂點出發(fā)，沿著棱爬行、它爬行過每條梭一次且僅一次，并且最終回到原地為什么解不可能?？蓪⒘⒎襟w的一個頂點看作圖的一個頂點，把立方體的棱看作圖的邊，那么該圖的四個頂點都是三度的，因此不可能從一個頂點出發(fā)，遍歷所有的邊一次且僅一次，并且最終回到原頂點。2、請設(shè)想一張圖，它的64個頂點表示國際象棋棋盤的64個方格，頂點間的邊表示:在這兩個頂點表示的方格之間可以進(jìn)行“馬步”的行走。試指出其頂點有哪幾類(依其度分類)，每類各有多少個頂點。解其頂點有5類：二度頂點合計4個,三度頂點合計8個,四度頂點,合計20個,六度頂點,合計16個頂點,八度頂點,合計16個頂點。23444432346666434688886446888864468888644688886434666643234444323、（l）證明：n個頂點的簡單圖中不會有多于n（n—1）條邊。2（2）n個頂點的有向完全圖中恰有n2條邊。證（l）n個頂點的簡單完全圖的邊數(shù)總和為（n-1）+（n-2）+…+2+1=n（n-1）（2）n個頂點的有向完全圖的邊數(shù)總和為n+nHFn+n=nxn=n24、證明：在任何n（n#2）個頂點的簡單圖G中，至少有兩個頂點具有相同的度。證如果G有兩個孤立頂點，那么它們便是具有相同的度的兩個頂點。如果G恰有一個孤立頂點，那么我們可對有n-1個頂點但沒有孤立頂點的G'（它由G刪除孤立頂點后得到）作下列討論。不妨設(shè)G沒有孤立頂點，那么G的n個頂點的度數(shù)應(yīng)是：1,2,3,…,n-1這n-1無種可能之一，因此必定有兩個頂點具有相同的度。5、圖是一個迷宮,其中數(shù)字表示通道、和死胡同（包括目標(biāo)）。請用一個圖來表示這個迷宮（用結(jié)點表示通道、和死胡同（包括目標(biāo)））,用邊表示它們之間的可直接到達(dá)關(guān)系。22圖16圖166、在晚會上有n個人，他們各自與自己相識的人握一次手。已知每人與別人握手的次數(shù)都是奇數(shù)，問n是奇數(shù)還是偶數(shù)。為什么解n是偶數(shù)。用n個頂點表示n個人，頂點間的一條邊表示一次握手,可構(gòu)成一個無向圖。若n是奇數(shù)，那么該圖的頂點度數(shù)之和為奇數(shù)（奇數(shù)個奇數(shù)的和），這是不可能的，因此n是偶數(shù)。7、n個城市間有m條相互連接的直達(dá)公路。證明：當(dāng)m>（“—1）（"—2）時,人們便能通過這些公路在任何兩個城市間旅行。證用n個頂點表示n個城市，頂點間的邊表示直達(dá)公路，據(jù)題意需證這n個城市的公路網(wǎng)絡(luò)所構(gòu)成的圖G是連通的。反設(shè)G不連通，那么可設(shè)G由兩個不相關(guān)的子圖（沒有任何邊關(guān)聯(lián)分別在兩個子圖中的頂點）Gl,G2組成，分別有n,n個頂點，從而，n二n+n,n21,n21。l2l2l2由于各子圖的邊數(shù)不超過n（"廠°（見練習(xí)之3），因此G的邊數(shù)m滿2足：mn(n-1)二(n(n-1)+n(n-1))2ii21122i=1=-((n-1)(n-1)+(n-1)(n-1))212=丄(n-1)(n+n-2)212=2(n-1)(n-2)與已知m〉(n-1)(n-2)矛盾，故圖G是連通的。2(本題是定理的特例，當(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ù)序列（d,d,…，d）滿足d>d>???>d，那么當(dāng)它為一簡12n12n單圖的度序列時必有工d為偶數(shù)；ii=1對任一k，lWkWn,工dWk(k-1)+min(k,d)。iii=1i=k+1證（1）由于7個頂點的簡單圖中不可能有7度的頂點，因此序列（7，

6，5，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)也不是簡單圖的度序列。證(2)Yd為偶數(shù)是顯然的。ii=1考慮圖中的k個頂點(k=l,2,…,n)，這k個頂點的生成子圖的度數(shù)總和Wk(k-l)，而其余n-k個頂點v,v,…,v,可使v,v,…，v增k+lk+2nl2k加的度數(shù)不會超過Ymin(k,d)ii=k+1因此我們有工dWk(k-l)+工min(k,d)。iii=1i=k+19、畫出圖中圖的補圖及它的一個生成子圖。補圖生成子圖補圖10、一個簡單圖，如果同構(gòu)于它的補，則該圖稱為自補圖。（1）給出一個4個頂點的自補圖。（2）給出一個5個頂點的自補圖。（3）是否有3個頂點或6個頂點的自補圖（4）證明一個自補圖一定有4k或4k+1個頂點（k為正整數(shù)）。解（1）4個頂點的自補圖：2）5個頂點的自補圖：解（1）4個頂點的自補圖：2）5個頂點的自補圖：（3）沒有。（4）證設(shè)G為自補圖，有n個頂點。我們已知n個頂點的完全圖有

nn—1）條邊，因此G應(yīng)恰有呦—1）條邊。故或者n是4的整數(shù)倍，或者n-124是4的整數(shù)倍，即圖G—定有4k或4k+1個頂點（k為正整數(shù)）。11、（1）證明圖中（a）與（b）同構(gòu)。B圖B圖2）給出所有不同構(gòu)的4個結(jié)點的簡單圖的圖示。（l）證在圖（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、K表示n個頂點的無向完全圖。n（1）對K的各邊用紅、藍(lán)兩色著色，每邊僅著一種顏色，紅、藍(lán)任選。6證明：無論怎樣著色，圖上總有一個紅色邊組成的K或一個藍(lán)色邊組成的3K。3（2）用（l）證明下列事實：任意6個人之間或者有三個人相互認(rèn)識，或者有3個人相互都不認(rèn)識。證（l）考慮K的頂點V,與之關(guān)聯(lián)的邊有5條，其中至少有3條著同6一顏色。不妨設(shè)均著紅色，這三邊的另一個端點分別是u1,u2,u3（如圖所

示）。再考慮關(guān)聯(lián)u1,u2,u3的三條邊。如果它們中有一條著紅色的邊，那

么我們就已經(jīng)得到一個紅色邊組成的K,如果它們中沒有著紅色的邊，那3么我們就能夠得到一個藍(lán)色邊組成的K。3u2u1u2u1證（2）用六個頂點表示6個人，頂點間紅色邊表示人員間相互認(rèn)識，頂點間藍(lán)色邊表示人員間相互不認(rèn)識，便產(chǎn)生一個邊著紅、藍(lán)兩色的完全圖K。利用（1）的結(jié)論，可以斷定6個人之間或者有三個人相互認(rèn)識，或6者有3個人相互都不認(rèn)識。路徑、回路及連通性內(nèi)容提要路徑與回路定義圖G的頂點v到頂點v的擬路徑（pseudopath）是指如下頂點1l與邊的序列：l-1el-1l-1el-111223其中v,v,v,…，v,v為G的頂點e,e,…，e為G的邊，且e(i=123l-1l12l-1i1,2,…，l-1）以v及v為端點，（對有向圖G，e以v為起點，以vii+1iii+1為終點）,擬路徑的邊數(shù)1—1稱為該擬路徑的長度。當(dāng)e（i=1,2,…，1-1）i各不相同時，該擬路徑稱為路徑（walk）,又當(dāng)v（i=1,2,…，1）各不相i同時（除v與v），則稱此路徑為通路（Path）。v=v的路徑稱為閉路徑1111（closedwalk）；v=v的通路稱為回路（circuit）。11當(dāng)討論限于簡單圖或無平行邊的有向圖時，上述擬路徑、路徑、通路等可用頂點序列來表示，例如用（「篤，.…U）代替式v1'e1'v2，e2，v3，???」1-1，「1，人。定理在有n個頂點的圖G中，如果有從頂點u到v（u?v）的擬路徑，那么從u到v必有路徑，并且必有長度不大于n-1的通路。定理8?5在具有n個頂點的圖G中，如果有從v到v的閉路徑，那么必定有一條從v到v的長度不大于n的回路。8?2?2連通性定義稱圖中頂點u到v是可達(dá)的(accesible)，如果u二v，或者有一條u到v的路徑。定義稱無向圖G是連通的(connected)，如果G的任何兩個頂點都是相互可達(dá)的。稱有向圖G是強連通的，如果G的任何兩個頂點都是相互可達(dá)的;稱有向圖G是單向連通的，如果G的任何兩個頂點中，至少從一個頂點到另一個頂點是可達(dá)的；稱有向圖G是弱連通的，如果G的有向邊被看作無向邊時是連通的。定義圖G'稱為圖G的連通分支(connectedcomponents),如果G'是G的子圖，G'是連通的，并且不存在G的真子圖G''，使G''是連通的，且G''以G'為真子圖。定義設(shè)G'為有向圖G的子圖，若G'是強連通的(單向連通的、弱連通的)，且G沒有真子圖G''使G'為其真子圖，而G''強連通(單向連通、弱連通)，那么稱G'為G的一個強分圖(單向分圖、弱分圖)。定理8?6一個圖G是不連通的，當(dāng)且僅當(dāng)G的頂點集V可以分成兩個不交的非空子集V1和V2,使得任何邊都不以V1的一個頂點和V2一個頂點為其兩端點。定理如果圖G恰有兩個不同的奇數(shù)度的頂點u，v，那么u到v必定是可達(dá)的。定理若圖G為具有n個頂點、k個連通分支的簡單圖，那么G至多有(n-k)(n-k+1)條邊。2八°A8?2?3連通度定義設(shè)S為連通圖G的頂點集V的子集，稱S為G的點割集(cut-setofnodes)，如果從G中刪除S中的所有頂點后得到的圖不連通，但S的任何真子集均無這一特性。當(dāng)點割集為單元素集合｛v｝時，v稱為割點(cut-nodes)。定義x(G)稱為G的點連通度(node-connectivity)，定義如下：0若G非連通圖X(G)=\n-1若G為Knmin｛|S|:S為點割集｝若G連通，G豐Kn定義設(shè)S為連通圖G邊集E的子集，稱S為G的邊割集(cut-setofedges)，或割集，如果從G中刪除S的所有邊后所得的圖是不連通的，但S的任何真子集均無這一特性。當(dāng)割集為單元素集｛e｝時，稱e為割邊(cut-edges)。定義入(G)稱為圖G的邊連通度(edge-connectivity)，定義如下：0當(dāng)G非連通圖時九(G)=<0當(dāng)G為一孤立結(jié)點時min｛|S|:S為G的割集｝否則定理對任何簡單無向圖G,x(G)W入(G)S(G)定理設(shè)G為n個頂點、m條邊的簡單連通圖，那么入(G)W如。n習(xí)題解答練習(xí)1、證明定理。證設(shè)n個頂點的圖G中，有從v到v的閉路徑，表示為（v,v,v,…，V,v）12k如果v,v,v,…,v中沒有相同頂點（因而不多于n個），那么它便是一條12k從v到v的長度不大于n的回路。如果v,v,v,v中有相同頂點v二v，12kij例如（v,v,…，v,…，v,v，…，v,v）1ijj+1k那么刪除v到v的閉路徑，得到ij（v,v,…，v,v,…，v,v）1ij+1k仍然為從v到v的閉路徑。如此不斷刪除閉路徑內(nèi)相同頂點構(gòu)成的閉路徑，最終必可得到一條從v到v的長度不大于n的回路。2、證明：在簡單無向圖G中，從結(jié)點u到結(jié)點v,如果既有奇數(shù)長度的通路又有偶數(shù)長度的通路，那么G中必有一奇數(shù)長度的回路。證設(shè)G中，從結(jié)點u到結(jié)點v的奇數(shù)長度的通路為0，偶數(shù)長度的通路為E。對O和E的除結(jié)點u和v的相交結(jié)點的數(shù)目歸納k。k=0,那么O和E恰好構(gòu)成G的奇數(shù)長度的回路。設(shè)奇數(shù)長度的通路與偶數(shù)長度的通路的相交結(jié)點的數(shù)目少于k時，命題成立。設(shè)圖G中，從結(jié)點u到結(jié)點v的奇數(shù)長度的通路與偶數(shù)長度的通路有k個相交結(jié)點，如圖所示：-1"-個相交結(jié)點，如圖所示：-1"-””””「.2J".」,k考慮結(jié)點u到結(jié)點k,如果從結(jié)點u到結(jié)點k,既有奇數(shù)長度的通路又有偶數(shù)長度的通路，那么據(jù)歸納假設(shè)，其中有一奇數(shù)長度的回路，因而G中必有一奇數(shù)長度的回路。如果從結(jié)點u到結(jié)點k的兩條通路均為偶數(shù)長度，或均為奇數(shù)長度,那么結(jié)點k到結(jié)點v必然既有奇數(shù)長度的通路又有偶數(shù)長度的通路，因而構(gòu)成一奇數(shù)長度的回路。3、證明：若簡單無向圖G是不連通的，那么G—3、證設(shè)簡單無向圖G是不連通的，那么G由兩個不相關(guān)的子圖（沒有任何邊關(guān)聯(lián)分別在兩個子圖中的頂點）G1，G2組成，分別有頂點，u,u,…,u和v,v,…,V］。12k12l由于邊(u,v)均不在6中(i=1,2,…，k,j=1,2,???，i)ij因此（u,v）全部在G—中，從而G—是連通的。ij4、有向圖可用于表示關(guān)系，圖表示的二元關(guān)系是傳遞的嗎說說如何由有向圖判定關(guān)系的傳遞性。求圖表示的二元關(guān)系的傳遞閉包，說說構(gòu)作有向圖傳遞閉包的方法。

解圖表示的二元關(guān)系不是傳遞的。有向圖表示的關(guān)系是傳遞的，當(dāng)且僅當(dāng)對圖中任意兩個結(jié)點u,v,如果有從u到V的路徑，則必有從u到V的邊。圖表示的二元關(guān)系的傳遞閉包如圖（b）所示。構(gòu)作有向圖傳遞閉包的方法是：對圖中任意兩個結(jié)點u,v,如果有從u到V的路徑，則添加從u到V的邊。5、給出圖中有向圖的強分圖,單向分圖和弱分圖,作出它的凝聚圖。圖V5、給出圖中有向圖的強分圖,單向分圖和弱分圖,作出它的凝聚圖。圖V10解圖中有向圖的強分圖有：<{V,V},{<V,V>,<V,V>}>,121221<{V,V,V},{<V,V>,<V,V>,<V,V>,<V,V>}>,34535434554<{V6},{<V6,V6>}>,<{V,V,V},{<V,V>,<V,V>,<V,V>}>,789788997

<{v},{}>10圖中有向圖的單向分圖有：<{v,v,v,v,v,v},{<v,v>,<v,v>,<v,v>,<v,v>,<v,v>,<v,v>123456122114234335,<v,v>,<v,v>,<v,v>}>,455436<{v,v,v,v},{<v,v>,<v,v>,<v,v>,<v,v>}>78910788997710TOC\o"1-5"\h\z圖的凝聚圖：{v}102o*o{V3，V4{V3，V4，V「}5o789106、有7人a,b,c,d,e,f,g分別精通下列語言，問他們7人是否可以自由交談（必要時借助他人作翻譯）。a精通英語。b精通漢語和英語。c精通英語、俄語和意大利語。d精通日語和英語。e精通德語和意大利語。f精通法語、日語和俄語。g精通法語和德語。解下圖中7個頂點表示7個人,關(guān)聯(lián)兩個頂點的邊表示兩個人同時精a通某一種語言：d

d由于該圖是連通的，因此他們7人是可以自由交談（必要時借助他人作翻譯）。7、證明：一個有向圖是單向連通的，當(dāng)且僅當(dāng)它有一條經(jīng)過每一結(jié)點的路徑。證充分性是顯然的。必要性：設(shè)有向圖G是單向連通的，P是G中的一條路徑，起點為u,1終點為u。如下延長這一路徑：k考慮路徑外的任意頂點w,若（1）有頂點w到u的路徑，則我們?nèi)缭浮?（2）有頂點u到w的路徑，則我們?nèi)缭?。否則，由于有向圖是單向連通k的，（3）有頂點w到u的路徑，和頂點u到w的路徑，則我們?nèi)缭?。否則,kk-1由于有向圖是單向連通的，⑷有頂點w到7的路徑，和頂點兒-2到w的路徑，則我們?nèi)缭浮７駝t,（5）如此等等…，有頂點w到u的路徑，和頂點u到w的路徑，則我k1們?nèi)缭浮Ｈ缟喜粩嘌娱L這一路徑，直至產(chǎn)生一條經(jīng)過每一結(jié)點的路徑。8、稱d(u,v)為圖G=<V,E,屮〉中結(jié)點u,v間的距離：0當(dāng)u=vd(u,v)=當(dāng)u到v不可達(dá)u,v間最短路徑長度否則d稱為圖G的直徑，如果d=max{d(u,v)?u,v?V}。試求圖中圖的直徑,x(G)，入(G),6(G),并指出一個點割集和一個邊割集。圖解d=3,x(G)=3，入(G)=3,S(G)=3。9、頂點v是簡單連通圖G的割點，當(dāng)且僅當(dāng)G中存在兩個頂點vl,v2,使vl到v2的通路都經(jīng)過頂點v。試證明之。證充分性是顯然的。必要性：設(shè)頂點v是簡單連通圖G的割點，如果不存在兩個頂點vl,v2,使v1到v2的通路都經(jīng)過頂點v,那么對任意兩個頂點vl,v2,都有一條通路不經(jīng)過頂點v，因而刪除頂點v不能使G不連通，與v是簡單連通圖G的割點矛盾。故G中必存在兩個頂點vl,v2，使vl到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的割邊11、試用有向圖描述下列問題的解：某人m帶一條狗d，—只貓c和一只兔子r過河。m每次游過河時只能帶一只動物，而沒人管理時，狗與兔子不能共處，貓和兔子也不能共處。問m怎樣把三個動物帶過河去（提示：用結(jié)點代表狀態(tài)，狀態(tài)用序偶〈S1,S2＞來表示，這里S1，S2分別是左岸和右岸的人及動物集合，例如初始狀態(tài)為＜{m,d,c,r},?＞。解描述上述問題的有向圖如下：12、有向圖可以刻劃一個系統(tǒng)的狀態(tài)轉(zhuǎn)換，例如用圖中的有向圖可以描述識別010?10序列的狀態(tài)轉(zhuǎn)換系統(tǒng)。其中S為初始狀態(tài)，在此讀入序列，然后依序列中符號轉(zhuǎn)入后續(xù)狀態(tài)（讀到0進(jìn)入S1,讀到1進(jìn)入S2,如此等等）°S4表示讀完序列010?10應(yīng)進(jìn)入的最后狀態(tài),S5表示讀完一個非010?10序列應(yīng)進(jìn)入的最后狀態(tài)。試自行構(gòu)作識別序列01（10）?10的有向圖刻劃的狀態(tài)轉(zhuǎn)換系統(tǒng)。（上文中w?表示空字或重復(fù)任意多次導(dǎo)所得的字。）Q-―~~o1-—o——oSK.11S30歐拉圖與哈密頓圖內(nèi)容提要3.1歐拉圖與歐拉路徑定義圖G稱為歐拉圖（Eulergraph）,如果圖G上有一條經(jīng)過G的所有頂點、所有邊的閉路徑。圖G稱為歐拉路徑（Eulerwalk），如果圖G上有一條經(jīng)過G所有頂點、所有邊的路徑。定理無向圖G為歐拉圖當(dāng)且僅當(dāng)G連通，并且所有頂點的度都是偶數(shù)。有向圖G為歐拉圖，當(dāng)且僅當(dāng)G是弱連通的，并且每個頂點的出度與入度相等。定理如果G為歐拉圖，那么G可分成若干個（一個或幾個）回路。定理無向圖G為歐拉路徑（非歐拉圖），當(dāng)且僅當(dāng)G連通，并且恰有兩個頂點的度是奇數(shù)。有向圖G為歐拉路徑（非歐拉圖），當(dāng)且僅當(dāng)G連通，并且恰有兩個頂點的入度與出度不等，它們中一個的出度比入度多1，另一個入度比出度多l(xiāng)。哈密頓圖及哈密頓通路定義無向圖G稱為哈密頓圖（Hamiltongraph），如果G上有一條經(jīng)過所有頂點的回路（也稱這一回路為哈密頓回路）。稱無向圖有哈密頓通路（非哈密頓圖），如果G上有一條經(jīng)過所有頂點的通路（非回路）。定理設(shè)圖G為具有n個頂點的簡單無向圖，如果G的每一對頂點的度數(shù)之和都不小于n-1,那么G中有一條哈密頓通路；如果G的每一對頂點的度數(shù)之和不小于n,且n#3,那么G為一哈密頓圖。

定理當(dāng)n為不小于3的奇數(shù)時，K上恰有」條互相均無任何公共2邊的哈密頓回路。定義圖G稱為可2-著色（2-chromatic），如果可用兩種顏色給G的所有頂點著色，使每個頂點著一種顏色，而同一邊的兩個不同端點必須著不同顏色。定理設(shè)圖G是可2-著色的。如果G是哈密頓圖，那么著兩種顏色的頂點數(shù)目相等；如果G有哈密頓通路，那么著兩種顏色的頂點數(shù)目之差至多為一。習(xí)題解答練習(xí)&31、試作出四個圖的圖示，使第一個既為歐拉圖又為哈密頓圖；第二個是歐拉圖而非哈密頓圖；第三個是哈密頓圖卻非歐拉圖；第四個既非歐拉圖也非哈密頓圖。解（a）既為歐拉圖又為哈密頓圖；（b）是歐拉圖而非哈密頓圖；（c）是哈密頓圖卻非歐拉圖；（d）既非歐拉圖也非哈密頓圖。(b)(b)2、像第一題要求的那樣對歐拉路徑和哈密頓通路作出四個圖。解（a）既有歐拉路徑又有哈密頓通路；（b）有歐拉路徑而無哈密頓通a)歐拉(b)(c)a)歐拉(b)(c)3、問n為何種數(shù)值時，K既是歐拉圖又是哈密頓圖。問k為何值時，nk-正則圖既是歐拉圖又是哈密頓圖。解n為奇數(shù)時，K既是歐拉圖又是哈密頓圖。k為大于或等于n/2的n偶數(shù)時，k-正則圖既是歐拉圖又是哈密頓圖。4、證明：恰有兩個奇數(shù)度頂點u,v的無向圖G是連通的，當(dāng)且僅當(dāng)在G上添加邊（u,v）后所得的圖G*是連通的。證必要性是顯然的。設(shè)G*是恰有兩個奇數(shù)度頂點u,v的無向圖G添加邊（u，v）后所得，且是連通的,那么圖G*是一個歐拉圖（每一個頂點都是偶數(shù)度的連通圖），因此G*中刪除邊（u,v）后所得的圖G仍是連通的。5、參閱練習(xí)第2題。問馬可否從某處出發(fā)完成所有可能的跳步一次且僅一次后回到原地。解練習(xí)第2題中的圖不是歐拉圖（它有三個3度的頂點），因此馬不可能從某處出發(fā)完成所有可能的跳步一次且僅一次后回到原地。6、參閱練習(xí)第2題。問馬可否從某處出發(fā)跳遍棋盤的所有方格一次且僅一次后回到原地。解馬可以從某處出發(fā)跳遍棋盤的所有方格一次且僅一次后回到原地。具體跳步如下圖所示:

幻方中數(shù)字n表示第n個跳步的起點。下圖則表示跳步的圖示。50112463143726352362511225341538104964214013362761229523328391648760120415429594458533217426472574419305535854631564318幻方7、試計算K(n#3)中不同的哈密頓回路共有多少條。n解不同的哈密頓回路共有(n1)!條。可以用依次選取每一條邊來生成2哈密頓回路。因為組成回路的第一條邊的選擇可能是n種,組成回路的第

二條邊的選擇可能是n-1種，…，組成回路的第n-1條邊的選擇可能是2種，組成回路的第n條邊的選擇可能是1種，而每一哈密頓回路由此生成兩次，因此不同的哈密頓回路共有0二1!條。28、十一個學(xué)生在一張圓桌旁共進(jìn)晚餐，要求在每次晚餐上每個學(xué)生的鄰座都與其它各次晚餐的鄰座不同。問這樣共進(jìn)晚餐能安排多少次。解每次晚餐上每個學(xué)生的鄰座都與其它各次晚餐的鄰座不同的安排方式有口種（根據(jù)定理。）29、判別圖中各圖是否為哈密頓圖，若不是，請說明理由，并回答它是否有哈密頓通路。(c)(c)解（a），（b）是為哈密頓圖。（c）不是哈密頓圖，也沒有哈密頓通路。在圖（c）中增加頂點k,并對其頂點做二著色，構(gòu)成圖（d）（如下）。圖（d）不是哈密頓圖，也沒有哈密頓通路。因為圖中白色頂點比黑色頂點多兩個。故（c）不是哈密頓圖，也沒有哈密頓通路。否則它的哈密頓回路或哈密頓通路必定經(jīng)過頂點k（k在兩個二度頂點之間的邊上），從而圖（d）也是哈密頓圖，也有哈密頓通路，矛盾。kk2210、證明：對哈密頓圖G=〈V,E,屮〉刪除S(?V)中的所有頂點后，所得圖G'的連通分支數(shù)不大于？S?。證設(shè)G1是G中的哈密頓回路，顯然在G1中刪除S(?V)中的所有頂點后，所得圖G1'的連通分支數(shù)k1,不小于在G中刪除S(?V)中的所有頂點后，所得圖G'的連通分支數(shù)k,即kWk1。由于G1是一條回路，在G1中刪除S(?V)中的所有頂點后，所得圖G1'的連通分支數(shù)k1不大于？S?是顯然的，即k1W?S?。因此kWk1W?S?11、設(shè)G為(n,m)圖。證明：如果m>C2+2，那么G為哈密頓圖(提n—1示：運用定理)。證設(shè)G中有兩個頂點v1和v2的度數(shù)之和不大于n-1，那么以v1和v2為端點的邊不多于n-1條。而其余頂點之間的邊的數(shù)目不多于(n—2)(n—3)條。故G的總邊數(shù)m滿足kk=1k=1m<n—1+(n—2)(n—3)2=*(2n一2+n2一5n+6)=2(n2一3n+4)=-(n—1)(n—2)+12=C2+1n—1與m>C2+2矛盾，故G中任意兩個頂點的度數(shù)之和大于n。根據(jù)定理，Gn—1為哈密頓圖。12、設(shè)有n個圍成一圈跳舞的孩子，每個孩子都至少與其中n個是朋2友。試證明，總可安排得使每個孩子的兩邊都是他的朋友。證設(shè)n個孩子為n個頂點，用邊表示頂點間的朋友關(guān)系構(gòu)成一個圖G。由于每個孩子都至少與其中n個是朋友，因此G的每一頂點的度數(shù)至少是2n，從而G的任何兩個頂點的度數(shù)之和至少是n。根據(jù)定理，G為哈密頓圖。2即G有哈密頓回路，這表明，總可安排n個孩子圍成一圈跳舞，使每個孩子的兩邊都是他的朋圖的矩陣表示內(nèi)容提要8.4.1關(guān)聯(lián)矩陣定義設(shè)G為(n，m)圖，那么n?m矩陣A二［a.］，ij［1當(dāng)邊e以頂點v為端點a=<j°ij|0否則稱為G的關(guān)聯(lián)矩陣(incidencematrix)，記為A(G)。

定理若G為(n,m)連通簡單圖。那么A的秩為n-l(即其最大非零行列式的階數(shù)為n-l)。鄰接矩陣定義設(shè)G二〈V,E,屮〉為一無重邊的有向圖。其中V二{v,v,…,v},TOC\o"1-5"\h\z12n那么n?n矩陣A=[a],ij'1a=<

ij0當(dāng)<v,v>GE(或(v'1a=<

ij0ijij當(dāng)<v,v>電E(或(v,v)電E)ijij稱為圖G的鄰接矩陣(adjacencymatrix),記為A[G]用A】表示l個矩陣A的乘積。令A(yù)】二[a(i)]，那么a(i)的意義是：G中從頂點v到v的長度為lijijij的擬路徑恰為a(i)條。ij令A(yù)OAi=[b]，那么b的意義是：有b個頂點v,使得v到v,ijijijiv到v都有邊(兩邊交于v)。因而b表示頂點v的出度。jiii令A(yù)iOA=[b]，那么b的意義是：有b個頂點v,使得v到ijijijv,v到v都有邊；因而b表示頂點v的入度。ijiii路徑矩陣與可達(dá)性矩陣設(shè)n個頂點的圖G的鄰接矩陣為A,V及人表示如下定義的矩陣運算.若A=[a],C=[c]，貝Ui