Hall定理/正则二部图完美匹配

本文主要是介绍Hall定理/正则二部图完美匹配，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

相异代表系

设 \(S_1,S_2,\cdots,S_m\) 是一族集合，它们的一个相异代表系为一个 \(m\) 维向量 \((x_1,x_2,\cdots,x_m)\)

满足：

• 代表性：\(x_i\in S_i\)
• 互异性：\(\forall i\ne j,x_i\ne x_j\)

相异代表系也简称为SDR

对于一族指标 \(J\subseteq[m]\)，我们定义它们的并 \(\text{union}(J)\) 为：

Hall定理

有限集族 \(S_1,S_2,\cdots,S_m\) 存在SDR当且仅当HC成立，其中HC：\(\forall J\subseteq[m],|\text{union}(J)|\ge|J|\)

（严谨性未知）

笔者口胡的反证法：如果一个集合满足HC但是不存在SDR，那么一定存在一个 \(S_i\)，其中的元素无法选择，并且对于 \(j\ne i\)，\(S_j\) 中选择的元素无法更换，因为如果可以更换，那么我们相应的更换 \(S_k,k\ne j,k\ne i\) 中的元素，直到更换至 \(S_i\)，即存在SDR，此时我们不选择 \(S_i\)，余下的集族不满足HC，矛盾

（正规证明）

使用数学归纳法：

定义一个指标族 \(J\) 临界，若 \(\{S_j:j\in J\}\) 存在SDR，并且 \(|\text{union}(J)|=|J|\)

空集与全集如果是临界指标族，那么称为平凡的临界指标族

首先我们讨论 \(S_1,S_2,\cdots,S_m\) 不存在非平凡临界指标族

显然当 \(m=1\) 时成立，现在我们假设在小于 \(m\) 时均成立

显然由HC得 \(S_m\) 非空，我们选择一个元素 \(x_m\in S_m\)，将 \(S_i(1\le i< m)\) 里的 \(x_m\) 剔除，将此剔除后的集合的并函数设为 \(\text{union}^\prime(J)\)

注意到不存在非平凡临界指标族，所以之后对于 \(J\subseteq[m-1]\)，有：

\[\begin{align*} |\text{union}^\prime(J)|&=|\text{union}(J)|+1 \\ &\ge|J|+1-1 \\ &\ge|J| \end{align*} \]

满足了HC，之后构造SDR显然，证毕

现在我们来讨论存在非平凡临界指标族的情况

由上例的思想，我们显然可以将这一个非平凡临界指标族捆绑起来，然后从剩余的里面剔除掉这个指标族的并，然后由于 \(J\) 是临界的，我们直接展开即得

\(\bold{1.}\) 设 \((A_1,A_2,\cdots,A_m)\) 为 \(\{1,2,\cdots,n\}\) 的一个子集组，且关联矩阵

可逆，证明 \((A_1,A_2,\cdots,A_m)\) 有SDR

证：

可逆 \(\Rightarrow\) 非降秩矩阵，证毕

\(\bold{2.}\) 01矩阵的最小覆盖数 \(m\) 等于最大匹配数 \(M\)

证：

匹配显然要找一对行与列都不同的 \(1\)，这一对 \(1\) 显然要至少 \(1\) 条线来覆盖，即 \(m\ge M\)

然后我们设 \(S_i\) 为一条横线上存在的 \(1\) 的位置，在满足最小覆盖的情况下，显然这东西满足HC，因此存在一个SDR，可推出 \(M\ge m\)，即 \(m=M\)

正则二部图完美匹配

二部图 \(G=X\triangle Y\) 具有覆盖了 \(X\) 的匹配当且仅当HC2成立，HC2：\(\forall J\subseteq X,|N(J)|\ge|J|\)

其中对于一个图 \(G=(V,E)\)，\(N(v)=\{u\in V:u\sim v\}\)，\(u\sim v\) 当且仅当有边连接它们

不难发现这就是HC换了个皮，证明也很显然

定理：正则的二部图一定存在完美匹配

设此二部图为 \(G=X\triangle Y\)，并且 \(\forall y\in Y,\exist x\in X,x\sim y\)

设 \(\deg(v)=k\)，其中 \(\deg(v)\) 表示顶点 \(v\) 的度

事实上如果 \(G\) 中存在孤立点，那么此图不存在边

也就是说 \(E=\varnothing\)

现在我们来证明 \(|X|=|Y|\)，不难发现 \(\sum\limits_{x\in X}\deg(x)=\sum\limits_{y\in Y}\deg(y)\)，由此图正则即可得

\(\forall J\in X\)，\(F=\{e:e\in E,e_f\in J,e_t\in Y\}\)，其中 \(e_f\) 与 \(e_t\) 分别是一条边的起点与终点

则显然有 \(|F|=k|J|\)，\(|F|\le k|N(J)|\)

\(|N(J)|\ge |J|\)，证毕

这篇关于Hall定理/正则二部图完美匹配的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！