Combinatorial Optimization-Matroid

前言

拟阵这个概念在各个场合听了很多遍了，一直没有系统地整理过。本篇基于组合优化经典教材Combinatorial Optimization-Algorithms and Complexity第12章, 主要介绍拟阵的一些基本性质和两拟阵交算法。

独立集系统和拟阵

定义独立集系统$S=(E, \mathcal{I})$, $E$是基本元素的集合, $\mathcal{I} \subseteq 2^{E}$, $\mathcal{I}$中的元素称为独立集。
$\mathcal{I}$需要满足遗传性: 如果$A \in \mathcal{I}, B \subseteq A$, 那么$B \in \mathcal{I}$.

举例:
定义在无向图$G(V, E)$上的独立集系统, $\mathcal{I}$是不构成环的边集合, 显然满足遗传性。
求无向图的最大生成树, 实际上是先给$E$中每个元素赋予一个权值(边权), 然后求一个权值最大的独立集。
回忆一下kruskal算法, 每次选一条边权最大的边, 如果把它加入答案不形成环，就把它加入答案。
推广一下，给定任意独立系统，任意给每个元素一个非负的权值，要求权值最大的独立集，容易得到下面的贪心算法:

将元素按权值从大到小排序.
按顺序依次考虑每个元素, 如果把这个元素加入答案后仍然是一个独立集，就加入答案。

不幸的是, 这个算法只有在特定条件下才会给出最优解。
比如考虑求二分图图的最大权值匹配, 定义独立集为可以形成匹配的边集。考虑一个4个点3条边的图$V=\{u_1, u_2, u_3, u_4\}, w(u_1,u_2)=w(u_3, u_4)=5, w(u_1, u_4)=8, w(u_2, u_3) = 1$, 贪心算法会选择边$(u_1, u_4), (u_2, u_3)$, 权值是9, 最优解是$(u_1, u_2), (u_3,u_4)$, 权值是10.
我们把贪心算法能够使用的独立集系统称为拟阵(matroid), 比如上面定义在无向图边集上的独立集系统(一个边集是独立集当且仅当不包含环)，贪心算法实际上就是kruskal算法, 为了方便, 给它一个名字叫图拟阵(graphic matroid)。
特别地, 很多问题只要求取一个最大的独立集, 即元素权重都是单位1的特殊情况, 如果这个独立集系统是拟阵, 我们称这种拟阵叫做unweighted matroid.

拟阵的性质

那么如何判定一个独立集系统$M$是不是拟阵呢？下面三条定义是等价的:

$M$是拟阵, 任意给元素分配非负的权值, 贪心算法能得到最优解。
假设有2个独立集$I_1, I_2, |I_2| = |I_1|+1$, 那么$\exists e \in I_1\backslash I_2, I_1 \cup e \in \mathcal{I}$. 通俗地讲，就是如果2个独立集大小相差1, 那么一定可以从大的独立集那里拿一个给小的, 使新的集合还是独立集。
若$A \subseteq E$, $I_1, I_2 \subseteq A$是$A$上的极大独立集, 那么$|I_1|=|I_2|$. 也就是$E$的任意子集上的极大独立集大小相同。

证明:
$1 \rightarrow 2:$
设$|I_1|=k, |I_2| = k+1$, 只要令

$w(e) = \begin{cases} k+2 & e \in I_1 \\ k+1 & e \in I_1 \backslash I_2 \\ 0 & e \notin I_1 \cup I_2 \end{cases}$

假设$\forall e \in I_1\backslash I_2, I_1 \cup e \notin \mathcal{I}$, 按照贪心算法会选择$I_1$, 权值是$k(k+2)$, 实际上$I_2$的权值是$(k+1)(k+1)$更大，贪心算法就挂了。

