图论作业2.docx

习题四：3.（1）画一个有Euler 闭迹和Hamilton圈的图；（2）画一个有Euler闭迹但没有Hamilton圈的图；（3）画一个有Hamilton圈但没有Euler闭迹的图；（4）画一个即没有Hamilton圈也没有Euler闭迹的图；解：找到的图如下：一个有Euler 闭迹和Hamilton圈的图；一个有Euler闭迹但没有Hamilton圈的图；(3)一个有Hamilton圈但没有Euler闭迹的图; (4)一个即没有Hamilton圈也没有Euler闭迹的图.4.设n阶无向简单图G有m条边，证明:若,则是图。证明: G是H图。若不然，因为G是无向简单图，则,由定理1：若G是的非单图，则G度弱于某个.于是有：这与条件矛盾！所以G是H图。8.证明：若G有个奇点，则存在条边不重的迹,使得.证明：不失一般性，只就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):10.证明：若：（1）不是二连通图，或者（2）是具有二分类的偶图，这里,则是非Hamilton图。证明：（1）不是二连通图，则不连通或者存在割点,有,由于课本上的相关定理：若是Hamilton图，则对于的任意非空顶点集，有：,则该定理的逆否命题也成立，所以可以得出：若不是二连通图，则是非Hamilton图(2)因为是具有二分类的偶图，又因为，在这里假设,则有,也就是说：对于的非空顶点集，有：成立，则可以得出则是非Hamilton图。11.证明：若有Hamilton路，则对于V的每个真子集S，有.证明：G是H图，设C是G的H圈。则对V(G)的任意非空子集S, 容易知道:所以，有：,则必然有：.12.设G是度序列为(d1,d2,…,dn)的非平凡单图，且d1≦d2≦…≦dn。证明：若G不存在小于(n+1)/2的正整数m，使得：dmm且dn-m+1n-m,则G有H路。证明：在G之外加上一个新点v,把它和G的其余各点连接得图G1 G1的度序列为：(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的非邻接顶点对间添边得到。据此设计算法如下：图的闭包算法：令=G ,k=0;在中求顶点与,使得：3) 如果则转4);否则，停止，此时得到G的闭包；4) 令,,转2).复杂性分析：在第k次循环里，找到点u0与v0，要做如下运算: (a) 找出所有不邻接点对----需要n(n-1)/2次比较运算；(b) 计算不邻接点对度和----需要做n(n-1)/2-m(G)次加法运算;(c ),选出度和最大的不邻接点对----需要n(n-1)/2-m(G)次比较运算。所以，总运算量为：所以，上面的闭包算法是好算法。(2) 若某图的闭包是完全图，求该图的H圈。方法：采用边交换技术把闭包中的一个H圈逐步转化为G的一个H圈。该方法是基于如下一个事实：在闭包算法中，, 与在中不邻接，且度和大于等于n.如果在中有H圈如下：我们有如下断言：若不然，设那么在Gk中，至少有r个顶点与v0不邻接，则≦(n-1)-r n-r，这样与u0，v0在Gk中度和大于等于n矛盾！上面结论表明：可以从Ck+1中去掉而得到新的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),令： 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正则偶图。事实上，