离散数学习题答案-ch10-ch13-2015

习题十1、设G是一个（n,m）简单图；证明：m≤C(n,2)等号成立，当且仅当G是完全图证明：此题有两个内容，第一方面证明简单图满足m≤C(n,2)，第二证明，m=C(n,2)当且仅当G是完全图(1):因为在简单无向图中，每个结点的最大度数为n-1，所以图的总度数的上限为n(n-1),所以边的上限为n(n-1)/2，因此任意一个简单无像图G，其边数满足：m≤n(n-1)/2=C(n,2)(2)：m=C(n,2)⇒G是完全图因为，当m=C(n,2)时，全图的总度数为n(n-1),因此其平均点度为(n-1)，因为n阶简单无向图中点度的最大值为（n-1）,所以此时每个点的度数都相同并为（n-1）,根据完全图的定义，此图为完全图G是完全图⇒m=C(n,2)当G为完全图时，既每个结点都和其他结点相邻，所以全图的总边数m=n(n-1)/2=C(n,2)4、证明：在（n,m）图中δ≤2m/n≤Δ证明：因为2m/n代表简单无向图的平均点度值，所以平均值大于等于最小值，小于等于最大值，结论成立6、设G是（n,m）简单二部图，证明：m≤n2/4证明：设G的两个顶点集合中顶点个数分别为n1,n2，并有n=n1+n2(1式)；同时，在简单二部图中，当其为完全二部图是，其边数最大，及max(m)=n1×n2(2式)；联立（1）（2）式，通过高等数学的知识，当n1=n2=1/2n时，max(m)取得最大值n2/4，所以一般（n,m）简单二部图，其边数小于等于此最大值既m≤n2/49、如果G≌G’，称G是自补图；确定一个图为自补图的最低条件：画出一个自补图解：因为G和自己的补图同构，那么G和G’应该有相等条数的边，所以m=m’，又因为m+m’=n(n-1)/2，所以G的边的条数必须满足m=n(n-1)/4.因此图G的阶数或阶数减一必需是4的倍数，这就是最低条件。图略（4阶或5阶这样的图都容易画出）10、判断图10-29中的两个图是否同构，并说明理由答：这两个图不同构，因为这两个图中，都有唯一的3度点，因此在同构映射中一定相互对应，但一个图中的3度点连接两个一度点，而在另一个图中其3度点只连接了一个一度点，不能相互映射。因此不同构15、如果u和v是图G中仅有的两个奇数度结点，证明u和v必是连通的证明：假设u,v分别在图G的两个分中G1,G2中，那么G1，G2各自的总结点度数就是奇数，与握手定理矛盾。因此，u,v必在一个连通分支中，所以是连通的16、证明：G是二部图当且仅当G的回路都是偶长回路（非平凡图，n1）证明：（1）先证明在二部图中，所有奇长道路的两个端点必定分别在两个顶点集合中使用归纳方法：A）当道路长度L(P)=1时，就是图G的边和其两个端点，根据二部图的定义，两个端点分别在两个顶点集合中B）假设道路长度L(P)=2n+1(n0)时结论成立，及P=V1V2….V2n+2,其中V1,V2n+2分别属于两个顶点集合C)当L(P)=2(n+1)+1（n0）时，P=V1V2….V2n+2V2n+3V2n+4；当我们删除此道路的最后两个结点，道路长度变为L(P’)=2n+1，根据(B)的假设，那么V1,V2n+2就分别在两个顶点集合。现在把V2n+3加入到道路中，因为V2n+3是V2n+2的邻结点，所以V2n+3在V2n+2的对集中，既和V1在一个顶点集合中；同理V2n+4就在V1的对集中，也就是V1,V2n+4在不同的顶点集合中综上所述，（1）结论成立（2）G是二部图⇒G的回路都是偶长的设C是G中的任意回路，那么C=V1…..V1，假设L(C)为奇数，那么根据（1）的结论，V1,V1应该在不同的集合中，矛盾；所以L(C)必为偶数G的回路都是偶长的⇒G是二部图首先，按如下方式对G的连通分支进行着色，任选一个结点，着红色，然后将其所有邻结点着为黑色，（将红色结点标记），然后逐一对黑色结点的邻结点着为红色并标记黑结点，如此往复，值到全部结点着色标记完成，或遇到已着色的结点被重新着色为相反的颜色（此图有奇长度回路）。下面说明，如果是偶长的，那么就是二部图：证明：从染色的顺序看，红点到黑点之间的距离为单数，红点到红点的距离为双数，并且相同颜色的点不会相邻。所以可以将图的顶点集合分成两个集合，每个集合的点的颜色一致。根据二部图的定义，这是一个二部图。如果着色过程中出现已着色点被重新着色成相反颜色，例如：v1是开始的红点，如果现在有点为u1点为黑色，并且开始对他的邻结点进行早色，我们发现w1是u1的邻结点，但已经被着色成黑色，那么，我们就找到得到v1到u1的距离为单数的道路p1，v1到w1距离为单数的道路p2，如果p1+u1w1+p1，就形成一个回路，此回路为奇数，与前提矛盾。所以不可能出现这种情况。（注:对其他分支重复这种方法，如果遇到孤立结点，则交替着红色和黑色）19、设G=(V,E)是点度均为偶数的连通图，证明：对任何uV,ω(G-u)≤d(u)/2证明：因为G的点度都为偶数，因此G-u最多形成d(u)个奇数度点，而奇数度点必须成对出现在连通分支中，所以ω(G-u)的最大值为d(u)/2，所以ω(G-u)≤d(u)/223、证明：在具有n(n≥2)个结点的简单无向图G中，至少有两个结点度数相同证明：在n个结点的简单无向图中，每个结点的可能度数为0、1、2…n-1，共n种，但是如果有结点度为0，那么就不存在有结点度数为n-1；同理，有结点度数为n-1，那就不存在孤立结点，所以可能的点度只能有n-1种，但有n个结点，所以必有两个结点度数要相同30、略习题十一1、设一个树中度为k的结点数是nk(2≤k),求它的叶的数目解：设T中叶结点数目为t，那么根据握手定理，及数的点边关系可以得到：n=t+n2+n3+…+nk(1)Σd(v)=2m=t+2n2+3n3+…+knk=2(n-1)(2)所以：t+2n2+3n3+…+knk=2（t+n2+n3+…+nk）-2t=n3+2n4+…+(k-2)nk+22、证明：树T中最长简单道路的起点和终点必都是T的叶证明:a)首先证明在T中的任意最长道路P中，其起点u和终点v的所有邻结点必然在P中，否则此道路可以变长，与最长条件矛盾b)假设在T中存在最长道路P,其起点u或终点v不是叶结点(假设是u)，那么d(u)1，及u至少有两个邻结点u1,u2，他们都将出现在道路中，既P=uu1…u2…v，因为u2是u的邻结点，所以在T中就存在C=uu1..u2u的简单回路，与树的基本性质矛盾，所以u,v必是叶结点10、设e是连通图G的一条边，证明：e是G的割边当且仅当e含于G的每个生成树中证明：a)e是G的割边⇒e含于G的每个生成树中假设e不包含在G的生成树T’中，那么删除e边后，T’依然包含在G-{e}中，因为T’连通，所以G-{e}连通，与e是割边矛盾，所以e必包含在G的任何生成树中b)e含于G的每个生成树中⇒e是G的割边假设e不是割边，那么G-{e}依然连通，所以存在生成数T’，当然T’也是G的生成树，但e不包含在T’中，与题设矛盾，因此e是G的割边12、略23、略（参考课堂ppt）讲解习题十二1、证明：图12-7中的图都是平面图略（只需要画处其平面图的形式即可）（a多一条边，c多了一条边）3、设G是阶数不小于11的图，证明：G或G’(代表G的补图)中至少有一个是非平面图证明：假设G和G’都是平面图，因为m(G)+m(G’)=n(n-1)/2,因此至少有一图的边至少为n(n-1)/4，根据平面图边与点的关系，n(n-1)/4≤3n–6，得到n2-13n+24≤0,因此n≤10,与题设矛盾；因此必有一图为非平面图5、证明：少于30条边的简单平面图至少有一个顶点的度不大于4证明：（反证）假设少于30条边的简单平面图所有的顶点的度都大于等于5，那么根据握手定理和平面图的性质有：5n≤2m（1）m≤3n–6（2）⇒5n≤6n–12⇒n≥12根据（1）式，60≤2m，既m≥30与题设矛盾，因此至少有一个顶点的度不大于47、证明：对K3,3的任意一条边e，K3,3-e是平面图；同样，对K5的任何边e，K5-e也是平面图证明：因为K3,3的任意一条边ei,ej，K3,3-ei,K3,3-ej都是同构的，而根据题1（a）的结论，我们可以平面嵌入它，因此K3,3-e是平面图；同理，K5-e也是平面图9、如果一平面图与其对偶图同构，则称这个平面图为自对偶图，推导自对偶图必须满足的结点数n与边数m的关系，并找出一些自对偶图解：如果一个图是平面图，那么满足欧拉公式：n–m+f=2（1）其对偶图也是平面图，因此也应满足欧拉公式：n*-m*+f*=2(2)因为对偶关系，因此：n=f*f=n*又因为此二图同构，因此n=n*,m=m*所以：n=f,并且2n–m=2据此可以找到一些自对偶图：K1,G(2,2)–有两种图像，K4习题十三1、构造(n,m)欧拉图，使其满足条件：（1）m,n奇偶性相同；（2）m,n奇偶性相反答：略2、设G=（V，E）是一个具有2k(k0)个奇数度结点的连通图。证明：G中必存在k条边不相重的简单道路P1,P2,…,Pk,使得E=E(P1)E(P2)…E(Pk)证明：把2k个奇数度结点分成两两一组的k组，然后每组结点新加一条边，所得图为欧拉图，故存在欧拉回路C；然后去掉欧拉回路C中的k条新加入的边，得到k条互无重复边的道路P1,P2,…,Pk,即为所求5、在图13-10中求中国邮递员问题的解解：如上图标号：图中有4个奇数度结点v1,v6,v9,v3,求两两之间最短长度：Pv1v6=3(v1v6),Pv1v9=7(v1v2v3v4v9),Pv1v3=4(v1v2v3),Pv6v9=7(v6v7v8v9),Pv3v6=6(v3v8v7v6),Pv3v9=3(v3v4v9),Pv1v6和Pv3v9满足最小性要求，复制v1v6和v3v4v9的边，图中欧拉回路即为所求解6、设G是有两个奇数度点的连通图，设计一个构造G的欧拉道路的算法v9v6v3v1v2v4v5v7v8v1022111133v1134415562解：此算法只要在书中欧拉回路的算法中，添加起点为奇数结点即可，详细描述略9、证明：凡有割点的图都不是哈密顿图证明：假设e为图G的割点，根据割点的定义，ω(G-e)1，因此不满足哈图的必要条件；所以不是哈图13、假定在n(2)个人的团体中，任何2人合起来认识其余的n-2个人，证明：（1）这n个人可以排成一排，使得站在中间的每个人的两旁都是自己认识的人，站在两端的人旁边各有1个认识的人（2）当n≥4时，这n个人可以围成一个圆圈，使得每个人两旁都是自己所认识的人证明：如果团体中的个人看成是结点，而人于人的关系看成是边，那么就构成一个认识与否的图，对于问题（1），就转化为此图中存在哈道路问题；问题（2），就转化为图中存在哈圈的问题，现说明如下：在此题中，任何2人合起来认识其余的n-2个人蕴含任何人最多只有一人不认识，因为如果a，不认识b和c,那么b和c就不能认识完剩下的全部人，因此此图既有d(u)≥n-2那么，任意两个结点u,v，d(u)+d(v)≥n-2+n-2，因为n2，所以d(u)+d(v)≥n-1，根据书中定理，此图存在哈道路如果n≥4，那么d(u)+d(v)≥n-2+n-2≥n，根据书中定理，此图存在哈圈