$2 \rightarrow 3:$
显然, 如果$|I_1| \lt |I_2|$, 考虑$I_3 \subseteq I_2, |I_3|=|I_1|+1$, 根据(2)可以从$I_3$那里拿一个元素给$I_1$构成一个更大的独立集, 与$I_1$是极大的矛盾。

$3 \rightarrow 1:$
假设$w(e_1) \geq w(e_2) \geq w(e_3) \geq \cdots$, 贪心算法求出的权值最大独立集是$I=\{e_{i_1}, e_{i_2}, \cdots, e_{i_m} \}$, 最优解是$J=\{e_{j_1}, e_{j_2}, \cdots, e_{j_m} \}$.
设$k$是最小的正整数满足$i_k \gt j_k$. (让$I$和$J$的元素一一对应, 前面$k-1$个都是$I$中编号小, 第$k$个是$J$中编号小, 因为$J$的权值比$I$大, $k$一定存在). 利用(3), 令$A:=\{e_1, e_2, \cdots, e_{j_k}\}$, 根据贪心算法的过程 $I \cap A$是 $A$上的极大独立集, 大小为$k-1$, 而$J \cap A$也是$A$上的独立集, 甚至还不是极大的，大小却是$k$. 违反了(3).

另外(2)还可以推出只要两个独立集大小不一样, 就可以从大集合里拿一个给小的, 新集合还是独立集。

接下来引入几个概念:

秩(Rank). 根据上面第3条, $E$的任意子集$A$上的极大独立集大小相等。这个大小就是$A$的秩, 记为$r(A)$.
基(Basis). $A$的基上的任意极大独立集称为$A$的基.
回路(Circuit). 极小的非独立集(相关集), 即它本身不是独立集，但删掉任意一个元素后都是独立集。

为了方便理解, 我们以图拟阵为例子.
图拟阵中任意边集$A \subseteq E$, $r(A)$是其生成子图的生成森林边数(也就是生成子图的顶点数-联通块个数), 基就是任意生成森林, 回路就是一个简单环。

再看一个独立集系统, 它的元素集合是一些维数相同的向量, 独立集的定义就是线性无关的向量集合。根据线性代数的知识, 任意向量集合的极大线性无关组大小相同，即满足上面的判断独立集是否是拟阵的第3条，所以该独立集系统是一个拟阵，之后我们称它为线性拟阵。
线性拟阵的秩, 基都和线性代数中吻合, 回路就是极小的线性相关组。
参加过算法竞赛的同学可以去拿BZOJ2460练练手, 就是求一个定义域在$F_2^n$下的线性拟阵权值最大的独立集, 用贪心算法解决即可。

下面是关于回路的一个有用的定理:
定理1:
如果往独立集$I$中加入一个元素$e$后, $I+e$不独立了, 那么$I+e$中包含唯一的一个回路。并且这个回路就是$\{c \mid I+e-c \in \mathcal{I}\}$

可以拿图拟阵来理解这个定理: 考虑不成环的一些边(独立), 往里面加了一条, 如果成环(不独立), 那么会有唯一的一个简单环(回路), 这个回路就是新的边集($I+e$)里面那些去掉后会使得图没有环的边。

我们首先证明$C=\{c \mid I+e-c \in \mathcal{I}\}$确实是$I+e$中的回路。

显然$C \subseteq I+e$, 先证明$C$不是独立集。假设$C$是独立集, 那么一定可以往$C$里面加元素将它扩充成$I+e$的一个基$C’$. 因为$r(I+e) = r(I) = |I|$, 因此$|C’|=|I|$, 所以$C’ = I+e-c, c \notin C’$, 而根据$C$的定义, $c \in C$, 导致矛盾。
再证明$C$去掉任意一个元素后都是独立集. $\forall c \in C, I+e-c \in \mathcal{I}$,而$ C-e \subseteq I+e-c$, 根据遗传性$C-e \in \mathcal{I}$.

