《计算机数学基础(1)》辅导

《《计算机数学基础(1)》辅导》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、6《计算机数学基础(1)》辅导¾¾第6章几种特殊的图(2004级用)本章重点：欧拉图和哈密顿图、平面图和树的基本概念.一、重点内容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=中½V½³3,任意不同结点,则G是哈密顿图.(充分条件，定理4)(2)有向完全图D＝,若，则图D是哈密顿图.(充分条件，定理5推

3、论)(3)设无向图G=,"V1ÌV，则P(G－V1)£½V1½(必要条件，定理3)若此条件不满足，即$V1ÌV，使得P(G－V!)>½V1½,则G一定不是哈密顿图(非哈密顿图的充分条件).3.平面图h平面图一个图能画在平面上，除结点之外，再没有边与边相交.面、边界和面的次数由连通平面图G的边围成的其内部不含G的结点和边的区域是面，常用r表示.围成面的各边组成的回路是边界.边界回路的长度是面的次数，记作deg(r).h重要结论(1)平面图(所有面的次数之和＝边的2倍)(定理6).(2)欧拉公式：平面图面数为r，则(结点数与面数之和＝边数＋2)(定理7)(3

4、)平面图(定理8)h判定条件：图G是平面图的充分必要条件是G不含与K3，3或K5在2度结点内同构的子图.4.树h树连通无回路的无向图.6h树的判别图,T是树的充分必要条件是(六个等价定义)(定理14):(1)T是无回路的连通图；(2)图T无回路且m＝n－1；(3)图T连通且m＝n－1(4)图T无回路，若增加一条边，就得到一条且仅一条回路；(5)图T连通，若删去任一边，G则不连通；(6)图T的每一对结点之间有一条且仅有一条通路.h生成树图G的生成子图是树，该树就是生成树.h权与带权图n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图.G的生成树T的所

5、有边的权之和是生成树T的权，记作W(T).h最小生成树带权最小的生成树.h有向树有向图删去边的方向为树，该有向图就是有向树.h根树与树根非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树.h每个结点的出度小于或等于2的根树为二元树(二叉树)；每个结点的出度等于0或2的根树为二元完全树(二叉完全树)；每个结点的出度等于2的根树称为正则二元树(正则二叉树).h哈夫曼树用哈夫曼算法得到的最优二叉树.v4hhv5v2hhv3hv1　例1图　v1hdhv4　　　　　fhagec　　　　v2hbhv3D2D1　4.有关树的求法h生成树的破圈法

6、和避圈法求法；h最小生成树的克鲁斯克尔求法；h哈夫曼树的哈夫曼求法.二、实例例1判别如例6.1图的两幅图是否有欧拉通路、回路？若有请把欧拉回路写出来.？解在例1图D1中，deg(v1)=deg(v2)=deg(v3)＝3有两个以上的结点的度为3.故在D1中不存在欧拉通路，不能一笔画出.图D2中，各个结点的出度、入度都相等2，所以存存欧拉回路，图D2是欧拉图.一个欧拉回路为v1av2bv3fv1ev3cv4hv2gv4dv1例2指出例2图各图是否哈密顿图，有无哈密顿通路，回路？解(1)容易判断，存在哈密顿回路，故是哈密顿图.(2)只有哈密顿通路，无哈密顿回路，故不是

7、哈密顿图.(3)无哈密顿通路，显然不是哈密顿图.ihhhhhhhhhhhhh(1)(2)(3)例2图例3画出具有下列条件的有5个结点的无向图.(1)不是哈密顿图，也不是欧拉图；(2)有哈密顿回路，没有欧拉回路；(3)没有哈密顿回路，有欧拉回路；(4)是哈密顿图，也是欧拉图.解作图如例3图(不唯一).6hhhhhhhhhhhhhhhhhhhh(1)(2)(3)(4)例3图例4给定三个图如例6.5所示，试判断它们是否为欧拉图、哈密顿图、或平面图？并说明理由，abcdefg图G1图G2图G3例4图解图G1是欧拉图，因为每个结点度数均为偶数．图G2是哈密顿图，存在哈密顿回

8、路，如cd