图拟阵

图拟阵（graphic matroid），也称圈拟阵，以有限无向图的边作为底集，以不含环的边集作为独立集。它把图中的森林、生成树和环分别对应到拟阵的独立集、基和极小相关集，使图论对象能用统一的交换与秩语言处理。

设图有四个顶点，边为 $a=12,b=23,c=31,d=34$。边 $a,b,c$ 构成三角形，$d$ 是连向顶点四的桥。$\{a,b,d\}$ 是生成树；加入 $c$ 后出现唯一环，必须从 $a,b,c$ 中删去一条才能恢复为树。删去 $d$ 则不能消除三角形。

相关性来自三角形中的三个元素；桥 d 不属于任何环。

森林满足交换公理

对有限无向图 $G=(V,E)$，令 $${ℐ}_G=\{F\subseteq E:(V,F)\text{ 不含环}\}.$$ 本文允许平行边和自环：两条平行边组成长度二的环，自环本身就是长度一的环。若只考虑简单图，则没有这两种情形。图拟阵是 $M(G)=(E,{ℐ}_G)$。

空集和森林的子集仍是森林，故只需证明增广。设森林 $F,H$ 满足 $|F|<|H|$。假如 $H$ 的每条边都落在 $(V,F)$ 某个连通分量内部，把这些分量记为 $V_1,\dots ,V_q$。森林在 $|V_i|$ 个顶点上至多有 $|V_i|-1$ 条边，因此 $$|H|\le \sum _{i=1}^q(|V_i|-1)=|V|-q=|F|,$$ 矛盾。所以 $H\setminus F$ 中存在连接 $F$ 两个不同分量的边；加入它不可能成环。这就验证了增广公理。

这里使用的森林计数可以由叶子归纳得到：单顶点树有零条边；任意至少两个顶点的有限树有叶子，删去叶子及其唯一边，顶点数和边数都减一。逐个分量相加，森林恰有 $|V|-q$ 条边，孤立顶点也计作分量。

基、秩与图的连通分量

在 $G$ 的每个连通分量中选一棵生成树，所得森林不能再加边而保持无环，因此是图拟阵的基。反过来，若一个极大森林尚未连通某个原图分量，原图内一条跨越其分量的边还可加入，矛盾。因此基恰是“每个原图分量各取一棵生成树”。原图不连通时，基并不是覆盖整个图的一棵树。

对任意 $A\subseteq E$，设 $c(V,A)$ 为保留全部顶点、只保留 $A$ 中边后所得图的连通分量数，则 $$r(A)=|V|-c(V,A).$$ 每个分量内的森林都有相应边数上界，而逐分量取生成树达到该上界，所以公式同时包含了上界与可达性证明。

开头图中 $r(\{a,b,c\})=4-2=2$，因为顶点四孤立；$r(E)=4-1=3$。全部基是 $\{a,b,d\},\{a,c,d\},\{b,c,d\}$。桥 $d$ 属于每一个基；自环则不属于任何独立集。环恰是极小相关边集，因为环整体相关，而删掉任意一条环边便断开该环。

关联矩阵的线性表示

给每条非自环边任意选方向，构造实矩阵 $B$：每列在边的起点填 $-1$，终点填 $1$，其余为零；自环列置零。边的方向只选择列的正负，不把图变成有向无环问题。

沿一个无向环依次前进，把顺向边列加、逆向边列减，所有顶点的项抵消，得到非平凡列关系。反之，若森林的列存在线性关系，在有边分量取一个叶子；该叶子所在行只含与它相连的唯一一条边的一个非零项，迫使该边系数为零。删去这条边后重复，最终所有系数均为零。因此边集无环当且仅当对应列线性独立。这个证明把图拟阵明确表示成了线性拟阵。

变式。 给例图再加一条平行于 $d=34$ 的边 $e$，秩是否增加？答案是不增加，仍为三，因为连通分量不变；但 $\{d,e\}$ 是新的二元素圈，基可以用 $e$ 替代 $d$。若把边都改为有向并只禁止有向环，则通常不再得到这个拟阵，不能照搬无向森林的交换证明。

图拟阵保留边集的相关结构，并不记录图的全部几何位置；把同一图画成弯线或直线不会改变它。最小生成树利用的是森林可交换这一结构，而反馈边集利用的是删边后留下一个独立边集的互补关系。