Hall定理/正则二部图完美匹配
2021/4/9 18:56:58
本文主要是介绍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)\) 为:
\[\text{union}(J)=\bigcup\limits_{j\in J}S_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\}\) 的一个子集组,且关联矩阵
\[\bold M=(m_{ij}),m_{ij}= \begin{cases} 1&i\in A_j \\ 0&i\notin A_j \end{cases} \]可逆,证明 \((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定理/正则二部图完美匹配的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-11正则表达式学习:入门指南与实践技巧
- 2024-08-15正则表达式入门:基础教程与实践指南
- 2024-01-0939. 干货系列从零用Rust编写负载均衡及代理,正则及格式替换
- 2024-01-08如何编写高效的正则表达式?
- 2023-12-29"Matlab中的正则表达式:强大而灵活的工具"
- 2023-09-30这个正则 为啥同样的单号第二个就提取不出来?
- 2023-06-086.2 re 正则表达式
- 2023-06-06将字符串里的\x01,\x02这些替换掉用正则表达式无效?
- 2023-05-24正则表达式详解
- 2023-05-17我让gpt写了一段正则表达式代码,可是运行报错,可以帮忙看看哪里出了问题?