第五章習(xí)題1．解：4個頂點的所有非同構(gòu)連通圖如下圖所示：2．解：圖G是1-可著色的當(dāng)且僅當(dāng)G是空圖。3．解：(1)設(shè)w為分圖個數(shù)，由公式m≤1w=3時，m≤126-36-3+1=6。所以分圖個數(shù)w>2時，邊數(shù)不能超過6(2)由一個孤立頂點和一個Kn-1組成的圖。4．解：以所有二位三進制數(shù)作為頂點，在這頂點集{aa,ab,ac,ba,bb,bc,ca,cb,cc}中，若頂點u的后一個字母與頂點v的前一個字母相同，則u到v有一個弧。這樣所得圖如下圖所示，其中e0=aaa,e1=aab,e2=aac,e3=aba,e4=abb,e5=abc,e6=aca,e7=acb,e8=acc,e9=baa,e10=bab,e11=bac,e12=bba,e13=bbb,e14=bbc,e15=bca,e16=bcb,e17=bcc,e18=caa,e19=cab,e20=cac,e21=cba,e22=cbb,e23=cbc,e24=cca,e25=ccb,e26=ccc。此圖有一條歐拉回路:（e0,e1,e3,e11,e7,e21,e10,e4,e14,e16,e22,e13,e12,e9,e2,e8,e26,e25,e23,e15,e20,e6,e19,e5,e17,e24,e18）,對應(yīng)的排列是aaabacbabbcbbbaacccbcacabcc。5．解：(a)鄰接矩陣為A=01010011(b)A(2)=0111020101110011，A(3)=0212由A，A(2)，A(3)，A(4)可知從v1到v4長度為1，2，3，4的路徑分別為1，1，2，3條。(c)AT=0000101101001110，ATA=00000302AAT中第(2，3)個元素為1，說明從v2和v3引出的邊能共同終止于同一結(jié)點的只有一個，即v4。AAT中第(2ATA中第(2，3)個元素為0，說明沒有結(jié)點引出的邊同時終止于v2和v3，ATA中第(2，2)個元素為(d)A2=0111010101110011，A3=01110111P=A∨A2∨A3∨A4=01110111(e)PT=0000111111111111，P^P所以強分圖的頂點集為：{v1}，{v2,v3,v4}。6．解：完全圖K1,K2,K3,K4分別如下圖所示：7．解：該無向圖的鄰接矩陣A=011118．解：由鄰接矩陣可知a11=1,a12=1,a13=2,a14=0,a22=2,a23=1,a24=3,a33=0,a34=1,a44=0,故頂點v1處有一個環(huán)，v1與v2間有一條邊，v1與v3間有2條邊，v1與v4間沒有邊相連，v2處有2個環(huán)，v2與v3間有一條邊，v2與v4間有3條邊，v3處沒有環(huán)，v3與v4間有一條邊，v4處沒有環(huán)，即一共有3個環(huán)和5條多重邊。根據(jù)鄰接矩陣所得多重圖G如下圖所示，經(jīng)檢驗答案正確。9．解：上圖的強分圖有：<{v1,v2,v3,v4,v5},{<v1,v2>,<v2,v3>,<v3,v4>,<v4,v1>,<v2,v5>,<v5,v3>}>;弱分圖和單向分圖有：<{v1,v2,v3,v4,v5},{<v1,v2>,<v2,v3>,<v3,v4>,<v4,v1>,<v2,v5>,<v5,v3>}>;<{v5,v6},{<v5,v6>}>;<{v6,v7,v8},{<v7,v6>,<v8,v7>}>;強分圖、弱分圖和單向分圖分別如下圖(a)(b)(c)所示：10．解：在完全圖中，每個頂點都與其余（n–1）個頂點相鄰。因此，每個頂點都需要一種新的顏色。因此，色數(shù)K6=6，K10=10，Kn=n。11．解：根據(jù)題意，有10個可能的狀態(tài)，分別為S1:<{m,d,r,c},?>;S2:<{d,c},{m,r}>;S3:<{m,d,c},{r}>;S4:<djztpvx,{m,r,c}>;S5:<{c},{m,d,r}>;S6:<{m,d,r},{c}>;S7:<{m,r,c},lvbbhft>;S8:<{r},{m,d,c}>;S9:<{m,r},{d,c}>;S10:<?,{m,d,c,r}>。如右圖所示，由圖可知，至少有兩個解：(S1,S2,S3,S4,S6,S8,S9,S10)或(S1,S2,S3,S5,S7,S8,S9,S10)。12．解：在圖同構(gòu)意義下，具有三個結(jié)點的所有簡單有向圖如下圖所示：13．證明：先證明充分性。 給定有向圖G=<V,E>,且G有一條經(jīng)過每個結(jié)點的路為v1e1v2e2…vn-1en-1vn，其中V={v1,v2,…vn},{e1,e2,…en-1}?E,ei=<vi,vi+1>,1≤i≤n-1。任給兩個結(jié)點vj,vm∈V，不妨設(shè)j<m，則vjejvj+1ej+1…em-1vm就是從結(jié)點vj出發(fā)到達結(jié)點vm的路，故G是單向連通的。下面證明必要性。對結(jié)點數(shù)目n進行歸納證之，當(dāng)n=1，n=2時，單向連通的圖顯然有一條經(jīng)過該圖中每個結(jié)點的路。當(dāng)n=k時，假設(shè)有一條經(jīng)過每個結(jié)點的路v1v2…vp,其中結(jié)點可能有重復(fù)出現(xiàn)，其結(jié)點下標(biāo)只表示它在路中所經(jīng)過結(jié)點的次序，顯然k≤p。當(dāng)n=k+1時，取一結(jié)點u，在圖G中刪去u，使G-{u}還是單向連通圖。根據(jù)歸納假設(shè)，G-{u}有一條經(jīng)過每一條結(jié)點的路v1v2…vm,令p=max{i|vi到u有路}，q=min{i|u到vi有路}。假設(shè)q>p+1,則必有r，使p<r<q。由于圖G是單向連通的，vr與u之間有路。若該路是從vr到u，則與p=max{i|vi到u有路}矛盾。若該路是從u到vr，則與q=min{i|u到vi有路}矛盾。因此q>p+1不可能，只可能是q≤p+1。當(dāng)q=p+1時，有經(jīng)過每個結(jié)點的路v1v2…vp…u…vp+1vp+2…vm,如下圖(a)所示。當(dāng)q≤p時，有一條經(jīng)過每個結(jié)點的路v1v2…vq…vp…u…vq…vpvp+1…vm,如下圖(b)所示。綜上，定理得證。14．解：用Dijkstra算法，將計算結(jié)果列表如下：結(jié)點步驟kv1v2v3v4v5v6v701234560/v1322/v7∞∞1077/v6∞∞∞∞161616/v3∞1010888/v6∞744/v211/v1由上表可知，v1到v7的最短鏈?zhǔn)?；v1到v2，中間經(jīng)過結(jié)點是v7，其最短鏈?zhǔn)?；v1到v3，中間經(jīng)過結(jié)點v7，v2和v6，其最短鏈?zhǔn)?；v1到v4，中間經(jīng)過結(jié)點v7，v2，v6和v3，其最短鏈?zhǔn)?6；v1到v5，中間經(jīng)過結(jié)點v7，v2和v6，其最短鏈?zhǔn)?。15．解：關(guān)聯(lián)矩陣為M=-

