图拟阵

图拟阵只记录“哪些边可以同时保留而不产生环路”。每加一条独立边，就把两个分量合并，分量数恰减一；一旦两端已经连通，新边只能制造冗余环路，不再增加秩。这使森林的边数像线性无关向量的数量一样，具有稳定的维数意义。

在秩与闭包理路拟阵的秩与闭包Matroid rank · Matroid closure · Matroid flat证明有限拟阵秩的子模性及秩公理的逆向重建，由此推出闭包交换，并用同一个四列矩阵计算秩、平坦与依赖证书。语言中，边 $uv$ 属于 $X$ 的闭包，当且仅当 $u,v$ 已在 $(V,X)$ 中连通。自环的两端本就是同一点，因此自环总在闭包内，却从不属于独立集。

三角形的三个边元素形成秩为 $2$ 的图拟阵：任意两边是森林，三边合起来是唯一的拟阵回路理路拟阵回路Matroid circuit · Circuit of a matroid拟阵中按包含关系极小的依赖集，是独立性首次失效的局部证书。。若 $X=\{ab,bc\}$，则 $r(X)=2$，而 $ac$ 属于 $X$ 的闭包，加入它不增秩。

再给三角形添加一个孤立点 $d$，则 $|V|=4,c(G)=2$，总秩仍为 $2$。孤立点改变原图却不改变边的独立性，因此图拟阵不能恢复原图全部信息。四点路径和四点星形图的三个边都可任意选取，二者也给出同构的自由拟阵。

自环给一元回路，两条平行边给二元回路；若忽略这些短圈，就会错误地把它们判为独立。图不连通时，基是生成森林，而不是覆盖整个图的一棵树。反过来，并非每个拟阵都能由某张图的森林族产生。

任意给图的非环边定向，关联矩阵中每列在尾点写 $-1$、头点写 $1$，其余为零，自环列为零。这个矩阵在每个域上都表示理路可表示拟阵Representable matroid · Linear matroid能由某个域上矩阵列向量的线性无关关系实现的拟阵。图拟阵：圈上的列可按方向配符号相加为零；森林若有非平凡线性关系，从叶子的行先迫使唯一关联边的系数为零，再逐叶删去就得到矛盾。特征为二时 $-1=1$，论证仍成立。

因此每个图拟阵都是可表示拟阵理路可表示拟阵Representable matroid · Linear matroid能由某个域上矩阵列向量的线性无关关系实现的拟阵。，而且能在每个域上表示，故称为正则拟阵。拟阵贪心定理理路拟阵贪心定理Matroid greedy theorem完整证明有限独立系统的贪心双向刻画，区分任意实权重的基优化与非负权重的独立集优化，并在四列矩阵上核对每次接受、拒绝及最优值。应用到边权时，得到生成树或生成森林的最小权基算法；Kruskal 的“若不成圈就加入”正是在保持拟阵独立性。

若把候选元素改为整个圈的二元边向量，目标便是另一种线性基优化：Horton最小权圈基理路Horton 最小权圈基算法Horton minimum cycle basis algorithm · Horton algorithm for minimum cycle basis · Horton 最小环基算法从一致最短路树构造多项式大小的圈候选，证明候选完备性，再用二元消元选出总权最小的圈基。先构造完备候选，再按权消元；de Pina算法理路de Pina 支撑向量圈基算法de Pina minimum cycle basis algorithm · Support-vector minimum cycle basis · de Pina 最小圈基算法维护与已选圈正交的二元支撑，以双层最短路求最轻奇支撑圈，并通过基交换证明逐轮输出的圈基总权最小。改用支撑向量逐轮求最轻奇圈。此时基有m−n+c个圈，目标把共享边按出现的圈数计费，不能用图拟阵的最小生成森林替代。

图拟阵的对偶称为余图拟阵。若原图连通且有平面嵌入，对偶拟阵理路拟阵对偶Matroid duality从秩公理证明基的补集确实定义对偶拟阵，推导对偶秩公式，并以四列矩阵及其正交核给出所有子集上的可复算证书。可由平面对偶图表示，生成树补边对应对偶生成树。删除与收缩则把图的化简转成拟阵操作，也是 Tutte 多项式与网络可靠性计数的重要基础。