唯一性证明:
假设还有另一个回路$D$. 考虑$c \in C \backslash D$, 容易发现$ D \subseteq I+e-c$, 根据$C$的定义, $I+e-c \in \mathcal{I}$, 从而根据遗传性推出$D$是独立集,导致矛盾。

下面的内容和书上不完全一致, 因为我自己看书的时候在这些地方卡了好几天, 所以我尝试用自己的方法来解释, 因此可能会有一些错误, 希望发现的兄弟指出来。

为了之后方便解释拟阵交的算法，还需要引入一个span的概念。
考虑$A \subseteq E, S(A):=\{B \mid A \subseteq B, r(A)=r(B)\}$.
先来验证$S(A)$关于集合的并操作封闭, 即$\forall B_1,B_2 \in S(A), B_1 \cup B_2 \in S(A)$.
证明:
设$\mathcal{B}$是$A$的基, 那么显然它也是$ B_1, B_2$的基。我们证明它还是$ B_1 \cup B_2$的基: 如果它不是，那么它是非极大的独立集, 那么可以往里面加一个元素使它还是独立集, 但是它已经是$ B_1, B_2$的基了，所以又不可能往它里面加$B_1$或者$B_2$的元素, 导致矛盾。

定义$span(A):=\bigcup\limits_{B_i \in S(A)} B_i$, 显然$span(A) \in S(A)$, 等价地, $span(A)$就是极大的(也是最大的)$A$的超集, 满足秩和$A$的秩一样。

引理1: $\forall B \in S(A), span(B) = span(A)$.
证明:
$B \in S(A) \rightarrow B \subseteq span(A) \rightarrow span(A) \in S(B) \rightarrow span(A) \subseteq span(B)$
$A \subseteq span(A) \subseteq span(B) \rightarrow span(B) \in S(A) \rightarrow span(B) \subseteq span(A)$.
所以$span(A)=span(B)$.
根据上面的引理, 容易验证$span(span(A)) = span(A)$.

在图拟阵中, 如果$A$是某个边集, $span(A)$ 就是往$A$中加入尽可能多的边, 使得生成子图的顶点数不会增多。

下面的定理更加简洁的表示出了$span(A)$.
定理2: $span(A) = \{e \mid r(A+e)=r(A)\}$
证明:

记$K=\{e \mid r(A+e)=r(A)\}$, 那么$K$可以写作 $\bigcup\limits_{e \in E \backslash A: r(A+e)=r(A)} (A+e)$ 而$\forall e \in E \backslash A, r(A+e)=r(A)$, 有$A+e \in S(A)$, 故$K \in S(A), K \subseteq span(A)$.
反过来, 考虑$e \in span(A) \backslash A$, 显然$r(A+e) = r(A)$. 因此$span(A)$可以写成 $\bigcup\limits_{e \in span(A) \backslash A: r(A+e)=r(A)} (A+e)$ 容易看到$span(A) \subseteq K$.

下面为拟阵交做铺垫的两个引理:

引理2: $span(A) = A \cup \{C \mid \text{C is circuit with all but one element in } A \}$
证明:

首先证明$span(A)$可以表示成$A$和若干特殊回路的并, 特殊回路指的是只有一个元素不在$A$内的回路。根据上面的定理 $\begin {split} span(A) &= \bigcup\limits_{e \in E \backslash A: r(A+e)=r(A)} (A+e) \\ &= A \cup \bigcup\limits_{e \in E \backslash A: r(A+e)=r(A)} (A+e) \\ &= A \cup \bigcup\limits_{e \in E \backslash A: r(A+e)=r(A)} (\text{Basis of } A +e) \\ &= A \cup \bigcup\limits_{e \in E \backslash A: r(A+e)=r(A)} (\text{Circuit consists of basis of } A \text{ and } e) \end{split}$
再证明任意特殊回路$\subseteq span(A)$. 给定某个特殊回路, 我们把它表示成$I+e, I \in \mathcal{I}$, 我们只要证明$r(A+e)=r(A)$. 假设$r(A+e) \gt r(A)$, 那么存在一个$A$的基$B, B+e \in \mathcal{I}$. 考虑$I$, 如果它不是$A$的基, 那么可以先把它扩充成$A$的基, 记作$I’$. 比较$I’$和$B+e$, 后者大小比前者大1, 因此可以从后者拿一个元素给前者, 但是这个元素不可能来自$B$, 否则$I’$就不是集了。所以这个元素只能是$e$, 因此$I’+e \in \mathcal{I}$, 而它的子集$I+e$却是一个回路, 导致矛盾。

