电子科技大学-图论第二次作业-杨春.doc

《电子科技大学-图论第二次作业-杨春.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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闭迹的图.4.设n阶无向简单图G有m条边，证明:若m≥n-12+2,则G是Hamilt

2、on图。证明:G是H图。若不然，因为G是无向简单图，则n≥3,由定理1：若G是n≥3的非单图，则G度弱于某个Cm,n.于是有：这与条件矛盾！所以G是H图。8.证明：若G有2k≥0个奇点，则存在k条边不重的迹Q1,Q2…Qk,使得EG=EQ1∪EQ2∪EQ3∪⋯∪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（

3、1≦i≦k):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，在这里假设XX,也就是说：对于v（G）的非空顶点集S，有：w(G-S)>S成立，则可以得出则G

4、是非Hamilton图。11.证明：若G有Hamilton路，则对于V的每个真子集S，有wG-S≤S+1.证明：G是H图，设C是G的H圈。则对V(G)的任意非空子集S,容易知道:所以，有：,则必然有：wG-S≤S+1.12.设G是度序列为(d1,d2,…,dn)的非平凡单图，且d1≦d2≦…≦dn。证明：若G不存在小于(n+1)/2的正整数m，使得：dm

5、dm+1≦m,且dn-m+1+1

6、，要做如下运算:(a)找出所有不邻接点对----需要n(n-1)/2次比较运算；(b)计算不邻接点对度和----需要做n(n-1)/2-m(G)次加法运算;(c),选出度和最大的不邻接点对----需要n(n-1)/2-m(G)次比较运算。所以，总运算量为：所以，上面的闭包算法是好算法。(2)若某图的闭包是完全图，求该图的H圈。方法：采用边交换技术把闭包中的一个H圈逐步转化为G的一个H圈。该方法是基于如下一个事实：在闭包算法中，Gk+1=Gk+u0v0,u0与v0在Gk中不邻接，且度和大于等于n.如果在Gk+1中有H圈Ck+1如下：我们有如下断言：若不然，设

7、dGku0=r那么在Gk中，至少有r个顶点与v0不邻接，则dGkv0≦(n-1)-r

8、k上，且有：uu0,vv0∈E(Gk-1),令：4)若k=1,转5