拟阵回路

形式陈述 ​

设 $M=(E,\mathcal{I})$ 是有限拟阵公理库拟阵Matroid用遗传性和交换公理抽象线性无关集与森林结构的组合系统。。集合 $C\subseteq E$ 称为一个回路，若 $C\notin \mathcal{I}$，而每个真子集 $C^{\prime }⊊C$ 都属于 $\mathcal{I}$。也就是说，回路是按包含关系极小的依赖集。全体回路组成的族记为 $\mathcal{C}(M)$。

回路族满足三条性质：$\varnothing \notin \mathcal{C}(M)$；不同回路互不真包含；若 $C_1,C_2$ 是不同回路且 $e\in C_1\cap C_2$，则存在回路

$$C_3\subseteq (C_1\cup C_2)\setminus \{e\}.$$

最后一条称为回路消去公理。这三条性质也可反过来定义有限拟阵：令不含任何回路的集合为独立集，即可恢复 $\mathcal{I}$。若 $B$ 是基而 $e\notin B$，则 $B\cup \{e\}$ 中恰有一个回路，称为 $e$ 关于 $B$ 的基本回路。

直觉 ​

回路是独立性失败时不能再缩小的证书。依赖集可能夹带许多无关元素，回路则剥去这些冗余：删除其中任意一个元素，依赖立刻消失。它记录的不是“依赖有多大”，而是哪些元素刚好共同造成一次不可避免的依赖。

消去公理表达两份最小依赖可以重新组合。若两条依赖共享元素 $e$，消去 $e$ 后，其余元素中仍藏有某条最小依赖；在线性代数中这对应消去两个线性关系中的同一列，在图中则对应两条圈沿共同边拼接后还能找出圈。

例子与边界 ​

图拟阵的回路是简单圈的边集。三角形的三条边构成回路：三边一起成圈，删去任一边就成为森林。若两个图圈共享一条边，取它们的对称差可以从去掉共享边后的边集中找到另一个圈，这正是回路消去的图论图像。

在线性拟阵中取

$$v_1=(1,0),v_2=(0,1),v_3=(1,1).$$

$\{v_1,v_2,v_3\}$ 线性相关，而任意两个都线性无关，所以它是回路。零向量单独构成一元素回路，对应 loop；两个非零平行向量构成二元素回路。

“极小依赖”是按包含关系极小，不是基数最小。一个拟阵可以同时含二元素回路与更大的回路，后者不会因为前者更短就失去回路资格，只要它本身不包含更小依赖集。一般拟阵回路也没有顶点次序、方向或几何闭合曲线；把图论圈的画面强加给抽象拟阵会产生不存在的结构。

推论与应用 ​

集合 $I\subseteq E$ 独立，当且仅当它不含任何回路。因而回路给出依赖性的局部证书，并允许用“找到回路后删去一个元素”的方式维护独立集。对基 $B$ 加入新元素 $e$ 所产生的基本回路指出了所有可与 $e$ 交换的基元素：若 $f\in C_B(e)\setminus \{e\}$，则 $(B-\{f\})\cup \{e\}$ 仍是基。

在图拟阵中，这一交换就是给生成树加一条边后出现唯一简单圈，再从圈上删去另一条边；最小生成树算法的交换论证由此获得统一语言。对偶拟阵公理库拟阵对偶Matroid duality以基的补集为基定义的对偶拟阵构造。的回路称为原拟阵的 cocircuit，在图拟阵中对应极小割。回路消去还支撑拟阵交、表示性判别和编码理论中最小相关列集的研究。

参考资料

• James Oxley, Matroid Theory, 2nd ed., Oxford University Press, 2011, Chapter 1.
• D. J. A. Welsh, Matroid Theory, Academic Press, 1976, Chapters 1–2.