离散数学课件：6-1-1 特殊的图

1、第6章 特殊的图 6.1 二部图6.2 欧拉图6.3 哈密顿图6.4 平面图 6.1 二部图 n在实际工作中可能会遇到一类问题：n单位有不同类型的工作空缺，也有一群填补空缺的应单位有不同类型的工作空缺，也有一群填补空缺的应征者，每个人能胜任其中的某些工作，如何聘任应征征者，每个人能胜任其中的某些工作，如何聘任应征者，使得被聘任的人得到他适合的工作岗位。者，使得被聘任的人得到他适合的工作岗位。n在在CBA联赛中，如何把参赛队配对？联赛中，如何把参赛队配对？n学校有多个社团，各学生可参加多个社团，若社长不学校有多个社团，各学生可参加多个社团，若社长不可兼任，在什么情况下可选出合法的社长？可兼任，在

2、什么情况下可选出合法的社长？n 这些都涉及到匹配问题。x y za b c d二部图 n定义定义 设无向图 G=,n若能将若能将V 分成分成V1 和和 V2 (V1 V2=V, V1 V2=), 使得使得G中中的每边的两个端点一个属于的每边的两个端点一个属于V1, 另一个属于另一个属于V2, 则称则称G为为二部图二部图, 记为记为, 称称V1和和V2为为互补顶点子集互补顶点子集. 完全二部图 n 定义定义 设无向图 G=,n若能将若能将V 分成分成V1 和和 V2 (V1 V2=V, V1 V2=), 使得简单使得简单图图G中的每边的两个端点都一个属于中的每边的两个端点都一个属于V1, 另一个

3、属于另一个属于V2, 且且V1中每个顶点均与中每个顶点均与V2中每个顶点都相邻中每个顶点都相邻, 则称则称G为为完完全二部图全二部图, 记为记为Kr,s, 其中其中r =|V1|, s=|V2|. n 注意注意: n 阶零图为二部图阶零图为二部图. K3,3K2,3二部图的判别法 例例: : 下述各图是否是二部图下述各图是否是二部图? ? 定理定理 无无向图向图G=是二部图当且仅当是二部图当且仅当G中中无奇无奇长度的回路。长度的回路。 不是不是匹配 设设G=n 匹配匹配(边独立集边独立集): 任任2条边均条边均不相邻不相邻的边子集。的边子集。n 极大匹配极大匹配: 添加任一条边后都不再是匹配的

4、边子集。添加任一条边后都不再是匹配的边子集。n 最大匹配最大匹配: 边数最多的匹配。边数最多的匹配。n匹配数匹配数: : 最大匹配中的边数最大匹配中的边数, 记为记为 1 n 例求下面例求下面 3个图中匹配数个图中匹配数n匹配数匹配数 依次为依次为3, 3, 4. 匹配 设M为G中一个匹配n vi与vj被M匹配: (vi,vj)Mn v为M饱和点: M中有边与v关联n v为M非饱和点: M中没有边与v关联n M为完美匹配: G的每个顶点都是M饱和点 n 例 关于M1, a,b,e,d是饱和点 f,c是非饱和点 M1不是完美匹配 M2是完美匹配是完美匹配二部图中的匹配 n定义定义 设设G=为二部

5、图为二部图, n|V1| |V2|, M是是G中最大匹配中最大匹配, 若若V1中顶点全是中顶点全是M饱和饱和点点, 则称则称M为为G中中V1到到V2的的完备匹配完备匹配.n 当当|V1|=|V2|时时, 完备匹配变成完备匹配变成完美匹配完美匹配.n例：图中红边组成各图的一个匹配，(1)(2)(3) 是完备匹配是完备匹配, , 但不是完美匹配但不是完美匹配是最大匹配是最大匹配不是不是完备匹配完备匹配, , 图中无完备匹配图中无完备匹配是完美匹配是完美匹配Hall定理 nHall定理：定理：设二部图设二部图G=中，中，|V1| |V2|. G中存在从中存在从V1到到V2的的完备匹配完备匹配当且仅当

6、当且仅当V1中任意中任意k个顶点至少与个顶点至少与V2中的中的k个顶点相邻个顶点相邻(k=1,2,|V1|)n 由Hall定理不难证明, 下图(2)没有完备匹配. (1)(2)(3)相异性条件相异性条件二部图完备匹配判定的充分条件 n定理定理 设二部图设二部图G=中中, 若若t 0, 使得使得nV1中每个顶点中每个顶点至少至少关联关联 t 条边，条边，nV2中每个顶点中每个顶点至多至多关联关联 t 条边，条边，则则G中存在中存在V1到到V2的完备匹配。的完备匹配。 (1)(2)(3)完备匹配的条件完备匹配的条件 V1中中k个顶点个顶点至少至少关联关联 kt 条边，这条边，这 kt 条边条边至少

7、至少关联关联 V2中中k个顶点，个顶点， 即即V1中任意中任意k个顶点至少邻接个顶点至少邻接V2中的中的k个顶点个顶点. t 条件条件二部图的应用实例1 n 某课题组要从a, b, c, d, e 这5人中派3人分别到上海、广州、香港去开会。已知：a只想去上海，只想去上海，b只想去广州，只想去广州，c, d, e都表示想去广州或香港都表示想去广州或香港. 问该课题组在满足个人要求的条件下，共有几种派遣方案？ 解：解： 令G=, 其中 V1=s, g, x, V2=a, b, c, d, e, E=(u,v) | u V1, v V2, v想去想去u,其中其中s, g, x分别表示上海、广州和香港分别表示上海、广州和香港. G 满足满足相异性条件相异性条件，因而可给，因而可给 出派遣方案，出派遣方案， 相当于求相当于求完备匹配数完备匹配数， 共有共有9种派遣方案种派遣方案二部图的应用实例2n 证明：在88的国际象棋棋盘的一条主对角线上移去两端的方格后，所得棋盘不能用12的长方形不重叠地填满。n 证：作二部图G=如下： V1=v | v 位于白格内位于白格内, V2=v | v 位于黑格位于黑格内内, E=(u,v)|