二分图相关定理及其伪证

• 最小顶点覆盖数 (n) = 最大匹配数 (m)

  1. 对于每组匹配点 ((u, v)), 发现其中只有一个点会连向非匹配点.

     证明: 如果 (u) 连向非匹配点 (x), (v) 连向非匹配点 (y), 那么可以找到增广路 (x->u->v->y). 与匹配最大前提不符.

  2. 考虑构造方案: 对于每组匹配点 ((u, v)), 选取其中连有非匹配点的点加入覆盖, 总数为 (m)

     1. 证明(可行性): 既覆盖了匹配边与非匹配边, 合法.
     2. 证明 (n geq m): 如果 (n < m), 匹配边无法完全覆盖. 故 (n geq m).

  3. 综上, (n = m).

• 最小路径覆盖数 = 顶点数 - 最大匹配数

  1. 首先建图. 考虑拆点, 把每个点 (i) 拆成 (i) 和 (i'), 分别表示每个点的出边和入边. 对于原图的边 ((u -> v)) 在二分图中连 ((u -> v')).

  2. 分析每一个点 (i'). 其作为匹配点表示点 (i) 入度非零. 匹配最大相当于最小化入度为 (0) 的点数. 匹配又保证了是路径覆盖.

     因此, 最小路径覆盖数 = 最少入度为 (0) 点数 = 顶点数 - 最大匹配数.

• 最大独立点集 = 顶点数 - 最小点覆盖

  1. 分析独立点集与点覆盖两者定义. 发现把一个二分图中的点覆盖去掉后就是一个独立点集. 也就是说, 独立点集与点覆盖互为补集.
  2. 因此, 最小化点覆盖相当于最大化独立点集, 即最大独立点集 = 顶点数 - 最小点覆盖.

• (Hall) 定理: 二分图存在完全匹配的充要条件是: 二分图中的集合 (X) 和 (Y) ( (|X| < |Y|) ), (∀ s subseteq X), 以及与 (s) 有连边的集合 (N(s) subseteq Y), 都有 (|s| leq |N(s)|).

  1. 必要性证明: 反证法. 假设有一个二分图存在完全匹配但不满足 (Hall) 定理.

     那么存在一个点集 (s subseteq X), (|N(s)| < |s|). 说明存在 (x in X), 且 (x) 无相连顶点. 与假设矛盾, 因此必要性得证.

  2. 充分性证明: 反证法. 假设有一个二分图，满足 (Hall) 定理但不存在完全匹配.

     说明最大匹配非完全匹配即存在 (x in X) 未匹配. 根据 Hall 定理, (x) 一定至少连向一个点 (y). 若 (y) 未匹配, 则找到了一条增广路, 说明匹配非最大匹配.

     因此 (y) 已匹配. 考虑 (y) 的匹配点 (u), 再次运用 Hall 定理, (|N({x, u})| geq 2), 即 (u) 还与 (Y) 中除 (y) 以外的点有连边......

     这样递归下去, 边界为 (X) 中所有点相连的 (Y) 中的点均已匹配. 与假设矛盾, 因此充分性得证.

• (Dilworth) 定理: 偏序集能划分成的最少的全序集个数 (n) 等于最长反链的元素个数 (m)

  1. 证明: (n geq m) : 最长反链两两元素不可比, 至少都要划分 (m) 个全序集, 因此 (n geq m).

  2. 构造 (n = m) 方案 : 首先划分出 (m) 个全序集, 分别包含一个最长反链上的元素. 考虑新加一个元素, 必定会被 (m) 个全序集中的一个包含.

     • 证明: 假设不被包含, 则说明存在反链元素个数为 (m + 1), 与前提矛盾. 所以新加元素必然被 (m) 个全序集中的一个包含.

     这样每加一个元素就把他扔到 (m) 个全序集中可比的一个, 成功构造出 (n = m) 的方案.

  3. 综上, (Dilworth) 定理成立.