几种特殊的图

关于几种特殊的图第一页，共十四页，2022年，8月28日几种特殊的图教学要求理解欧拉通路(回路)、欧拉图的概念，掌握欧拉图的判别方法。

理解哈密顿通路(回路)、哈密顿图的概念

了解平面图的概念：平面图、面、边界、面的次数和非平面图。掌握欧拉公式的应用。

了解无向树、树叶、分支点、平凡树、生成树和最小生成树等概念。会求最小生成树。

了解有向树、根树、有序树、最优二元（叉）树等概念，会用哈夫曼算法求最优二叉树。

第二页，共十四页，2022年，8月28日几种特殊的图本章重点：欧拉图和哈密顿图平面图树的基本概念。

第三页，共十四页，2022年，8月28日几种特殊的图欧拉图包含图G的每一条边，且每条边仅出现一次的通路，就是欧拉通路。包含图G的每一条边，且每条边仅出现一次的回路，就是欧拉回路。存在欧拉回路的图，就是欧拉图。

第四页，共十四页，2022年，8月28日几种特殊的图欧拉图欧拉图的判定：(1)无向连通图G是欧拉图

G不含奇数度的结点(即G

的所有结点的度均为偶数(0视为偶数))；(定理1)(2)非0平凡图G

是欧拉图

G

最多有两个奇数度的结点；(定理1的推论)(3)有向图D是欧拉图

D是连通的，且D的所有结点的入度等于出度。或除两个结点外，均出度等于入度，且这两点deg－(v)－deg＋(v)＝1。

(定理2)第五页，共十四页，2022年，8月28日几种特殊的图哈密顿图通过图G的每个结点一次，且仅一次的通路，就是哈密顿通路通过图G的每个结点一次，且仅一次的回路，就是哈密顿回路。存在哈密顿回路的图就是哈密顿图。第六页，共十四页，2022年，8月28日几种特殊的图哈密顿图哈密顿图的判定：(1)在无向简单图G=<V,E>中，若则G是哈密顿图；——充分条件(2)如果无向图<V,E>时哈密顿图，V1是V的任意非空子集，则有P（G－V1）<|V1|,。其中P（G－V1）是从G中删除V1后所得的图的连通支数。——必要条件(3)有向完全图D＝<V,E>,若，则图D是哈密顿图。第七页，共十四页，2022年，8月28日几种特殊的图平面图

重要结论

(1)平面图(所有面的次数之和＝边数的2倍)。

(2)欧拉公式：平面图

面数为r，则(结点数与面数之和＝边数＋2)。

(3)平面图（2）和（3）仅为必要条件，只能判断一个图不是平面图判定条件：一个图是平面图G的充分必要条件是G不含与K3，3或K5在2度结点内同构的子图。

第八页，共十四页，2022年，8月28日几种特殊的图平面图相关概念面和面的边界面的次数有限面与无限面同胚或同构图的着色结点着色、边着色、面着色结点着色的方法：韦而奇.鲍威尔面着色－>边着色->结点着色定理11：P205对偶图第九页，共十四页，2022年，8月28日几种特殊的图树树的判别：图，是树的充分必要条件是：G是无回路的连通图；无回路，且m＝n－1；连通且m＝n－1无回路，若增加一条边，就得到一条仅一条回路连通，若删去任一边，G则不连通；每一对结点之间有一条且仅有一条通路。证明略第十页，共十四页，2022年，8月28日几种特殊的图树相关概念树和森林无向树与有向树树叶与分支点平凡树、生成树和最小生成树

树枝、弦和生成树的补根数、树叶、分支点（树根、内点）层数和树高祖先、父亲、儿子和兄弟m元树、m元完全树和m元正则完全数第十一页，共十四页，2022年，8月28日几种特殊的图树任何非平凡树至少有两片树叶求最小生成树的算法－－Kruskal算法定理17：（m-1）i＝t－1哈夫曼树：最优二叉树定理19：P215（证明略）哈夫曼算法前缀码前缀码和二叉树第十二页，