资源描述：
《计算机数学基础离散数学辅导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《计算机数学基础》离散数学辅导（6）第6章几种特殊的图（2001级用）中央电大冯泰本章重点：欧拉图和哈密顿图、平面图和树的基本概念一、重点内容1.欧拉图•欧拉通路（回路）与欧拉图通过图G的每条边一次且仅一次，而且走遍每个结点的通路（回路），就是欧拉通路（回路）.存在欧拉回路的图就是欧拉图.欧拉回路要求边不能重复，结点可以重复.笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画.•欧拉图或通路的判定（1）无向连通图G是欧拉图oG不含奇数度结点（G的勿7有结点度数为偶数）:（定理1）（2）非平凡连通图G含有欧拉通路oG最多有两个奇数度的结点;（定理1的推论）（
2、3）连通有向图D含有有向欧拉回路（即欧拉图中每个结点的入度=出度连通有向图D含有有向欧拉通路oD中除两个结点外，其余每个结点的入度=出度，且此两点满足deg_（«）—deg+（v）=±l.（定理2）2.哈密顿图•哈密顿通路（回路）与哈密顿图通过图G的每个结点一次，且仅一次的通路（回路），就是哈密顿通路（回路）.存在哈密顿回路的图就是哈密顿图.判断哈密顿图是较为困难的.•哈密顿图的充分条件和必要条件（1）在无向简单图G二<认£>中
3、v
4、n3,任意不同结点u,vgG,deg（w）+deg（v）>
5、V
6、,K'JG是哈密顿图.（充分条件，定理4）（2）有向完全图D=vV,E>,若
7、
8、V
9、>3,则图D是哈密顿图・（充分条件，定理5推论）（3）设无向图G=,VV^Vf则必要条件，定理3）若此条件不满足，即使得则G—定不是哈密顿图（非哈密顿图的充分条件）.3•平面图•平面图一个图能画在平面上，除结点之外，再没有边与边相交.面、边界和面的次数由连通平面图G的边围成的其内部不含G的结点和边的区域是面，常用r表示.围成而的各边组成的回路是边界.边界回路的长度是面的次数，记作deg（r）.•重要结论⑴平面图G=,
10、V
11、=v,
12、E
13、=e,则工deg（,;J=2幺（所有面的次数之和=边的/=!2倍）（定理6）.（2）欧拉公式：平面图G=,
14、
15、V
16、=v,
17、£
18、=^面数为门则v-e+r=2（结点数与面数之和=边数+2）（定理7）（3）平面图G=,
19、V
20、=v,
21、£
22、=匕若u>3,贝呢<3v-6（定理8）•判定条件：图G是平面图的充分必要条件是G不含与K3心或K5任2度结点内同构的子图.4.树•树连通无回路的无向图.•树的判别图T=^=n]E=mJ是树的充分必要条件是(六个等价定义)(定理14):(1)T是无回路的连通图；(2)图T无回路且(3)图T连通且m=n~l(4)图T无回路，若增加一条边，就得到一条且仅一条回路；(5)图厂连通，若删去任一边，G则不连通:(6)图T的每一对结点之间有一
23、条且仅有一条通路.•生成树图G的生成子图是树，该树就是生成树.•权与带权图料个结点的连通图G,每边指定一正数，称为权，每边带权的图称为带权直.G的生成树T的所有边的权之和是生成树T的权，记作W(7).•最小生成树带权最小的生成树.•有向树有向图删去边的方向为树，该有向图就是有向树.•根树与树根非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1,该树为根树.•每个结点的出度小于或等于2的根树为二元树(二叉树)；每个结点的出度等于0或2的根树为二元完全树(二叉完全树)；每个结点的称为正则二元树(正则二叉树).•哈夫曼树用哈夫曼算法得到的最4.有关树的求•
24、生成树的破•最小生成树•哈夫曼树的二、实例例6・1判别图6-1的两幅图是否可以一笔画出？解在图6—1(d)屮，deg(vi)=deg(v2)=deg(v3)=3有两个以上的结点的度为3.故在⑺)中不存在欧拉通路，法圈法和避圈法求法;的克鲁斯克尔求法;哈夫曼求法.优二叉树.出度等于2的根树(。)图6-1不能一笔Id]出.在图6—1(/?)中,deg(A)=2,deg(B)=deg(Q=deg(D)=4,deg(E)=deg(F)=3只有两个奇数度的结点，所以存在欧拉通路，可以一笔画出.一条欧拉通路，如EDBEFCABCDF.例6・2判定图6-2中，两个图是否冇欧拉冋路？若有
25、请把欧拉冋路写出来解在图D1中，Z点的出度为2,入度为0;2的出度为0,入度为2,.且这两点出度与入度之差不等于±1,V2<所以，图D1不存在欧拉通路，图D不是欧拉图.'图0屮，各个结点的出度、入度都相等2,所以存存欧拉冋路，图0是欧拉图.一个欧拉回路为ViaV2bV3/vev3cv4hgv4dv例6・3指出图6-3各图是否哈密顿图，有无哈密顿通路，冋路?解（1）容易判断，存在哈密顿回路，故是哈密顿图.（2）只有哈密顿通路，无哈密顿冋路，故不是哈密顿图.（3）无哈密顿通路，显然不是哈密顿图.点的无向图.(1)不是哈密顿图，