引理3: 若$I \in \mathcal{I}, I+e \notin \mathcal{I}$, $C$是$I+e$中唯一的circuit, 则$\forall c \in C, span(I) = span(I+e-c)$, 且$I+e-c \in \mathcal{I}$.
证明:

$r(I+e)=r(I) \rightarrow I+e \in S(I)$, 根据引理1, $span(I) = span(I+e)$.
根据定理1, $I+e-c \in I$, $r(I+e-c) =r(I+e) =|I|$, 又因为$I+e-c \subseteq I+e$, 所以$I+e \in S(I+e-c)$, 从而有$span(I+e-c) = span(I+e)$.
综上$span(I+e-c) = span(I)$.

拟阵的交

许多时候, 一个组合优化问题并不能表示成一个拟阵, 但是却可以表示成两个拟阵甚至更多拟阵的交。比如二分图匹配, 在最开始我们已经举了一个反例说明它虽然是个独立集系统，但并不是一个拟阵。然而，我们可以把它表示成两个拟阵的交:
我们用$G(L, R, E)$表示一个二分图, $L, R$分别是两边的顶点集合, $E$是边集, 也是拟阵的基本元素集合。
定义拟阵$M_1(E, \mathcal{I}_1)$: 边集$A \in \mathcal{I}_1$ 当且仅当$A$中边的左端点互不相同。
定义拟阵$M_2(E, \mathcal{I}_2)$: 边集$A \in \mathcal{I}_2$ 当且仅当$A$中边的右端点互不相同。
容易验证$A$是合法的匹配当且仅当$A \in \mathcal{I}_1 \cap \mathcal{I}_2$.

一般地, 独立集系统$S(E, \mathcal{I})$表示成$K$个拟阵的交, 记作$S = \bigcap\limits_{i=1}^K M_i(E, \mathcal{I}_i)$, $\mathcal{I} = \bigcap\limits_{i=1}^K \mathcal{I}_i$.

如果一个独立集能表示成$K$个拟阵的交的形式, 能给我们带来什么方便之处呢?

定理3: 任意两个极大独立集$A, B$, 不妨设$|A| \leq |B|$, 一定满足$|B| \leq K|A|$.
从近似算法的角度, 如果只需要求最大独立集(unweighted matroid), 随便取一个极大独立集就可以做到$K$的近似比, 比如上面的不带权的二分图匹配问题, 随便取一个极大匹配, 它大小就至少是最优解的一半。

证明:

设$A_i$是第$i$个拟阵中$A\cup B$包含$A$的极大独立集。用反证法容易证明$\forall e \in B\backslash A, e \notin \bigcap A_i \backslash A$, (如果属于, 那么$A+e$也是独立集), 也就是说, $e$最多出现在$K-1$个$Ai \backslash A$里。因为$A_i \backslash A$里面的元素只能在$B\backslash A$里, 进一步可以推出$\sum\limits_{i=1}^{K} |A_i \backslash A| \leq (K-1)|B\backslash A| \leq (K-1)|B|$.
同样地, 定义$B_i$是第$i$个拟阵中$A\cup B$包含$B$的极大独立集, 根据拟阵的性质$|A_i| = |B_i|$.
$\begin{split} K|B| &\leq \sum\limits_{i=1}^K{|B_i|} \\ &= \sum\limits_{i=1}^K{|A_i|} \\ &= \sum\limits_{i=1}^K{(|A|+|A_i \backslash A|)} \\ &= K|A| + \sum\limits_{i=1}^K{|A_i \backslash A|} \\ &\leq K|A| + (K-1)|B| \end{split}$ 从而推出$B \leq K|A|$.

