计算机问题求解---论题3-12 图中的匹配与因子分解

Presentation on theme: "计算机问题求解---论题3-12 图中的匹配与因子分解"— Presentation transcript:

1 计算机问题求解---论题3-12 图中的匹配与因子分解

2 问题1:如何用图模型表达以下问题及其解？ |U|<=|W|
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|

3 什么是matching？Match的核心概念是什么？
二部图：f: A ->B 独立边集是匹配的核心概念

4 匹配、极大匹配、最大匹配、完美匹配 问题2：你能用集合论里面的基本概念解释匹配？极大匹配？完美匹配吗？ v2 v3 v4 v2 v3 v4
e1 e4 e2 e3 e5 e1 e2 e3 e1 e2 e3 匹配：A到A上的关系R的子集m：子集中元素的前分量各不相同，后分量各不相同 极大：匹配的基础上，不能再增加任何R中的元素 最大匹配: |m|最大者； 完美：极大匹配基础上，|m|=|A|/2 v1 e4 v1 e5 e4 e5 v5 v6 v5 v6

5 二部图中最大匹配的存在性 必要性： F：A-》B中，如果|A|>|B|,一定不会有单射，也不会有双射；
因此，应该能够想到|X|<=|N(X)|,对任意的U子集X；

6 u 奠基: |U|=1,显然 假设:|U|<=|W|且1<=|U|<k且满足Hall条件时均存在最大匹配
你能想到用数学归纳法证明吗？ 奠基: |U|=1,显然 假设:|U|<=|W|且1<=|U|<k且满足Hall条件时均存在最大匹配 归纳：当k=|U|以及|U|<=|W|且满足Hall条件时 从U任取一个u，从N(u)中任取一个w，构造H:G-{u,w}：H满足Hall条件吗? 如果对U的任意真子集S，|N(S)|>|S|, 是成立的。否则？ Case1：对所有U的真子集S，均有|N(S)|>|S| 取U中某个元素u，取u的相邻元素w(u至少和两个元素相邻) 构造H:G-{u,w}, 任取S子集，N(S)数量最多减少一个 均有H中的|N(S)|>=|S| 按照归纳假设存在H中的最大匹配 U W S u W 问题来源：数学归纳法是图论证明中进行构造证明的重要方法之一。通常对点数、边数、连通子图数、度数等进行归纳。此处采用U的势进行归纳。 分情形证明主要是在将G归纳到假设上的方法不一样：拿去一个w点，和，拿去和S一样多的w点 第二种情形证明中，S在H中的N(S)的计算公式、X和S互不相交。是两个注意点。 现在你能理解为什么在归纳证明中，需要分情形证明了吗？

7 N(X) X Case2：存在一个U的真子集X，|N(X)|=|X| S’ S
X和N(X)之间满足Hall条件，经归纳假设，存在M’完满匹配 构造H子图：U-X和W-N(X)，尝试证明H中有最大匹配 任取U-X中的子集S，H图中S’=N(S)∩(W-N(X)) |S|<=?|S’|吗？ |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’ 问题来源：数学归纳法是图论证明中进行构造证明的重要方法之一。通常对点数、边数、连通子图数、度数等进行归纳。此处采用U的势进行归纳。 分情形证明主要是在将G归纳到假设上的方法不一样：拿去一个w点，和，拿去和S一样多的w点 第二种情形证明中，S在H中的N(S)的计算公式、X和S互不相交。是两个注意点。

8 这个定理的直观含义是什么？ 构造2部图：U是n个集合，W是各个元素。边是集合中含有这个元素。

9 边独立集(Edge Independent Set)
匹配 极大匹配 最大匹配 最大匹配的势 此处𝜶′(𝑮)表示边独立数，和CZ教材中符合不一致 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

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)：最小边覆盖集的势 仔细观察边覆盖数和边独立数，你有什么预感？ 一个有2k个点的连通图，关于边覆盖和边独立，“最好”的现象是什么？

11 边覆盖集与边独立集 本质上，也必须这么多边！ Theorem 8.7 若图G (n 个节点) 不包含孤立点(即δ(G)>0)，则
α’(G)+β’(G)=n。 本质上，也必须这么多边！ 证明概要： 1，β’(G)<=α’(G)+(n-2α’(G))=n-α’(G): 最大边独立集覆盖2α’(G)个点；其余点可由n-2α’(G)条边覆盖 因此：α’(G)+β’(G)<=n 2，X是某个最小边覆盖集，l =|X|=β’(G),观察由X导出的图F 各个连通分量都是星型结构：没有长度超过2的通路 F是一个森林 因此，F由n-l 棵星树构成，从每棵树中取一条边，构成一个边独立集 因此， α’(G)>= n-l α’(G)+β’(G)>=n-l+l = n 不可能有长度大于等于3的通路或回路，否则去掉这条边可以得到更小的边覆盖集 有n个节点、k条边的森林，由n-k棵树构成

