上海交通大学离散数学课件第10章特殊图.ppt

第10章 特殊图 10.1;10.1 欧拉图与哈密顿图 ;10.1 欧拉图与哈密顿图 ;10.1 欧拉图与哈密顿图 ;10.1 欧拉图与哈密顿图 ;10.1 欧拉图与哈密顿图 ;10.1.2 哈密顿图及哈密;10.1.2 哈密顿图及哈密;10.1.2 哈密顿图及哈密;现考虑G中这条包含v1，v2，;10.1.2 哈密顿图及哈密;定理10.4 当n为不小于3的;10.1.2 哈密顿图及哈密;10.1.2 哈密顿图及哈密;10.1.2 哈密顿图及哈密;10.1.2 哈密顿图及哈密;10.1.2 哈密顿图及哈密;x ;基本步骤：（1）判断街区图是否;例10.6 下图表示五个城镇之;10.2.1 二分图基本概念;10.2.1 二分图基本概念;10.2.1 二分图基本概念;10.2.1 二分图基本概念;10.2.1 二分图基本概念;10.2 二分图 ;10.2 二分图 ;10.2 二分图 ;10.2 二分图 ;(2)，(3)交替执行，直到下;10.2 二分图 ;（1）置M = ?，对x1-x;10.2 二分图 ;10.2 二分图 ;证充分性：设G满足：对任一S?;显然，S?{x}中顶点与S中;例10.9 （1） k-正则二;例10.9 （2）某单位有四个;10.3.1 平面图基本概念;10.3.1 平面图基本概念;10.3.1 平面图基本概念;10.3.1 平面图基本概念;定理10.8 平面图所有面的度;定理10.9 极大平面图所有;10.3.2 欧拉公式和库拉;10.3.2 欧拉公式和库拉;10.3.2 欧拉公式和库拉;10.3.2 欧拉公式和库拉;10.3.2 欧拉公式和库拉;10.3.2 欧拉公式和库拉;10.3.2 欧拉公式和库拉;10.3.2 欧拉公式和库拉;10.3.2 欧拉公式和库拉;10.3.2 欧拉公式和库拉;10.3.2 欧拉公式和库拉;10.3.2 欧拉公式和库拉;10.3.3 平面图的应用：;例10.17 图(b)是(a;例10.18 图(a)，(b;对偶图的性质： (1) ;定理10.16 任何平面图都;考虑v0的着色。（1）设d (;若v1和v3同属于一个G（RY;10.4.1 根树的概念 ;10.4.1 根树的概念 ;根树除有树的一般特性外，还有下;10.4.1 根树的概念 ;例10.20 有10个文件;例10.21 有8枚硬币，其中;定义10.14 除树叶外，每;另一方面，如果高为h的完全二元;10.4.2 二元树的性质及;定义10.15 每个结点都;(a),(b) 作为一般3元树;重要事实： 任何;4元有序树表示为2元位置树： ;用2元位置树表示由n元有序树组;(1) 先根算法（前序遍历法）;先根算法得 / - ?;www.themegaller