资源描述：
《分图、平面图和树王元元》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第九章二分图、平面图和树1重点：二分图及匈牙利算法﹑平面图﹑树掌握二分图及匹配的概念；掌握求最大匹配的匈牙利算法；掌握平面图的概念；掌握平面图的欧拉定理；能够判断简单图是否平面图；掌握两个典型的非平面图：K5和K3,3；了解库拉托夫斯基定理；2重点：二分图及匈牙利算法﹑平面图﹑树掌握无向树的六个等价的定义；掌握无向图的生成树和最小生成树的概念；掌握求最小生成树的kruskal算法；掌握根树的概念；掌握n元树、完全n元树的概念；了解2元树的基本性质。39.1二分图9.1.1二分图的基本概念定义9-1无向图G=称为二分图(bipartitegraph)，如果有非空集
2、合X，Y使X∪Y=V，X∩Y=，且对每一eE，都有e={x,y}，xX，yY。此时常用表示二分图G。若对X中任一x及Y中任一y恰有一边eE，使e={x,y},则称G为完全二分图(completebipartitegraph)。当X=m，Y=n时，完全二分图G记为Km,n。4例9-1简单无向图G是二分图，当且仅当G可二着色。5判断二分图的定理定理9-1无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。推论任何无回路的图均是二分图。6例：7练习六名间谍a,b,c,d,e,f被我捕获，他们分别懂得的语言是a：汉语，法
3、语，日语；b：德语，日语，俄语；c：英语，法语；d：汉语，西班牙语；e：英语，德语；f：俄语，西班牙语。问至少用几个房间监禁他们，才能使同一房间的人不能互相直接对话。8判断二分图的定理作为一种数学模型二分图是十分有用的，许多问题可以用它来刻划。例如“资源分配”、“工作安排”、“人员择偶”等等。但是，利用二分图分析解决这类问题时，还需要有关二分图的另一个概念——匹配。99.1.2匹配定义9-2设G=为二分图，ME。称M为G的一个匹配(matching)，如果M中任何两条边都没有公共端点。M=时称M为空匹配。G的所有匹配中边数最多的匹配称为最大匹配(maxi
4、malmatching)。109.1.2匹配定义9-2如果X中任一顶点均为匹配M中边的端点，那么称M为X-完全匹配(perfectmatching)。如果Y中任一顶点均为匹配M中边的端点，那么称M为Y-完全匹配(perfectmatching)。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配。11例9-2图9-2中各图的红线表示匹配中的边(简称匹配边)。(a)(b)G(c)129.1.2匹配注意：最大匹配总是存在但未必唯一；X(Y)-完全匹配及G的完全匹配必定是最大的，但反之则不然；X(Y)-完全匹配未必存在，存在不唯一。13有四名教师张征、王兴、李忠和赵华，
5、分别派他们教四门课程：数学、物理、电工和计算机导论。张征懂物理和电工；王兴懂数学和计算机导论；李忠懂数学、物理和电工；赵华只懂电工。问应该如何分派，才不会使任何人去讲他不懂的课程而又不存在有的课程无人教？14匹配的应用安排工作：现有6个工人{x1,x2,…,x6},有6项工作{y1,y2,…,y6}。假设在同一时间内，每人只能干一项工作，每项工作只需一个人干，每个工人能干的工作用边来表示。安排工作就是求二分图的一个匹配问题。求最大匹配就是一个工作最佳的安排问题，使尽可能多的人有工作干，尽可能多的工作被人干。15术语介绍定义9-3设G=，M为G的一个匹配。(1
6、)M中边的端点称为M-顶点，其它顶点称为非M-顶点。16术语介绍定义9-3(2)G中vk到vl的通路P称为交替链，如果P的起点vk和终点vl为非M-顶点，而其边的序列中非匹配边与匹配边交替出现(从而首尾两边必为非匹配边，除顶点vk，vl以外各顶点均为M-顶点)。特别地，当一边{v,v'}两端点均为非M-顶点，通路{v,v'}亦称为交替链。17由交替链的定义可以推出下述三个结论：1)P的路径长度必定为奇数，第一条边和最后一条边都不属于M。2)P经过取反操作可以得到一个更大的匹配M′。3)M为G的最大匹配当且仅当不存在相对于M的交替链。18匈牙利算法求最大匹配的一种显而易见的
7、算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。19用交替链求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出)算法轮廓：(1)置M为空(2)找出一条交错链P，通过取反操作获得更大的匹配M′代替M(3)重复(2)操作直到找不出交错链为止匈牙利算法20例9-3用匈牙利算法求图9.3的一个最大匹配。x1x2x3x4x5x6y1y2y3y4y5y6y721x1x2x3x4x5x6y1y2y3y4y5y6y7例9-3用匈牙利算法求图9.3的一个
