组合数学(第9章9.1).ppt

第九章二分图中的匹配学习内容n9.1 一般问题表述几个问题n问题1 具有禁止位置的非攻击型车： 带有禁止方格的m行n列棋盘能够摆放棋盘上的非攻击型车的最多个数是多少？×××以前对于一些有禁止位置的情况，运用容斥原理已经解决n问题2 具有禁止位置的多米诺牌覆盖： 一个某些方格被禁止的m行n列棋盘使得每一块多米诺牌盖住两个方格，并且没有交叠，最大牌数？ 一个特殊情况：具有禁放方格棋盘的完美覆盖问题n问题3 工作的配对问题： m个人申请担任n项工作，每项工作由1名具有资格的人担任，可以被担任的工作最大数是多少？ 以上这些问题都抽象为同一个数学问题二分图的概念n三元组G=(X, , Y)称为二分图二分图其中： X={x1, x2,…, xm}和Y={y1, y2,…, yn}是两个不相交的集合，即XY=Ø. ={(xi, yj)} 是一些有序对集，称为边的集合，其中xiX, yjYn XY的元素称为二分图G的顶点， 称为G的边。

二分图n二分图是一种特殊的图特殊的图1) 顶点集是两个部分的划分X, Y.2) 每条边分别关联着X和Y的一个顶点nX的元素称为左顶点左顶点，Y的元素称为右顶点x1x2x3x4y1y2y3X={x1, x2, x3, x4}Y={y1, y2, y3}={(x1, y1), (x1, y3), (x2, y1), (x3, y2), (x3, y3), (x4, y3)}二分图的匹配n二分图G=(X, , Y)的匹配定义为的一个子集M，满足M中没有两条边有公共顶点n二分图的匹配一般不是唯一的n每个顶点至多与匹配的一条边关联x1x2x3x4y1y2y3例：例：={(x1, y3), (x2, y1), (x3, y2)}（1）二分图与具禁止位置的棋盘×××××××x1x2x3x4y1y2y3y4y5第i行xi第j行yj每个可以放棋子的方格对应序对(xi, yj)，因此具有禁止位置的(m, n)棋盘对应对应一个二分图G=(X,,Y)二分图与具禁止位置的棋盘×××××××x1x2x3x4y1y2y3y4y5X={x1, x2, x3, x4}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)}x1x2x3x4y2y3y4y1y5匹配与具禁止位置棋盘的非攻击型车摆放×××××××x1x2x3x4y1y2y3y4y5棋盘上非攻击型车与二分图的匹配匹配一一对应一一对应！非攻击型车的个数等于匹配的边数。

x1x2x3x4y2y3y4y1y5任两个车不在任两个车不在同一行和一列同一行和一列任两条边没有任两条边没有公共顶点公共顶点n车车-二分图二分图：G=(X, , Y), 每个车对应二分图的一条边，非攻击型车对应一个匹配n定义：最大匹配边数(G)=max{ |M|: M是G的匹配} 等于G对应的具禁止位置棋盘的非攻击型车的最大数（2）二分图匹配与具禁止位置棋盘的多米若牌覆盖n例：对具有禁止位置的棋盘交错涂成黑、白两种颜色存在多少张多米若牌的覆盖？w1×w2 b1 w3b2w4×w5××b3×b4××w6b5w7b6w1w2w3w4b2b3b4w5w6w7b1b5b6每两个相邻方格对应一条边每两个相邻方格对应一条边n一张多米若牌对应一条边，不交叠的多米若牌集合对应了没有公共顶点的边的集合（即匹配）w1×w2b1 w3b2w4×w5××b3×b4××w6b5w7b6w1w2w3w4b2b3b4w5w6w7b1b5b6因此，覆盖多米若牌最大数等于对应二分图G的匹配最大边数(G)n有禁止位置的m行n列棋盘确定一个二分图G=(X, , Y)（称为多米若二分图）. 其中， X={w1,w2,…,wp}是白方格集合； Y={b1,b2,…,bq}是黑方格集合。

(wi, bj)当且仅当有一张多米若牌可覆盖wi和bj两个方格 不重叠的多米若牌覆盖与多米若二分图G的匹配一一对应问题2等价求(G)注意注意：不是每个二分图都可以对应一个禁止位置棋盘的多米若二分图这与车这与车-二分图不同二分图不同！例(3) 二分图匹配与工作指派 n例：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对应二分图x1x2x3x4y2y3y4y1y5n每项工作只能一个人做，一个工作指派工作指派对应相应二分图的一个匹配 x1  y1 x2  y4 x3  y2 x4  y3x1x2x3x4y2y3y4y1y5匹配工作指派与禁止位置棋盘的非攻击型车布局工作指派与禁止位置棋盘的非攻击型车布局是同一个抽象数学问题是同一个抽象数学问题！小结n二分图是两个不相交集合的关系刻画，一个匹配是一对一的关系。

n禁止位置棋盘的非攻击型车布局和多米若牌覆盖，以及工作指派关系对应同一个数学问题求二分图的最大匹配(G)n如何计算(G)呢？。