几种特殊的图

1、几种特殊的图教师：孙继荣电话：87768609Email:几种特殊的图几种特殊的图n教学要求教学要求n理解欧拉通路(回路)、欧拉图的概念，掌握欧拉图的判别方法。 n理解哈密顿通路(回路)、哈密顿图的概念 n了解平面图的概念：平面图、面、边界、面的次数和非平面图。掌握欧拉公式的应用。 n了解无向树、树叶、分支点、平凡树、生成树和最小生成树等概念。会求最小生成树。 n了解有向树、根树、有序树、最优二元（叉）树等概念，会用哈夫曼算法求最优二叉树。 几种特殊的图几种特殊的图n本章重点：n欧拉图和哈密顿图n平面图n树的基本概念。 几种特殊的图几种特殊的图n欧拉图欧拉图n包含图G的每一条边，且每条边仅出现

2、一次的通路，就是欧拉通路。n包含图G的每一条边，且每条边仅出现一次的回路，就是欧拉回路。n存在欧拉回路的图，就是欧拉图。 几种特殊的图几种特殊的图n欧拉图欧拉图n欧拉图的判定：n(1) 无向连通图G是欧拉图 G不含奇数度的结点(即G 的所有结点的度均为偶数(0视为偶数)；(定理1)n(2) 非0平凡图G 是欧拉图 G 最多有两个奇数度的结点；(定理1的推论)n(3) 有向图D是欧拉图 D是连通的，且D的所有结点的入度等于出度。或除两个结点外，均出度等于入度，且这两点deg(v)deg(v)1。 (定理2)几种特殊的图几种特殊的图n哈密顿图哈密顿图n通过图G的每个结点一次，且仅一次的通路，就是哈

3、密顿通路n通过图G的每个结点一次，且仅一次的回路，就是哈密顿回路。n存在哈密顿回路的图就是哈密顿图。几种特殊的图几种特殊的图n哈密顿图哈密顿图n哈密顿图的判定：n(1) 在无向简单图G =中，若 则G是哈密顿图；充分条件n(2) 如果无向图时哈密顿图，V1是V的任意非空子集，则有P（GV1）|V1|,。其中P（GV1）是从G中删除V1后所得的图的连通支数。必要条件n(3)有向完全图D, 若 ，则图D是哈密顿图。VvuGvu)deg()deg(,3V3V几种特殊的图几种特殊的图n平面图平面图 n重要结论n (1) 平面图 (所有面的次数之和边数的2倍)。n (2) 欧拉公式：平面图 面数为r，

4、则(结点数与面数之和边数2)。n (3) 平面图 n（2）和（）和（3）仅为必要条件，只能判断一个图不是平面图）仅为必要条件，只能判断一个图不是平面图n判定条件：一个图是平面图G的充分必要条件是G不含与K3，3或K5在2度结点内同构的子图。 ereEvVEVGrii2)deg(,1则,eEvVEVG2rev633,veveEvVEVG，则若几种特殊的图几种特殊的图n平面图平面图n相关概念n面和面的边界n面的次数n有限面与无限面n同胚或同构n图的着色n结点着色、边着色、面着色n结点着色的方法：韦而奇.鲍威尔n面着色边着色-结点着色n定理11：P205n对偶图几种特殊的图几种特殊的图n树树n树的判

5、别： 图，是树的充分必要条件是：nG是无回路的连通图；n无回路，且mn1；n连通且mn1n无回路，若增加一条边，就得到一条仅一条回路n连通，若删去任一边，G则不连通；n每一对结点之间有一条且仅有一条通路。n证明略mEnVEVG,几种特殊的图几种特殊的图n树树n相关概念n树和森林n无向树与有向树n树叶与分支点n平凡树、生成树和最小生成树 n树枝、弦和生成树的补n根数、树叶、分支点（树根、内点）n层数和树高n祖先、父亲、儿子和兄弟nm元树、m元完全树和m元正则完全数几种特殊的图几种特殊的图n树树n任何非平凡树至少有两片树叶n求最小生成树的算法Kruskal算法n定理17： （m-1）i t 1n哈夫曼树：最优二