匹配的一些结论

• 点覆盖: 在二分图中找到一些点, 使得二分图的每一条边都至少有一个端点在这个点集中, 这个点集称为点覆盖

  • 最小点覆盖

• 独立集: 在二分图中找到一些点, 使得这些点两两之间没有边的存在, 这个点集就叫做独立集

  • 最大独立集: 在一个二分图中, 若一个独立集所包含的点是所有独立集中最多的, 则该独立集为最大独立集

• 路径覆盖: 在有向图中, 找到一些路径, 若这些路径所经过点的并集即为原图的点集, 那么这些路径即构成路径覆盖

  • 最小路径覆盖: 是要找到最少的一些路径完成路径覆盖
    • 最小不相交路径覆盖 ： 就是我们找到的每条路径不能相交，就是每条路径不能有同一个点
    • 最小可相交路径覆盖 ： 这个与上面相对应，就是可以相交

• 链: 在有向无环图中, 是一个点集, 对于集合中任意两点 (x,y), 要么 (x) 可以走到 (y), 要么 (y) 可以走到 (x) ( 即我们平常认知中的链 )

  • 所以说, 上面的路径覆盖又可称链覆盖

• 反链: 在有向无环图中, 是一个点集, 对于集合中任意两点 (x, y)

(x, y) 之间互相无法抵达 ( 长得不像我们平时认知中的链, 而是一些离散的点, 互相之间没有任何联系 )

• 最长反链: 元素个数最多

• (二元) 关系: 一个很玄学的概念, 比如说 (<,le, =,...) , 上面这些都是 (二元) 关系, 应为它是用于二者之间的比较, 好像一般就都是二元关系吧, 当然, 可以自定义二元关系

  当二者存在关系, 我们说它们是可比较的

  当二者不存在关系, 我们说它们是不可比较的

  example: 对于三元组 ((a,b,c)), 对于 ((a,b,c) , (a',b',c')) , 若 $a leq a',bleq b', cleq c' $, 我们可以定义 ((a,b,c) leq (a',b',c'))

• 全序集: 在某一关系下, 集合内任意一对元素可以比较

• 偏序集: 在某一关系下, 存在至少一对元素无法比较

参考:

1. litble学姐课件
2. 一个csdn的博客
3. 一个博客园的博客
4. 可能还有些我参考了, 但是忘记写上来了

(不保证以下证明的正确性)

最小点覆盖 = 二分图的最大匹配

# 证明覆盖

假设有一条边没有被覆盖, 记为 $ (u,v)$

那么 (u,v) 均不在匹配点集中

显然可以把 (u,v) 连上

显然原匹配不是最大匹配

# 证明最小

假设去掉点 (u), 其原对应点为 (v) ( (v) 不在覆盖点集中 )

显然, 对于 ((u,v)) , 那 (v) 必须加入

如果 (v) 加入, 那么匹配点集大小不变

• 注意到, 二分图的最大匹配中, 对于每一条匹配边, 我们只取任一端点放入最小点覆盖的点集 (不把两个端点同时放入)

  
  

最大独立集 = 点的总数 - 最小点覆盖

# 证明最小点覆盖集必须删

若存在一个点 (u) 未被删去, 同时在最小点覆盖集中, 其它非最小点覆盖集中的点存在

那么与它相连的边都存在, 因为没有必要一条边两个点都在 最小点覆盖集 中

既然有边存在, 那就不是独立集

# 证明这为最大独立集

点覆盖集是最小的, 所以这个独立集是最大的

最小不相交路径覆盖

在一个图中, 将每个点拆成两点, 若原图存在边 ((x,y)), 新图中连边 ((x,y'))

那么, 最小不相交路径覆盖 = 原图点数 - 新图最大匹配数

# 证明

先思考对于一个点 (x_0), 将其拆成 (x,x') 是什么含义

对于原图中的一条有向边 ((x,y )), (x) 相当于这条边的起始位置, 而 (y') 相当于这条边的结束位置

我们一开始把每一个点当作一条长度为 (0) 的路径

显然, 对于一个匹配, 我们相当于把两条路径首尾相连

• 首尾相连: 因为根据匹配的性质, 在新图中, 每一个点只可能有一个匹配边, 所以, 我们这个新的匹配一定对应着两个还未匹配的点, 而如果连上的是已经匹配了的点, 那么说明一定有两条路径交于同一点, 而我们这里条论的是 最小不相交路径覆盖

所以, 每一次匹配, 相当于消掉一条路径 ( 二合一 )

显然, 最小不相交路径覆盖 = 原图点数 - 新图最大匹配数

Dilworth定理

偏序集能划分成的最少的全序集个数等于最大反链的元素个数

(什么鬼)

翻一翻前面的定义, 我们可能会我所明白

我们根据关系构建有向图, 然后发现...... ( 注意到关系是可以传递的 )

就是 最小不相交路径覆盖

最长反链 = 最小路径(链)覆盖

由 Dilworth定理 推知 ( 最短证明 )

最长链 = 最小反链覆盖

# 证明

假设有 (5) 条链:

1. - - - - - -
2. - - -
3. - - - - - - - - -
4. - -
5. - - - - -

(比较抽象)

不妨排个序

1. - -
2. - - -
3. - - - - -
4. - - - - - -
5. - - - - - - - - -

对于这 (5) 条链

我们把它们的第一个抽出来 ( 标记为 ~ )

1. ~ -
2. ~ - -
3. ~ - - - -
4. ~ - - - - -
5. ~ - - - - - - - -

显然, 我们可以把这 (5) 个 ~ 合起来作为一条反链

记最长链的长度为 (L)

显然, 按照这种方式, 我们能构造出 (L) 条反链

对于任意一条反链, 我们都无法在给它加点

因为这个点必然属于这 (5) 条链中

而这条反链的所有点各自属于一条链

加入的新点一定与其中一个点产生联系