资源描述
文档供参考,可复制、编制,期待您的好评与关注! 计算机数学基础离散数学辅导(6) 第6章 几种特殊的图(2001级用) 中央电大 冯 泰本章重点:欧拉图和哈密顿图、平面图和树的基本概念. 一、重点内容1. 欧拉图h 欧拉通路(回路)与欧拉图 通过图G的每条边一次且仅一次,而且走遍每个结点的通路(回路),就是欧拉通路(回路). 存在欧拉回路的图就是欧拉图. 欧拉回路要求边不能重复,结点可以重复. 笔不离开纸,不重复地走完所有的边,且走过所有结点,就是所谓的一笔画. h欧拉图或通路的判定(1) 无向连通图G是欧拉图G不含奇数度结点(G的所有结点度数为偶数):(定理1)(2) 非平凡连通图G含有欧拉通路G最多有两个奇数度的结点;(定理1的推论)(3) 连通有向图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)若此条件不满足,即$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. 树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有向树 有向图删去边的方向为树,该有向图就是有向树. 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的两幅图是否可以一笔画出?解 在图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点的出度为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例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所示,试判断它们是否为欧拉图、哈密顿图、或平面图?并说明理由, a b c d e f g 图G1 图G2 图G3 图65 解 图G1是欧拉图,因为每个结点度数均为偶数图G2是哈密顿图,存在哈密顿回路,如cdgfebac(不惟一) 图G3是平面图可以改画成可平面图,如图67 例6.6 在具有n个结点的完全图Kn中,需要删去 图67多少条边才能.得到树? 解 n个结点的完全图共有条边,而n个结点的树共有n1条边. 因此需要删去 条边后方可得到树. 例6.7 设G是图,无回路,但若外加任意一条边于G后,就形成一回路. 试证明G必为树. b 23 1 15c 25 a 4 f 28 9 16 3 d 15 e 图68证明 由树的定义可知,只需证G连通即可. 任取不相邻两点u,v, 由题设,加上边就形成一回路,于是去掉边,从u到v仍有路u,v,即u,v连通,由u,v的任意性可知,G是连通的,故G必是树. 例6.8 如图68是有6个结点a,b,c,d,e,f的带权无向图,各边的权如图所示. 试求其最小生成树.解 构造连通无圈的图,即最小生成树, b 23 1 c a 4 f 9 3 d e 图69.用克鲁斯克尔算法:第一步: 取ab1;第二步: 取af=4;第三步: 取fe=3;第四步: 取ad=9;第五步: 取bc=23.如图69. 权为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个结点的无向完全图,则从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. 图610是( ) h h h h h h 图610(A) 完全图 (B)欧拉图 (C) 平面图 (D) 哈密顿图 答案:(D)解答:因为n=6, 每对结点度数之和大于或大于6,满足存在哈密顿回路的条件,故为哈密顿图. 选择(D)正确. 例6.10 填空题 1.设G是完全二叉树,G有15个结点,其中有8个是树叶,则G有 条边,G的总度数是 ,G的分支点数是 ,G中度数为3的结点数是 . 答案: 14; 28; 7; 6. h h h h h h hhhhhhhhh 图611解答:可画图如图611. 有8个树叶,15个结点的完全二叉树,2. 连通有向图D含有欧拉回路的充分必要条件是 答案:D中每个结点的入度出度. 解答:见欧拉回路的判断方法,定理2. 3. 设G是n个结点的简单图,若G中每对结点的度数之和 ,则G一定是哈密顿图. 答案:大于或等于n解答:见定理4. 4.设G是有n个结点,m条边的连通图,要确定G的一棵生成树,必须删去G的 条边. 答案:mn+1解答:见生成树的破圈或避圈求法. 5. 一个有向树T称为根树,若 ,其中 ,称为树根, 称为树叶. 答案:若有向图T恰有一个结点的入度为0,其余结点入度为1;入度为0的结点;入度为1的结点. 解答:见根树、树根、树叶的定义. 三、练习题1. 在图612中,哪些是欧拉图?哪些是哈密顿图?哪些是平面图? huh h h hv (1) h hh hh h h h h h (2) h h h h h hh h (4) h hh h h h h (3) hh h h hh h h h h (5) (6) 图6122. 设G是平面图,并且G的所有面的次数均为3,证明其中e是G的边数. v是G的结点数. 11 23 43. 设G是无向图,如图 a 3 d613,说明G不 是欧拉图;4. 求带权图,如图 e614的最小生成树. 5 6 5.将平面图G1,G2(如图6 b c 15) 改写成不相交的形式. 图613 图614 6. 已知有向图D的邻接矩阵为 h h h h h h h h h h h h h G1 G2 图615 试作出D的图,并求关联矩阵 7. (1)在1棵有2个2度结点,4个3度结点,其余为树叶的无向树中,应该有几片树叶?(2) 画出两棵不同构的满足条件(1)的结点度数的无向树T1,T2. 8.设G是有p个结点,s条边的连通图,则从G中删去多少条边,才能确定图G的一棵生成树?9.画出满足下列条件的图:(1) 画一个有一条欧拉回路和一条哈密顿回路的图;(2) 画一个有一条欧拉回路,但没有哈密顿回路的图;(3) 画一条没有欧拉路,但有一条哈密顿回路的图. 四、练习题答案1. (1)的图记作G1,从G1中删去结点u,v,得到G1的三个连通分支,有由定理3的逆可知,G1不是哈密顿图. 由于它是连通的,且无奇数度结点,由定理1可知,它是欧拉图,显然是平面图;(2) 是平面图. 由于它非连通,所以它不是欧拉图. 也不是哈密顿图;(3) 是平面图. 因为无回路,所以它不是欧拉图,也不是哈密顿图;(4) 是平面图. 因为奇数度的结点超过2个,根据定理1的推论,该图不是欧拉图;在图中容易找到一条哈密顿回路,故是哈密顿图;(5)是平面图. 因为无奇数度的结点,所以是欧拉图,又因为可以找到一条哈密顿回路,所以是哈密顿图. (6)不是平面图. 又奇数度的结点多于2个,所以它不是欧拉图,可以找到一条哈密顿回路,是哈密顿图. 2. 因为G的所有面的次数为3,因此对G的任意面r,有 deg(r)=3从而, 又根据定理6,G的所有面的次数之和等于其边数的2倍,即 即 代入欧拉公式 , 3. 因为G中各结点均为奇数度,由欧拉图的充分必要条件知,G不是欧拉图. 4. 最小生成树为T1 或用图形表示,如图616. h h h h h h h h h h h h h G1 G2 图6 17 a d e b c 图6185. 改写后的图,如图617v2h e1 hv1 e2 e4 e5 hv5v3h e3 hv4 图 6186. 图形如图618M(D)= 7. (1)设有k片树叶,则该树有k+2+4个结点,根据树的等价定义,有k+5条边. 由握手定理,2(k+5)=k+22+43k+16,故k=6. 即有6片树叶. (2) 如图619 l l l l l l l l l l l l l l l l l l l l l l l l T1 T2 不惟一. 图619 8. sp+1 9. (1)有一条欧拉回路和一条哈密顿回路的图,如图620(a)(2)有一条欧拉路,但没有哈密顿回路的图,如图620(b)h h h h h h h h h h h h h h h h h (a) (b) (c) 图620(2) 画一条没有欧拉路,但有一条哈密顿回路的图,如图620(c) 7 / 7
展开阅读全文