《组合数学(第9章9.1).ppt》由会员分享，可在线阅读，更多相关《组合数学(第9章9.1).ppt（18页珍藏版）》请在装配图网上搜索。
1、第九章二分图中的匹配,学习内容,9.1 一般问题表述,几个问题,问题1 具有禁止位置的非攻击型车： 带有禁止方格的m行n列棋盘。能够摆放棋盘上的非攻击型车的最多个数是多少？,以前对于一些有禁止位置的情况，运用容斥原理已经解决。,问题2 具有禁止位置的多米诺牌覆盖： 一个某些方格被禁止的m行n列棋盘。使得每一块多米诺牌盖住两个方格，并且没有交叠，最大牌数？ 一个特殊情况：具有禁放方格棋盘的完美覆盖问题。,问题3 工作的配对问题： m个人申请担任n项工作，每项工作由1名具有资格的人担任，可以被担任的工作最大数是多少？ 以上这些问题都抽象为同一个数学问题。,二分图的概念,三元组G=(X, , Y)称
2、为二分图。其中： X=x1, x2, xm和Y=y1, y2, yn是两个不相交的集合，即XY=. =(xi, yj) 是一些有序对集，称为边的集合，其中xiX, yjY。 XY的元素称为二分图G的顶点， 称为G的边。,二分图,二分图是一种特殊的图 1) 顶点集是两个部分的划分X, Y. 2) 每条边分别关联着X和Y的一个顶点。 X的元素称为左顶点，Y的元素称为右顶点。,x1,x2,x3,x4,y1,y2,y3,X=x1, x2, x3, x4,Y=y1, y2, y3,=(x1, y1), (x1, y3), (x2, y1), (x3, y2), (x3, y3), (x4, y3),二分
3、图的匹配,二分图G=(X, , Y)的匹配定义为的一个子集M，满足M中没有两条边有公共顶点。 二分图的匹配一般不是唯一的。 每个顶点至多与匹配的一条边关联。,x1,x2,x3,x4,y1,y2,y3,例：,=(x1, y3), (x2, y1), (x3, y2),（1）二分图与具禁止位置的棋盘,x1,x2,x3,x4,y1,y2,y3,y4,y5,第i行,xi,第j行,yj,每个可以放棋子的方格对应序对(xi, yj)，因此具有禁止位置的(m, n)棋盘对应一个二分图G=(X,Y),二分图与具禁止位置的棋盘,x1,x2,x3,x4,y1,y2,y3,y4,y5,X=x1, x2, x3, x
4、4,Y=y1, y2, y3 , y4 , y5,=(x1, y1), (x1, y3), (x1, y4), (x1, y5), (x2, y1), (x2, y2), (x2, y3), (x2, y4), (x3, y), (x3, y4), (x4, y2), (x4, y3), (x4, y4), (x4, y5),x1,x2,x3,x4,y2,y3,y4,y1,y5,匹配与具禁止位置棋盘的非攻击型车摆放,x1,x2,x3,x4,y1,y2,y3,y4,y5,棋盘上非攻击型车与二分图的匹配一一对应！非攻击 型车的个数等于匹配的边数。,x1,x2,x3,x4,y2,y3,y4,y1,y
5、5,任两个车不在同一行和一列,任两条边没有公共顶点,车-二分图：G=(X, , Y), 每个车对应二分图的一条边，非攻击型车对应一个匹配。 定义：最大匹配边数 (G)=max |M|: M是G的匹配 等于G对应的具禁止位置棋盘的非攻击型车的最大数。,（2）二分图匹配与具禁止位置棋盘的多米若牌覆盖,例：对具有禁止位置的棋盘交错涂成黑、白两种颜色。存在多少张多米若牌的覆盖？,w1,w2,w3,w4,b2,b3,b4,w5,w6,w7,b1,b5,b6,每两个相邻方格对应一条边,一张多米若牌对应一条边，不交叠的多米若牌集合对应了没有公共顶点的边的集合（即匹配）。,w1,w2,w3,w4,b2,b3,
6、b4,w5,w6,w7,b1,b5,b6,因此，覆盖多米若牌最大数等于对应二分图G的匹配最大边数(G)。,有禁止位置的m行n列棋盘确定一个二分图G=(X, , Y)（称为多米若二分图）. 其中， X=w1,w2,wp是白方格集合； Y=b1,b2,bq是黑方格集合。 (wi, bj)当且仅当有一张多米若牌可覆盖wi和bj两个方格。 不重叠的多米若牌覆盖与多米若二分图G的匹配一一对应。问题2等价求(G)。,注意：不是每个二分图都可以对应一个禁止位置棋盘的多米若二分图。这与车-二分图不同！,例(3) 二分图匹配与工作指派,例：4个人x1, x2, x3, x4申请5项工作y1, y2, y3, y4, y5。设有对应关系： x1适合y1, y3, y4, y5； x2适合y1, y2, y4； x3适合y2, y4； x4适合y2, y3, y4, y5,对应二分图,每项工作只能一个人做，一个工作指派对应相应二分图的一个匹配。 x1 y1 x2 y4 x3 y2 x4 y3,x1,x2,x3,x4,y2,y3,y4,y1,y5,匹配,工作指派与禁止位置棋盘的非攻击型车布局是同一个抽象数学问题！,小结,二分图是两个不相交集合的关系刻画，一个匹配是一对一的关系。 禁止位置棋盘的非攻击型车布局和多米若牌覆盖，以及工作指派关系对应同一个数学问题求二分图的最大匹配(G)。 如何计算(G)呢？,
组合数学(第9章9.1).ppt
