计算机问题求解-论题3-12 图中的匹配与因子分解 2018-11-29
计算机问题求解---论题3-12 图中的匹配与因子分解 2018-11-29
问题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=U W.Then G contains a matching of cardinality r if and only if G satisfies Hall's condition. ·奠基：U川=1，显然 你能想到用数学归纳 法证明吗？ ·假设：U川ISL,是成立的。否则？ W ·Case1:对所有U的真子集S,均有|N(S)川>SI ·取U中某个元素u,取u的相邻元素w(u至少和两个元素相邻) ·构造H:G-u,w,任取S子集，N(S)数量最多减少一个 ·均有H中的IN(S)川>=|S ·按照归纳假设存在H中的最大匹配 现在你能理解为什么在归纳证明中，需要分 情形证明了吗？
U W S u S W • 奠基: |U|=1,显然 • 假设:|U||S|, 是成立的。否则？ • Case1：对所有U的真子集S，均有|N(S)|>|S| • 取U中某个元素u，取u的相邻元素w(u至少和两个元素相邻) • 构造H:G-{u,w}, 任取S子集，N(S)数量最多减少一个 • 均有H中的|N(S)|>=|S| • 按照归纳假设存在H中的最大匹配 你能想到用数学归纳 法证明吗？ 现在你能理解为什么在归纳证明中，需要分 情形证明了吗？
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条件，经归纳假设，存在W完满匹配 ·构造H子图：U-X和W-N(X),尝试证明H中有最大匹配 ·任取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+SI IN(X)I=|X刈 ·IsI>=lsl ·H中有最大匹配M” U ·构造G中匹配M'+
• Case2：存在一个U的真子集X，|N(X)|=|X| • X和N(X)之间满足Hall条件，经归纳假设，存在M’完满匹配 • 构造H子图：U-X和W-N(X)，尝试证明H中有最大匹配 • 任取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 [S,S2,...S of nonempty finite sets has a system of distinct representatives if and only if for each integer k with 1 sksn,the union of any k of these sets contains at least k elements. For example,consider the sets S,S2,....S,where 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 sets2where S1={1,3,5,6} S%={3,4 Sg={4,5} S4={3,4,5} Sg={1,2,4,6}S%={3,5} do not have a system of distinct representatives as S2U{3,4,5 so distinct representatives do not exist for the sets
这个定理的直观含义是什么？
边独立集(Edge Independent Set) ·边独立集(edge independent set)I 匹配 A set of independent edges of G · 极大边独立集(maximal edge independent set)极大匹配 一不是任何一个边独立集的真子集 ·最大边独立集(maximum edge independent set)最大匹配 -具有最大势(cardinality)的边独立集 · 边独立数(edge independence number)最大匹配的势 一最大边独立集的势 -a'(G) V> e e, e e V e V6 9
边独立集(Edge Independent Set) 9 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 匹配 极大匹配 最大匹配 最大匹配的势
边覆盖集(Edge Cover) ·边覆盖集(edge cover) ·L是G的边覆盖集：u∈V(G),v∈V(G),(u,v)∈L ·隐含要求：G中无孤立顶点，即6(G>0 仔细观察边覆 ·极小边覆盖集(minimal edge cover) 盖数和边独立 ·边数极少（任何一个真子集都不再是边覆盖集） ·最小边覆盖集(minimum edge cover) 数，你有什么 ·边数最少 预感？ ·边覆盖数(edge cover number) ·'(G:最小边覆盖集的势 10
边覆盖集(Edge Cover) • 边覆盖集(edge cover) • L是G的边覆盖集：∀u∈V(G), ∃v∈V(G), (u, v)∈L • 隐含要求：G中无孤立顶点，即δ(G)>0 • 极小边覆盖集(minimal edge cover) • 边数极少（任何一个真子集都不再是边覆盖集） • 最小边覆盖集(minimum edge cover) • 边数最少 • 边覆盖数(edge cover number) • β’(G)：最小边覆盖集的势 10 仔细观察边覆 盖数和边独立 数，你有什么 预感？