图论作业2

习题四：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闭迹的图.4.设n阶无向简单图G有m条边，证明:若m≥(n−12)+2,则G是Hamilton图。证明:G是H图。若不然，因为G是无向简单图，则n≥3,由定理1：若G是n≥3的非单图，则G度弱于某个Cm,n.于是有：2,1()()(2)(1)(1)2111(1)(2)(1)(21)2211.2mnEGECmnmnmmmnmmmnmn这与条件矛盾！所以G是H图。8.证明：若G有2k≥0个奇点，则存在k条边不重的迹Q1,Q2…Qk,使得E(G)=E(Q1)∪E(Q2)∪E(Q3)∪⋯∪E(Qk).证明：不失一般性，只就G是连通图进行证明。设G=(n,m)是连通图。令vl，v2，…,vk,vk+1,…,v2k是G的所有奇度点。在vi与vi+k间连新边ei得图G*（1≦i≦k).则G*是欧拉图，因此，由Fleury算法得欧拉环游C.在C中删去ei（1≦i≦k).得k条边不重的迹Qi（1≦i≦k):12()()()()kEGEQEQEQ10.证明：若：（1）G不是二连通图，或者（2）G是具有二分类(X,Y)的偶图，这里|X|≠|Y|,则G是非Hamilton图。证明：（1）G不是二连通图，则G不连通或者存在割点v,有w(G−v)≥2,由于课本上的相关定理：若G是Hamilton图，则对于v（G）的任意非空顶点集S，有：w(G−S)≤|S|,则该定理的逆否命题也成立，所以可以得出：若G不是二连通图，则G是非Hamilton图(2)因为G是具有二分类(X,Y)的偶图，又因为|X|≠|Y|，在这里假设|X||Y|,则有w(G−X)=|Y||X|,也就是说：对于v（G）的非空顶点集S，有：w(G−S)|S|成立，则可以得出则G是非Hamilton图。11.证明：若G有Hamilton路，则对于V的每个真子集S，有w(G−S)≤|S|+1.证明：G是H图，设C是G的H圈。则对V(G)的任意非空子集S,容易知道:()CSS所以，有：()()GSCSS,则必然有：w(G−S)≤|S|+1.12.设G是度序列为(d1,d2,…,dn)的非平凡单图，且d1≦d2≦…≦dn。证明：若G不存在小于(n+1)/2的正整数m，使得：dmm且dn-m+1n-m,则G有H路。证明：在G之外加上一个新点v,把它和G的其余各点连接得图G1G1的度序列为：(d1+1,d2+1,…,dn+1,n)，由条件：不存在小于(n+1)/2的正整数m,使得dm+1≦m,且dn-m+1+1n-m+1=(n+1)-m。于是由度序列判定定理知：G1是H图，得G有H路。15.写出下列问题的一个好算法：(1)构作一个图的闭包；(2)若某图的闭包是完全图，求该图的H圈。解：(1)构作一个图的闭包：根据图的闭包定义，构作一个图的闭包，可以通过不断在度和大于等于n的非邻接顶点对间添边得到。据此设计算法如下：图的闭包算法：1)令G0=G,k=0;2)在Gk中求顶点u0与V0,使得：00()()max()()()kkkkGGGGkdudvdudvuvEG3)如果00()()kkGGdudvn则转4);否则，停止，此时得到G的闭包；4)令Gk+1=Gk+u0v0,k=k+1,转2).复杂性分析：在第k次循环里，找到点u0与v0，要做如下运算:(a)找出所有不邻接点对----需要n(n-1)/2次比较运算；(b)计算不邻接点对度和----需要做n(n-1)/2-m(G)次加法运算;(c),选出度和最大的不邻接点对----需要n(n-1)/2-m(G)次比较运算。所以，总运算量为：211(1)2(1)()()22nnnnmGOn所以，上面的闭包算法是好算法。(2)若某图的闭包是完全图，求该图的H圈。方法：采用边交换技术把闭包中的一个H圈逐步转化为G的一个H圈。该方法是基于如下一个事实：在闭包算法中，Gk+1=Gk+u0v0,u0与v0在Gk中不邻接，且度和大于等于n.如果在Gk+1中有H圈Ck+1如下：100120(,,,...,,)knCuvvvu我们有如下断言：11001,,,()kiiiikCvvuvvvEG在上，使得若不然，设dGk(u0)=r那么在Gk中，至少有r个顶点与v0不邻接，则dGk(v0)≦(n-1)-rn-r，这样与u0，v0在Gk中度和大于等于n矛盾！上面结论表明：可以从Ck+1中去掉u0v0而得到新的H圈，实现H圈的边交换。由此，我们设计算法如下：1)在闭包构造中，将加入的边依加入次序记为ei(1≦i≦N),这里，N=n(n-1)/2-m(G).在GN中任意取出一个H圈CN,令k=N;2)若ek不在Ck中，令Gk-1=Gk-ek,Ck-1=Ck;否则转3);3)设ek=u0v0∈Ck,令Gk-1=Gk-ek;求Ck中两个相邻点u与v使得u0,v0,u,v依序排列在Ck上，且有：uu0,vv0∈E(Gk-1),令：10000,,kkCCuvuvuuvv4)若k=1,转5)；否则，令k=k-1,转2);5)停止。C0为G的H圈。复杂性分析：一共进行N次循环，每次循环运算量主要在3),找满足要求的邻接顶点u与v,至多n-3次判断。所以总运算量：N(n-3),属于好算法。习题五：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),我们取(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)!!同样的推导方法可归纳出Kn,n的不同完美匹配个数为：n!2.证明树至多存在一个完美匹配。证明：若不然，设M1与M2是树T的两个不同的完美匹配，那么M1ΔM2≠Φ,容易知道：T[M1ΔM2]每个非空部分顶点度数为2，即它存在圈，于是推出T中有圈，矛盾。7.将K9表示为四个生成圈之和。证明：K4n+1=K2(2n)+1,所以，可以分解为2n个边不重的2因子之和。而K9=K2×4+1。所以K9可以表示为四个边不重的2因子之和，对于每个分解出的因子的路径为：Pi=vivi−1vi+1vi−2vi+2vi−3…vi−nvi+n,则K9的四条路径为：P1=v1v8v2v7v3v6v4v5,P2=v2v1v3v8v4v7v5v6,P3=v3v2v4v1v5v8v6v7,P4=v4v3v5v2v6v1v7v8,则生成圈Hi是V2n+1与Pi的两个端点连线生成的。所以可以将K9表示为四个生成圈之和。10.证明：若n为偶数，且δ(G)≥n/2+1,则n阶图G有3因子。证明：因δ(G)≥n/2+1,由狄拉克定理：n阶图G有H圈C.又因n为偶数，所以C为偶圈。于是由C可得到G的两个1因子。设其中一个为F1。考虑G1=G-F1。则δ(G1)≥n/2。于是G1中有H圈C1.作H=C1∪F1。显然H是G的一个3因子。19.证明：对n≥1,K4n+1有一个4因子分解。证明：K4n+1=K2(2n)+1,所以，可以分解为2n个边不重的2因子之和。而任意2个2因子可以并成一个4因子。所以，共可以并成n个4因子。即K4n+1可以分解为n个4因子的和。所以：对n≥1,K4n+1有一个4因子分解