Hall定理正则⼆部图完美匹配相异代表系
设S1,S2,⋯,S m是⼀族集合，它们的⼀个相异代表系为⼀个m维向量 (x1,x2,⋯,x m)
满⾜：
代表性：x i∈S i
互异性：∀i≠j,x i≠x j
相异代表系也简称为SDR
对于⼀族指标J⊆[m]，我们定义它们的并 union(J) 为：
union(J)=⋃j∈J S j
Hall定理
有限集族S1,S2,⋯,S m存在SDR当且仅当HC成⽴，其中HC：∀J⊆[m],|union(J)|≥|J|
（严谨性未知）
笔者⼝胡的反证法：如果⼀个集合满⾜HC但是不存在SDR，那么⼀定存在⼀个S i，其中的元素⽆法选择，并且对于j≠i，S j中选择的元素⽆法更换，因为如果可以更换，那么我们相应的更换S k,k≠j,k≠i中的元素，直到更换⾄S i，即存在SDR，此时我们不选择S i，余下的集族不满⾜HC，⽭盾
（正规证明）
使⽤数学归纳法：
定义⼀个指标族J临界，若 {S j:j∈J} 存在SDR，并且 |union(J)|=|J|
空集与全集如果是临界指标族，那么称为平凡的临界指标族
⾸先我们讨论S1,S2,⋯,S m不存在⾮平凡临界指标族
正则匹配横线显然当m=1 时成⽴，现在我们假设在⼩于m时均成⽴
显然由HC得S m⾮空，我们选择⼀个元素x m∈S m，将S i(1≤i<m) ⾥的x m剔除，将此剔除后的集合的并函数设为 union′(J)注意到不存在⾮平凡临界指标族，所以之后对于J⊆[m−1]，有：
|union′(J)|=|union(J)|+1
≥|J|+1−1
≥|J|
满⾜了HC，之后构造SDR显然，证毕
现在我们来讨论存在⾮平凡临界指标族的情况
由上例的思想，我们显然可以将这⼀个⾮平凡临界指标族捆绑起来，然后从剩余的⾥⾯剔除掉这个指标族的并，然后由于J是临界的，我们直接展开即得
1.设 (A1,A2,⋯,A m) 为 {1,2,⋯,n} 的⼀个⼦集组，且关联矩阵
M=(m ij),m ij=1i∈A j 0i∉A j
可逆，证明 (A1,A2,⋯,A m) 有SDR
证：
可逆⇒⾮降秩矩阵，证毕
2. 01矩阵的最⼩覆盖数m等于最⼤匹配数M
{
证：
匹配显然要⼀对⾏与列都不同的 1，这⼀对 1 显然要⾄少 1 条线来覆盖，即m≥M
然后我们设S i为⼀条横线上存在的 1 的位置，在满⾜最⼩覆盖的情况下，显然这东西满⾜HC，因此存在⼀个SDR，可推出M≥m，即m=M
正则⼆部图完美匹配
⼆部图G=X△Y具有覆盖了X的匹配当且仅当HC2成⽴，HC2：∀J⊆X,|N(J)|≥|J|
其中对于⼀个图G=(V,E)，N(v)={u∈V:u∼v}，u∼v当且仅当有边连接它们
不难发现这就是HC换了个⽪，证明也很显然
定理：正则的⼆部图⼀定存在完美匹配
设此⼆部图为G=X△Y，并且∀y∈Y,∃x∈X,x∼y
设 deg(v)=k，其中 deg(v) 表⽰顶点v的度
事实上如果G中存在孤⽴点，那么此图不存在边
也就是说E=∅
现在我们来证明 |X|=|Y|，不难发现∑
x∈X deg(x)=
∑
y∈Y deg(y)，由此图正则即可得
∀J∈X，F={e:e∈E,e f∈J,e t∈Y}，其中e f与e t分别是⼀条边的起点与终点则显然有 |F|=k|J|，|F|≤k|N(J)|
|N(J)|≥|J|，证毕
Processing math: 100%

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。