湘潭大学刘任任版离散数学课后习题答案习题8

习题81、图中8.10中哪些是E图？哪些是半E图？分析：根据欧拉定理及其推论，E图是不含任何奇点的图，半E图是最多含两个奇点的图。解：(a)半E图。（b）E图。（c）非半E图和E图2、试作出一个E图G(p,q),使得p与q均为奇数。能否作出一个E图G(p,q)，使得p为偶数，而q为奇数？如果是p为奇数，q为偶数呢？解：以下E图中，p与q的奇偶如下表pqG1奇数奇数G2偶数奇数G3奇数偶数3、求证：若G是E图，则G的每个块也是E图。分析：一个图如果含有E回路，则该图是E图；另一方面一个块是G中不含割点的极大连通不可分子图，且非割点不可能属于两个或两个以上的块。这样沿G中的一条E回路遍历G的所有边时，从一个块到达另一个块时，只能经过割点才能实现。证明：设B是G的块，任取G中一条E回路C，由B中的某一点v出发，沿C前进，C只有经过G的割点才能离开B，也就是说只有经过同一个割点才能回到B中，注意到这个事实后，我们将C中属于B外的一个个闭笔回路除去，最后回到v时，我们得到的就是B上的一个E回路，所以B也是E图。4、求证：若G无奇点，则G中存在边互不重的回路，使得分析：G中无奇点，则除了孤立点后其他所有点的度至少为2，而孤立点不与任何边关联，因此在分析由边构成的回路时可以不加考虑；而如果一个图所有的顶点的度至少为2，则由第五章习题18知该图必含回路。证明：将G中孤立点去掉以后得到图G1，显然G1也是一个无奇点的E图，且2)1(G。由第五章习题18知，G1必含有回路C1；在图G1-C1中去掉孤立点，得图G2，显然G2仍然是一个无奇点的图，且2)2(G，于是G2中也必含回路C2，…如此直到Gm中有回路)(a)(b)(cmCC,,1)()()()(21mCECECEGE3G2G1GCm，且Gm-Cm全为孤立点为止，于是有：5、求证：若G有2k0个奇点，则G中存在k个边互不重的链,使得：分析：一个图的E回路去掉一条边以后，将得到一条E链。证明：设为G中的奇数度顶点，k≥1在Vi和Vi+k之间用新边ei连接，ⅰ=1，2….k,所得之图记为G*，易知G*的每个顶点均为偶数，从而G*存在E闭链C*。现从C*中删去ei（ⅰ=1，2….k），则C*被分解成k条不相交的链Qi(ⅰ=1，2….k),显然有:6、证明：如果（1）G不是2—连通图，或者（2）G是二分图X,Y,且X≠Y,则G不是H图。分析：G不是2—连通图，说明1)(G，于是1)(G或0)(G，如果0)(G，则说明G不连通，如G不连通，显然G不是H图，如1)(G则G中存在孤立点，因此有ω(G-v)≥2，由定理8.2.1G不是H图。若G是二分图X，Y，则X或Y中的任意两个顶点不邻接，因此G-X剩下的是Y中的点，这些点都是孤立点；同样G-Y剩下的是X中的点，这些点也是孤立点；即有||)(||)(XYGYXG，，如果X≠Y，则有||||)(||||)(YXYGXYXG或成立。无论哪个结论成立，根据定理8.2.1都有G不是H图。证明：若（1）成立则G不连通或者是G有割点u，若G不连通,则G不是H图，若G有割点u，取S={u},于是ω(G-u)S因此G不是H图.因此G不是H图.7、证明：若G是半H图,则对于V(G)的每一个真子集S，有:分析：图G的权与它的生成子图的连通分支数满足：，因为一个图的生成子图是在该图的基础上去掉若干边得到的，显然去掉边以后只能使该图的连通分支增加。对于图G的一条H通路C，满足任取VS,证明:设C是G的一条H通路，任取VS,易知)()()()(21mCECECEGEkQQ,,1)()()()(21kQEQEQEGEkkkVVVVV212,1,,,,,)()()()(21kQEQEQEGE.,.2SSGSXYSGXSYX）（即：）（则令）成立，不妨设若（.1)(SSG.1)(SSC')()(GG'G.1)(SSC而C-S是G-S的生成子图.8、试述H图与E图之间的关系。分析：H图是指存在一条从某个点出发经过其他顶点有且仅有一次的回路；而E图是指从某点出发通过图中所有的边一次且仅有一次的回路。从定义可看出，这两者之间没有充分或必要的关系。解：考虑如下四个图:易知G1是E图，但非H图;G2是H图，但非E图;G3既非E图，又非H图；G4既是E图，也是H图。9、作一个图，它的闭包不是完全图分析：一个p阶图的闭包是指对G中满足d(u)+d(v)≥p的顶点u,v，若uvE(G)，则将边uv加到G中，得到G+uv，如此反复加边，直到满足d(u)+d(v)≥p的所有顶点均邻接。由闭包的定义，如果一个图本身不存在任何一对顶点u,v，满足d(u)+d(v)≥p，则它的闭包就是其自身。显然可找到满足这种条件的非完全图。10、若G的任何两个顶点均由一条H通路连接着，则称G是H连通的。（2）对于p≧4，构造一个具有的H连通图G。分析：根据定理5.3.1有)(21piivdq，因此2/)(1piivdq而)()(1Gpvdpii，所以q≥p*δ(G)/2，因此如果能判断δ(G)≥3，则有下面的证明关键是判断δ(G)≥3。1G3G4G2G.1)()(SSCSG故.1)(SSG故不是完全图。，但，解：如右图GGGG.)13(21,4)1(pqpHG则连通的，且是证明：若)13(21pqG;)13(212/32/)(pPGpq证明：（1）任取w∈V(G),由于G是连通的，所以d(w)≥1。若d(w)=1,则与w邻接的顶点u与w之间不可能有一条H通路连接它们，否则因为p≥4，所以G中除了u与w外还有其他顶点，因此，如果u与w之间有一条H通路的话，这条H通路与u与w的连线就构成了一个回路，这样与d(w)=1矛盾，所以d(w)≠1；同样的道理，若d(w)=2，则与w邻接的顶点u与v之间不存在H通路。因此δ(G)≥3。从而2q=∑d(u)≥3p,即：2q≥3p,也即q≥3p/2(ⅰ)若p为奇数，于是(ⅱ)若p为偶数，则3p为偶数，于是综合以上各种情况，有：（2）(ⅰ)当p=偶数时，q=3p/2，满足条件的图如下图(a);(ⅱ)当p=奇数时，满足条件的图如下图(b);图(a)图(b));13(21pq;)13(21pq;)13(21pq,)13(21pq…………11、证明：若G是一个具有p≧2δ的连通简单图，则G有一条长度至少是2δ的通路。分析：使用反证法，假设G中没有一条长度大于或等于2δ的通路。先找到图G的一条最长通路P，设其长度为m，由假设m2δ。再在P的基础上构造一条长度为m+1的回路C，显然C中包含的顶点数小2δ，由于p≧2δ，所以图G至少还有一个顶点v不在该圈中，又由于G是连通的，所以v到C上有一条通路P’。于是P’+C的长度等于通路P的长度的通路构成了一条比P更长的通路，这与P是G的一条最长通路矛盾。从而本题可得到证明。证明：(用反证法)设是G的最长通路,其长度为m，假设m2δ。由P是G的最长通路，则V1,Vm+1只能与P中的顶点相邻，注意到G是简单图分析：由定理8.2.4，如果p（≥3）阶简单图G的各顶点度数序列下面的证明就是利用这个定理来判断当mp/2时，dm满足dmm。从而G是H图。图。是）则（为奇数，还有若均有证明：若对任何的度序列为：阶简单图、设）（HGpdpmdpmmdddGppmp121,2/)1(1,.)3(1212121图。是知，从而，由定理，，也即即于是，则若则由题设有若为奇数，则）若（HGmpdmppdpddpppppmppmbmdpmapmpmpmppmpm4.2.81)1(21)1(21212122121)(,,21)(212)1(21图。为知再由定理由题设有即），则必有：为偶数（若证明：对任何正整数HGmdpmpppmpppmm4.2.8,,2/)1(1,21221213)1(,2121mVVVP。）（，）（令11111})({)},({mimiiivdTvdSGEvvvTGEvvvS。即事实上，于是因此，由定义知：TSTSTSTSTSTSTSTSmTSTSvm,022,,2,1故结论成立。的假设矛盾！此与且：是有通路），（连接。不妨设外的通路与连通可知，有一条由）。（外至少还有一个顶点所以，因：的回路中的长为从而有设PPPvvvvvvvvvvPmjGEvvCPGGVvCmpvvvvvvvCmGTSviimmijjjimmii,..11,21,2.1,11111100011121图。是，则或有，而且对任何HGmpdmdpmdddmpmp,2/2113、在图8-8中，如果分别去掉v3，v4和v5，则相应得到的旅行推销员问题的解分别取什么下界估计值？分析：利用Kruskal算法可给出一个关于旅行推销员问题的的下界估计式：任选赋权完全图Kn的一个顶点v，用Kruskal算法求出Kn-v的最优树T，设C是最优的H回路，于是有C-v也是Kn-v的一个生成树，因此有：w(T)≤w(C-v)设e1和e2是Kn中与v关联的边中权最小的两条边，于是：w(T)+w(e1)+w(e2)≤w(C)上式左边的表达式即是w(C)的下界估计式。解：（1）去掉v3后的最优数T3的权为w(T3)=5+5+1+7=18,而与v3关联的5条边中权最小的两条之权为w(e1)=8,w(e2)=9,因此下界估计值为w(C3)=18+8+9=35,(2)去掉v4后，仿上有w(T4)=20,w(C4)=20+7+8=35;（3）去掉v5后,有w(T5)=26,w(C5)=26+1+5=32.14、设G是一种赋权完全图，其中对任意x,y,z∈V(G),都满足：证明：G中最优H回路最多具有权其中T是G中的一棵最优树。分析：H回路是指从图中某点出发，经过图中每个顶点有且仅有一次，最后回到出发点的一条回路。由于G是一种赋权完全图，所以从任意顶点出发包括了G的其他所有顶点有且仅有一次再回到原点的回路都构成了G的一条H回路'C，且最优H回路C的权满足。因此只需证明G中存在一条H回路'C，其权即可，因此证明本题的关键是找到满足这个结论的H回路'C。证明：设T是G中的一棵最优树，将T的每边加倍得到图'T，则'T的每个顶点的度数均为偶数。所以'T有一欧拉回路Q，设),(121vvvvQn，，，，(n≥|v(G)|)，Q中某些顶点可能有重复，且。在Q中，从v3开始，凡前面出现过的顶点全部删去，得到G的|v(G)|个顶点的一个排列π。由于G是完全的，所以π可以看作G中的一个H回路。在π中任意边(u,v)，在T中对应存在唯一的(u,v)-通路P，由权的三角不等式有。由于将π中的边(u,v)用T中的P来代替时，就得到Q，因而。故G中的最优H回路C的权）（）（）（xzyzxy,2）（T)(2TQ）（)(,Pvu）（)(2)(TQ）（)(2)(TC）（')(CC）（)(2'TC）（