南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）图中的匹配与覆盖

计算机问题求解-论题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(an element of one prescibed subset of W)? 二部图：独立边！

问题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 (an element of one prescibed subset of W)? |U|<=|W| 二部图：独立边！

什么是matching？Match的核心概念是什么？ By a matching in a graph G,we mean an independent set of edges in G. a d h A B 品 (a） (b) Figure 8.2:A matching in a bipartite graph 独立边集是匹配的核心概念

什么是matching？Match的核心概念是什么？ 独立边集是匹配的核心概念 By a matching in a graph G, we mean an independent set of edges in G

匹配、极大匹配、最大匹配、完美匹配 问题2：你能用集合论里面的基本概念解释 匹配？极大匹配？最大匹配？完美匹配吗？ e e e N es 6 6 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. For a nonempty set X of U the neighborhood MX)of X is the union of the neighborhoods Mx).Equivalently,MX)consists of all those vertices of W that are the neighbors of one or more vertices in X.The graph G is said to satisfy Hall's condition if MX) for every nonempty subset Xof U

二部图中最大匹配的存在性 For a nonempty set X of U, the neighborhood N(X) of X is the union of the neighborhoods N(x). Equivalently, N(X) consists of all those vertices of W that are the neighbors of one or more vertices in X. The graph G is said to satisfy Hall’s condition if |N(X)| ≥ |X| for every nonempty subset X of U

二部图中最大匹配的存在性 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 D F K L M

二部图中最大匹配的存在性 必要性：

Theorem 8.3 Let G be a bipartite graph with partite sets U and W such that r=U W.Then G contains a matching of cardinality r if and only if G satisfies Hall's condition. 你能想到用数学归纳 ·奠基：U川=1，显然 法证明吗？ ·假设：U川IS引。 ·2,如果有U的某个真子集S,IN(S)川=|S。 ·分别构造上述两种情况下的最大匹配 请注意：为什么我们 要区分这两种情形？

• 奠基: |U|=1,显然 • 假设:|U||S|。 • 2，如果有U的某个真子集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. ·归纳：当U川lS ·取U中某个元素u,任取u的某个相邻元素w(u至少和 两个元素相邻) ·构造H:G-{u,w,任取S子集，N(S)数量最多减少一个 W ·均有H中的IN(S)川>=|S H满足Hal条件，找到H中的最大匹配M',加上uw, 就是归纳结论 如果某个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| • H满足Hall条件，找到H中的最大匹配M’，加上uw， 就是归纳结论 如果某个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(X) W ·1S1=|XUsI(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’ M’

这个定理的直观含义是什么？ 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 婚姻定理