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

习题四：

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条边，证明:若 ,则 是 图。 证明: G是H图。

若不然，因为G是无向简单图，则 ,由定理1：若G是 的非单图，则G度弱于某个 .于是有：

E(G)?E(Cm,n)?12?m?(n?2m)(n?m?1)?m(m?1)???2

?n?1?1???1?(m?1)(m?2)?(m?1)(n?2m?1)?2?2??n?1?????1.?2?这与条件矛盾！所以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):

E(G)?E(Q1)E(Q2)E(Qk)

10.证明：若：

（1） 不是二连通图，或者

（2） 是具有二分类 的偶图，这里 , 则 是非Hamilton图。

证明：（1） 不是二连通图，则 不连通或者存在割点 ,有 ,由于课本上的相关定理：若 是Hamilton图，则对于 （ ）的任意非空顶点集 ，有： ,则该定理的逆否命题也成立，所以可以得出：若 不是二连通图，则 是非Hamilton图

(2)因为 是具有二分类 的偶图，又因为 ，在这里假设 ,则有 ,也就是说：对于 （ ）的非空顶点集 ，有： 成立，则可以得出则 是非Hamilton图。

11.证明：若 有Hamilton路，则对于V的每个真子集S，有 .

证明：G是H图，设C是G的H圈。则对V(G)的任意非空子集S, 容易知道:

?(C?S)?S

所以，有：?(G?S)??(C?S)?S ,则必然有： .

12. 设G是度序列为(d1,d2,…,dn)的非平凡单图，且d1≦d2≦…≦dn。证明：若G不存在小于(n+1)/2的正整数m，使得：dm

证明：在G之外加上一个新点v,把它和G的其余各点连接得图G1

G1的度序列为： (d1+1,d2+1,…,dn+1, n) ，由条件：不存在小于(n+1)/2的正整数m,使得dm+1≦m,且dn-m+1+1

15. 写出下列问题的一个好算法： (1) 构作一个图的闭包；

(2) 若某图的闭包是完全图，求该图的H圈。 解：(1) 构作一个图的闭包： 根据图的闭包定义，构作一个图的闭包，可以通过不断在度和大于等于n的非邻接顶点对间添边得到。据此设计算法如下： 图的闭包算法： 1) 令 =G ,k=0;

2) 在 中求顶点 与 ,使得：

dGk(u0)?dGk(v0)?maxdGk(u)?dGk(v)uv?E(Gk)

??3) 如果 dGk(u0)?dGk(v0)?n 则转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)次比较运算。所以，总运算量为：

1?1?n(n?1)?2?n(n?1)?m(G)??O(n2) 2?2?所以，上面的闭包算法是好算法。

(2) 若某图的闭包是完全图，求该图的H圈。

方法：采用边交换技术把闭包中的一个H圈逐步转化为G的一个H圈。 该方法是基于如下一个事实：

在闭包算法中， , 与 在 中不邻接，且度和大于等于n. 如果在 中有H圈 如下：

Ck?1?(u0,v0,v1,...,vn?2,u0)

我们有如下断言：

在Ck?1上，?vi,vi?1,使得u0vi,v0vi?1?E(Gk)

若不然，设 那么在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),令：

Ck?1?Ck??u0v0,uv???uu0,vv0?

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)!! 同样的推导方法可归纳出K n, n的不同完美匹配个数为：n!

2. 证明树至多存在一个完美匹配。

证明：若不然，设M1与M2是树T的两个不同的完美匹配，那么M1ΔM2≠Φ,容易知道：T[M1ΔM2]每个非空部分顶点度数为2，即它存在圈，于是推出T中有圈，矛盾。

7.将 表示为四个生成圈之和。

证明：K4n+1= K 2(2n)+1 , 所以，可以分解为2n个边不重的2因子之和。而 。 所以 可以表示为四个边不重的2因子之和，对于每个分解出的因子的路径为：

,

则 的四条路径为：

, , , ,

则生成圈 是 与 的两个端点连线生成的。所以可以将 表示为四个生成圈之和。

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= K 2(2n)+1 , 所以，可以分解为2n个边不重的2因子之和。而任意2个2因子可以并成一个4因子。所以，共可以并成n个4因子。即K4n+1可以分解为n个4因子的和。所以：对n≥1,K4n+1有一个4因子分解

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= K 2(2n)+1 , 所以，可以分解为2n个边不重的2因子之和。而任意2个2因子可以并成一个4因子。所以，共可以并成n个4因子。即K4n+1可以分解为n个4因子的和。所以：对n≥1,K4n+1有一个4因子分解

本文来源：https://www.bwwdw.com/article/n3a7.html