第六章習(xí)題1．解：由歐拉公式n-m+r=2可知，此題區(qū)域數(shù)目R=2+E-V，故R=2+E-V=2+14-10=6；R=2+E-V=2+7-6=3；R=2+E-V=2+60-25=37；R=2+E-V=2+13-14=1；2．解：由歐拉公式n-m+r=2可知，此題頂點數(shù)V=2+E-R，故V=2+E-R=2+6-3=5;V=2+E-R=2+4-1=5;V=2+E-R=2+10-8=4;V=2+E-R=2+27-11=18;3．解：對于平面圖有:邊數(shù)小于等于3倍頂點數(shù)減6。所以對于8個頂點的平面圖而言，邊數(shù)最多可能是3×8-6=18。對于4個頂點的平面圖而言，邊數(shù)最多可能是3×4-6=6。4．解：(a)該圖的一種2-著色如下圖所示：從v1開始的6個循環(huán)：v1v3v2v4v1，v1v3v2v5v1，v1v3v2v6v1，v1v4v2v5v1，v1v4v2v6v1，v1v5v2v6v1成為偶圖的充分必要條件是Ｇ的所有回路的長度均為偶數(shù)，所以這個圖的回路都是偶數(shù)長度的。該題6個從v1開始的循環(huán)長度都是4，符合定理。5．證明：在上圖的(a,c)和(j,i)邊上新增一點，并使用A和B標(biāo)記所得圖的頂點，如下圖所示。上圖有哈密爾頓圖回路當(dāng)且僅當(dāng)下圖有哈密爾頓回路。而下圖有6個A和7個B，相差1個，因此沒有哈密爾頓回路，所以上圖也沒有哈密爾頓回路。6．解：令G'=G+[v2,v3]，且v2,v3不相鄰，d(v2)+d(v3)≥7。G'若是哈密爾頓圖，G也是哈密爾頓圖。因為在G'中，δ(G')≥(7/2)，可知G'是哈密爾頓圖，故G也是哈密爾頓圖。 G的哈密爾頓圈是：v1v2v4v5v6v3v7v1。7．證明：用反證法。假設(shè)G不是哈密爾頓圖，必存在v1,v2∈V，使得d(v1)+d(v2)≤m-1。在圖G-{v1,v2}中，其結(jié)點數(shù)為|V|-2=m-2，故它的邊數(shù)≤(1/2)(m-2)(m-3)。G中的邊數(shù)n，有n≤(1/2)(m-2)(m-3)+(m-1)＜(1/2)(m-2)(m-3)+m=(m-12)+2。這與題意已知條件矛盾，所以G8．證明：給定彼得森圖G如圖所示，令邊集E={(v1,v6),(v2,v7),(v3,v8),(v4,v9),(v5,v10)},于是G-E為非連通圖。故G中任意哈密爾頓圈必含E中的偶數(shù)條邊。若G中某圈只含E中兩條邊，則該圈不可能是哈密爾頓圈。于是，G中每一個哈密爾頓圈必含E中4條邊。 設(shè)C是含(v5,v10),(v1,v6),(v2,v7)和(v3,v8)，而不含邊(v4,v9)的哈密爾頓圈，則該圈C中必含(v4,v5),(v3,v4),(v6,v9)和(v7,v9)。又因為v3和v5在C中的度為2，所以邊(v1,v5)和(v2,v3)不在C中。此時，v1和v2在C中的度為2，所以邊(v1,v2)必在C中。但邊(v1,v2),(v2,v7),(v7,v9),(v9,v6)和(v6,v1)構(gòu)成一圈且在C中，這是不可能的。所以，彼得森圖G不是哈密爾頓圖。9．證明：令|V1|=m1,則|V2|=m-m1,于是有n≤m1(m-m1)=m1m-m1因為(m/2-m1)2≥0，即m2/4≥mm1-m12,故n≤m210．解：它們的對偶圖如下圖所示：11．解：如下圖所示：12．解：在圖G1中，存在奇度結(jié)點，如v2,v4等，而在圖G2中，每個結(jié)點都是偶結(jié)點。所以G1不是歐拉圖，G2是歐拉圖。G2的歐拉圈是v1v2v3v2v11v4v3v11v5v4v5v6v11v10v6v7v6v9v7v8v9v10v2v9v1v8v1。

第七章習(xí)題1．解：是。二叉樹是有序樹，每個結(jié)點最多兩棵子樹。一般樹是無序樹，且每個結(jié)點可以有多棵子樹。2．解：(a)前序為：ABDEHKCFIJLMG中序為：DBKHEAIFLJMCG后序為：DKHEBILMJFGCA3．解：具有六個結(jié)點的不同的樹如下圖所示：4．證明：設(shè)G是一棵樹且e是G的一條邊。由于G無回路，所以e包含在G的無回路部分中，由定理“當(dāng)且僅當(dāng)G的一條邊e不包含在G的回路中時，e才是割邊”可知，e是G的一條割邊。反之，設(shè)G連通但不是樹，則G包含一條回路C，則C中的邊不會是G的割邊。5．證明：用反證法。令T=<V,E'>是簡單連