组合数学〔第9章9.1〕.pptVIP

第九章二分图中的匹配 学习内容 9.1 一般问题表述 几个问题 问题1 具有禁止位置的非攻击型车： 带有禁止方格的m行n列棋盘。能够摆放棋盘上的非攻击型车的最多个数是多少？ 问题2 具有禁止位置的多米诺牌覆盖： 一个某些方格被禁止的m行n列棋盘。使得每一块多米诺牌盖住两个方格，并且没有交叠，最大牌数？ 一个特殊情况：具有禁放方格棋盘的完美覆盖问题。 问题3 工作的配对问题： m个人申请担任n项工作，每项工作由1名具有资格的人担任，可以被担任的工作最大数是多少？ 以上这些问题都抽象为同一个数学问题。 二分图的概念 三元组G=(X, ?, Y)称为二分图。其中： X={x1, x2,…, xm}和Y={y1, y2,…, yn}是两个不相交的集合，即X?Y=?. ?={(xi, yj)} 是一些有序对集，称为边的集合，其中xi?X, yj?Y。 X?Y的元素称为二分图G的顶点， ?称为G的边。 二分图 二分图是一种特殊的图 1) 顶点集是两个部分的划分X, Y. 2) 每条边分别关联着X和Y的一个顶点。 X的元素称为左顶点，Y的元素称为右顶点。 二分图的匹配 二分图G=(X, ?, Y)的匹配定义为?的一个子集M，满足M中没有两条边有公共顶点。 二分图的匹配一般不是唯一的。 每个顶点至多与匹配的一条边关联。 （1）二分图与具禁止位置的棋盘 二分图与具禁止位置的棋盘 匹配与具禁止位置棋盘的非攻击型车摆放 车-二分图：G=(X, ?, Y), 每个车对应二分图的一条边，非攻击型车对应一个匹配。 定义：最大匹配边数 ?(G)=max{ |M|: M是G的匹配} 等于G对应的具禁止位置棋盘的非攻击型车的最大数。 （2）二分图匹配与具禁止位置棋盘的多米若牌覆盖 例：对具有禁止位置的棋盘交错涂成黑、白两种颜色。存在多少张多米若牌的覆盖？ 一张多米若牌对应一条边，不交叠的多米若牌集合对应了没有公共顶点的边的集合（即匹配）。 有禁止位置的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 小结 二分图是两个不相交集合的关系刻画，一个匹配是一对一的关系。 禁止位置棋盘的非攻击型车布局和多米若牌覆盖，以及工作指派关系对应同一个数学问题求二分图的最大匹配?(G)。 如何计算?(G)呢？ * * × × × 以前对于一些有禁止位置的情况，运用容斥原理已经解决。 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)} x1 x2 x3 x4 y1 y2 y3 例： ?={(x1, y3), (x2, y1), (x3, y2)} × × × × × × × 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, 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