《电子科技大学-图论第二次作业-杨春》由会员分享，可在线阅读，更多相关《电子科技大学-图论第二次作业-杨春（6页珍藏版）》请在金锄头文库上搜索。
1、习题四：习题四：3. 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. 4.设 n 阶无向简单图
2、G 有 m 条边，证明:若证明证明: G 是 H 图。若不然，因为 G 是无向简单图，则度弱于某个.于是有：,由定理 1：若 G 是的非单图，则 G,则 是图。E(G) E(Cm,n) 12m (n2m)(nm1)m(m1)2n111(m1)(m2)(m1)(n2m1)22n11.2这与条件矛盾！所以 G 是 H 图。8. 8.证明：若 G 有个奇点，则存在条边不重的迹.,使得证明：证明：不失一般性，只就 G 是连通图进行证明。设 G=(n, m)是连通图。令 vl，v2，,vk,vk+1,v2k是 G 的所有奇度点。在 vi与 vi+k间连新边 ei得图 G*（1ik).则 G*是欧拉图，因
3、此，由 Fleury 算法得欧拉环游 C.在 C 中删去 ei（1ik).得k 条边不重的迹 Qi（1ik):E(G) E(Q1)U E(Q2)ULU E(Qk)10.10.证明：若：（1） 不是二连通图，或者（2） 是具有二分类则 是非 Hamilton 图。证明：证明： （1） 不是二连通图，则 不连通或者存在割点 ,有上的相关定理：若是 Hamilton 图，则对于,由于课本的偶图，这里,的任意非空顶点集，有：,则该定理的逆否命题也成立，所以可以得出：若 不是二连通图，则 是非 Hamilton 图(2)因为是具有二分类有的偶图，又因为，在这里假设,则成,也就是说： 对于的非空顶点集 ，
4、 有：立，则可以得出则 是非 Hamilton 图。11.11.证明：若 有 Hamilton 路，则对于 V 的每个真子集 S，有.证明：证明：G 是 H 图，设 C 是 G 的 H 圈。则对 V(G)的任意非空子集 S, 容易知道:(CS) S所以，有：(GS)(CS) S,则必然有：.12.12. 设 G 是度序列为(d1,d2,dn)的非平凡单图，且 d1d2dn。证明：若 G不存在小于(n+1)/2的正整数 m，使得：dmm 且 dn-m+1n-m,则 G 有 H 路。证明：证明：在 G 之外加上一个新点 v,把它和 G 的其余各点连接得图 G1G1的度序列为： (d1+1,d2+1
5、,dn+1, n) ，由条件：不存在小于(n+1)/2的正整数m,使得 dm+1m,且 dn-m+1+1n-m+1=(n+1)-m。于是由度序列判定定理知： G1是 H图，得 G 有 H 路。15.15. 写出下列问题的一个好算法：(1) 构作一个图的闭包；(2) 若某图的闭包是完全图，求该图的 H 圈。解：解：(1) 构作一个图的闭包：根据图的闭包定义， 构作一个图的闭包， 可以通过不断在度和大于等于 n 的非邻接顶点对间添边得到。据此设计算法如下：图的闭包算法：1) 令2) 在=G ,k=0;中求顶点与,使得：dGk(u0)dGk(v0) max dGk(u)dGk(v) uvE(Gk)3
6、) 如果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 1n(n1)2n(n1)m(G) O(n2)22所以，上面的闭包算法是好算法。(2) 若某图的闭包是完全图，求该图的 H 圈。方法：采用边交换技术把闭包中的一个 H 圈逐步转化为 G
7、 的一个 H 圈。该方法是基于如下一个事实：在闭包算法中，如果在中有 H 圈如下：Ck1 (u0,v0,v1,., vn2,u0),与在中不邻接，且度和大于等于 n.我们有如下断言：在Ck1上，vi,vi1,使得u0vi,v0vi1E(Gk)若不然，设那么在 Gk中，至少有 r 个顶点与 v0不邻接，则(n-1)-r n-r，这样与 u0，v0在 Gk中度和大于等于 n 矛盾！上面结论表明：可以从Ck+1中去掉而得到新的 H 圈，实现H 圈的边交换。由此，我们设计算法如下：1)在闭包构造中，将加入的边依加入次序记为 ei(1iN),这里，N=n(n-1)/2-m(G).在 GN中任意取出一个
8、H 圈 CN,令 k=N;2) 若 ek不在 Ck中，令 Gk-1=Gk-ek, Ck-1=Ck; 否则转 3);3) 设 ek=u0v0Ck, 令 Gk-1=Gk-ek; 求 Ck中两个相邻点 u 与 v 使得 u0,v0,u,v 依序排列在 Ck上，且有：uu0,vv0E(Gk-1),令：Ck1Cku0v0,uvuu0,vv04) 若 k=1,转 5)；否则，令 k=k-1,转 2);5) 停止。C0为 G 的 H 圈。复杂性分析：一共进行 N 次循环，每次循环运算量主要在 3),找满足要求的邻接顶点 u 与v,至多 n-3 次判断。所以总运算量：N(n-3),属于好算法。习题五：1. 1
9、. （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 方体中找
10、出完美匹配。设 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. 2. 证明树至多存在一
11、个完美匹配。证明证明：若不然，设 M1与 M2是树 T 的两个不同的完美匹配，那么 M1M2,容易知道： TM1M2每个非空部分顶点度数为 2， 即它存在圈， 于是推出 T 中有圈，矛盾。7. 7.将表示为四个生成圈之和。2(2n)+1证明证明：K4n+1= K。所以, 所以，可以分解为2n 个边不重的2 因子之和。而可以表示为四个边不重的 2 因子之和，对于每个分解出的因子的路径为：,则的四条路径为：,则生成圈是与 的两个端点连线生成的。所以可以将表示为四个生成圈之和。10.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=C1F1。显然 H 是 G 的一个 3 因子。19.19. 证明：对 n1,K4n+1有一个 4 因子分解。证明：证明：K4n+1= K2(2n)+1, 所以，可以分解为 2n 个边不重的 2 因子之和。而任意 2个 2 因子可以并成一个 4 因子。所以，共可以并成 n 个 4 因子。即 K4n+1可以分解为 n 个 4 因子的和。所以：对 n1,K4n+1有一个 4 因子分解
