几种特殊的图精选PPT.ppt

关于几种特殊的图第1页，讲稿共14张，创作于星期日几种特殊的图几种特殊的图n教学要求教学要求n理解欧拉通路(回路)、欧拉图的概念，掌握欧拉图的判别方法。n理解哈密顿通路(回路)、哈密顿图的概念 n了解平面图的概念：平面图、面、边界、面的次数和非平面图。掌握欧拉公式的应用。n了解无向树、树叶、分支点、平凡树、生成树和最小生成树等概念。会求最小生成树。n了解有向树、根树、有序树、最优二元（叉）树等概念，会用哈夫曼算法求最优二叉树。第2页，讲稿共14张，创作于星期日几种特殊的图几种特殊的图n本章重点：n欧拉图和哈密顿图n平面图n树的基本概念。第3页，讲稿共14张，创作于星期日几种特殊的图几种特殊的图n欧拉图欧拉图n包含图G的每一条边，且每条边仅出现一次的通路，就是欧拉通路。n包含图G的每一条边，且每条边仅出现一次的回路，就是欧拉回路。n存在欧拉回路的图，就是欧拉图。第4页，讲稿共14张，创作于星期日几种特殊的图几种特殊的图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)第5页，讲稿共14张，创作于星期日几种特殊的图几种特殊的图n哈密顿图哈密顿图n通过图G的每个结点一次，且仅一次的通路，就是哈密顿通路n通过图G的每个结点一次，且仅一次的回路，就是哈密顿回路。n存在哈密顿回路的图就是哈密顿图。第6页，讲稿共14张，创作于星期日几种特殊的图几种特殊的图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第7页，讲稿共14张，创作于星期日几种特殊的图几种特殊的图n平面图平面图 n重要结论n(1)平面图 (所有面的次数之和边数的2倍)。n(2)欧拉公式：平面图 面数为r，则(结点数与面数之和边数2)。n(3)平面图 n（2）和（3）仅为必要条件，只能判断一个图不是平面图n判定条件：一个图是平面图G的充分必要条件是G不含与K3，3或K5在2度结点内同构的子图。ereEvVEVGrii2)deg(,1则,eEvVEVG2rev633,veveEvVEVG，则若第8页，讲稿共14张，创作于星期日几种特殊的图几种特殊的图n平面图平面图n相关概念n面和面的边界n面的次数n有限面与无限面n同胚或同构n图的着色n结点着色、边着色、面着色n结点着色的方法：韦而奇.鲍威尔n面着色边着色-结点着色n定理11：P205n对偶图第9页，讲稿共14张，创作于星期日几种特殊的图几种特殊的图n树树n树的判别：图，是树的充分必要条件是：nG是无回路的连通图；n无回路，且mn1；n连通且mn1n无回路，若增加一条边，就得到一条仅一条回路n连通，若删去任一边，G则不连通；n每一对结点之间有一条且仅有一条通路。n证明略mEnVEVG,第10页，讲稿共14张，创作于星期日几种特殊的图几种特殊的图n树树n相关概念n树和森林n无向树与有向树n树叶与分支点n平凡树、生成树和最小生成树 n树枝、弦和生成树的补n根数、树叶、分支点（树根、内点）n层数和树高n祖先、父亲、儿子和兄弟nm元树、m元完全树和m元正则完全数第11页，讲稿共14张，创作于星期日几种特殊的图几种特殊的图n树树n任何非平凡树至少有两片树叶n求最小生成树的算法Kruskal算法n定理17：（m-1）i t 1n哈夫曼树：最优二叉树n定理19：P215（证明略）n哈夫曼算法n前缀码n前缀码和二叉树第12页，讲稿共14张，创作于星期日几种特殊的图几种特殊的图n本章重点：本章重点：n欧拉图n哈密顿图n平面图n树的基本概念。第13页，讲稿共14张，创作于星期日感谢大家观看感谢大家观看9/13/2022第14页，讲稿共14张，创作于星期日