计算机问题求解-论题3-12 图中的匹配与因子分解 2020-12-2
计算机问题求解---论题3-12 图中的匹配与因子分解 2020-12-2
问题1：如何用图模型表达以下问题及其解？ There is a related mathematical question here.Let U and W be two sets.Does there exist a one-to-one function f:U>W? lU<=|W What if the image of each element of U cannot be just any element of W? G: B M
问题1:如何用图模型表达以下问题及其解？ • There is a related mathematical question here. Let U and W be two sets. Does there exist a one-to-one function f : U → W ? • What if the image of each element of U cannot be just any element of W? |U|<=|W|
什么是matching？Match的核心概念是什么？ a d h t Q 0 R A B D (a) (b) Figure 8.2:A matching in a bipartite graph 独立边集是匹配的核心概念
什么是matching？Match的核心概念是什么？ 独立边集是匹配的核心概念
匹配、极大匹配、最大匹配、完美匹配 问题2：你能用集合论里面的基本概念解 释匹配？极大匹配？完美匹配吗？ NA e V1 es 6
匹配、极大匹配、最大匹配、完美匹配 v1 v2 v3 v4 v5 v6 e1 e4 e2 e3 e5 v1 v2 v3 v4 v5 v6 e1 e4 e2 e3 e5 v1 v2 v3 v4 v5 v6 e1 e4 e2 e3 e5 问题2：你能用集合论里面的基本概念解 释匹配？极大匹配？完美匹配吗？
二部图中最大匹配的存在性 Theorem 8.3 Let G be a bipartite graph with partite sets U and W such that r=Us W.Then G contains a matching of cardinality r if and only if G satisfies Hall's condition. 必要性： G B F K L M
二部图中最大匹配的存在性 必要性：
Theorem 8.3 Let G be a bipartite graph with partite sets U and W such that r=Us W.Then G contains a matching of cardinality r if and only if G satisfies Hall's condition. ·奠基：U川=1，显然 你能想到用数学归纳 法证明吗？ ·假设：U川ISl。H是否满足Hall条件 ·2,如果有U的某个真子集s,IN(S)川=|Sl。H是否满足Hall条件 ·如果满足Ha条件，找到这个最大匹配'，加上uw,就是归纳结论
• 奠基: |U|=1,显然 • 假设:|U||S|。H是否满足Hall条件 • 2，如果有U的某个真子集S，|N(S)|=|S|。H是否满足Hall条件 • 如果满足Hall条件，找到这个最大匹配M’，加上uw，就是归纳结论 你能想到用数学归纳 法证明吗？
Theorem 8.3 Let G be a bipartite graph with partite sets U and W such that r=Us W.Then G contains a matching of cardinality r if and only if G satisfies Hall's condition. ·归纳：当US引 取U中某个元素u,任取u的某个相邻元素w(u至少和 两个元素相邻) W · 构造H:G-{u,w,任取s子集，N(S)数量最多减少一个 均有H中的|N(S)川>=IS| 如果某个S,|N(S)川=S,上述推理哪里过不去？
U W S u S W • 归纳：当|U||S| • 取U中某个元素u，任取u的某个相邻元素w(u至少和 两个元素相邻) • 构造H:G-{u,w}, 任取S子集，N(S)数量最多减少一个 • 均有H中的|N(S)|>=|S| 如果某个S，|N(S)|=|S|，上述推理哪里过不去？
Theorem 8.3 Let G be a bipartite graph with partite sets U and W such that r=Us W.Then G contains a matching of cardinality r if and only if G satisfies Hall's condition. ·Case2:存在一个U的真子集X,IN(X)川=X ·X和N()之间满足Hal条件，经归纳假设，存在最大匹配M' ·构造H子图：U-X和W-N(X),尝试证明H满足HaII条件 ·任取U-X中的子集s,H图中s'=NS)n(W-N() W ·1S1=|XUs|(Hall条件) N() Si .IN(X)I+S'I=IN(XUS)I>=I XUS I=IXI+ISI ·IN(X)=X ·IsI>=lsl ·H中有最大匹配M” U ·构造G中匹配M'+M
• Case2：存在一个U的真子集X，|N(X)|=|X| • X和N(X)之间满足Hall条件，经归纳假设，存在最大匹配M’ • 构造H子图：U-X和W-N(X)，尝试证明H满足Hall条件 • 任取U-X中的子集S，H图中S’=N(S)∩(W-N(X)) • |S|=| XꓴS | （Hall条件） • |N(X)|+|S’|=|N(X ꓴ S)|>=| XꓴS |=|X|+|S| • |N(X)|=|X| • |S’|>=|S| • H中有最大匹配M’’ • 构造G中匹配M’+M’’ U W X N(X) S S’
这个定理的直观含义是什么？ Theorem 8.4 A collection [SS2....S of nonempty finite sets has a system of distinct representatives if and only if for each integer k with 1 sks n,the union of any k of these sets contains at least k elements. For example,consider the sets SS2,.S,where Hal婚姻定理 S1={1,2,3}S2={2,4,6} S3={3,4,5} S4={1,4,7} S5={1,5,6}S6={3,6,7} S7={2,5,7} Then this collection of sets has a system of distinct representatives.In particular,1,2,..., 7(that is,iS for i=1,2,...,7)is a system of distinct representatives.On the other hand,the sets S1,2...where S1={1,3,5,6} S%={3,4} S3={4,5} S4={3,4,5} S5={1,2,4,6}S%={3,5}, do not have a system of distinct representatives asSS3,4,5 sodistinct representatives do not exist for the sets
这个定理的直观含义是什么？ Hall 婚姻定理
边独立集(Edge Independent Set) ·边独立集(edge independent set)l 匹配 -A set of independent edges of G 0 极大边独立集(maximal edge independent set)极大匹配 一不是任何一个边独立集的真子集 ·最大边独立集(maximum edge independent set)最大匹配 -具有最大势(cardinality)的边独立集 0 边独立数(edge independence number)最大匹配的势 一最大边独立集的势 -a'(G) V, e e N N ea 10
边独立集(Edge Independent Set) 10 v1 v2 v3 v4 v5 v6 e1 e4 e2 e3 e5 v1 v2 v3 v4 v5 v6 e1 e4 e2 e3 e5 v1 v2 v3 v4 v5 v6 e1 e4 e2 e3 e5 匹配 极大匹配 最大匹配 最大匹配的势