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

习题四： 3.（ 1）画一个有 Euler 闭迹和 Hamilton 圈的图； （2）画一个有 Euler 闭迹但没有 Hamilton 圈的图；（3）画一个有 Hamilton 圈但没有 Euler 闭迹的图； （4）画一个即没有 Hamilton 圈也没有 Euler 闭迹的图；解：找到的图如下： 一个有 Euler 闭迹和 Hamilton 圈的图； 一个有 Euler 闭迹但没有 Hamilton 圈的图； 一个有 Hamilton 圈但没有 Euler 闭迹的图 ; (4)一个即没有 Hamilton 圈也没有 Euler 闭迹的图 . 4.设 n 阶无向简单图 G 有 m 条边，证明 :若 ,则 是 图。 证明: G是 H 图。 若不然，因为 G 是无向简单图， 则 ,由定理 1：若 G 是 的非单图，则 G 度弱于某个 .于是有： E(G) E(Cm, n ) 1 m2 ( n 2m)( n m 1) m(m 1) 2 n 1 1 1)(m 2) (m 1)(n 2m 1) 2 1 (m 2 n 1 2 1. 这与条件矛盾！所以 G 是 H 图。 8.证明：若 G 有 个奇点，则存在 条边不重的迹 , 使得 . 证明：不失一般性，只就 G 是连通图进行证明。设 G=(n, m)是连通图。令 vl， ， ?,v ? ,v2k 是 G 的所有奇度点。在 v 与 v 间连新边 e 得图 G*（ 1≦ i≦k). v2k,vk+1, i i+k i 则 G*是欧拉图，因此，由 Fleury 算法得欧拉环游 C.在 C 中删去 e （ ≦ ≦ 得 i 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 ,则必然有： . 设 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,使得 d +1≦ m,且 d +1n-m+1=(n+1)-m。于是由度序列判定定理知： G 是 H m n-m+1 1 图，得 G有 H路。 写出下列问题的一个好算法： 构作一个图的闭包； 若某图的闭包是完全图，求该图的 H 圈。解： (1) 构作一个图的闭包： 根据图的闭包定义， 构作一个图的闭包， 可以通过不断在度和大于等于 接顶点对间添边得到。据此设计算法如下： 图的闭包算法： 1) 令 =G ,k=0; 2) 在 中求顶点 与 ,使得：  n 的非邻 dGk (u0 ) dGk (v0 ) max dGk (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 n(n 1) 2 1 n( n 1) m(G ) O (n2 ) 2 2 所以，上面的闭包算法是好算法 。 若某图的闭包是完全图，求该图的