第九单元 二分图、平面图和树王元元.pptVIP

第九章 二分图、 平面图和树 重点：二分图及匈牙利算法﹑平面图﹑树 重点：二分图及匈牙利算法﹑平面图﹑树 9.1 二分图 判断二分图的定理 例： 练习 六名间谍a,b,c,d,e,f被我捕获，他们分别懂得的语言是 a：汉语，法语，日语； b：德语，日语，俄语； c：英语，法语； d：汉语，西班牙语； e：英语，德语； f：俄语，西班牙语。 问至少用几个房间监禁他们，才能使同一房间的人不能互相直接对话。 判断二分图的定理 9.1.2 匹配 9.1.2 匹配 例9-2 图9-2中各图的红线表示匹配中的边(简称匹配边)。 9.1.2 匹配 有四名教师张征、王兴、李忠和赵华，分别派他们教四门课程：数学、物理、电工和计算机导论。张征懂物理和电工；王兴懂数学和计算机导论；李忠懂数学、物理和电工；赵华只懂电工。问应该如何分派，才不会使任何人去讲他不懂的课程而又不存在有的课程无人教？ 匹配的应用 安排工作：现有6个工人{x1,x2,…,x6},有6项工作{y1,y2,…,y6}。假设在同一时间内，每人只能干一项工作，每项工作只需一个人干，每个工人能干的工作用边来表示。 安排工作就是求二分图的一个匹配问题。求最大匹配就是一个工作最佳的安排问题，使尽可能多的人有工作干，尽可能多的工作被人干。 术语介绍 术语介绍 由交替链的定义可以推出下述三个结论： 匈牙利算法 求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。 匈牙利算法 用交替链求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出) 算法轮廓： (1)置M为空 (2)找出一条交错链P，通过取反操作获得更大的匹配M′代替M (3)重复(2)操作直到找不出交错链为止 例9-3 用匈牙利算法求图9.3的一个最大匹配。 例9-3 用匈牙利算法求图9.3的一个最大匹配。 例9-3 用匈牙利算法求图9.3的一个最大匹配。 例9-3 用匈牙利算法求图9.3的一个最大匹配。 例9-3 用匈牙利算法求图9.3的一个最大匹配。 完全匹配的存在条件 完全匹配的存在条件 例 应用 有六位未婚女子,L1 , L2 , L3 , L4 , L5 , L6 和六位未婚男子,G1 , G2 , G3 , G4 , G5 , G6 中 六位女子分别对下列集合的男子中意： L1 ：{G1 , G2 , G4 }, L2 ：{G3, G5}, L3 ：{G1 , G2 , G4 }, L4 ：{G2 , G5 , G6 }, L5：{G3 , G6}, L6 ：{G2 , G5 , G6 } 六位男子分别对下列集合的女子中意： G1 ：{L1 , L3 , L6 }, G2 ：{L2 , L4 , L6 }, G3 ：{L2 , L5}, G4 ：{L1 , L3}, G5：{L2 , L6}, G6 ：{L3 , L4 , L5 } 现需涉及一个有6个元件的电路，把6个元件分成两组，每组3个元件，设计要求每组中的任一个元件必须与另一组中的所有元件用导线连接。问能否设计电路使导线不交叉？如果能，画出设计方案，如果不能，说明理由，并画出一个导线交叉最少的设计方案。 9.2 平面图 例 K3,3与K5称为库拉托夫斯基（Kuratowski）图 9.2 面的概念 例9-6 9.2 平面图 9.2 平面图 例 9.2.2 欧拉公式 推论 推论 例 推论 推论 证明：定理9-9的结论可加强为“至少有3个顶点的度数不大于5”。 (1)切割操作 (2) 贯通操作 3 库拉托夫斯基定理 例 9.3 树 性质 性质 性质 树等价定义形式 树等价定义形式 9.3.2 生成树 9.3.2 生成树 求生成树方法 例9-4 最小生成树 例 克鲁斯克尔（Kruskal）算法 克鲁斯克尔（Kruskal）算法 指出两点 克鲁斯克尔（Kruskal）算法正确性 克鲁斯克尔（Kruskal）算法正确性 9.3.3 根树 9.3.3 根树 9.3.3 根树 根树性质 例9-18 完全2元树 完全2元树性质 完全2元树性质 完全2元树性质 二元树 二元树 例9-19 例 例 树的遍历 1、先根算法(前序遍历法) (1) 访问二元树树根r； (2) 如果r有左儿子，那么又以先根算法遍访r的左子树； (3) 如果r有右儿子，那么又以先根算法遍访r的右子树. 树的遍历 2、中根