第9章 特殊图与应用.ppt

第9章 特殊图与应用;第1节 欧拉图与哈密顿图;一、欧拉图;欧拉图的起源;欧拉图;解答;定理;哥尼斯堡七桥问题;欧拉图应用举例;解答;定理;定理应用举例;解答;解答;定理应用举例;4、有向欧拉图;定理;有向欧拉图举例;解答;解答;定理;二、哈密顿图;1、哈密顿图的起源;2、哈密顿图;哈密顿图举例;解答;判断哈密顿图的必要条件定理;解释;定理应用举例;解答;判断哈密顿图的充分条件定理;解释;定理应用举例;第2节 平面图与欧拉公式;1、平面图;平面图举例;解答;2、平面图的区（面）;平面图的面举例;平面图的面举例;3、相邻区;相邻区举例;定理（欧拉公式）; 证明(对边数m进行归纳);证明（续）;证明（续）;证明（续）;解释;定理(欧拉公式的推论);解释;平面图的不等式举例;平面图的不等式举例;4、在2度结点内同构;举例;库拉托夫斯基定理;库拉托夫斯基定理的应用举例;证明;库拉托夫斯基定理的应用举例;证明;第3节 二部图与匹配 ;一、二部图;1、二部图的定义;二部图举例;2、完全二部图;完全二部图举例;二、匹配(略);1、匹配;2、极大匹配;3、最大匹配、匹配数;解释;匹配举例;4、完备匹配;完备匹配举例;定理;解释;定理应用举例;定理应用举例;定理;定理应用举例;解答;第4节 对偶图与着色(简介);解释;对偶图举例;解答;6、自对偶图;自对偶图举例;解答;解答;解答（续）;第5节 树;1、树、树叶、分枝结点、树枝;树的举例;2、最小连通图;定理;证明: (1)?(2);证明（续）;证明: (2)?(3);定理;证明;3、森林;4、生成树、树枝、连枝;生成树举例;定理;5、求连通图G的生成树的方法;（1）避回路法;避回路法举例;（2）破回路法;破回路法举例;6、最小生成树;7、求最小生成树的算法;（1）避回路法;避回路法求最小生成树举例;解答;（2）破回路法;破回路法求最小生成树举例;第9节 根树及其应用;1、有向树;2、根树;结点的层次、树的高度;根树举例;3、有序树;有序树举例;有序树举例;子孙、儿子、兄弟(家族术语);4、子树;子树举例;5、m叉树、完全m叉树;举例;2叉树、完全2叉树;定理;证明;定理;定理;证明;6、有序树转化为二叉树的方法;有序树转化为二叉树的方法（续）;有序树转化为二叉树举例;解答;7、二杈树遍历的三种方法;（1）前序遍历（DLR遍历）;（2）中序遍历（LDR遍历）;（3）后序遍历（LRD遍历）;前、中、后序遍历举例;解答（1）前序遍历：;解答（2）中序遍历;解答（3）后序遍历;8、带权二杈树;9、最优二杈树;10、构造具有t片树叶的最优二叉树的方法;求最优二叉树举例;解答