下面的定理挺有趣, 但似乎没什么卵用。
定理4: 任意一个独立集系统$S(E, \mathcal{I})$都可以表示成有限个拟阵的交。
证明:

设独立集系统包含$K$个极小非独立集$C_1, C_2 \cdots C_K$.
构造$K$个拟阵$M_i(E, \mathcal{I}_i)$, 其中$ \mathcal{I}_i = \{ A \subseteq E \mid C_i \not \subseteq A\}$, 用判定你真的第二条规则可以证明$M_i$是拟阵。
我们证明$S$可以表示成它们的交, 即$ \forall A \in \mathcal{I}$当且仅当$\forall i, A \in \mathcal{I}$, 这个根据$M_i$的定义很容易证明。

上面这个整理看起来很厉害，但对大多数实际问题并没有很大的帮助, 因为由上面的方法构造出来的独立集往往是很多个拟阵的交。
ps: 上面两个定理来自张国川老师在zju开的课程<<应用运筹学基础>>。

下面的定理说明表示成三个或者超过三个拟阵的交对解决问题并没有很大的帮助。
定理5: 如果把一个独立集系统表示成3个unweighted matroid的交, 求它的最大独立集是NP-Hard的。
证明:

哈密顿路径问题可以规约到3拟阵交。哈密顿路径问题指的是给定有向图$G(V,E)$, 起点$s$和终点$t$, 求一条$s$到$t$的路, 且经过图中所有点一次。
定义$M_1$是定义在将图$G$的边去掉方向后的无向图$G’$上的图拟阵。
定义$M_2$是定义在图$G$上边集的拟阵, 独立的定义是每个点的出度不超过1, $t$的出度是0. (利用第三条规则证明是拟阵)
定义$M_3$是定义在图$G$上边集的拟阵, 独立的定义是每个点的入度不超过1, $s$的入度是0.
容易验证上面3个拟阵的交的独立集是若干条不相交路径的并, 且其中一条路径是从$s$到$t$. 原图存在哈密尔顿路径当且仅当最大独立集的规模是$|V|-1$.

Intersection of 2 unweighted matroids

2个拟阵的交是多项式可解的, 这里介绍一下算法(有点难理解, 需要多花点时间)。我花了很多时间去揣摩算法一步步推导的motivation, 个人觉得学习算法不但要理解算法的过程和正确性，更要学习作者是如何一步步想到这个算法的。因此我希望把下面的过程写成诱导性质的，而不是
直接给出一个算法，然后证明它的正确性和复杂度。

我们先回忆一下不带权二分图最大匹配的过程:
假设当前已经求得匹配$I$, 定义相对于$I$的增广路为长度为奇数的边的序列$L=[e_1, e_2 \cdots e_{2n-1}]$, 其中$e_{2k-1} \notin I, e_{2k} \in I$, 容易验证$I \oplus S$也是一个匹配, 且大小相比$M$增加了1. 增广路定理表明如果当前匹配是$I$, 且不存在相对于$I$的增广路，那么它就是最大匹配。

