拟阵

拟阵保留“独立性”中最适合交换和贪心的部分。向量是否线性无关依赖具体系数，图中的边是否成环依赖具体连接方式；拟阵把这些细节暂时忘掉，只记录哪些子集可以同时选择。

遗传性保证选择可以安全撤回。交换公理则保证不同选择路径不会把人困在大小不同的极大解中：若一个独立集比另一个小，总能从后者借来一个元素继续扩张。正是这条性质，使按权重从大到小选择元素的贪心算法能够修正局部选择，并到达全局最优基。

所有基等势是交换公理的直接后果，而不是额外假设。若 $B_1,B_2$ 都是基却有 $|B_1|<|B_2|$，增广公理会允许向 $B_1$ 再加入一个元素，与其极大性矛盾。拟阵中的“维数”因此像线性代数一样稳定。

给定图 $G=(V,E)$，把不含环的边集视为独立集，得到图拟阵公理库图拟阵Graphic matroid以图边为底集、以无环边集为独立集的拟阵。。若图连通，基正是生成树；若图有多个连通分量，基是各分量生成树的并。回路则对应图中的简单环。

给定矩阵，把列向量的线性无关子集视为独立集，得到向量拟阵。不同矩阵甚至不同域上的表示可能产生同一个拟阵，因为拟阵只记住依赖模式，不保留具体系数。能由某个域上的向量组表示的拟阵称为可表示拟阵公理库可表示拟阵Representable matroid · Linear matroid能由某个域上矩阵列向量的线性无关关系实现的拟阵。，但并非所有拟阵都可表示。

均匀拟阵 $U_{r,n}$ 的底集有 $n$ 个元素，所有大小不超过 $r$ 的子集都独立。它把约束简化为纯粹的容量限制，基就是任意 $r$ 元子集。分区拟阵则把底集分成若干块，并限制每块最多选择给定数量的元素；许多配额与资源分组约束都能写成这种形式。

向下封闭本身还不够。设

这个集合族满足遗传性，但 $\{a\}$ 无法从较大的独立集 $\{b,c\}$ 中加入任何元素，因此违反交换公理。它存在大小为 $1$ 和 $2$ 的不同极大独立集，恰好暴露了秩不稳定的问题。

本页采用有限拟阵。无限底集上，简单地把基数不等式写进增广公理不足以保证所需结构，通常还要加入适合无限链的极大性公理。拟阵独立也与概率独立无关；二者共享词语，却描述完全不同的关系。

拟阵贪心定理公理库拟阵贪心定理Matroid greedy theorem有限独立系统中，按非增权重加入可行元素对每个非负权重都产生最大权独立集，当且仅当该系统是拟阵。给出一条精确刻画：一个有限独立系统对所有权重都能由标准贪心算法找到最大权基，当且仅当它是拟阵。拟阵不是“贪心有时有效”的例子，而是贪心对任意权重普遍正确的结构边界。

拟阵的秩函数满足单调性与子模性：

这一性质把维数的递减边际收益推广到组合系统，并连接子模函数公理库子模函数Submodular function定义在有限集合幂集上的边际收益递减函数。优化。闭包描述加入哪些元素不会增加秩，回路则压缩最小依赖；二者分别提供几何与局部证书视角。

拟阵对偶公理库拟阵对偶Matroid duality以基的补集为基定义的对偶拟阵构造。把基取补集，交换图论中的环与割。图拟阵的对偶在平面图中对应对偶图的图拟阵，这使生成树、割空间与回路空间处在同一框架中。

两个拟阵约束下的最大共同独立集由拟阵交定理公理库拟阵交定理Matroid intersection theorem · Edmonds matroid intersection theorem两个有限拟阵的最大共同独立集大小，等于一次底集切分上的两侧秩之和的最小值。控制，并可通过交换图增广算法公理库拟阵交算法Matroid intersection algorithm · Unweighted matroid intersection在两个有限拟阵的交换有向图中寻找最短增广路，以独立性 oracle 构造最大公共独立集并在无路时输出秩和证书。求解。共同独立集族通常不再是拟阵，所以不能直接重复使用单拟阵贪心。

在算法模型中，拟阵常通过独立性 oracle 给出。贪心只需询问“加入当前元素后是否仍独立”，不必知道独立性的内部来源；更复杂的拟阵交、次模最大化和在线选择问题则需要额外的交换结构与查询复杂度分析。