12 点独立集 点独立可以用来建什么问题的模型？ 为了关联（带动）所有节点，最少的点运维的代价！再增加一个点，浪费了

13 点覆盖集 点覆盖可以用来建什么问题的模型？ 点覆盖集 (vertex cover)
F是G的点覆盖集：∀(u, v)∈E(G), {u, v}∩F≠∅ 极小点覆盖集 (minimal vertex cover) 顶点数极少（任何一个真子集都不再是点覆盖集） 最小点覆盖集 (minimum vertex cover) 顶点数最少 点覆盖数 (vertex cover number) β(G)：最小点覆盖集的势 为了管理所有边，所需要的最少维护点

14 F是点覆盖集当且仅当V(G)-F是 点独立集
点覆盖集与点独立集什么关系？ F是点覆盖集当且仅当V(G)-F是 点独立集

15 F是点覆盖集当且仅当V(G)-F是点独立集。
点覆盖集与点独立集什么关系？ F是点覆盖集当且仅当V(G)-F是点独立集。 证明： F是点覆盖集 ⇔ G的每条边都有至少一个端点在F中 ⇔ 没有两端点都在V(G)-F中的边 ⇔ V(G)-F是点独立集

16 点覆盖集与独立集 (续) 推论 F是极小点覆盖集当且仅当V(G)-F是极大点独 立集。 证明： F是点覆盖集当且仅当V(G)-F是点独立集
F是极小点覆盖集 ⇔ F中去除任意一些点就会将至 少一条边的两个端点都去除 ⇔ V(G)-F中加入任意 一些点就会将至少一条边的两个端点都加入 ⇔ V(G)-F是极大点独立集

17 点覆盖集与独立集 (续) Gallai恒等式

18

19 边集的一个子集, 其中没有任何两条边有公共顶点
i1 i2 i3 i4 j1 j2 j3 j4 边集的一个子集, 其中没有任何两条边有公共顶点

20 因子分解(Factorization) k-因子 (k-factor) 1-因子对应什么？ 可k-因子分解的 (k-factorable)
图G的k-正则生成子图（k-regular spanning subgraph） 1-因子对应什么？ 完美匹配 可k-因子分解的 (k-factorable) 图G有一组k-因子的边集构成E(G)的一个划分 = ∪

21 这个图为什么不可能有完美匹配？ V的某个匹配会导致某个分支是奇数点

22 奇分支

23 有完美匹配的充要条件(Tutte,1947) 一个 奇分支 一个 奇分支 其它偶分支 S

24 有完美匹配的充分条件证明基本思路 S 数学归纳法：对G的点数进行归纳 Gi G2 G1 通常的思路归纳时会遇到的困难： Gk
R:从每个偶分量中去掉一个非割点的点 则可得到一个odd 分支； 因此，必须进行S的特定构造，以保证： 各个奇分支都能够被S消化掉！ Gi中去掉一个点，满足基本条件！

25 有完美匹配的充要条件 (续) S一定存在？ Base case: n=2, G=K2, 显然成立
Base case: n=2, G=K2, 显然成立 R:从每个偶分量中去掉一个非割点的点 则可得到一个odd 分支； S一定存在？ Corollary5.6: every nontrivial connected graph contains at least two vertices that are not cut-vertices

26 有完美匹配的充要条件 (续) … … G2 Gk G1 Theorem 8.4 u1 u2 uk v1 v2 vk
由于G的所有Component都是偶分支, 所以 𝑆_𝑖非空 Gi中为原先某个偶分支去掉奇数个(至少1个)节点（属于S）而得到的；故一定存在属于S的节点与Gi 相接 Theorem 8.4 a collection {𝑆_1,𝑆_2,…,𝑆_𝑛}of nonempty finite sets has a system of distinct representatives if and only if for each integer k with 1≤𝑘≤𝑛, the union of any k of these sets contains at least k elements. Theorem 8.4 u1 u2 G2 uk Gk … G1 v1 v2 vk …

27 在推导公式中：S的特殊性导致K_o(G-S)=|S|；K_o(Gi-Ui-W)>=|W|+2
有完美匹配的充要条件 (续) 由于G的所有Component都是偶分支, 所以 𝑆_𝑖非空 Gi中为原先某个偶分支去掉奇数个(至少1个)节点（属于S）而得到的；故一定存在属于S的节点与Gi 相接 Theorem 8.4 a collection {𝑆_1,𝑆_2,…,𝑆_𝑛}of nonempty finite sets has a system of distinct representatives if and only if for each integer k with 1≤𝑘≤𝑛, the union of any k of these sets contains at least k elements. 在推导公式中：S的特殊性导致K_o(G-S)=|S|；K_o(Gi-Ui-W)>=|W|+2 u2 G2 … u1 G1 uk Gk v1 v2 vk …

28 Open topics 请证明定理8.8。在证明中，请你给出以下思考：关于点覆盖/独 立的所有相关定理，是否在边覆盖/独立讨论范畴内，均有相应的 定理？你能“杜撰”出几条吗？