最优匹配.ppt

??的一个匹配。是中均不邻接,则称边在中任意两条若设图定义 GM G M EM,,E V, G 2??(或対集 Matching) 定义 3若匹配 M的某条边与点 v关联, 则称 M饱和点v, 并且称 v是M的饱和点, 否则称 v是M的非饱和点. 定义 4设M是图 G的一个匹配, 如果 G的每一个点都是 M的饱和点, 则称 M是完美匹配;如果 G中没有另外的匹配 M 0, 使| M 0 |>| M |, 则称 M是最大匹配. 每个完美匹配都是最大匹配, 反之不一定成立. 例16:判断下图的匹配最大匹配非完美匹配完美匹配定义 5设M是图 G的的一个匹配, 其边在 E\M和M 中交错出现的路, 称为 G的一条 M–交错路. 起点和终点都不是 M的饱和点的 M –交错路, 称为 M –增广路. Berge 定理: G的一个匹配 M是最大匹配的充要条件是 G不包含 M –增广路. 定义设V=X∪ Y 且X∩Y =?, E ?{xy|x∈X,y∈Y}, 称G =( X, Y, E). 如果 X中的每个点都与 Y中的每个点邻接,则称G =( X, Y, E)为完全二部图. 若F:E→ R +,则称 G =( X, Y, E, F ) A =(a ij ) |X|×| Y |, 其中 a ij = F (x i y j ). 注意:此赋权矩阵与图的邻接矩阵不同! X: x1 x2 x3 Y: y1 y2 6 3 4 8 1 2 123 6 0 3 4 8 0 y y x A x x ? ?? ??? ?? ?? ? 1 2 3 1 2 12312 0 0 0 6 0 0 0 0 3 4 0 0 0 8 0 6 3 8 0 0 0 4 0 0 0 x x x y y xxAxyy ? ?? ?? ?? ??? ?? ?? ?? ?邻接矩阵二部图赋权矩阵邻接矩阵 1 2 123 6 0 3 4 8 0 y y x A x x ? ?? ??? ?? ?? ?二部图赋权矩阵 Hall 定理设G = ( X, Y, E )为二部图, 则①G存在饱和 X的每个点的匹配的充要条件是对任意 S,有| N ( S ) | ≥ | S | . 其中, N ( S ) = { v | u∈S, v与u相邻}. ②G存在完美匹配的充要条件是对任意 S 或 S 有| N ( S ) | ≥ | S | . X?X? Y?二部图的匹配及其应用工作安排问题之一给n个工作人员 x 1, x 2, …, x n安排 n项工作 y 1, y 2, …, y n. n个工作人员中每个人能胜任一项或几项工作, 但并不是所有工作人员都能从事任何一项工作. 比如 x 1能做 y 1, y 2工作, x 2能做 y 2, y 3, y 4工作等. 这样便提出一个问题, 对所有的工作人员能不能都分配一件他所能胜任的工作? 二部图的匹配及其应用我们构造一个二部图 G = ( X, Y, E ), 这里 X = { x 1, x 2, …, x n },Y = { y 1, y 2, …, y n }, 并且当且仅当工作人员 x i胜任工作 y j时, x i与y j才相邻. 于是, 问题转化为求二部图的一个完美匹配. 因为|X |=|Y |, 所以完美匹配即为最大匹配. 二部图的匹配及其应用问题:如何求出二部图的一个完美匹配? 1965 年匈牙利人 Edmonds 基于 Hall 定理提出一个算法,一般称为匈牙利( Hungarian )算法匈牙利算法思路