电子科大图论 第二次作业(4、5章) 答案
4页1、习题四3.(1)画一个有Euler 闭迹和Hamilton圈的图; (2)画一个有Euler 闭迹但没有Hamilton圈的图; (3)画一个有Hamilton圈但没有Euler闭迹的图;(4)画一个即没有Hamilton圈也没有Euler闭迹的图;解:找到的图如下:(1) 一个有Euler 闭迹和Hamilton圈的图;(2) 一个有Euler 闭迹但没有Hamilton圈的图;(3) 一个有Hamilton圈但没有Euler闭迹的图; (4)一个即没有Hamilton圈也没有Euler闭迹的图.7. 将G中的孤立点去掉后的图为G1,则G1也是没有奇度点的,且G1的最小度大于等于2.则G1存在一个圈S1,在G1S1中去除孤立的点,得到一个新的图G2,显然G2也没有奇度的点,且G2的最小度大于等于2.这样G2中也存在一个圈S2,这样一直下去,指导Gm中有圈Sm,且Gm-Sm都是孤立的点。这样E(G)=E(G1)并E(G2)并E(Gm).命题得证。10证明:若:(1)G不是二连通图,或者(2)G是具有二分类X,Y的偶图,这里XY,则G是非Hamilton图。证明:(1)G不是二连通图,则
2、G不连通或者存在割点v,有w(G-v)2,由于课本上的相关定理:若G是Hamilton图,则对于v(G)的任意非空顶点集S,有:w(G-S)S,则该定理的逆否命题也成立,所以可以得出:若G不是二连通图,则G是非Hamilton图(2)因为 G是具有二分类X,Y的偶图,又因为XY,在这里假设XX,也就是说:对于v(G)的非空顶点集S,有:w(G-S)S成立,则可以得出则G是非Hamilton图。习题五1. (1)证明:每个k方体都有完美匹配(k大于等于2)(2) 求K2n和Kn,n中不同的完美匹配的个数。证明一:证明每个k方体都是k正则偶图。事实上,由k方体的构造:k方体有2k个顶点,每个顶点可以用长度为k的二进制码来表示,两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。如果我们划分k方体的2k个顶点,把坐标之和为偶数的顶点归入X,否则归入Y。显然,X中顶点互不邻接,Y中顶点也如此。所以k方体是偶图。又不难知道k方体的每个顶点度数为k,所以k方体是k正则偶图。由推论:k方体存在完美匹配。 证明二:直接在k方体中找出完美匹配。 设k方体顶点二进制码为(x1 ,x2,xk),我们
3、取(x1 ,x2,xk-1,0),和(x1 ,x2,xk-1,1) 之间的全体边所成之集为M.显然,M中的边均不相邻接,所以作成k方体的匹配,又容易知道:|M|=2k-1.所以M是完美匹配。 (2) 我们用归纳法求K2n和Kn,n中不同的完美匹配的个数。 K2n的任意一个顶点有2n-1种不同的方法被匹配。所以K2n的不同完美匹配个数等于(2n-1)K2n-2,如此推下去,可以归纳出K2n的不同完美匹配个数为:(2n-1)! 同样的推导方法可归纳出K n, n的不同完美匹配个数为:n! 6证明:K2n的1-因子分解的数目为(2n)!/(2n*n!)。因为K2n的不同完美匹配的个数为(2n-1)!。所以,K2n的一因子分解数目为(2n-1)!个,即2n)!/(2n*n!),命题得证。7将K9表示为四个生成圈之和。证明:K4n+1= K 2(2n)+1 , 所以,可以分解为2n个边不重的2因子之和。而K9=K24+1。所以K9可以表示为四个边不重的2因子之和,对于每个分解出的因子的路径为:Pi=vivi-1vi+1vi-2vi+2vi-3vi-nvi+n,则K9的四条路径为:P1=v1v8v2v7v3v6v4v5,P2=v2v1v3v8v4v7v5v6,P3=v3v2v4v1v5v8v6v7,P4=v4v3v5v2v6v1v7v8,则生成圈Hi是V2n+1与Pi的两个端点连线生成的。所以可以将K9表示为四个生成圈之和。13.所以最小的权值之和为30
《电子科大图论 第二次作业(4、5章) 答案》由会员jiups****uk12分享,可在线阅读,更多相关《电子科大图论 第二次作业(4、5章) 答案》请在金锄头文库上搜索。
建立安全生产长效机制-共创和谐平安输气管道
土石方爆破工程设计方案
康师傅百货商场制度汇编之退换货管理办法
庙头中学2012年中考百日誓师大会学生代表发言稿
围堰拆除爆破工程
华能洱源马鞍山风电场工程土石方爆破管理制度
国资委:全面开展管理提升活动-为培育世界一流企业奠定坚实基础
《专业技术人员职业发展与规划》电子书
应收票据审计方案
建筑给水排水与采暖工程质量验收用表
广播电视管理条例行政处罚裁量标准
广东电力系统调度运行操作管理规定
建筑给排水工程名词解释
幼儿园小班安全健康活动教案:宝宝误食后的急救
建业集团房屋建筑工程交房标准内容技术交底
建筑心理学论文(1)
康师傅百货商场制度汇编之工服管理程序009
建筑工程专业一级建造师继续教育培训结业报告20
廉洁风险防控回头看工作汇报材料
平台工作人员服务规范
2024-04-24 10页
2024-04-24 10页
2024-04-24 25页
2024-04-24 10页
2024-04-23 4页
2024-04-23 10页
2024-04-23 19页
2024-04-23 10页
2024-04-23 16页
2024-04-23 5页