形式陈述

给定有限无向图 $G=(V,E)$$G=(V,E)$，令

$$ \mathcal I=\{F\subseteq E:(V,F)\text{ 不含圈}\}. $$$$\mathcal{I}=\{F\subseteq E:(V,F)\text{ 不含圈}\}.$$

则 $M(G)=(E,\mathcal I)$$M(G)=(E,\mathcal{I})$ 是拟阵，称为 $G$$G$ 的图拟阵或圈拟阵。其独立集是森林，基是在每个连通分量内选取一棵生成树所得的边集，因而

$$ r(M(G))=|V|-c(G), $$$$r(M(G))=|V|-c(G),$$

其中 $c(G)$$c(G)$ 是连通分量数。拟阵的圈恰是图中圈的边集；在允许自环和平行边的多重图约定下，自环与两条平行边也分别给出一元圈和二元圈。闭包与秩同样可由图连通性描述。

直觉

图拟阵忘掉顶点的具体名称和画法，只保留“哪些边会形成环”这一独立结构。生成树大小恒定以及森林可交换扩张，正是拟阵交换公理在图中的来源。

例子与边界

三角形给出秩为 $2$$2$ 的拟阵：任意至多两条边独立，三条边合起来成为唯一的圈。若图不连通，基不是整图的一棵树，而是各分量生成树的并。自环从不独立；两条平行边组成长度为二的圈。不同图可能给出同构的图拟阵，所以图拟阵通常不能恢复原图。并非每个拟阵都是图拟阵；例如某些向量拟阵没有任何图表示。

推论与应用

图拟阵把生成树、割与环统一到拟阵语言中，使最小生成树成为拟阵贪心的特例。其对偶在平面图中与对偶图的图拟阵对应，也连接网络可靠性、删缩递推和 Tutte 多项式。

参考资料

• James Oxley, Matroid Theory, 2nd ed., Oxford University Press, 2011，Ch. 1 and Ch. 5, graphic matroids, forests, circuits, and rank。
• J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd ed., Cambridge University Press, 2001，Ch. 13, graphic matroids and spanning forests。