OI-wiki 拟阵Matroid完全指南从独立性公理到贪心算法与拟阵交【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本指南系统讲解 OI-wiki 数学模块中的拟阵理论。拟阵由哈斯勒·惠特尼Hassler Whitney于 1935 年提出是统一线性代数线性无关与图论无环两大独立性概念的抽象代数结构。读完本文你将掌握拟阵的四大核心构件独立集、基、圈、秩及其公理化定义熟悉均匀、图、线性、划分、有色五类典型拟阵理解拟阵如何为贪心算法提供严格的数学正确性依据以 Kruskal 求最小生成树为实战案例并了解拟阵交的增广路径算法如何解决图拟阵 × 颜色限制这类双约束优化问题。引言为什么需要拟阵在组合优化中很多问题都围绕独立展开线性代数中我们关心一组向量是否线性无关图论中我们关心一个边集是否无环构成森林。这两类问题看似无关却共享同一套结构性质。拟阵正是为这类独立性概念建立统一公理体系的数学结构其价值在于为贪心算法提供充分且必要的理论基础——只要一个问题能建模为拟阵上的加权最大独立集贪心策略就保证最优为匹配、生成树、指派等经典问题提供统一的建模语言在 OI / ICPC 竞赛中拟阵交算法可用于求解同时受两类约束的优化问题如后文的 Colorful Graph 例题。从 OI-wiki 的文档组织看拟阵属于 数学模块其应用则与 图论的最小生成树、基础模块的贪心算法 及 数据结构模块的并查集 直接关联。定义拟阵的四块基石拟阵Matroid一个拟阵可表示为 $M (E, \mathcal{I})$其中$E$ 是一个有限集称为基础集Ground Set$\mathcal{I}$ 是 $E$ 的子集族称为独立集族Family of Independent Sets其中的集合称为独立集Independent Set。独立集族 $\mathcal{I}$ 必须满足以下三个公理非空性空集是独立的即 $\emptyset \in \mathcal{I}$遗传性独立集的任意子集也是独立集——若 $I \in \mathcal{I}$则对任意 $I \subseteq I$ 都有 $I \in \mathcal{I}$扩张性若 $I, J \in \mathcal{I}$ 且 $|I| |J|$则存在 $j \in J \setminus I$使得 $I \cup {j} \in \mathcal{I}$。满足上述三条性质的 $(E, \mathcal{I})$ 即称为一个拟阵。直观理解遗传性保证了独立结构的向下封闭扩张性保证了小独立集可以被大独立集的元素扩充这正是后续贪心算法正确性证明的核心工具。基Basis基是拟阵中极大的独立集即无法再添加任何元素而保持独立性的独立集。所有基的集合称为基集族记为 $\mathcal{B}$。基具有两个关键性质等基数性所有基的大小都相同该共同大小称为拟阵的秩Rank扩张性任何独立集通过添加基中的元素都可以扩张为一个基。圈Circuit圈是拟阵中最小的依赖集其所有真子集都是独立的但自身不是独立集。由最小性可知任意两个圈之间不存在包含关系。可以类比理解图的环、向量组的最小线性相关组都是拟阵意义下的圈。秩Rank秩函数$r: 2^E \rightarrow \mathbb{Z}_{\geq 0}$ 将基础集 $E$ 的子集映射到非负整数。对任意 $S \subseteq E$$r(S)$ 定义为 $S$ 中最大独立集的大小$$ r(S) \max { |I| \mid I \subseteq S \wedge I \in \mathcal{I} }. $$秩函数满足三条性质非负性对任意 $S \subseteq E$有 $0 \leq r(S) \leq |S|$单调性若 $A \subseteq B \subseteq E$则 $r(A) \leq r(B)$次模性对任意 $A, B \subseteq E$有 $r(A \cup B) r(A \cap B) \leq r(A) r(B)$。次模性在组合优化中意义重大它正是很多资源有限问题下收益递减规律的抽象刻画。典型示例五类基础拟阵1. 均匀拟阵Uniform Matroid给定基础集 $E$ 和非负整数 $k$均匀拟阵 $U_{k,E}$ 的独立集族为所有大小不超过 $k$ 的子集$$ \mathcal{I} { I \subseteq E \mid |I| \leq k }. $$基所有大小为 $k$ 的子集圈所有大小为 $k 1$ 的子集秩$r(E) \min(k, |E|)$即独立集中最多包含 $k$ 个元素。均匀拟阵是最简单的拟阵——独立性的判定只取决于集合大小。2. 图拟阵Graphical Matroid给定无向图 $G (V, E)$图拟阵 $M(G)$ 的基础集是边集 $E$独立集族是所有不包含环的边集即所有森林。基连通图情形下的生成树——生成树是极大独立集无法再添加边而不形成环圈图中的简单环去掉环中任意一条边后剩余部分均为独立集秩$r(E) |V| - c$其中 $c$ 是图的连通分支数对连通无向图秩等于 $|V| - 1$。图拟阵是拟阵理论与图论衔接的桥梁也是后文贪心算法与最小生成树分析的核心载体。3. 线性拟阵Linear Matroid线性拟阵基于向量空间给定向量空间 $V$基础集 $E$ 是 $V$ 中的一组有限向量独立集族是 $E$ 中所有线性无关的向量子集。基极大的线性无关向量集其大小等于向量空间的维数圈最小的线性相关向量集合——任意真子集独立而自身线性相关秩$r(E) \dim(V)$即向量空间的维数独立集的大小不能超过维数。线性拟阵正是线性无关概念在拟阵公理下的抽象其圈即极小线性相关组。4. 划分拟阵Partition Matroid将基础集 $E$ 划分为不相交子集 $E_1, E_2, \dots, E_m$并为每个 $E_i$ 指定非负整数 $k_i$。划分拟阵的独立集族为$$ \mathcal{I} \left{ I \subseteq E \mid \forall i,, |I \cap E_i| \leq k_i \right}. $$基满足 $|I \cap E_i| k_i$ 的独立集即每个子集中恰好选取 $k_i$ 个元素圈最小的依赖集即包含至少一个元素数量超过 $k_i$ 的子集秩$r(E) \sum_{i1}^m k_i$即各子集允许选取最大元素数之和。划分拟阵常用于每类资源最多取若干的配额型约束建模。5. 有色拟阵Colored Matroid有色拟阵是划分拟阵的特殊形式给定基础集 $E$ 与颜色集 $C$每个元素 $e \in E$ 关联一个颜色 $c \in C$。有色拟阵的独立集除满足普通独立性条件外还必须遵守颜色限制例如同色元素最多选取一定数量。基符合颜色限制与独立性条件的极大独立集圈包含至少一个违反独立性或颜色限制元素的最小依赖集秩满足颜色限制条件下最大独立集的大小同时依赖于拟阵结构与颜色限制的具体规定。有色拟阵为后文 Colorful Graph 例题的颜色配额约束提供了直接建模手段。构造和运算对偶、删除与收缩对偶Dual给定拟阵 $M (E, \mathcal{I})$其对偶拟阵$M^* (E, \mathcal{I}^*)$ 定义为$$ \mathcal{I}^* { I^* \subseteq E \mid \exists B \in \mathcal{I}, |B| r(E), B \subseteq E \setminus I^* }. $$对偶拟阵的性质基$M^$ 的基是 $M$ 的基在基础集 $E$ 中的补集——若 $B$ 是 $M$ 的基则 $E \setminus B$ 是 $M^$ 的基秩函数$r^*(S) |S| - r(E) r(E \setminus S)$可由基础集大小、原拟阵秩与移除 $S$ 后的秩直接计算自反性$(M^)^ M$。图拟阵的对偶示例无向图 $G (V, E)$ 的图拟阵 $M(G)$ 对偶 $M(G)^$ 是由图的割集组成的拟阵。$M(G)$ 的基是生成树$M(G)^$ 的基是生成树的补集$M(G)^*$ 的圈则是最小割集——将图分成两个不连通部分的最小边集。例如三角形图 $G$边集 $E {e_1, e_2, e_3}$$M(G)$ 的基是两条边的集合如 ${e_1, e_2}$对偶 $M(G)^$ 的基是单条边的集合如 ${e_3}$$M(G)^$ 的圈是两条边的集合即最小割集如 ${e_2, e_3}$因为移除其中一条边就会将图分割为两个连通分支。删除Deletion与收缩Contraction删除对 $A \subseteq E$拟阵 $M$ 删除 $A$ 后得到 $M \setminus A$其独立集族为$$ \mathcal{I} { I \subseteq E \setminus A \mid I \in \mathcal{I} }. $$删除即从拟阵中移除某些元素保留剩余元素形成的独立集原独立集结构不变。收缩拟阵 $M$ 收缩 $A$ 后得到 $M / A$其独立集族为$$ \mathcal{I} \left{ I \subseteq E \setminus A ,\bigg|, \exists B \subseteq A,, B \in \mathcal{I},, r(B) r(A),, I \cup B \in \mathcal{I} \right}. $$收缩可理解为将 $A$ 中元素缩约选取 $A$ 的一个基 $B$考虑 $E \setminus A$ 中能与 $B$ 共同构成独立集的元素。收缩的结果依赖 $A$ 的基是对原拟阵高秩子集约简后得到的独立集。图拟阵视角图拟阵中删除即删除若干条边如从三角形图中删除一条边剩下两边仍是森林收缩即把某条边收缩为一个顶点——将该边的两个端点合并、删除该边合并后其余边仍可构成独立集如三角形图中收缩任意一条边后剩下两条边构成新的拟阵。拟阵与贪心算法数学层面的最优性保证问题形式化拟阵最重要的应用之一是刻画贪心算法的最优化问题。给定拟阵 $M (S, \mathcal{I})$ 及每个元素 $x \in S$ 的正整数权值 $w(x)$目标是找到权值最大的独立集$$ \max_{A \in \mathcal{I}} w(A) \max_{A \in \mathcal{I}} \sum_{x \in A} w(x). $$权值最大独立集必然是极大独立集若 $A$ 不是极大独立集则存在可加入的元素 $x$且 $w(x) 0$ 使总权值增加矛盾。贪心算法步骤元素排序将基础集 $S$ 按权值从大到小排序记为 $e_1, e_2, \dots, e_n$初始化设独立集 $A \emptyset$构建独立集依次考察 $e_i$若 $A \cup { e_i } \in \mathcal{I}$ 则更新 $A A \cup { e_i }$输出结果最终 $A$ 即为权值最大的独立集。复杂度分析设 $n |S|$$f(n)$ 为单次独立性判定的复杂度则总时间复杂度为$$ O(n \log n n f(n)) $$其中 $O(n \log n)$ 来自排序$O(n f(n))$ 来自逐一判定独立性。独立检测的工程实践对应 OI-wiki 文档中的备注图拟阵可用并查集高效检测是否成环使 $f(n)$ 接近常数。仓库中并查集的查询实现docs/ds/dsu.md采用路径压缩size_t dsu::find(size_t x) { return pa[x] x ? x : pa[x] find(pa[x]); }配合按秩合并后单次 find 的均摊复杂度接近 $O(\alpha(n))$线性拟阵独立性检测通常涉及矩阵运算高斯消元判线性无关复杂度取决于具体实现方式。正确性证明交换论证设 $A \in \mathcal{I}$ 是某个权值最大独立集 $T$ 的子集定义 $P { x \in S \setminus A \mid A \cup {x} \in \mathcal{I} }$ 为所有可加入 $A$ 的元素集合。设 $y$ 是 $P$ 中权值最大的元素则 $A A \cup { y }$ 仍是某个权值最大独立集的子集证明采用反证 交换论证假设 $A$ 不是任何权值最大独立集的子集则存在权值最大的 $T$ 且 $|A| |T|$由拟阵扩张性存在 $x \in T \setminus A$ 使 $A \cup { x } \in \mathcal{I}$反复扩张构造出 $|A| |T|$ 的独立集 $A$令 $K A \cap T$则 $x T \setminus K$$y A \setminus K$。因 $y$ 是 $P$ 中权值最大元素$w(x) \leq w(y)$于是 $w(A) w(K) w(y) \geq w(K) w(x) w(T)$若 $w(A) w(T)$则 $T$ 不是权值最大独立集矛盾若 $w(A) w(T)$则 $A$ 是权值最大独立集且 $A$ 为其子集与假设矛盾。综上贪心逐步扩展始终保持当前集是某个最优解的子集这一不变式最终得到权值最大独立集。这为排序 贪心选元素的算法范式提供了严格的理论保障。实战示例最小生成树中的拟阵视角给定连通无向图 $G (V, E)$边 $e$ 有权值 $w(e)$目标是找总权值最小的生成树。将其建模为图拟阵 $M(G)$基础集$S E$独立集族$\mathcal{I}$ 为所有无环边集森林。Kruskal 算法是典型的拟阵贪心算法详见最小生成树所有边按权值从小到大排序依次选择权值最小的边若加入后不成环则加入生成树重复至生成树包含 $|V| - 1$ 条边。注意这与最大权独立集的排序方向相反求最小生成树等价于在权值取负后求最大权独立集或直接按升序贪心——这正是拟阵贪心框架的两种等价表述。仓库 docs/graph/code/mst/mst_1.cpp 给出了完整的 Kruskal 实现骨架先std::sort(a 1, a m 1, cmp)按边权排序再用并查集find判断x ! y不成环后合并f[x] f[y]并累加ans a[i].z循环至num n - 1即得到最小生成树——排序对应拟阵贪心的元素排序步并查集成环检测对应独立性判定代码结构与拟阵贪心四步完全一一对应。Prim 算法同样是贪心算法但它从一个起始顶点出发逐步扩展生成树每次选择连接树内外的权值最小边其选择策略不基于拟阵的扩张性质。因此在拟阵理论的严格意义下Prim 不被视为典型的拟阵贪心算法最小生成树文档 也指出 Prim 是加点而非 Kruskal 的加边。拟阵交双约束优化问题的求解框架定义与注意事项对同一基础集 $S$ 上的两个拟阵 $M_1 (S, \mathcal{I}_1)$、$M_2 (S, \mathcal{I}_2)$若 $\mathcal{I} \mathcal{I}_1 \cap \mathcal{I}_2$ 满足拟阵独立集族的三条性质则 $M (S, \mathcal{I})$ 称为 $M_1$ 与 $M_2$ 的交。重要限制并非任意两个拟阵的交都是拟阵仅当交集仍满足三条公理时才构成拟阵。正因为交不一定是拟阵单拟阵贪心不再适用需要专门的拟阵交算法。问题描述最大独立集在 $\mathcal{I}_1 \cap \mathcal{I}_2$ 中找基数最大的独立集加权最大独立集给定权值 $w: S \to \mathbb{R}$在 $\mathcal{I}_1 \cap \mathcal{I}_2$ 中找权值和最大的独立集。无权版本的增广路径算法初始化取初始独立集 $I \in \mathcal{I}_1 \cap \mathcal{I}_2$通常为 $\emptyset$迭代根据当前 $I$ 构建交换图$D_{M_1, M_2}(I)$在交换图中寻找从源点 $s$ 到汇点 $t$ 的增广路径$P$增广沿 $P$ 遍历每个节点——若节点属于左部顶点$I$ 中的元素则从 $I$ 中移除若属于右部顶点$S \setminus I$ 中的元素则加入 $I$更新 $I$ 后重复直至找不到增广路径结果最终 $I$ 即为拟阵交 $M_1 \cap M_2$ 中的最大独立集。该算法与二分图最大匹配的增广路径思想同源交换图编码了换入换出的可行交换关系找不到增广路径即达到极大从而最优。加权版本为求权值和最大的独立集需在增广路径选择上优化权值设置对每个元素 $e \in S$ 定义交换图上的权值 $w(e)$左部顶点$I$ 中的元素$w(e) -w(e)$移除即损失权值右部顶点$S \setminus I$ 中的元素$w(e) w(e)$加入即获得权值路径选择在 $D_{M_1, M_2}(I)$ 中寻找使增广后总权值增加最大的路径 $P$增广条件为加入元素权值和大于移除元素权值和 $$ \sum_{y \in \text{加入的元素}} w(y) \sum_{x \in \text{移除的元素}} w(x) $$增广操作沿 $P$ 移除左部节点对应元素、加入右部节点对应元素迭代重复构建交换图与寻路逐步优化总权值终止条件无法找到满足增广条件的路径时终止结果最终 $I$ 为拟阵交中的权值最大独立集。复杂度增广次数设两拟阵最大秩为 $r_1, r_2$增广次数上界为 $\min(r_1, r_2)$每次增广构建交换图 $O(n^2)$$n |S|$寻路通常 $O(n^2)$如 BFS总时间复杂度$O(r \cdot n^2)$其中 $r \min(r_1, r_2)$。例题精讲例 1最小生成树给定无向图 $G (V, E)$每条边有权值 $w(e)$求包含所有顶点且总权值最小的生成树。详细介绍见最小生成树题目模板为洛谷 P3366【模板】最小生成树。解题思路使用 Kruskal 算法——所有边按权值从小到大排序后逐步选取若加入不成环则加入生成树最终即最小生成树。其正确性正是拟阵贪心定理的直接推论。例 2Colorful Graph拟阵交给定带颜色的无向图 $G (V, E)$每条边一个颜色求一个最大边集使得所选边不成任何环且每种颜色边数不超过 $k$。解题思路拟阵建模图拟阵 $M_1$独立集族 $\mathcal{I}_1$ 为所有不成环的边集颜色拟阵 $M_2$独立集族 $\mathcal{I}_2$ 为每种颜色边数 $\leq k$ 的边集这正是前述划分/有色拟阵的形态求解拟阵交求 $M M_1 \cap M_2$得到既不成环又满足颜色配额的最大边集。这是拟阵交算法的典型应用两个独立条件分别由两个拟阵刻画交集即为双约束可行解集合。例 3约束的资源分配问题有一组资源 $R {r_1, r_2, \dots, r_n}$ 和一组项目 $P {p_1, p_2, \dots, p_m}$每个项目 $p_i$ 需要一定数量的资源且每种资源总分配量不能超过供应量。目标寻找满足所有项目需求且不超过资源供应量的分配方案。解题思路拟阵建模需求拟阵 $M_1$独立集族 $\mathcal{I}_1$ 为满足各项目资源需求的分配方案供应拟阵 $M_2$独立集族 $\mathcal{I}_2$ 为不超过每种资源供应量的分配方案求解拟阵交求 $M M_1 \cap M_2$得到既满足所有需求又不超供应量的分配方案。扩展阅读与关联内容对称基交换性质拟阵的基满足对称交换性质symmetric base-exchange property这一引理也是 OI-wiki wqs 二分WQS 二分 中凸性结论可推广到一般拟阵的理论依据可见拟阵理论在 DP 优化中的渗透并查集拟阵贪心的独立性检测基础设施实现细节见并查集最小生成树Kruskal / Prim 算法完整讲解与模板见最小生成树贪心算法基础贪心思想的一般性讨论见贪心。参考资料与注释本文内容以 OI-wiki docs/math/matroid.md 为主体该文档引述了 Wikipedia Matroid 词条、百度百科拟阵词条及洛谷《拟阵与最优化问题》《从拟阵基础到 Shannon 开关游戏》两篇文章作为延伸阅读来源读者可在原文档中查看这些参考资料的原始链接。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 拟阵（Matroid）完全指南：从独立性公理到贪心算法与拟阵交
OI-wiki 拟阵Matroid完全指南从独立性公理到贪心算法与拟阵交【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本指南系统讲解 OI-wiki 数学模块中的拟阵理论。拟阵由哈斯勒·惠特尼Hassler Whitney于 1935 年提出是统一线性代数线性无关与图论无环两大独立性概念的抽象代数结构。读完本文你将掌握拟阵的四大核心构件独立集、基、圈、秩及其公理化定义熟悉均匀、图、线性、划分、有色五类典型拟阵理解拟阵如何为贪心算法提供严格的数学正确性依据以 Kruskal 求最小生成树为实战案例并了解拟阵交的增广路径算法如何解决图拟阵 × 颜色限制这类双约束优化问题。引言为什么需要拟阵在组合优化中很多问题都围绕独立展开线性代数中我们关心一组向量是否线性无关图论中我们关心一个边集是否无环构成森林。这两类问题看似无关却共享同一套结构性质。拟阵正是为这类独立性概念建立统一公理体系的数学结构其价值在于为贪心算法提供充分且必要的理论基础——只要一个问题能建模为拟阵上的加权最大独立集贪心策略就保证最优为匹配、生成树、指派等经典问题提供统一的建模语言在 OI / ICPC 竞赛中拟阵交算法可用于求解同时受两类约束的优化问题如后文的 Colorful Graph 例题。从 OI-wiki 的文档组织看拟阵属于 数学模块其应用则与 图论的最小生成树、基础模块的贪心算法 及 数据结构模块的并查集 直接关联。定义拟阵的四块基石拟阵Matroid一个拟阵可表示为 $M (E, \mathcal{I})$其中$E$ 是一个有限集称为基础集Ground Set$\mathcal{I}$ 是 $E$ 的子集族称为独立集族Family of Independent Sets其中的集合称为独立集Independent Set。独立集族 $\mathcal{I}$ 必须满足以下三个公理非空性空集是独立的即 $\emptyset \in \mathcal{I}$遗传性独立集的任意子集也是独立集——若 $I \in \mathcal{I}$则对任意 $I \subseteq I$ 都有 $I \in \mathcal{I}$扩张性若 $I, J \in \mathcal{I}$ 且 $|I| |J|$则存在 $j \in J \setminus I$使得 $I \cup {j} \in \mathcal{I}$。满足上述三条性质的 $(E, \mathcal{I})$ 即称为一个拟阵。直观理解遗传性保证了独立结构的向下封闭扩张性保证了小独立集可以被大独立集的元素扩充这正是后续贪心算法正确性证明的核心工具。基Basis基是拟阵中极大的独立集即无法再添加任何元素而保持独立性的独立集。所有基的集合称为基集族记为 $\mathcal{B}$。基具有两个关键性质等基数性所有基的大小都相同该共同大小称为拟阵的秩Rank扩张性任何独立集通过添加基中的元素都可以扩张为一个基。圈Circuit圈是拟阵中最小的依赖集其所有真子集都是独立的但自身不是独立集。由最小性可知任意两个圈之间不存在包含关系。可以类比理解图的环、向量组的最小线性相关组都是拟阵意义下的圈。秩Rank秩函数$r: 2^E \rightarrow \mathbb{Z}_{\geq 0}$ 将基础集 $E$ 的子集映射到非负整数。对任意 $S \subseteq E$$r(S)$ 定义为 $S$ 中最大独立集的大小$$ r(S) \max { |I| \mid I \subseteq S \wedge I \in \mathcal{I} }. $$秩函数满足三条性质非负性对任意 $S \subseteq E$有 $0 \leq r(S) \leq |S|$单调性若 $A \subseteq B \subseteq E$则 $r(A) \leq r(B)$次模性对任意 $A, B \subseteq E$有 $r(A \cup B) r(A \cap B) \leq r(A) r(B)$。次模性在组合优化中意义重大它正是很多资源有限问题下收益递减规律的抽象刻画。典型示例五类基础拟阵1. 均匀拟阵Uniform Matroid给定基础集 $E$ 和非负整数 $k$均匀拟阵 $U_{k,E}$ 的独立集族为所有大小不超过 $k$ 的子集$$ \mathcal{I} { I \subseteq E \mid |I| \leq k }. $$基所有大小为 $k$ 的子集圈所有大小为 $k 1$ 的子集秩$r(E) \min(k, |E|)$即独立集中最多包含 $k$ 个元素。均匀拟阵是最简单的拟阵——独立性的判定只取决于集合大小。2. 图拟阵Graphical Matroid给定无向图 $G (V, E)$图拟阵 $M(G)$ 的基础集是边集 $E$独立集族是所有不包含环的边集即所有森林。基连通图情形下的生成树——生成树是极大独立集无法再添加边而不形成环圈图中的简单环去掉环中任意一条边后剩余部分均为独立集秩$r(E) |V| - c$其中 $c$ 是图的连通分支数对连通无向图秩等于 $|V| - 1$。图拟阵是拟阵理论与图论衔接的桥梁也是后文贪心算法与最小生成树分析的核心载体。3. 线性拟阵Linear Matroid线性拟阵基于向量空间给定向量空间 $V$基础集 $E$ 是 $V$ 中的一组有限向量独立集族是 $E$ 中所有线性无关的向量子集。基极大的线性无关向量集其大小等于向量空间的维数圈最小的线性相关向量集合——任意真子集独立而自身线性相关秩$r(E) \dim(V)$即向量空间的维数独立集的大小不能超过维数。线性拟阵正是线性无关概念在拟阵公理下的抽象其圈即极小线性相关组。4. 划分拟阵Partition Matroid将基础集 $E$ 划分为不相交子集 $E_1, E_2, \dots, E_m$并为每个 $E_i$ 指定非负整数 $k_i$。划分拟阵的独立集族为$$ \mathcal{I} \left{ I \subseteq E \mid \forall i,, |I \cap E_i| \leq k_i \right}. $$基满足 $|I \cap E_i| k_i$ 的独立集即每个子集中恰好选取 $k_i$ 个元素圈最小的依赖集即包含至少一个元素数量超过 $k_i$ 的子集秩$r(E) \sum_{i1}^m k_i$即各子集允许选取最大元素数之和。划分拟阵常用于每类资源最多取若干的配额型约束建模。5. 有色拟阵Colored Matroid有色拟阵是划分拟阵的特殊形式给定基础集 $E$ 与颜色集 $C$每个元素 $e \in E$ 关联一个颜色 $c \in C$。有色拟阵的独立集除满足普通独立性条件外还必须遵守颜色限制例如同色元素最多选取一定数量。基符合颜色限制与独立性条件的极大独立集圈包含至少一个违反独立性或颜色限制元素的最小依赖集秩满足颜色限制条件下最大独立集的大小同时依赖于拟阵结构与颜色限制的具体规定。有色拟阵为后文 Colorful Graph 例题的颜色配额约束提供了直接建模手段。构造和运算对偶、删除与收缩对偶Dual给定拟阵 $M (E, \mathcal{I})$其对偶拟阵$M^* (E, \mathcal{I}^*)$ 定义为$$ \mathcal{I}^* { I^* \subseteq E \mid \exists B \in \mathcal{I}, |B| r(E), B \subseteq E \setminus I^* }. $$对偶拟阵的性质基$M^$ 的基是 $M$ 的基在基础集 $E$ 中的补集——若 $B$ 是 $M$ 的基则 $E \setminus B$ 是 $M^$ 的基秩函数$r^*(S) |S| - r(E) r(E \setminus S)$可由基础集大小、原拟阵秩与移除 $S$ 后的秩直接计算自反性$(M^)^ M$。图拟阵的对偶示例无向图 $G (V, E)$ 的图拟阵 $M(G)$ 对偶 $M(G)^$ 是由图的割集组成的拟阵。$M(G)$ 的基是生成树$M(G)^$ 的基是生成树的补集$M(G)^*$ 的圈则是最小割集——将图分成两个不连通部分的最小边集。例如三角形图 $G$边集 $E {e_1, e_2, e_3}$$M(G)$ 的基是两条边的集合如 ${e_1, e_2}$对偶 $M(G)^$ 的基是单条边的集合如 ${e_3}$$M(G)^$ 的圈是两条边的集合即最小割集如 ${e_2, e_3}$因为移除其中一条边就会将图分割为两个连通分支。删除Deletion与收缩Contraction删除对 $A \subseteq E$拟阵 $M$ 删除 $A$ 后得到 $M \setminus A$其独立集族为$$ \mathcal{I} { I \subseteq E \setminus A \mid I \in \mathcal{I} }. $$删除即从拟阵中移除某些元素保留剩余元素形成的独立集原独立集结构不变。收缩拟阵 $M$ 收缩 $A$ 后得到 $M / A$其独立集族为$$ \mathcal{I} \left{ I \subseteq E \setminus A ,\bigg|, \exists B \subseteq A,, B \in \mathcal{I},, r(B) r(A),, I \cup B \in \mathcal{I} \right}. $$收缩可理解为将 $A$ 中元素缩约选取 $A$ 的一个基 $B$考虑 $E \setminus A$ 中能与 $B$ 共同构成独立集的元素。收缩的结果依赖 $A$ 的基是对原拟阵高秩子集约简后得到的独立集。图拟阵视角图拟阵中删除即删除若干条边如从三角形图中删除一条边剩下两边仍是森林收缩即把某条边收缩为一个顶点——将该边的两个端点合并、删除该边合并后其余边仍可构成独立集如三角形图中收缩任意一条边后剩下两条边构成新的拟阵。拟阵与贪心算法数学层面的最优性保证问题形式化拟阵最重要的应用之一是刻画贪心算法的最优化问题。给定拟阵 $M (S, \mathcal{I})$ 及每个元素 $x \in S$ 的正整数权值 $w(x)$目标是找到权值最大的独立集$$ \max_{A \in \mathcal{I}} w(A) \max_{A \in \mathcal{I}} \sum_{x \in A} w(x). $$权值最大独立集必然是极大独立集若 $A$ 不是极大独立集则存在可加入的元素 $x$且 $w(x) 0$ 使总权值增加矛盾。贪心算法步骤元素排序将基础集 $S$ 按权值从大到小排序记为 $e_1, e_2, \dots, e_n$初始化设独立集 $A \emptyset$构建独立集依次考察 $e_i$若 $A \cup { e_i } \in \mathcal{I}$ 则更新 $A A \cup { e_i }$输出结果最终 $A$ 即为权值最大的独立集。复杂度分析设 $n |S|$$f(n)$ 为单次独立性判定的复杂度则总时间复杂度为$$ O(n \log n n f(n)) $$其中 $O(n \log n)$ 来自排序$O(n f(n))$ 来自逐一判定独立性。独立检测的工程实践对应 OI-wiki 文档中的备注图拟阵可用并查集高效检测是否成环使 $f(n)$ 接近常数。仓库中并查集的查询实现docs/ds/dsu.md采用路径压缩size_t dsu::find(size_t x) { return pa[x] x ? x : pa[x] find(pa[x]); }配合按秩合并后单次 find 的均摊复杂度接近 $O(\alpha(n))$线性拟阵独立性检测通常涉及矩阵运算高斯消元判线性无关复杂度取决于具体实现方式。正确性证明交换论证设 $A \in \mathcal{I}$ 是某个权值最大独立集 $T$ 的子集定义 $P { x \in S \setminus A \mid A \cup {x} \in \mathcal{I} }$ 为所有可加入 $A$ 的元素集合。设 $y$ 是 $P$ 中权值最大的元素则 $A A \cup { y }$ 仍是某个权值最大独立集的子集证明采用反证 交换论证假设 $A$ 不是任何权值最大独立集的子集则存在权值最大的 $T$ 且 $|A| |T|$由拟阵扩张性存在 $x \in T \setminus A$ 使 $A \cup { x } \in \mathcal{I}$反复扩张构造出 $|A| |T|$ 的独立集 $A$令 $K A \cap T$则 $x T \setminus K$$y A \setminus K$。因 $y$ 是 $P$ 中权值最大元素$w(x) \leq w(y)$于是 $w(A) w(K) w(y) \geq w(K) w(x) w(T)$若 $w(A) w(T)$则 $T$ 不是权值最大独立集矛盾若 $w(A) w(T)$则 $A$ 是权值最大独立集且 $A$ 为其子集与假设矛盾。综上贪心逐步扩展始终保持当前集是某个最优解的子集这一不变式最终得到权值最大独立集。这为排序 贪心选元素的算法范式提供了严格的理论保障。实战示例最小生成树中的拟阵视角给定连通无向图 $G (V, E)$边 $e$ 有权值 $w(e)$目标是找总权值最小的生成树。将其建模为图拟阵 $M(G)$基础集$S E$独立集族$\mathcal{I}$ 为所有无环边集森林。Kruskal 算法是典型的拟阵贪心算法详见最小生成树所有边按权值从小到大排序依次选择权值最小的边若加入后不成环则加入生成树重复至生成树包含 $|V| - 1$ 条边。注意这与最大权独立集的排序方向相反求最小生成树等价于在权值取负后求最大权独立集或直接按升序贪心——这正是拟阵贪心框架的两种等价表述。仓库 docs/graph/code/mst/mst_1.cpp 给出了完整的 Kruskal 实现骨架先std::sort(a 1, a m 1, cmp)按边权排序再用并查集find判断x ! y不成环后合并f[x] f[y]并累加ans a[i].z循环至num n - 1即得到最小生成树——排序对应拟阵贪心的元素排序步并查集成环检测对应独立性判定代码结构与拟阵贪心四步完全一一对应。Prim 算法同样是贪心算法但它从一个起始顶点出发逐步扩展生成树每次选择连接树内外的权值最小边其选择策略不基于拟阵的扩张性质。因此在拟阵理论的严格意义下Prim 不被视为典型的拟阵贪心算法最小生成树文档 也指出 Prim 是加点而非 Kruskal 的加边。拟阵交双约束优化问题的求解框架定义与注意事项对同一基础集 $S$ 上的两个拟阵 $M_1 (S, \mathcal{I}_1)$、$M_2 (S, \mathcal{I}_2)$若 $\mathcal{I} \mathcal{I}_1 \cap \mathcal{I}_2$ 满足拟阵独立集族的三条性质则 $M (S, \mathcal{I})$ 称为 $M_1$ 与 $M_2$ 的交。重要限制并非任意两个拟阵的交都是拟阵仅当交集仍满足三条公理时才构成拟阵。正因为交不一定是拟阵单拟阵贪心不再适用需要专门的拟阵交算法。问题描述最大独立集在 $\mathcal{I}_1 \cap \mathcal{I}_2$ 中找基数最大的独立集加权最大独立集给定权值 $w: S \to \mathbb{R}$在 $\mathcal{I}_1 \cap \mathcal{I}_2$ 中找权值和最大的独立集。无权版本的增广路径算法初始化取初始独立集 $I \in \mathcal{I}_1 \cap \mathcal{I}_2$通常为 $\emptyset$迭代根据当前 $I$ 构建交换图$D_{M_1, M_2}(I)$在交换图中寻找从源点 $s$ 到汇点 $t$ 的增广路径$P$增广沿 $P$ 遍历每个节点——若节点属于左部顶点$I$ 中的元素则从 $I$ 中移除若属于右部顶点$S \setminus I$ 中的元素则加入 $I$更新 $I$ 后重复直至找不到增广路径结果最终 $I$ 即为拟阵交 $M_1 \cap M_2$ 中的最大独立集。该算法与二分图最大匹配的增广路径思想同源交换图编码了换入换出的可行交换关系找不到增广路径即达到极大从而最优。加权版本为求权值和最大的独立集需在增广路径选择上优化权值设置对每个元素 $e \in S$ 定义交换图上的权值 $w(e)$左部顶点$I$ 中的元素$w(e) -w(e)$移除即损失权值右部顶点$S \setminus I$ 中的元素$w(e) w(e)$加入即获得权值路径选择在 $D_{M_1, M_2}(I)$ 中寻找使增广后总权值增加最大的路径 $P$增广条件为加入元素权值和大于移除元素权值和 $$ \sum_{y \in \text{加入的元素}} w(y) \sum_{x \in \text{移除的元素}} w(x) $$增广操作沿 $P$ 移除左部节点对应元素、加入右部节点对应元素迭代重复构建交换图与寻路逐步优化总权值终止条件无法找到满足增广条件的路径时终止结果最终 $I$ 为拟阵交中的权值最大独立集。复杂度增广次数设两拟阵最大秩为 $r_1, r_2$增广次数上界为 $\min(r_1, r_2)$每次增广构建交换图 $O(n^2)$$n |S|$寻路通常 $O(n^2)$如 BFS总时间复杂度$O(r \cdot n^2)$其中 $r \min(r_1, r_2)$。例题精讲例 1最小生成树给定无向图 $G (V, E)$每条边有权值 $w(e)$求包含所有顶点且总权值最小的生成树。详细介绍见最小生成树题目模板为洛谷 P3366【模板】最小生成树。解题思路使用 Kruskal 算法——所有边按权值从小到大排序后逐步选取若加入不成环则加入生成树最终即最小生成树。其正确性正是拟阵贪心定理的直接推论。例 2Colorful Graph拟阵交给定带颜色的无向图 $G (V, E)$每条边一个颜色求一个最大边集使得所选边不成任何环且每种颜色边数不超过 $k$。解题思路拟阵建模图拟阵 $M_1$独立集族 $\mathcal{I}_1$ 为所有不成环的边集颜色拟阵 $M_2$独立集族 $\mathcal{I}_2$ 为每种颜色边数 $\leq k$ 的边集这正是前述划分/有色拟阵的形态求解拟阵交求 $M M_1 \cap M_2$得到既不成环又满足颜色配额的最大边集。这是拟阵交算法的典型应用两个独立条件分别由两个拟阵刻画交集即为双约束可行解集合。例 3约束的资源分配问题有一组资源 $R {r_1, r_2, \dots, r_n}$ 和一组项目 $P {p_1, p_2, \dots, p_m}$每个项目 $p_i$ 需要一定数量的资源且每种资源总分配量不能超过供应量。目标寻找满足所有项目需求且不超过资源供应量的分配方案。解题思路拟阵建模需求拟阵 $M_1$独立集族 $\mathcal{I}_1$ 为满足各项目资源需求的分配方案供应拟阵 $M_2$独立集族 $\mathcal{I}_2$ 为不超过每种资源供应量的分配方案求解拟阵交求 $M M_1 \cap M_2$得到既满足所有需求又不超供应量的分配方案。扩展阅读与关联内容对称基交换性质拟阵的基满足对称交换性质symmetric base-exchange property这一引理也是 OI-wiki wqs 二分WQS 二分 中凸性结论可推广到一般拟阵的理论依据可见拟阵理论在 DP 优化中的渗透并查集拟阵贪心的独立性检测基础设施实现细节见并查集最小生成树Kruskal / Prim 算法完整讲解与模板见最小生成树贪心算法基础贪心思想的一般性讨论见贪心。参考资料与注释本文内容以 OI-wiki docs/math/matroid.md 为主体该文档引述了 Wikipedia Matroid 词条、百度百科拟阵词条及洛谷《拟阵与最优化问题》《从拟阵基础到 Shannon 开关游戏》两篇文章作为延伸阅读来源读者可在原文档中查看这些参考资料的原始链接。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考