离散数学概论 第2版 习题及答案 第五六七章图论

第五章习题1．解：4个顶点的所有非同构连通图如下图所示：2．解：图G是1-可着色的当且仅当G是空图。3．解：(1)设w为分图个数，由公式m≤1w=3时，m≤126-36-3+1=6。所以分图个数w>2时，边数不能超过6(2)由一个孤立顶点和一个Kn-1组成的图。4．解：以所有二位三进制数作为顶点，在这顶点集{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）,对应的排列是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引出的边能共同终止于同一结点的只有一个，即v4。AAT中第(2ATA中第(2，3)个元素为0，说明没有结点引出的边同时终止于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处有一个环，v1与v2间有一条边，v1与v3间有2条边，v1与v4间没有边相连，v2处有2个环，v2与v3间有一条边，v2与v4间有3条边，v3处没有环，v3与v4间有一条边，v4处没有环，即一共有3个环和5条多重边。根据邻接矩阵所得多重图G如下图所示，经检验答案正确。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）个顶点相邻。因此，每个顶点都需要一种新的颜色。因此，色数K6=6，K10=10，Kn=n。11．解：根据题意，有10个可能的状态，分别为S1:<{m,d,r,c},∅>;S2:<{d,c},{m,r}>;S3:<{m,d,c},{r}>;S4:<{d},{m,r,c}>;S5:<{c},{m,d,r}>;S6:<{m,d,r},{c}>;S7:<{m,r,c},{d}>;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．解：在图同构意义下，具有三个结点的所有简单有向图如下图所示：13．证明：先证明充分性。 给定有向图G=<V,E>,且G有一条经过每个结点的路为v1e1v2e2…vn-1en-1vn，其中V={v1,v2,…vn},{e1,e2,…en-1}⊆E,ei=<vi,vi+1>,1≤i≤n-1。任给两个结点vj,vm∈V，不妨设j<m，则vjejvj+1ej+1…em-1vm就是从结点vj出发到达结点vm的路，故G是单向连通的。下面证明必要性。对结点数目n进行归纳证之，当n=1，n=2时，单向连通的图显然有一条经过该图中每个结点的路。当n=k时，假设有一条经过每个结点的路v1v2…vp,其中结点可能有重复出现，其结点下标只表示它在路中所经过结点的次序，显然k≤p。当n=k+1时，取一结点u，在图G中删去u，使G-{u}还是单向连通图。根据归纳假设，G-{u}有一条经过每一条结点的路v1v2…vm,令p=max{i|vi到u有路}，q=min{i|u到vi有路}。假设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。当q=p+1时，有经过每个结点的路v1v2…vp…u…vp+1vp+2…vm,如下图(a)所示。当q≤p时，有一条经过每个结点的路v1v2…vq…vp…u…vq…vpvp+1…vm,如下图(b)所示。综上，定理得证。14．解：用Dijkstra算法，将计算结果列表如下：结点步骤kv1v2v3v4v5v6v701234560/v1322/v7∞∞1077/v6∞∞∞∞161616/v3∞1010888/v6∞744/v211/v1由上表可知，v1到v7的最短链是1；v1到v2，中间经过结点是v7，其最短链是2；v1到v3，中间经过结点v7，v2和v6，其最短链是7；v1到v4，中间经过结点v7，v2，v6和v3，其最短链是16；v1到v5，中间经过结点v7，v2和v6，其最短链是8。15．解：关联矩阵为M=-

第六章习题1．解：由欧拉公式n-m+r=2可知，此题区域数目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可知，此题顶点数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．解：对于平面图有:边数小于等于3倍顶点数减6。所以对于8个顶点的平面图而言，边数最多可能是3×8-6=18。对于4个顶点的平面图而言，边数最多可能是3×4-6=6。4．解：(a)该图的一种2-着色如下图所示：从v1开始的6个循环：v1v3v2v4v1，v1v3v2v5v1，v1v3v2v6v1，v1v4v2v5v1，v1v4v2v6v1，v1v5v2v6v1成为偶图的充分必要条件是Ｇ的所有回路的长度均为偶数，所以这个图的回路都是偶数长度的。该题6个从v1开始的循环长度都是4，符合定理。5．证明：在上图的(a,c)和(j,i)边上新增一点，并使用A和B标记所得图的顶点，如下图所示。上图有哈密尔顿图回路当且仅当下图有哈密尔顿回路。而下图有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．证明：用反证法。假设G不是哈密尔顿图，必存在v1,v2∈V，使得d(v1)+d(v2)≤m-1。在图G-{v1,v2}中，其结点数为|V|-2=m-2，故它的边数≤(1/2)(m-2)(m-3)。G中的边数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中的偶数条边。若G中某圈只含E中两条边，则该圈不可能是哈密尔顿圈。于是，G中每一个哈密尔顿圈必含E中4条边。 设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)构成一圈且在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中，存在奇度结点，如v2,v4等，而在图G2中，每个结点都是偶结点。所以G1不是欧拉图，G2是欧拉图。G2的欧拉圈是v1v2v3v2v11v4v3v11v5v4v5v6v11v10v6v7v6v9v7v8v9v10v2v9v1v8v1。

第七章习题1．解：是。二叉树是有序树，每个结点最多两棵子树。一般树是无序树，且每个结点可以有多棵子树。2．解：(a)前序为：ABDEHKCFIJLMG中序为：DBKHEAIFLJMCG后序为：DKHEBILMJFGCA3．解：具有六个结点的不同的树如下图所示：4．证明：设G是一棵树且e是G的一条边。由于G无回路，所以e包含在G的无回路部分中，由定理“当且仅当G的一条边e不包含在G的回路中时，e才是割边”可知，e是G的一条割边。反之，设G连通但不是树，则G包含一条回路C，则C中的边不会是G的割边。5．证明：用反证法。令T=<V,E'>是简单连