当前位置:网站首页>【学习笔记】拟阵
【学习笔记】拟阵
2022-07-04 13:32:00 【OneInDark】
“拟阵是向量空间的 ‘线性无关’ 概念的推广。” —— 知乎网友
用 ⊊ \subsetneq ⊊ 表示 “不包含于”。
壹、定义
1.拟阵
拟阵( M a t r o i d \rm Matroid Matroid) M = ( U , I ) \mathcal M=(\Bbb U,\mathcal I) M=(U,I),其中 I \mathcal I I 是 U \Bbb U U 上的集族,满足
- 遗传性:对于 I ∈ I , J ⊆ I I\in\mathcal I,\;J\subseteq I I∈I,J⊆I 有 J ∈ I J\in\mathcal I J∈I 。
- 基交换性 或 扩张性:对于 I , J ∈ I , ∣ I ∣ < ∣ J ∣ I,J\in\mathcal I,\;|I|<|J| I,J∈I,∣I∣<∣J∣ 有 ∃ x ∈ J ∖ I \exists x\in J\setminus I ∃x∈J∖I 使得 I ∪ { z } ∈ I I\cup\{z\}\in\mathcal I I∪{ z}∈I 。
不妨规定 ∣ I ∣ ≠ 0 |\mathcal I|\ne 0 ∣I∣=0,因此 ∅ ∈ I \varnothing\in\mathcal I ∅∈I 。
对于 I ∈ I I\in\mathcal I I∈I,称 I I I 为 独立集,即 I I I 是独立的。否则称 I I I 为不独立的。
2.基与环
基( b a s i s \rm basis basis)是极大独立集,环( c i r c u i t \rm circuit circuit)是极小非独立集。
Lemma 1. 矩阵中的所有基具有相同的大小。
Corollary 1. 对于不同的环 X , Y X,Y X,Y,若存在 e ∈ X ∩ Y e\in X\cap Y e∈X∩Y,则 X + Y − { e } X+Y-\{e\} X+Y−{ e} 是不独立的。
Proof. 显然存在 f ∈ X ∖ Y f\in X\setminus Y f∈X∖Y,设 Z Z Z 为 X ∪ Y X\cup Y X∪Y 中包含 X ∖ { f } X\setminus\{f\} X∖{ f} 的最大独立集,因 Y ⊊ Z Y\subsetneq Z Y⊊Z 得 ∣ Z ∣ < ∣ X + Y − { f } ∣ = ∣ X + Y − { e } ∣ |Z|<|X+Y-\{f\}|=|X+Y-\{e\}| ∣Z∣<∣X+Y−{ f}∣=∣X+Y−{ e}∣,因为 Z Z Z 是最大的,所以原命题得证。 ■ \blacksquare ■
Corollary 2. 对于 I ∈ I I\in\mathcal I I∈I,若 I ∪ { e } ∉ I I\cup\{e\}\notin\mathcal I I∪{ e}∈/I 则 I ∪ { e } I\cup\{e\} I∪{ e} 中有唯一的环。
Proof. 若存在两个环 C 1 , C 2 C_1,C_2 C1,C2,显然 e ∈ C 1 ∩ C 2 e\in C_1\cap C_2 e∈C1∩C2,由 corollary 1 \text{corollary 1} corollary 1 知 C 1 + C 2 − { e } C_1+C_2-\{e\} C1+C2−{ e} 不独立,与 I I I 是独立集矛盾。 ■ \blacksquare ■
3.秩函数
对于 S ⊆ U S\subseteq\Bbb U S⊆U,定义 秩(函数) r ( S ) r(S) r(S) 为 S S S 中极大独立集的大小。
- 有界性: 0 ⩽ r ( S ) ⩽ ∣ S ∣ 0\leqslant r(S)\leqslant |S| 0⩽r(S)⩽∣S∣ 。
- 单调性: ∀ A ⊆ B \forall A\subseteq B ∀A⊆B 有 r ( A ) ⩽ r ( B ) r(A)\leqslant r(B) r(A)⩽r(B) 。
- 次模性( submodular \text{submodular} submodular,也称子模): r ( A ∪ B ) + r ( A ∩ B ) ⩽ r ( A ) + r ( B ) r(A\cup B)+r(A\cap B)\leqslant r(A)+r(B) r(A∪B)+r(A∩B)⩽r(A)+r(B) 。
Proof. 证明 r ( A ∪ { x } ) − r ( A ) ⩽ r ( B ∪ { x } ) − r ( B ) r(A\cup\{x\})-r(A)\leqslant r(B\cup\{x\})-r(B) r(A∪{ x})−r(A)⩽r(B∪{ x})−r(B) 其中 B ⊆ A B\subseteq A B⊆A 是平凡的。然后从 * A , A ∩ B * \langle A,\;A\cap B\rangle *A,A∩B* 开始,将 B ∖ A B\setminus A B∖A 逐个加入 A A A 则得到 * A ∪ B , A ∩ B * \langle A\cup B,\;A\cap B\rangle *A∪B,A∩B*,加入 A ∩ B A\cap B A∩B 则得到 * A , B * \langle A,B\rangle *A,B*,在已经加入了 S S S 时,前者在集合 A + S A+S A+S 内增加,后者在 ( A ∩ B ) + S (A\cap B)+S (A∩B)+S 内增加,更大。 ■ \blacksquare ■
4.以秩定义
“我们将拟阵的组合问题转化为秩函数上的代数问题,通过研究秩函数的性质来求得拟阵的性质。”
依据满足上述三条性质的秩函数 r : 2 S ↦ N + r:2^S\mapsto\mathbb{N}^+ r:2S↦N+,我们可以重新定义拟阵 M = ( U , I ) \mathcal M=(\Bbb U,\mathcal I) M=(U,I),其中 I = { I : r ( I ) = ∣ I ∣ } \mathcal I=\{I:r(I)=|I|\} I={ I:r(I)=∣I∣} 。
Proof. 遗传性:若 r ( B ) = ∣ B ∣ , A ⊆ B r(B)=|B|,\;A\subseteq B r(B)=∣B∣,A⊆B,由 次模性
知 r ( B ) ⩽ r ( A ) + r ( B ∖ A ) r(B)\leqslant r(A)+r(B\setminus A) r(B)⩽r(A)+r(B∖A),由 有界性
知 r ( A ) = ∣ A ∣ r(A)=|A| r(A)=∣A∣ 。
交换性:反证法,设 B = { b 1 , b 2 , … , b ∣ B ∣ } B=\{b_1,b_2,\dots,b_{|B|}\} B={ b1,b2,…,b∣B∣},则 r ( A ∪ { b i } ) = ∣ A ∣ r(A\cup\{b_i\})=|A| r(A∪{ bi})=∣A∣ 。利用归纳法证明 r ( A ∪ { b 1 , b 2 , … , b n } ) = ∣ A ∣ r(A\cup\{b_1,b_2,\dots,b_n\})=|A| r(A∪{ b1,b2,…,bn})=∣A∣ 。对 n > 1 n>1 n>1,取 X = A ∪ { b 1 , b 2 , … , b n − 1 } , Y = A ∪ { b n } X=A\cup\{b_1,b_2,\dots,b_{n-1}\},\;Y=A\cup\{b_n\} X=A∪{ b1,b2,…,bn−1},Y=A∪{ bn},由 次模性
有 r ( A ∪ { b 1 , b 2 , … , b n } ) + r ( A ) ⩽ r ( X ) + r ( Y ) r(A\cup\{b_1,b_2,\dots,b_n\})+r(A)\leqslant r(X)+r(Y) r(A∪{ b1,b2,…,bn})+r(A)⩽r(X)+r(Y),由 r ( A ) = r ( X ) = r ( Y ) = ∣ A ∣ ⩽ r ( A ∪ { b 1 , b 2 , … , b n } ) r(A)=r(X)=r(Y)=|A|\leqslant r(A\cup\{b_1,b_2,\dots,b_n\}) r(A)=r(X)=r(Y)=∣A∣⩽r(A∪{ b1,b2,…,bn}) 知归纳法成立。
然而 r ( B ) = ∣ B ∣ > r ( A ∪ B ) = ∣ A ∣ r(B)=|B|>r(A\cup B)=|A| r(B)=∣B∣>r(A∪B)=∣A∣ 违反了 单调性
。 ■ \blacksquare ■
贰、线性拟阵和线性表出
“我们线性拟阵是你们图拟阵的老大哥!”
线性拟阵( linear matroid \text{linear matroid} linear matroid)即 U \Bbb U U 为向量集合,而 I = { I ∈ 2 U : dim ( span ( I ) ) = ∣ I ∣ } \mathcal I=\{I\in 2^{\Bbb U}:\dim(\text{span}(I))=|I|\} I={ I∈2U:dim(span(I))=∣I∣} 的特殊拟阵。
线性表出( linear representation \text{linear representation} linear representation)即将 U \Bbb U U 内每个元素映射到一个向量上,使得这些向量的线性拟阵得到的 I \mathcal I I 就是原拟阵的独立集集族。
按:作为 O I e r \rm OIer OIer 我并不想去研究向量空间的基域,因此相关内容略写
若拟阵可以被线性表出,问题就变成线性拟阵上的了。
1.均匀拟阵
均匀拟阵( uniform matroid \text{uniform matroid} uniform matroid)为 I = { I : ∣ I ∣ ⩽ k } \mathcal I=\{I:|I|\leqslant k\} I={ I:∣I∣⩽k} 。
它可以被线性表出为 k k k 维向量 v i = ( 1 , α i , α i 2 , … , α i k − 1 ) v_i=(1,\alpha_i,\alpha_i^2,\dots,\alpha_i^{k-1}) vi=(1,αi,αi2,…,αik−1),其中 { α i } \{\alpha_i\} { αi} 是两两相异的非零元:超过 k k k 个肯定线性相关,但不超过 k k k 个时,范德蒙德矩阵行列式为 ∏ i < j ( α j − α i ) ≠ 0 \prod_{i<j}(\alpha_j-\alpha_i)\ne 0 ∏i<j(αj−αi)=0,因此线性无关。
2.图拟阵
图拟阵( graph matroid \text{graph matroid} graph matroid)定义在无向图 G = ( V , E ) G=(V,E) G=(V,E) 上, U = E \Bbb U=E U=E 而 I \mathcal I I 为不构成环的边集的集族。
给 E E E 任意定向,对边 e = ( u , v ) e=(u,v) e=(u,v),向量 v e v_e ve 在第 u u u 维上是 1 1 1,在第 v v v 维上是 − 1 -1 −1 。不难验证其正确性。
“图拟阵是正则拟阵;任意的正则拟阵的基的计数都可以通过计算一个关联矩阵的行列式求得,而矩阵树定理是其中的特例。”
叁、最优化问题
1.最大权独立集
给定函数 ω : U ↦ R \omega:\Bbb U\mapsto\Reals ω:U↦R,求 max I ∈ I ∑ x ∈ I ω ( x ) \max_{I\in\mathcal I}\sum_{x\in I}\omega(x) maxI∈I∑x∈Iω(x) 。显然 ω ( x ) ⩽ 0 \omega(x)\leqslant 0 ω(x)⩽0 可被忽略。
只需将 U \Bbb U U 内元素按照 ω \omega ω 单调不降的顺序排列,然后线性扫描之,可以加入就加入。
Proof. 令 X = { x 1 , x 2 , … , x r } X=\{x_1,x_2,\dots,x_r\} X={ x1,x2,…,xr} 是真正的最大权独立集,其中 ω ( x i ) \omega(x_i) ω(xi) 单调不增,记 X n = { x 1 , x 2 , … , x n } X_n=\{x_1,x_2,\dots,x_n\} Xn={ x1,x2,…,xn} 。令 S n S_n Sn 为加入第 n n n 个元素后得到的独立集,归纳证明 ω ( S n ) ⩾ ω ( X n ) \omega(S_n)\geqslant\omega(X_n) ω(Sn)⩾ω(Xn) 。对 n ⩾ 1 n\geqslant 1 n⩾1,设 { u } = S n ∖ S n − 1 \{u\}=S_n\setminus S_{n-1} { u}=Sn∖Sn−1,根据 扩张性
有 ∃ v ∈ X n ∖ S n − 1 \exists v\in X_n\setminus S_{n-1} ∃v∈Xn∖Sn−1 使得 S n − 1 ∪ v ∈ I S_{n-1}\cup v\in\mathcal I Sn−1∪v∈I,然而根据算法流程 ω ( u ) ⩾ ω ( v ) \omega(u)\geqslant\omega(v) ω(u)⩾ω(v),根据 X X X 的排序方式 ω ( v ) ⩾ ω ( x n ) \omega(v)\geqslant\omega(x_n) ω(v)⩾ω(xn),因此 ω ( S n ) = ω ( S n − 1 ∪ { u } ) ⩾ ω ( X n − 1 ) + ω ( x n ) = ω ( X n ) \omega(S_n)=\omega(S_{n-1}\cup\{u\})\geqslant\omega(X_{n-1})+\omega(x_n)=\omega(X_n) ω(Sn)=ω(Sn−1∪{ u})⩾ω(Xn−1)+ω(xn)=ω(Xn) 。 ■ \blacksquare ■
注:其中 ω ( S ) \omega(S) ω(S) 是 ∑ x ∈ S ω ( x ) \sum_{x\in S}\omega(x) ∑x∈Sω(x) 的缩写。之后的问题中也可能这样简记。
2.最小权基
给定函数 ω : U ↦ R \omega:\Bbb U\mapsto\Reals ω:U↦R,求 min ∣ I ∣ = r ( I ) = r ( U ) ∑ x ∈ I ω ( x ) \min_{|I|=r(I)=r(\Bbb U)}\sum_{x\in I}\omega(x) min∣I∣=r(I)=r(U)∑x∈Iω(x) 。
流程与 最大权独立集
一样,只是不能去掉 ω ( x ) ⩾ 0 \omega(x)\geqslant 0 ω(x)⩾0 的。
3.最大最小带权环
很遗憾,最大带权环在 ω = 1 \omega=1 ω=1 的图拟阵上可以判定哈密顿路的存在性,因此是 NP-hard \text{NP-hard} NP-hard 。
最小带权环可以规约到 Even Set \text{Even Set} Even Set 问题上,而 Even Set \text{Even Set} Even Set 是 NPC \text{NPC} NPC 问题,因此最小带权环也是 NP-hard \text{NP-hard} NP-hard 。
肆、拟阵运算
1.对偶拟阵
M ∗ = ( U , I ∗ ) \mathcal M^*=(\Bbb U,\mathcal I^*) M∗=(U,I∗) 是 M = ( U , I ) \mathcal M=(\mathbb{U},\mathcal I) M=(U,I) 的 对偶拟阵( dual matroid \text{dual matroid} dual matroid),其中 I ∗ = { I : ∃ B is basis of M , B ⊆ U ∖ I } \mathcal I^*=\{I:\exists B\text{ is basis of }\mathcal M,\;B\subseteq\mathbb{U}\setminus I\} I∗={ I:∃B is basis of M,B⊆U∖I} 。
换句话说,记 B ( M ) \mathcal{B(M)} B(M) 为 M \mathcal M M 的所有 b a s i s \rm basis basis 的集族,则 B ( M ∗ ) = { U − I : I ∈ B ( M ) } \mathcal{B(M^*)}=\{\Bbb U-I:I\in\mathcal{B(M)}\} B(M∗)={ U−I:I∈B(M)} 。
Proof. 直接证明稍有困难;用 以秩定义
方法可行。
r ∗ ( S ) = max { ∣ S ∖ B ∣ : B ∈ B ( M ) } = ∣ S ∣ − min { ∣ S ∩ B ∣ : B ∈ B ( M ) } = ∣ S ∣ − r ( U ) + max { ∣ B ∩ ( U ∖ S ) ∣ : B ∈ B ( M ) } = ∣ S ∣ − r ( U ) + r ( U ∖ S ) \begin{aligned} r^*(S)&=\max\{|S\setminus B|:B\in\mathcal{B(M)}\}\\ &=|S|-\min\{|S\cap B|:B\in\mathcal{B(M)}\}\\ &=|S|-r(\Bbb U)+\max\{|B\cap(\Bbb U\setminus S)|:B\in\mathcal{B(M)}\}\\ &=|S|-r(\Bbb U)+r(\Bbb U\setminus S) \end{aligned} r∗(S)=max{ ∣S∖B∣:B∈B(M)}=∣S∣−min{ ∣S∩B∣:B∈B(M)}=∣S∣−r(U)+max{ ∣B∩(U∖S)∣:B∈B(M)}=∣S∣−r(U)+r(U∖S)
有界性、单调性显然。只需验证次模性。不难发现此时 ∣ S ∣ − r ( U ) |S|-r(\Bbb U) ∣S∣−r(U) 可消去,事实上就等价于 “次模函数在取补集后仍是次模的”。而这是 t r i v i a l \rm trivial trivial 的。 ■ \blacksquare ■
2.删除与收缩
对于 M = ( U , I ) \mathcal M=(\Bbb U,\mathcal I) M=(U,I) 和 S ⊆ U S\subseteq\Bbb U S⊆U,定义 M \mathcal M M删除 S S S 的拟阵为 ( U ∖ S , I ′ ) (\Bbb U\setminus S,\;\mathcal I') (U∖S,I′) 其中 I ′ = { I : I ∈ I , I ⊆ U ∖ S } \mathcal I'=\{I:I\in\mathcal I,\;I\subseteq\Bbb U\setminus S\} I′={ I:I∈I,I⊆U∖S},记为 M ∖ S \mathcal M\setminus S M∖S 。定义 M \mathcal M M收缩 S S S 的拟阵为 ( M ∗ ∖ S ) ∗ (\mathcal M^*\setminus S)^* (M∗∖S)∗,记为 M / S \mathcal M/S M/S 。1
前者即不再考虑这些元素。后者等价于 S S S 内的基必选——在 M ∗ \mathcal M^* M∗ 中去掉 S S S,也就是不能不选嘛。
当然也可以从 r r r 函数的角度考虑,有 r M / S ( Z ) = r M ( Z ∪ S ) − r M ( S ) r_{\mathcal M/S}(Z)=r_{\mathcal M}(Z\cup S)-r_{\mathcal M}(S) rM/S(Z)=rM(Z∪S)−rM(S) 。
这些操作对拟阵是封闭的,这可以通过 r r r 函数证明。这里我就选择相信论文了。
3.极小元
M \mathcal M M 经过 d e l e t i o n \rm deletion deletion 和 c o n t r a c t i o n \rm contraction contraction 得到的任意拟阵 M ′ \mathcal M' M′ 是 M \mathcal M M 的 极小元。
“不严谨的说,拟阵的极小元可以看成原拟阵的一个局部特征。”
4.拟阵并
对于给定的 k k k 个拟阵 M i = ( U i , I i ) ( 1 ⩽ i ⩽ k ) \mathcal M_i=(\Bbb U_i,\mathcal I_i)\;(1\leqslant i\leqslant k) Mi=(Ui,Ii)(1⩽i⩽k),定义这 k k k 个 拟阵的并 为 M = ( U , I ) \mathcal M=(\Bbb U,\mathcal I) M=(U,I),其中 U = ⋃ i = 1 k U i , I = { ⋃ j = 1 k I j : ∀ j , I j ∈ I j } \Bbb U=\bigcup_{i=1}^{k}\Bbb U_i,\;\mathcal I=\{\bigcup_{j=1}^{k}I_j:\forall j,\;I_j\in\mathcal I_j\} U=⋃i=1kUi,I={ ⋃j=1kIj:∀j,Ij∈Ij} 。
其遗传性与扩张性显然,即该运算是封闭的。
暂时先略过其秩函数的变化规律,与独立集判定法。
以后请提醒我补上。
伍、拟阵交
匈牙利算法才是万物的起源!——二分图匹配既是拟阵交,又是拟阵并。
由于 拟阵交
在拟阵上并不封闭,所以不列在 拟阵运算
当中。
l l l-拟阵交( l -matroid intersection l\text{-matroid intersection} l-matroid intersection):给定 M i = ( U , I i ) ( 1 ⩽ i ⩽ l ) \mathcal M_i=(\Bbb U,\mathcal I_i)\;(1\leqslant i\leqslant l) Mi=(U,Ii)(1⩽i⩽l),求 max { I : ∀ j ∈ [ 1 , l ] , I ∈ I j } \max\{I:\forall j\in[1,l],\;I\in\mathcal I_j\} max{ I:∀j∈[1,l],I∈Ij} 。
Theorem 1. 3 3 3-拟阵交问题是 NPC \text{NPC} NPC 问题。
Proof. 二分图上哈密顿路问题是 NPC \text{NPC} NPC 的。在两部点上,分别定义拟阵为 “边集不共用该部的顶点”,再与图拟阵求交,就可以求出二分图上哈密顿路,因此 3 3 3-拟阵交问题是 NPC \text{NPC} NPC 的。 ■ \blacksquare ■
所以我们只学会下面这个 P P P 的 2 2 2-拟阵交问题就行啦!
Theorem 2.(最大最小定理) max { ∣ I ∣ : I ∈ I 1 ∩ I 2 } = min S ⊆ U { r 1 ( S ) + r 2 ( U ∖ S ) } \max\{|I|:I\in\mathcal{I}_1\cap\mathcal{I}_2\}=\min_{S\subseteq\Bbb U}\{r_1(S)+r_2(\Bbb U\setminus S)\} max{ ∣I∣:I∈I1∩I2}=minS⊆U{ r1(S)+r2(U∖S)} 。
简单的一侧,即 LHS ⩽ RHS \text{LHS}\leqslant\text{RHS} LHS⩽RHS 是显然的。而可以取等的证明就是构造性算法。
1.强基交换定理
定义 闭包( closure \text{closure} closure)算子 clos ( A ) = { x ∈ U : r ( A ∪ { x } ) = r ( A ) } \text{clos}(A)=\{x\in\Bbb U:r(A\cup\{x\})=r(A)\} clos(A)={ x∈U:r(A∪{ x})=r(A)} 。
Lemma 2. 若 A ⊆ S A\subseteq S A⊆S 则 clos ( A ) ⊆ clos ( S ) \text{clos}(A)\subseteq\text{clos}(S) clos(A)⊆clos(S) 。
Proof. x ∈ clos ( A ) x\in\text{clos}(A) x∈clos(A) 等价于 A A A 的某个基 B B B 满足 B ∪ { x } ∉ I B\cup\{x\}\notin\mathcal I B∪{ x}∈/I,而 S S S 存在基 B ′ ⊇ B B'\supseteq B B′⊇B,因此 x ∈ clos ( S ) x\in\text{clos}(S) x∈clos(S) 立刻成立。 ■ \blacksquare ■
Lemma 3. 若 x ∈ clos ( A ) x\in\text{clos}(A) x∈clos(A) 则 clos ( clos ( A ) ) = clos ( A ) = clos ( A ∪ { x } ) \text{clos}(\text{clos}(A))=\text{clos}(A)=\text{clos}(A\cup\{x\}) clos(clos(A))=clos(A)=clos(A∪{ x}) 。
Theorem 3.(强基交换定理) 对于 M \mathcal M M 的两个不同的基 A , B A,B A,B,对于 ∀ x ∈ A ∖ B \forall x\in A\setminus B ∀x∈A∖B 都存在 y ∈ B ∖ A y\in B\setminus A y∈B∖A 使得 A − { x } + { y } A-\{x\}+\{y\} A−{ x}+{ y} 和 B − { y } + { x } B-\{y\}+\{x\} B−{ y}+{ x} 都是拟阵的基。
Proof. 由 corollary 2 \text{corollary 2} corollary 2 得 B + { x } B+\{x\} B+{ x} 包含唯一的环 C ⊇ { x } C\supseteq\{x\} C⊇{ x} 。显然 x ∈ clos ( C − { x } ) x\in\text{clos}(C-\{x\}) x∈clos(C−{ x}),由 lemma 2,3 \text{lemma 2,3} lemma 2,3 有 clos ( ( A ∪ C ) ∖ { x } ) = clos ( A ∪ C ) = U \text{clos}((A\cup C)\setminus\{x\})=\text{clos}(A\cup C)=\Bbb U clos((A∪C)∖{ x})=clos(A∪C)=U,因此存在 M \mathcal M M 的基 A ′ ⊆ ( A ∪ C ) ∖ { x } A'\subseteq(A\cup C)\setminus\{x\} A′⊆(A∪C)∖{ x} 。由 交换性
,存在 y ∈ A ′ ∖ ( A − { x } ) y\in A'\setminus(A-\{x\}) y∈A′∖(A−{ x}) 使得 A − { x } + { y } A-\{x\}+\{y\} A−{ x}+{ y} 是 M \mathcal M M 的基。
注意到 A ′ ∖ ( A − { x } ) ⊆ ( ( A ∪ C ) ∖ { x } ) ∖ ( A − { x } ) ⊆ C ∖ { x } A'\setminus(A-\{x\})\subseteq((A\cup C)\setminus\{x\})\setminus(A-\{x\})\subseteq C\setminus\{x\} A′∖(A−{ x})⊆((A∪C)∖{ x})∖(A−{ x})⊆C∖{ x},所以 B + { x } − { y } B+\{x\}-\{y\} B+{ x}−{ y} 把 B + { x } B+\{x\} B+{ x} 中的唯一环 C C C 拆掉了,所以 B − { y } + { x } B-\{y\}+\{x\} B−{ y}+{ x} 也是基。 ■ \blacksquare ■
2.交换图
对于 M = ( U , I ) \mathcal M=(\mathbb{U},\mathcal{I}) M=(U,I) 和 I ∈ I I\in\mathcal I I∈I,定义 交换图 D M ( I ) D_{\mathcal M}(I) DM(I) 为 X = I , Y = U ∖ I {\frak X}=I,\;{\frak Y}=\Bbb U\setminus I X=I,Y=U∖I 的二部图,其中 x ∈ X x\in\frak X x∈X 和 y ∈ Y y\in\frak Y y∈Y 之间有边当且仅当 I − { x } + { y } ∈ I I-\{x\}+\{y\}\in\mathcal I I−{ x}+{ y}∈I 成立。
Lemma 4. 若 I , J ∈ I I,J\in\mathcal I I,J∈I,且 ∣ I ∣ = ∣ J ∣ |I|=|J| ∣I∣=∣J∣,则 D M ( I ) D_{\mathcal M}(I) DM(I) 中存在 I ∖ J I\setminus J I∖J 和 J ∖ I J\setminus I J∖I 的完美匹配。
Proof. 不妨令独立集大小均不超过 ∣ I ∣ |I| ∣I∣,则 I , J I,J I,J 是两个基。根据 强基交换定理
, ∃ x ∈ I ∖ J , y ∈ J ∖ I \exists x\in I\setminus J,\;y\in J\setminus I ∃x∈I∖J,y∈J∖I 使得 I − { x } + { y } I-\{x\}+\{y\} I−{ x}+{ y} 是基。因此 * x , y * \langle x,y\rangle *x,y* 可匹配,然后递归 J ′ = J − { y } + { x } J'=J-\{y\}+\{x\} J′=J−{ y}+{ x} 即可。 ■ \blacksquare ■
Theorem 4. 若 I ∈ I , ∣ I ∣ = ∣ J ∣ I\in\mathcal I,\;|I|=|J| I∈I,∣I∣=∣J∣ 且 D M ( I ) D_{\mathcal M}(I) DM(I) 中存在唯一的 I ∖ J I\setminus J I∖J 和 J ∖ I J\setminus I J∖I 的完美匹配,则 J ∈ I J\in\mathcal I J∈I 。
Proof. 令 P P P 是唯一的匹配,将 P P P 中的边定向为 U ∖ I \Bbb U\setminus I U∖I 到 I I I,其余反之。匹配唯一说明不存在有向环,用拓扑序重编号(编号小的点指向编号大的点)。设 P = { * y i , x i * } P=\{\langle y_i,x_i\rangle\} P={ *yi,xi*},其中 y i ∈ J ∖ I y_i\in J\setminus I yi∈J∖I 。重排使得 x i → y j ( i < j ) x_i\to y_j\;(i<j) xi→yj(i<j) 不存在边。
假设 J J J 不独立,取环 C ⊆ J C\subseteq J C⊆J 与最小的 i i i 使得 y i ∈ C y_i\in C yi∈C,这样的 i i i 显然存在。此时 ∀ y ∈ C ∖ { y i } \forall y\in C\setminus\{y_i\} ∀y∈C∖{ yi},因为 y y y 的实际位置比 y i y_i yi 更大,因此 x i → y x_i\to y xi→y 不存在边,即 I − { x i } + y ∉ I I-\{x_i\}+y\notin\mathcal I I−{ xi}+y∈/I,即 C ∖ { y i } ⊆ clos ( I ∖ { x i } ) C\setminus\{y_i\}\subseteq\text{clos}(I\setminus\{x_i\}) C∖{ yi}⊆clos(I∖{ xi}) 。此时有 y i ∈ clos ( C ∖ { y i } ) ⊆ clos ( I ∖ { x i } ) y_i\in\text{clos}(C\setminus\{y_i\})\subseteq\text{clos}(I\setminus\{x_i\}) yi∈clos(C∖{ yi})⊆clos(I∖{ xi}),这与 * x i , y i * \langle x_i,y_i\rangle *xi,yi* 是交换图里的边矛盾。 ■ \blacksquare ■
3.拟阵交算法
定义 交换图 D M 1 , M 2 ( I ) D_{\mathcal{M}_1,\mathcal{M}_2}(I) DM1,M2(I) 为 X = I , Y = U ∖ I {\frak X}=I,\;{\frak Y}=\Bbb U\setminus I X=I,Y=U∖I 的有向二部图,其中 x ∈ X x\in\frak X x∈X 和 y ∈ Y y\in\frak Y y∈Y 之间有 * x , y * \langle x,y\rangle *x,y* 边当且仅当 I − { x } + { y } ∈ I 1 I-\{x\}+\{y\}\in\mathcal I_1 I−{ x}+{ y}∈I1 成立,有 * y , x * \langle y,x\rangle *y,x* 边当且仅当 I − { x } + { y } ∈ I 2 I-\{x\}+\{y\}\in\mathcal I_2 I−{ x}+{ y}∈I2 。
初始令 I = ∅ I=\varnothing I=∅ 。每次令 X i = { x ∉ I : I ∪ { x } ∈ I i } ( i = 1 , 2 ) X_i=\{x\notin I:I\cup\{x\}\in\mathcal I_i\}\;(i=1,2) Xi={ x∈/I:I∪{ x}∈Ii}(i=1,2),然后在 D M 1 , M 2 ( I ) D_{\mathcal M_1,\mathcal M_2}(I) DM1,M2(I) 中找到 X 1 X_1 X1 到 X 2 X_2 X2 的最短路 P P P,然后令 I = I ⊕ P I=I\oplus P I=I⊕P,这里 ⊕ \oplus ⊕ 表示对称差。直到找不到路径。此时就得到了最大的 ∣ I ∣ |I| ∣I∣,以及 最大最小定理
中的 S = { z : z can reach X 2 } S=\{z:z\text{ can reach }X_2\} S={ z:z can reach X2} 。
3.1.独立性
令最短路 P = { y 0 , x 1 , y 1 , x 2 , y 2 , … , x t , y t } P=\{y_0,x_1,y_1,x_2,y_2,\dots,x_t,y_t\} P={ y0,x1,y1,x2,y2,…,xt,yt},令 J = { y 1 , y 2 , … , y t } ∪ ( I ∖ { x 1 , x 2 , … , x t } ) J=\{y_1,y_2,\dots,y_t\}\cup(I\setminus\{x_1,x_2,\dots,x_t\}) J={ y1,y2,…,yt}∪(I∖{ x1,x2,…,xt}) 。可以得到 ∣ I ∣ = ∣ J ∣ |I|=|J| ∣I∣=∣J∣,且 I ∖ J I\setminus J I∖J 和 J ∖ I J\setminus I J∖I 在 D M 1 ( I ) D_{\mathcal M_1}(I) DM1(I) 里有唯一完美匹配(在只保留 X → Y \frak X\to Y X→Y 边的图上;因为是最短路)。
由 theorem 4 \text{theorem 4} theorem 4 即得 J ∈ I 1 J\in\mathcal I_1 J∈I1 。又因为 P P P 最短可知 y i ∉ X 1 ( 1 ⩽ i ⩽ t ) y_i\notin X_1\;(1\leqslant i\leqslant t) yi∈/X1(1⩽i⩽t) 即 I ∪ { y i } ∉ I 1 I\cup\{y_i\}\notin\mathcal I_1 I∪{ yi}∈/I1 即 r 1 ( I ∪ J ) = r 1 ( I ) r_1(I\cup J)=r_1(I) r1(I∪J)=r1(I) 。由于 I ∪ { y 0 } ∈ I 1 I\cup\{y_0\}\in\mathcal I_1 I∪{ y0}∈I1 故 J ∪ { y 0 } ∈ I 1 J\cup\{y_0\}\in\mathcal I_1 J∪{ y0}∈I1,而 J ∪ { y 0 } = I ⊕ P J\cup\{y_0\}=I\oplus P J∪{ y0}=I⊕P 。
同理,令 J = I ⊕ P ⊕ { y t } J=I\oplus P\oplus\{y_t\} J=I⊕P⊕{ yt} 则 J ∈ I 2 J\in\mathcal I_2 J∈I2,由 r 2 ( I ∪ J ) = r 2 ( I ) r_2(I\cup J)=r_2(I) r2(I∪J)=r2(I) 得 J ∪ { y t } ∈ I 2 J\cup\{y_t\}\in\mathcal I_2 J∪{ yt}∈I2 。 ■ \blacksquare ■
3.2.最大最小
先证明 r 1 ( S ) ⩽ ∣ I ∩ S ∣ r_1(S)\leqslant|I\cap S| r1(S)⩽∣I∩S∣ 。反证法。设 r 1 ( S ) > ∣ I ∩ S ∣ r_1(S)>|I\cap S| r1(S)>∣I∩S∣,根据定义即 ∃ x ∈ S ∖ I \exists x\in S\setminus I ∃x∈S∖I 使得 ( I ∩ S ) ∪ { x } ∈ I 1 (I\cap S)\cup\{x\}\in\mathcal I_1 (I∩S)∪{ x}∈I1 。由于 x ∈ S x\in S x∈S 即 x x x 可到达 X 2 X_2 X2,必然有 x ∉ X 1 x\notin X_1 x∈/X1 即 I ∪ { x } ∉ I 1 I\cup\{x\}\notin\mathcal I_1 I∪{ x}∈/I1 。
由 独立性
知 I ∪ { x } I\cup\{x\} I∪{ x} 存在唯一环 C ⊇ { x } C\supseteq\{x\} C⊇{ x} 。由 ( I ∩ S ) ∪ { x } ∈ I 1 (I\cap S)\cup\{x\}\in\mathcal I_1 (I∩S)∪{ x}∈I1 知 C ⊊ ( I ∩ S ) C\subsetneq(I\cap S) C⊊(I∩S) 。于是 ∃ y ∈ C ∖ ( I ∩ S ) \exists y\in C\setminus(I\cap S) ∃y∈C∖(I∩S) 使得 I − { y } + { x } ∈ I 1 I-\{y\}+\{x\}\in\mathcal I_1 I−{ y}+{ x}∈I1 。
上式说明 y → x y\to x y→x 边存在,因此 y ∈ S y\in S y∈S,与 y ∈ C ∖ ( I ∩ S ) y\in C\setminus(I\cap S) y∈C∖(I∩S) 矛盾(注意 C ⊆ I C\subseteq I C⊆I 哦)。 ■ \blacksquare ■
3.3.复杂度
寻找增广路的复杂度是 O ( r 2 n ) \mathcal O(r^2n) O(r2n) 其中 r = min { r 1 ( U ) , r 2 ( U ) } r=\min\{r_1(\Bbb U),r_2(\Bbb U)\} r=min{ r1(U),r2(U)} 。
我们还有一些更好的 没有应用价值的 上界:增广路径长度和是 O ( ∣ I ∣ log ∣ I ∣ ) \mathcal O(|I|\log|I|) O(∣I∣log∣I∣) 的,其中 I I I 是最大公共独立集 [3]; n n n 点 m m m 边的图拟阵的拟阵交可以在下面的复杂度内完成 [4]:
- O ( n 1 / 2 m ) \mathcal O(n^{1/2}m) O(n1/2m) 其中 m = Ω ( n 3 / 2 log n ) m=\Omega(n^{3/2}\log n) m=Ω(n3/2logn) 。
- O ( n m 2 / 3 log 1 / 3 n ) \mathcal O(nm^{2/3}\log^{1/3}n) O(nm2/3log1/3n) 其中 m = Ω ( n log n ) m=\Omega(n\log n) m=Ω(nlogn) 且 m = O ( n 3 / 2 log n ) m=\mathcal O(n^{3/2}\log n) m=O(n3/2logn) 。
- O ( n 4 / 3 m 1 / 3 log 2 / 3 n ) \mathcal O(n^{4/3}m^{1/3}\log^{2/3}n) O(n4/3m1/3log2/3n) 其中 m = O ( n log n ) m=\mathcal O(n\log n) m=O(nlogn) 。
4.带权拟阵交
这一节 O n e I n D a r k \sf OneInDark OneInDark 没看懂,如果有人懂可不可以讲讲啊 🥺
类似于 最优化问题
:给定 ω : U ↦ R \omega:\Bbb U\mapsto\Reals ω:U↦R 求 max { ∑ x ∈ I ω ( x ) : I ∈ I 1 ∩ I 2 } \max\{\sum_{x\in I}\omega(x):I\in\mathcal I_1\cap\mathcal I_2\} max{ ∑x∈Iω(x):I∈I1∩I2} 。按:疑为 R + \Reals^+ R+ 。
使用带权的 最大最小定理
max I ∈ I 1 ∩ I 2 ∑ x ∈ I ω ( x ) = min ω 1 , ω 2 { max { ω 1 ( I ) : I ∈ I 1 } + max { ω 2 ( I ) : I ∈ I 2 } } \max_{I\in\mathcal I_1\cap\mathcal I_2}\sum_{x\in I}\omega(x)=\min_{\omega_1,\omega_2}\big\{\max\{\omega_1(I):I\in\mathcal I_1\}+\max\{\omega_2(I):I\in\mathcal I_2\}\big\} I∈I1∩I2maxx∈I∑ω(x)=ω1,ω2min{ max{ ω1(I):I∈I1}+max{ ω2(I):I∈I2}}
其中 ω 1 , ω 2 \omega_1,\omega_2 ω1,ω2 是两个 U ↦ R \Bbb U\mapsto\Reals U↦R 的函数满足 ∀ x ∈ U , ω 1 ( x ) + ω 2 ( x ) = ω ( x ) \forall x\in\Bbb U,\;\omega_1(x)+\omega_2(x)=\omega(x) ∀x∈U,ω1(x)+ω2(x)=ω(x) 。
在算法实现中,我们在交换图中定义点权
ν ( x ) = { ω ( x ) , x ∉ I − ω ( x ) , x ∈ I \nu(x)=\begin{cases}\omega(x),&x\notin I\\-\omega(x),&x\in I\end{cases} ν(x)={ ω(x),−ω(x),x∈/Ix∈I
求最短路改为求 X 1 X_1 X1 到 X 2 X_2 X2 的路径中,在点权最小的前提下使得经过的边数最小。
“可以证明交换图中不存在负权环,因此这个算法一定有解。”
陆、参考
[1] 杨乾澜,浅谈拟阵的一些拓展及其应用, I O I 2018 \rm IOI2018 IOI2018 中国国家队候选队员论文。
[2] 好地方bug,拟阵及应用,知乎专栏。
[3] William H. Cunningham, Improved Bounds for Matroid Partition and Intersection Algorithms.[J]. SIAM J. Comput.,1986,15(4). 10.1137/0215066.
[4] H. N. Gabow and M. Stallman, Efficient algorithms for graphic matroid intersection and parity, extended abstract, in Automata, Languages and Programming, Lecture Notes in Computer Science, Springer, Berlin, 1985. 10.1007/BFb0015746.
[5] zghtyarecrenj,从拟阵基础到 Shannon 开关游戏,luogu-blog.
英文名为 deletion \text{deletion} deletion 和 contraction \text{contraction} contraction,论文作者未找到标准翻译。 ︎
边栏推荐
- 金额计算用 BigDecimal 就万无一失了?看看这五个坑吧~~
- C language achievement management system for middle school students
- 韩国AI团队抄袭震动学界!1个导师带51个学生,还是抄袭惯犯
- A keepalived high availability accident made me learn it again
- Transplant tinyplay for imx6q development board QT system
- 10. (map data) offline terrain data processing (for cesium)
- How to handle exceptions in multithreading?
- LVGL 8.2 LED
- Introduction to modern control theory + understanding
- Pandora IOT development board learning (RT thread) - Experiment 3 button experiment (learning notes)
猜你喜欢
IO flow: node flow and processing flow are summarized in detail.
Opencv learning notes - linear filtering: box filtering, mean filtering, Gaussian filtering
Query optimizer for SQL optimization
Test evaluation of software testing
[local differential privacy and random response code implementation] differential privacy code implementation series (13)
leetcode:6110. The number of incremental paths in the grid graph [DFS + cache]
[MySQL from introduction to proficiency] [advanced chapter] (IV) MySQL permission management and control
Quick introduction to automatic control principle + understanding
flutter 报错 No MediaQuery widget ancestor found.
Helix swarm Chinese package is released, and perforce further improves the user experience in China
随机推荐
局部修改-渐进型开发
现代控制理论入门+理解
5g TV cannot become a competitive advantage, and video resources become the last weapon of China's Radio and television
LVGL 8.2 Line
PLC Analog input analog conversion FC s_ ITR (CoDeSys platform)
深度学习 神经网络的优化方法
Alcohol driving monitoring system based on stm32+ Huawei cloud IOT design
Luo Gu - some interesting questions 2
都在说DevOps,你真正了解它吗?
Data Lake (13): spark and iceberg integrate DDL operations
LVGL 8.2 Draw label with gradient color
Detailed explanation of visual studio debugging methods
Details of FPGA underlying resources
深度学习 网络正则化
Redis publish and subscribe
The performance of major mainstream programming languages is PK, and the results are unexpected
LeetCode 1200 最小絕對差[排序] HERODING的LeetCode之路
They are all talking about Devops. Do you really understand it?
[differential privacy and data adaptability] differential privacy code implementation series (XIV)
毕业季-个人总结