我们从拟阵的角度来看这个过程:
假设我们每次是从左边($M$)的点出发找增广路.
$I \oplus S = I + e_1 - e_2 + e_3 \cdots -e_{2n-2} + e_{2n-1}$.
$I+e_1$在保持左边独立性的前提下让独立集大小增加1($I+e_1 \in \mathcal{I}_1$), 但多了一条边之后, 右边的某个点就会和2条边相关, 右边的独立性被破坏($I+e_1 \notin \mathcal{I}_2$).
$I+e_1-e_2$这一步去掉$e_2$, 又让右边满足独立($I+e_1-e_2 \in \mathcal{I}_2$), 而且是去掉一个元素, 左边肯定还是独立。
…
$I + e_1 - e_2 + e_3 \cdots -e_{2n-2} + e_{2n-1}$这一步在保持左边独立性的前提下让独立集大小增加1, 而且幸运的是, 右边也是独立的, 于是就找到了一条增广路。
这个过程本质上是在奇数步尝试增加一个元素, 并且保持$M_1$中的独立性，然而这可能会导致$M_2$中的独立性被破坏, 所以在偶数步又去掉一个元素, 使得重新满足$M_2$中的独立性, 直到在某个奇数步运气特别好, 没有破坏右边的独立性。拟阵交算法就是从中受到启发得出的。

上面的过程看起来似乎挺简单的？但是有一个问题，用上面的方法找增广路, 在第$i$步找一个元素$e_i$, 它符不符合要求是和$e_1, e_2 \cdots e_{i-1}$的选择有关的, 这样搜索空间就相当大了, 难以用多项式bound住, 所以我们需要把增广路的条件放宽一点, 后面会证明放宽条件之后找到的解也一定是最优解。

后面的内容主要是基于MIT matroid lecture, 因为我个人觉得书上讲得过于突兀, 有点摸不着头脑, 我看了3-4遍才看明白。相比之下MIT的这份课件要易于理解一些。当然, 能将两者结合起来看，可以更好地理解算法提出的motivation。

假设当前的独立集是$I \in \mathcal{I}_1 \cap \mathcal{I}_2$, 如何放宽条件呢？

考虑奇数步(第$2k+1$步), 原本我们是要求$I+e_1-e_2\cdots -e_{2k} + e_{2k+1} \in \mathcal{I}_1$, 但是这个条件太难了, 我们放宽成: $I-e_{2k}+e_{2k+1} \in \mathcal{I}_1$.
同理偶数步放宽成$I - e_{2k} + e_{2k-1} \in \mathcal{I}_2$.

定义:

$X_1 := \{e \mid e \notin I, I+e \in \mathcal{I}_1 \}$.
$X_2 := \{e \mid e \notin I, I+e \in \mathcal{I}_2 \}$.
辅助图$G$(有向图, 而且是二分图), 点是独立集基本元素, 两个点$e_x \in E \backslash I$, $e_y \in I$:
- 如果$I-e_y+e_x \in \mathcal{I}_2$, 那么$e_x$向$e_y$连边。
- 如果$I-e_y+e_x \in \mathcal{I}_1$, 那么$e_y$向$e_x$连边。

容易验证放宽条件后的增广路(为了方便, 把它叫做”广义增广路”好了)就是辅助图中从$X_1$出发到$X_2$的一条简单路径。
看下面图中的例子, (a)是定义在有向图边集上的一个独立集系统, 将它表示成2个拟阵的交, $M_1$是图拟阵(独立条件是不考虑边的方向无环), $M_2$独立集的条件是每个点最多有一条入边, 当前已经选择的独立集$I=\{e_2, e_4, e_6\}$, 即圈起来的边, 图(b)是相应的辅助图:

一条广义增广路对应$e_1$到$e_5$的一条简单路。观察发现, $L_1=[e_1, e_2, e_3, e_4, e_5]$就是一条广义增广路, 但是$I \oplus L_1=\{e_1, e_3, e_5, e_6\}$并不是原问题的独立集($\{e_1, e_3, e_6\}$构成环)。
再看$L_2= \{e_1, e_4, e_5\}$, 观察发现$I \oplus L_2 = \{e_1, e_2, e_5, e_6\} $是独立集。说明广义增广路不一定是增广路, 即$I \oplus L \in \mathcal{I}_1 \cap \mathcal{I}_2$不一定被满足。
注意$L_2$的长度要比$L_1$短, 因此我们大胆猜测, 如果我们找的是一条从$X_1$到$X_2$最短路, 那么这条广义增广路是增广路。

