拟阵

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

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

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

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

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

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

向下封闭本身还不够。设

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

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

拟阵贪心定理理路拟阵贪心定理Matroid greedy theorem完整证明有限独立系统的贪心双向刻画，区分任意实权重的基优化与非负权重的独立集优化，并在四列矩阵上核对每次接受、拒绝及最优值。给出一条精确刻画：一个有限独立系统对所有实权重都能由“按权重递减扫描、能加就加、一直扩张到极大”的算法找到最大权基，当且仅当它是拟阵。这里的目标是基；即使剩余权重为负，也可能必须加入元素才能成为基。若改为在所有独立集中求最大权，则应跳过负权元素。例如单元素拟阵中唯一元素权重为 $-1$，最优基是单元素集，最优独立集却是空集。

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

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

拟阵对偶理路拟阵对偶Matroid duality从秩公理证明基的补集确实定义对偶拟阵，推导对偶秩公式，并以四列矩阵及其正交核给出所有子集上的可复算证书。把基取补集，交换图论中的环与割。图拟阵的对偶在平面图中对应对偶图的图拟阵，这使生成树、割空间与回路空间处在同一框架中。

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

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

秩、贪心与对偶三页共用同一个有理数域四列配置 $a=(1,0),b=(0,1),c=(1,1),d=(2,2)$。秩页证明子模性及逆向公理重建，贪心页在权重 $(4,3,6,5)$ 下逐次得到最优基 $ac$、值 $10$，对偶页由正交核矩阵确认全部补基。三种描述因而能在同一组标号上逐项核对，同时保留各自适用于任意有限拟阵的一般证明。