资源描述:
《分图、平面图和树王元元》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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的一个