因此我们得到下面的算法:

初始化$I:=\emptyset$.
构造相对于$I$的辅助图$G(I)$.
找到相应的起点终点集合$X_1, X_2$.
用宽度优先搜索(BFS)找到从$X_1$到$X_2$最短路$L$, 令$I:= I \oplus L$, 返回第2步。如果从$X_1$到$X_2$没路, 算法结束。

幸运的是，这个算法就是对的。下面给出证明, 不关心证明的大哥们可以直接用上面的算法。

首先来证明最短的广义增广路是增广路, 设最短的广义增广路$L=\{e_1, e_2 \cdots e_{2k+1}\}(k>=1)$, $k=0$的情况, 说明$e_1 \in X_1 \cap X_2$, 显然合法。
因为$L$是最短路, $e_2, e_3, \cdots e_{2k+1} \notin X_1$, $e_1, e_2, \cdots e_{2k} \notin X_2$, 为了方便, 我们用$L_{i,j}$来表示$[e_i, e_2 \cdots e_j]$.

$I \oplus L \in \mathcal{I}_1$:
- 我们通过归纳法证明$\forall 0 \leq i \leq k, span_1(I+e_1) = span_1(I\oplus L_{1, 2i+1})$, $span_i$表示第$i$个拟阵的span, 显然这个结论比$I+e_1-e_2 \cdots + e_{2i+1}\in \mathcal{I}_1$更强。
- $i = 0$显然成立。
- 考虑$i \geq 1$, 因为$I \in \mathcal{I}_1, I+e_{2i+1} \notin \mathcal{I_1}(否则e_{2i+1}\in X_1)$, 那么$I+e_{2i+1}$包含唯一circult $C$, 且$e_{2i} \in C$。
- 假设$span_1(I+e_1) = span_1(I\oplus L_{1,2i-1})$, 那么$I\oplus L_{1,2i-1} \in \mathcal{I}_1$。如果$\{e_2, e_4, \cdots e_{2i-2} \}$中的某一个$e_j \in C$, 那么$I-e_j+e_{2i+1} \in \mathcal{I}_1$, 根据辅助图的定义$e_j$到$e_{2i+1}$有边, 那么$[e_1, e_2 \cdots e_{2i+1}]$就不是最短路了, 因为$[e_1, e_2, \cdots e_j, e_{2i+1}]$更短。
- $I \oplus L_{1,2i-1} + e_{2i+1}$可以看做$I+e_{2i+1}$删去$e_2, e_4 \cdots e_{2i-2}$再加上$e_1, e_3, \cdots e_{2i-1}$, 上一条说明没有删掉$C$中的边, 因此$C \subseteq I \oplus L_{1,2i-1} + e_{2i+1} $。
- $I \oplus L_{1,2i-1} \in \mathcal{I}_1$, 但是$I \oplus L_{1,2i-1} + e_{2i+1} $, 因此$I \oplus L_{1,2i-1} + e_{2i+1} $包含唯一circult, 并且就是$C$.
- $e_{2i} \in C$, 所以根据引理3,
  $span_1(I \oplus L_{1,2i-1} + e_{2i+1} -e_{2i}) = span_1(I \oplus L_{1,2i-1}) = span_1(I+e_1)$.
$I \oplus L \in \mathcal{I}_2$:
- 同样使用归纳法证明, 只不过方向需要反一下, $\forall 0 \leq i \leq k, span_2(I) = span_2(I\oplus L_{2i+1, 2k+1})$.
- 所有的证明和上面都是对称的(从$i=k$开始, 推到$i=0$)。

最后还剩下一件事, 我们得证明如果不存在从$X_1$到$X_2$的广义增广路, 那么当前独立集$I$就是最大的。

定理6(Min-Max Formula):

