基本数学模型-匹配.pptxVIP

运筹与统计匹配 1匹配 的非空子集 称为 的一个匹配（matching），若 中任何两条边在 中均不相邻若 中所有顶点都与匹配 中某条边关联，则称 为完美匹配（perfect matching） 图中边数最多的匹配称为最大基数匹配，赋权图中总权重最大的匹配称为最大权匹配，赋权图中总权重最小的完美匹配称为最小权完美匹配完美匹配最大基数匹配 2匹配最大基数匹配最大权匹配二部图 任意图Egervary，1931Kuhn，1955Edmonds，1965Edmonds，1965Jack Edmonds（1934－ ）加拿大数学家完全二部图的最小权完美匹配＝指派问题Edmonds, J., Paths, trees, and flowers.?Canadian Journal of Mathematics, 17, 449–467, 1965Edmonds, J., Maximum matching and a polyhedron with 0,1-vertices.?Journal of Research National Bureau of Standards B,?69, 125–130, 1965Blossom Algorithm 3Hall定理 设 为二部图，则 存在匹配 ，使得 中的任一个顶点均与 中某条边关联的充要条件是 这里 为 中所有与 相邻的顶点集合将52张扑克牌分成13叠，必可从每一叠中抽出一张，使得抽出的13张牌包含所有点数 Philip Hall（1904－1982）英国数学家 4相异代表元系设有 元集合 ， 是 的 个子集。若存在 中 个互不相同的元素 ，使得 ，则称 为 的一个相异代表元系（system of distinctive representation，SDR）子集族 存在SDR，当且仅当 5图－集合－矩阵 6Frobenius定理 设 为二部图，则 有完美匹配 的充要条件是 且对任意 或 ，均有 Ferdinand Georg Frobenius（1849－1917）德国数学家