匹配问题及算法.pptVIP

图论中的匹配问题及算法 吕长虹 华东师范大学数学系 Email:chlu@math.ecnu.edu.cn 愿天下有情人终成眷属! 图论中的匹配问题(match problem)在组合数学中也称为相异代表系(system of distinct representatives). 用集合的语言描述：给定集合族 A=(A1,A2,A3,…,An)，希望在每一集合Ai 中选出一个元素ai，使得a1,a2,…,an是相 异的n个元素。我们称a=(a1,a2,…,an) 是A的一个相异代表系。 用图的方法描述：每个集合Ai看作一个点，集合中每个元素看作点。如果元素a在集合Ai中，则用线连接aAi。 Example A1={a,b,c} A2={c,d} A3={b,d} A4={c,d} 匹配问题可以有多种解释，可以把它解 释为委员会选派代表问题，可以解释为工作安 排问题，也可以解释为月下老人牵红线的问题 等等。 Ex3 A1={3,4}, A2={3,7,9}, A3={2,3}, A4={6,11,12}, A5={4,6,8}, A6={2,6,9}, A7={3,4,8}, A8={3,5,10,13}, A9={2,3,7,9}, A10={2,8,9} A=(A1,A2,…,A10) 是否存在相异代表系？ 指派问题是在加权完全二部图中找权和最大的完美匹配问题，此问题有著名的匈牙利方法(Kuhn,1955),也是多项式算法，也可转化为0-1规划来解。 * * 如果上帝也懂一点数学… A1 A2 A3 A4 a b c d A1 —— a A2 —— d A3 —— b A4 —— c 完美匹配 Ai——看成是第i个女孩可能托付终身的白马 王子集； 月老的任务是要将每位女孩许配给一位白马 王子，但二女不可同配一夫。 Ai为做第i个工作所合适的人员集合，问题就是 要为每个工作寻找一个工人，但同一人不能做 一个以上的工作。 … … 为了解问题所在，我们看几个例子： EX1 A1={a,b,c}， A2={c,d} A3={b,d}， A4={c,d} 恰有两组相异代表系(a,c,b,d)和(a,d,b,c)。 EX2 A1={a} A2={b}, A3={a,b} A4={c,d,e,f,g,h} A={A1,A2,A3,A4} 没有相异代表系（或不存在一个匹配饱和A）。 答案：不存在相异代表系。因为： A1∪A2∪A3∪A5∪A6∪A7∪A9∪A10 ={2,3,4,6,7,8,9} 八个集合只包含七个元素 所以 不可能找到一个相异代表系。 Hall’s Theorem A=(A1,A3,…,An) 存在一个相异代表系 ?对所有 恒有 证明：必要性显然，现证条件为充分的。 如果对所有 恒有 ，我们 可以假设A是满足这个条件的最小集合族。也 就是，从任何一个Ai中去掉任一个元素所得的 新集合族不再满足上述条件。 首先我们证明：所有Ai恰含一个元素.否则假设 A1含有x及y，但x≠y，则(A1\{x},A2,…,An)和 (A1\{y},A2,…,An}都不满足上述条件，因此存在 下标集I,J {2,3,…,n} 使得 |X|≤|I| 且 |Y|≤|J| 其中 Hall’s Theorem A=(A1,A3,…,An) 存在一个相异代表系 ?对所有 恒有 所以 |I|+|J|≥|X|+|Y| =|X∪Y|+|X