$\max_{I \in \mathcal{I}}|I| = \min_{U \subseteq E}{r_1(U)+r_2(E \backslash U)}$

首先容易证明$\forall I \in \mathcal{I}, \forall U \subseteq E, |I| \leq r_1(U)+r_2(E \backslash U)$:

把$I$分成$A=I \cap U和B= I \backslash A$两部分。
$A \subseteq U, A \in \mathcal{I}_1 \rightarrow r_1(U) \geq |A|$.
$B \subseteq E \backslash U, B \in \mathcal{I}_2 \rightarrow r_2(E \backslash U) \geq |B|$.

考虑算法的最后一次迭代, 也就是发现$X_1$到$X_2$没有路的时候, 所求出的独立集是$I$.
如果$X_1$或者$X_2$是空集, 那么$I$是$M_1$或者$M_2$的极大独立集, 显然$I$就是最大独立集。之后默认$X_1,X_2 \neq \emptyset$。
令$U$为辅助图中能到达$X_2$的元素的集合, 我们证明$|I| = r_1(U) + r_2(E \backslash U)$, 即上面的定理的等号成立。

$X_2 \subseteq U, X_1 \cap U = \emptyset$, 否则算法会继续迭代。
证明$r_1(U)=|I\cap U|$:
- 假设$ r_1(U) \neq |I\cap U|$, 那么$r_1(U) \gt |I \cap U|$, 进而$\exists x\in U \backslash I, (I \cap U) + x \in \mathcal{I}_1$.
- 如果$I \subseteq U$,即$I \cap U = I$, 那么$I+x \in \mathcal{I}_1$, 说明$e \in X_1$, 而$X_1 \cap U = \emptyset$, 所以这种情况不可能发生, 也就是说$I \backslash U \neq \emptyset$.
- 因为$I \cap U + x \in \mathcal{I}_1$, 所以$I+e$要么$\in \mathcal{I}_1$, 要么包含唯一的circuit, 不管哪种情况, 都$\exists y \in I \backslash U, I+x-y \in \mathcal{I}_1$, 从而根据辅助图的定义$y$到$x$有边, 根据$U$的定义$x \in U$可以推出$y \in U$, 导致矛盾。
同理可以证明$r_2(E \backslash U) = |I \cap (E \backslash U)|$, 和前面部分是对称的。
综上$|I| = r_1(U) + r_2(E \backslash U)$。

编程练习

codechef monthly challenge的一个题目。
题目大意是给出两个$n$个点$m$条边的无向图$G_1(V_1, E_1), G_2(V_2, E_2)$, 求一个最小的下标集合$J$, 使得$G_1(V_1, E_1(J))$和$G_2(V_2, E_2(J))$ 都是联通的。

这个题需要转化一下, 只需要求出定义在$G_1$和$G_2$上的图拟阵的交的最大独立集$|I|$,容易验证 $|J| = 2n-2-|I| $。

求两个图拟阵的交的细节:
构造辅助图：

$X_1, X_2$就是加入后仍然不构成环的那些边。只需要预处理每个点属于哪个联通块(DFS/并查集)。
如果$I-e_y+e_x \in \mathcal{I}_2$, 那么$e_x$向$e_y$连边。实际上只需要考虑加入第$i$条边后, 如果在$G_2$中构成环, 那么环上的每条边对应的点在辅助图中向第$i$条边对应的点连边。
如果$I-e_y+e_x \in \mathcal{I}_1$, 那么$e_y$向$e_x$连边。实际上只需要考虑加入第$i$条边后, 如果在$G_1$中构成环, 那么环上的每条边对应的点在辅助图中向第$i$条边对应的点连边。
如何遍历一个环: 我的做法是将森林预处理成有根树的集合, 边$(u,v)$加入后如果形成环, 那么让$u, v$沿着父亲边向上走直到他们在最近公共祖先相遇。

参考代码

还有几个练习题也是拟阵交：