《（广告传媒）第四次辅导欢迎访问安徽广播电视大学网站！》由会员分享，可在线阅读，更多相关《（广告传媒）第四次辅导欢迎访问安徽广播电视大学网站！（15页珍藏版）》请在金锄头文库上搜索。
1、15 计算机数学基础(1)第四单元辅导本单元重点：欧拉图和哈密顿图、平面图和树的基本概念. 代数运算及性质，群的概念，交换群和循环群.一、重点内容1. 欧拉图h 欧拉通路(回路)与欧拉图 通过图G的每条边一次且仅一次，而且走遍每个结点的通路(回路)，就是欧拉通路(回路). 存在欧拉回路的图就是欧拉图. 欧拉回路要求边不能重复，结点可以重复. 笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画. h欧拉图或通路的判定(1) 无向连通图G是欧拉图G不含奇数度结点(G的所有结点度数为偶数):(定理1)(2) 非平凡连通图G含有欧拉通路G最多有两个奇数度的结点；(定理1的推论)(3)
2、连通有向图D含有有向欧拉回路(即欧拉图)D中每个结点的入度出度连通有向图D含有有向欧拉通路D中除两个结点外，其余每个结点的入度出度，且此两点满足deg(u)deg(v)1. (定理2)2. 哈密顿图h哈密顿通路(回路)与哈密顿图 通过图G的每个结点一次，且仅一次的通路(回路)，就是哈密顿通路(回路). 存在哈密顿回路的图就是哈密顿图. 判断哈密顿图是较为困难的. h哈密顿图的充分条件和必要条件 (1) 在无向简单图G=中V3,任意不同结点,则G是哈密顿图.(充分条件，定理4)(2) 有向完全图D, 若，则图D是哈密顿图. (充分条件，定理5推论)(3) 设无向图G=,V1V，则P(GV1)V1
3、(必要条件，定理3)若此条件不满足，即$V1V，使得P(GV!)V1,则G一定不是哈密顿图(非哈密顿图的充分条件).3.平面图h 平面图 一个图能画在平面上，除结点之外，再没有边与边相交. 面、边界和面的次数 由连通平面图G的边围成的其内部不含G的结点和边的区域是面，常用r表示. 围成面的各边组成的回路是边界. 边界回路的长度是面的次数，记作deg(r). h重要结论(1)平面图(所有面的次数之和边的2倍)(定理6). (2)欧拉公式：平面图 面数为r，则(结点数与面数之和边数2)(定理7)(3)平面图(定理8) h判定条件：图G是平面图的充分必要条件是G不含与K3，3或K5在2度结点内同构的
4、子图. 4. 树h树 连通无回路的无向图. h树的判别 图,T是树的充分必要条件是(六个等价定义) (定理14):(1) T是无回路的连通图； (2) 图T无回路且mn1；(3) 图T连通且mn1 (4) 图T无回路，若增加一条边，就得到一条且仅一条回路；(5) 图T连通，若删去任一边，G则不连通；(6) 图T的每一对结点之间有一条且仅有一条通路. h生成树 图G的生成子图是树，该树就是生成树. h权与带权图 n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图. G的生成树T的所有边的权之和是生成树T的权，记作W(T). h最小生成树 带权最小的生成树. h有向树 有向图删去边
5、的方向为树，该有向图就是有向树. h根树与树根 非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树. h每个结点的出度小于或等于2的根树为二元树(二叉树)；每个结点的出度等于0或2的根树为二元完全树(二叉完全树)；每个结点的出度等于2的根树称为正则二元树(正则二叉树).h哈夫曼树 用哈夫曼算法得到的最优二叉树. v4h hv5 Eh h F hAv2h h v3 Bh h C hv1 h D（a） (b) 图614. 有关树的求法h生成树的破圈法和避圈法求法；h最小生成树的克鲁斯克尔求法；h哈夫曼树的哈夫曼求法. 二、实例例6.1 判别图61的两幅图是否可以一
6、笔画出？解 在图61(a) 中， deg(v1)=deg(v2)=deg(v3)3有两个以上的结点的度为3. 故在(a)中不存在欧拉通路，不能一笔画出. 在图61(b) 中，deg(A)=2, deg(B) =deg(C)= deg(D)=4，deg(E) =deg(F)=3只有两个奇数度的结点，所以存在欧拉通路，可以一笔画出. 一条欧拉通路，如EDBEFCABCDF. v1h v1h d h v4v2h h v5 f h a g e c v3 h h v4 v2 h b h v3 D1 D2 图62例6.2 判定图62中，两个图是否有欧拉回路？若有请把欧拉回路写出来. 解 在图D1中，v1点
7、的出度为2，入度为0； v5的出度为0，入度为2，且这两点出度与入度之差不等于1，所以，图D1不存在欧拉通路，图D1不是欧拉图. 图D2中，各个结点的出度、入度都相等2，所以存存欧拉回路，图D2是欧拉图. 一个欧拉回路为v1 a v2 b v3 f v1 e v3 c v4 h v2 g v4 dv1例6.3 指出图63各图是否哈密顿图，有无哈密顿通路， 回路？解 (1) 容易判断，存在哈密顿回路，故是哈密顿图.(2) 只有哈密顿通路，无哈密顿回路，故不是哈密顿图.(3) 无哈密顿通路，显然不是哈密顿图. i h h h h h h h h h h h h h (1) (2) (3) 图63例
8、6.4 画出具有下列条件的有5个结点的无向图.(1) 不是哈密顿图，也不是欧拉图；(2) 有哈密顿回路，没有欧拉回路；(3) 没有哈密顿回路，有欧拉回路；(4) 是哈密顿图，也是欧拉图. 解 作图如图64(不唯一). h h h h h h h h h h h h h h h h h h h h(1) (2) (3) (4) 图64 例6.5判断图65是否为平面图？解 在G中，将(v1,v4)和(v3,v4)改画成如虚线所示.可见G是平面图. v1h 例6.6 在具有n个结点的完全 图Kn中，需要删去多少条边才能 v2h h v3 .得到树？ v4h h v5 G 图65 解 n个结点的完全图
9、共有条边，而n个结点的树共有n1条边. 因此需要删去 条边后方可得到树. 例6.7 设G是图，无回路，但若外加任意一条边于G后，就形成一回路. 试证明G必为树. b 23 1 15c 25 a 4 f 28 9 16 3 d 15 e 图66证明 由树的定义可知，只需证G连通即可. 任取不相邻两点u,v, 由题设，加上边就形成一回路，于是去掉边,从u到v仍有路u,v，即u,v连通，由u,v的任意性可知，G是连通的，故G必是树. 例6.8 如图66是有6个结点a,b,c,d,e,f的带权无向图，各边的权如图所示. 试求其最小生成树.解 构造连通无圈的图，即最小生成树，.用克鲁斯克尔算法：第一步：
10、 取ab1；第二步： 取af=4；第三步： 取fe=3；第四步： 取ad=9； b 23 1 c a 4 f 9 3 d e 图67第五步： 取bc=23.如图67。权为1+4+3+9+23=30例6.9 单项选择题1.无向图G是欧拉图，当且仅当( ) (A)G的所有结点的度数为偶数 (B) G的所有结点的度数为奇数(C) G连通且所有结点的度数为偶数 (D) G连通且所有结点的度数为奇数答案：(C) 解答：见本单元定理1. 2. 设为连通平面图且有r个面，则r( )(A) mn+2 (B) nm2 (C) n+m-2 (D) m+n+2答案：(A)解答：见定理7欧拉公式. 3. 设G是5个结
11、点的无向完全图，则从G中删去( )条边可以得到树. (A) 4 (B)5 (C)6 (D)10答案：(C)解答：删去边的公式为. 故选择(C)正确. 4. 在5个结点的二元完全树中，若有4条边，则有 ( )片树叶。(A) 2 (B) 3 (C) 5 (D) 4答案：(B)解答：二元完全树，即每个结点只有0个或2树枝的树，树根必有2个树枝，于是2个树枝只能其一又有2个树枝，而另一个就无树枝. 满足5个结点4条边. 可见有3片树叶. 选择(B)正确. 一般地，在二元完全树中，有m条边，t片树叶，则有m=2(t1)5. 图68是( ) (A) 完全图 (B)欧拉图 (C) 平面图 (D) 哈密顿图 h h h h h h 图68 答案：(D)解答：因为n=6, 每对结点度数之和大于或大于6，满足存在哈密顿回路的条件，故为哈密顿图. 选择(D)正确. 例6.10 填空题 1.设G是完全二叉树，G有15个结点，其中有8个是树叶，则G有 条边，G的总度数是 ，G的分支点数是 ，G中度数为3的结点数
