昨天 CMD round 要用♿ 不会就来学了
??? ???
基础定义性质
拟阵和基、环
定义 1.1
给定全集 \(U\)，\(U\) 和一个 \(U\) 上的集族 \((U,F)\) 被称作拟阵当：
\(U\) 中的元素叫做边，\(F\) 中的元素 \(S\in F\) 叫做独立集。
第二条叫做遗传性质，第三条叫做交换性质。
定义拟阵的基为极大独立集，环为极小非独立集。
引理 1.1
拟阵的所有基大小相等。
证明：显然小的基可以通过交换性质变大，由于交换性质。
定理 1.1
对于两组不同的基 \(A,B\)，\(\forall x\in A-B,\exists y\in B-A,\text{s.t.} A-\{x\}+\{y\}\) 也是一组基。
证明：考虑独立集 \(A-\{x\}\)（由遗传性质知道）和 \(B\) 的交换性质。那么 \(y\in B-(A-\{x\})= B-A\)。
定义 1.2
给定拟阵 \((U,F)\)，对于任意集合 \(S\subseteq U\)，记秩函数为 \(S\) 子集的极大独立集大小。根据引理 \(1.1\)，这些 \(S\) 的基（在拟阵 \((S,\{S'\mid S'\subseteq S,S'\in F\})\) 上应用）相等。
性质 1.1
有界性：\(\forall S\subseteq U,0\le r(S)\le |S|\)。
单调性：\(\forall A\subseteq B\subseteq U,r(A)\le r(B)\)
次模性：\(\forall A,B\subseteq U,r(A\cup B)+r(A\cap B)\le r(A)+r(B)\)
下面证明第三条性质。
记 \(Z_{S}\) 为 \(S\) 上的基。
不妨设 \(Z=Z_{A\cap B},Z_{A\cup B}\) 是从 \(Z\) 交换扩充而来。分割 \(Z_{A\cup B}\) 为 \(Z'=Z_{A\cup B}\cap (A\cap B)\)和\(E_{A}=Z_{A\cup B}\cap (A-B),E_B=Z_{A\cup B}\cap(B-A)\)。
由构造知道，\(Z\subseteq Z'\)，又 \(Z\) 是极大的，故 \(Z=Z'\)。
此时
定义 1.3
拟阵是二元组 \((U,F)\)，其中 \(U\) 是全集，\(F=\{A\mid r(I)=I\}\) 是集族，\(r\) 是满足秩函数性质的函数。
引理1.2
上述定义等价于定义 1.1 。
证明：
\(0\le r(0)\le 0\)，故 \(r(0)=0,\varnothing \in F\)。
遗传性：对于 \(B\in F,A\subseteq B\)，\(|B|=r(B)\le r(A)+r(B-A)\)，而 \(r(A)\le |A|,r(B-A)=|B-A|,|A|+|B-A|=|B|\)，故两者同时取上界，故 \(r(A)=|A|,A\in F\)。
交换性：设 \(A,B\in F,|A|<|B|\)。
反证：设已有 \(\forall b\in B,r(A\cup \{b_{1:n}\})=|A|\)，则：
而 \(r(A)<r(B)\le r(A\cup B)\)，矛盾。证毕。
因此，可以通过秩函数定义拟阵。
几种特殊拟阵
定义 2.1
设有限全集为 \(U\)，\(U\) 中的边 \(e\) 附有一个同一域上的向量 \(v_e\)，并且这些向量维数相同。
设集族 \(F\)，\(S\in F\) 当且仅当向量组 \(\{v_e\mid e\in S\}\) 线性无关。
此时称 \((U,F)\) 是线性拟阵。
引理 2.1
\((U,F)\) 是拟阵。
证明：
显然 \(\varnothing \in F\)，且一个线性无关向量组任何子向量组都线性无关。
若 \(A,B\in F,|A|<|B|\)，则 \(\{v_e\mid e\in A\}\) 张出空间的维数是 \(|A|\)，\(\{v_e\mid e\in B\}\) 张出空间的维数是 \(|B|\)。
由于 \(|A|<|B|\)，必然存在 \(e'\in B-A,\) \(\{v_e\mid e\in A\}\) 不能线性表出 \(e'\)。那么 \(A\cup e'\in F\)。
定义 2.2
构造一矩阵 \(M\)，列向量是所有全集中的向量 \(v_e\)。
此时称 \(M\) 可以线性表出 \((U,F)\)。并且 \(M\) 的秩和 \((U,F)\) 的秩相等。
定义 2.3
定义均匀拟阵：
设有限全集为 \(U\)，\(F=\{S\mid S\subseteq U, |S|\le k\}\)。
不难验证这是拟阵。
性质 2.1
均匀拟阵在 \(GF(p)(p>n)\) 下是线性拟阵。
证明：设向量 \(v_{e_i}=(1,\alpha_i,\alpha_i^2,\dots,\alpha_i^{k-1})\)，其中 \(\alpha_i\) 为两两不同的 \(GF(p)\) 中的非零元。
-什么是 \(GF(p)\)？
-有 \(p\) 个元素的有限域（Galois Field）
那么存在这个矩阵。只需证明：向量组大小不超过 \(k\) 当且仅当他们线性无关。
首先，如果向量组大小超过 \(k\)，他们一定线性相关，因为维数只有 \(k\)。
显然只需考虑大小等于 \(k\) 的向量组。
考虑以其为列向量矩阵，是范德蒙德矩阵；
\(\operatorname{det}(A)\neq 0\) 当且仅当 \(\alpha_i\) 两两不同，而这被满足了。这就说明这些向量线性无关。
定义 2.4
对于一个无向图 \((V(G),E(G))\)，定义全集为 \(U=E(G)\)，边集 \(S\) 属于 \(F\) 的充要条件是生成子图 \((V(G),S)\) 无环，即是生成森林。
此时称 \((U,F)\) 为图拟阵。
性质 2.2
图拟阵 \((U,F)\) 是拟阵。
证明：空集和遗传显然满足。
下面证明满足交换性质。
设 \(A,B\in F,|A|<|B|\)，则 \((V(G),A)\) 的连通块数是 \(n-|A|\)，\((V(G),B)\) 的连通块数是 \(n-|B|\)。则 \(n-|A|>n-|B|\)，那么 \(B\) 中存在一条边 \(e'\) 连接 \((V(G),A)\) 中两个连通块，连上之后不会出现环。那么 \((V(G),A\cup \{e'\})\) 无环。那么 \(A\cup \{e'\}\in S\)。
性质 2.3
图拟阵在任何域中均可被线性表出（当然所以图拟阵是线性拟阵）。
证明：
对于一条边 \((u,v)\)，构造向量 \((v_1,v_2,\dots,v_n)\)，其中 \(v_u=1,v_v=-1\)，其他均为 \(0\)。
对于一个带圈生成子图 \((V(G),A)\)，遍历圈，如果正向访问到（\(e_i=(u,v)\) 从 \(u\) 到 \(v\)）就赋权系数 \(\alpha_i=1\)，否则 \(\alpha_i=-1\)。没有遍历到的 \(\alpha_i=0\)。
容易验证此时每个点都被访问了两遍，一个正的一个负的，抵消得到 \(\sum v_e\alpha_e =\bf0\)。
而不带圈的图如果线性相关，如果去掉系数为 \(0\) 的边向量，总有一个点只连接了一条边，它的贡献不可能被抵消，所以不带圈的图一定不线性相关。
注意到我们仅仅使用了单位元，单位元的逆元和零元，所以以上过程对任意域成立。
定义 2.5
给定一二分图，设左/右部点为 \(U\)，\(F=\{A\mid A\subseteq U,A\text{ 可以被一组匹配覆盖}\}\)。则称 \((U,F)\) 为横截拟阵。
性质 2.4
横截拟阵是拟阵。
空集和遗传性显然。
设 \(A,B\in F,|A|<|B|\)。
从一个点 \(u\in B\) 开始，找出匹配点，再回来到 \(A\) 中某个点再去匹配点；如此交替下去直到不能进行。若成环，则删去环；
由于 \(|A<|B|\)，存在一个点这样的路一定在 \(B\) 中开始，\(B\) 的匹配点结束。此时找到了增广路，就可以把 \(A\) 加一个左部点进去。
拟阵上的算法
拟阵贪心
算法 3.1
设有一拟阵 \((U,F)\)。
1.令初始解集 \(S\) 为 \(\varnothing\)。
2.循环：找到最小权值的未加入解集且能保证解集加上他独立的边 \(x\) 并 \(S\cup\{x\}\to S\)。
3.若不能找到，退出循环，输出 \(S\)。
定理 3.1
上述算法得到的解集为最小带权基。
证明：设 \(X\) 为 \((U,F)\) 的最小带权基。
设 \(X=\{x_1,x_2,\dots,x_r\},x_i\le x_{i+1}\)。归纳证明 $w(S)\le w(X) $。
设 \(S_i\) 为第 \(i\) 步得到的结果，\(X_i=\{x_1,x_2,\dots x_i\}\)。
显然 \(S_0\) 和 \(X_0\) 满足。下面认为 \(w(S_{i-1})\le w(X_{i-1})\)。
设 \(u=S_i-S_{i-1}\)，则根据交换性质，\(\exists v\in X_i,\text{s.t. }S_{i-1}\cup \{v\}\in F\)，而 \(w(x_i)\ge w(v)\ge w(u)\)，所以 \(w(S_i)\le w(X_i)\)。
不难发现，这是 Kruskal 算法。
这也说明了我们线性基从小到大插入的正确性。
注：似乎可以证明非拟阵则贪心不正确。
拟阵运算
定义 3.1
对于拟阵 \(M=(U,F)\)，定义其对偶拟阵 \(M^*=(U,F^*)\)，其中 \(F^*=\{A\mid \exists B\text{ is base}\subseteq U-A\}\)。
性质 3.1
对偶拟阵是拟阵。
这里我们依靠定义 1.3，依托秩函数证明。
这里证明几条公理。
有界性：\(\because r(U)\ge r(U-A),r^*(A)=|A|-r(U)+r(U-A)\le|A|\)
单调性：若 \(|A|<|B|\)