揭示线性代数与图论背后共同的代数结构，为贪心算法提供统一的最优性保证
选择你最关心的问题，课件例子、提示和 AI 学伴都会围绕它展开。
选择或输入后，本课会围绕你的问题展开。
不用紧张，诊断题只是帮助我们了解你的基础，不计分。
Q1．集合 $V = \{v_1,v_2,v_3\}$，$\mathbb{R}^2$ 中三向量 $v_1=(1,0),\,v_2=(0,1),\,v_3=(1,1)$。以下哪个子集是最大线性无关组？
Q2．图 $G$ 有 4 个顶点、5 条边，其最小生成树有多少条边？
观察以下两个经典问题：
给定向量组 $V = \{v_1,\ldots,v_n\}$，按模长从大到小排序，依次加入，如果新向量与已选向量线性无关则加入，否则跳过。
结果：得到最大线性无关组（基）
算法保证最优 ✔
给定加权图 $G=(V,E)$，按边权从小到大排序，依次加入，如果新边不形成圈则加入，否则跳过。
结果：得到最小权生成树
算法保证最优 ✔
设 $E$ 是有限集，$\mathcal{I} \subseteq 2^E$ 是 $E$ 的子集族。若满足以下三条公理，则称 $(E, \mathcal{I})$ 为拟阵，$\mathcal{I}$ 中的集合称为独立集。
直觉：什么都不选，自然独立
直觉：线性无关组的子集仍无关；无圈子图的子图仍无圈
直觉：维数较小的无关组可以从更大无关组中"借"一个向量
| 概念 | 线性拟阵 $M[A]$ | 图拟阵 $M(G)$ |
|---|---|---|
| 基础集 $E$ | 矩阵 $A$ 的列集合 | 图 $G$ 的边集合 |
| 独立集 $\mathcal{I}$ | 线性无关的列子集 | 无圈的边子集（森林） |
| 基 $B$ | 最大线性无关组（列空间的基） | 生成树（或生成森林） |
| 圈 $C$ | 最小线性相关集 | 图中的圈 |
| 秩 $r(E)$ | $A$ 的列秩 | $n - $ 连通分量数 |
💡 概念测验：以下哪个集合系统不是拟阵？
$E=\{1,2,3\}$。判断下列 $\mathcal{I}$：
👁️ 看见它
线性拟阵：从矩阵列中看见独立性。图拟阵：从边的森林结构中看见拟阵。两者表面不同，但满足相同的三条公理。
🔧 拆开它
拟阵的核心只有三公理：I1（起点）、I2（遗传）、I3（扩张）。所有其他性质（基等势、圈-基互换、秩次模）均由这三条导出。
📊 解释它
为什么贪心最优？因为 I3 扩张公理保证了"当前解小的时候，总能从最优解借元素"。这正是贪心证明的核心——每次交换不降权重。
🚀 迁移它
拟阵思想扩展到：拟阵交（两个拟阵的共同独立集）、拟阵并、次模函数最大化。这些是现代近似算法和机器学习特征选择的理论基础。
拟阵的三个核心派生概念，由独立集族出发自然导出。
$B \in \mathcal{I}$ 且 $B$ 极大（无法再加元素保持独立）
定理：所有基等势（等秩定理）
$C \notin \mathcal{I}$ 且 $C$ 极小（任去一元素变独立集）
图拟阵中对应图的基本圈
若 $B$ 是基，$e \notin B$，则 $B\cup\{e\}$ 中存在唯一圈 $C(B,e)$。
对任意 $f \in C(B,e)\setminus\{e\}$：
贪心算法中，每次"交换"就是这个定理的应用
下图是一个带权图（5顶点，7条边）。点击边来添加/移除，系统会实时验证当前选中边集是否构成独立集（无圈子集），并检验三条公理的满足情况。
下方图示展示了图拟阵秩函数 $r(A)$ 随子集大小 $|A|$ 的变化规律。拖动滑块观察不同图结构下的次模性体现。
横轴：子集大小 |A|；纵轴：秩 r(A)。紫色虚线 = 理想线性增长（如果所有边都独立），青色实线 = 实际秩函数（超过 n−1 = 5 后饱和）。次模性体现：边际增量递减。
秩函数是拟阵理论中最重要的数值函数，它桥接了组合结构与凸分析。
对任意 $A \subseteq E$，拟阵的秩函数定义为：
$$r(A) = \max\{|X| : X \subseteq A,\; X \in \mathcal{I}\}$$即 $A$ 的最大独立子集的大小。
图拟阵 $M(K_4)$（完全图 $K_4$），$E$ 为6条边，$n=4$ 个顶点。计算各子集的秩：
Q：$r(E) = $ ？（$K_4$ 的图拟阵的秩）
这是拟阵理论最深刻的定理，也是为什么学拟阵如此重要的核心原因。
设 $(E, \mathcal{I})$ 是独立集系统（满足 I1、I2）。以下等价：
点击"下一步"逐步模拟 Kruskal 算法，理解每一步如何对应拟阵的扩张公理。
在进入综合测评之前，先检验你对贪心最优性条件的理解。
💡 思考题（ConcepTest）：若将贪心算法用于下面的集合系统，还能保证最优吗？
集合 $E = \{a,b,c\}$，独立集族 $\mathcal{I} = \{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{b,c\}\}$，权重 $w(a)=3, w(b)=2, w(c)=1$。贪心应选：先选 $a$，再选 $b$，得 $\{a,b\}$，权重 $= 5$。是最优吗？
Q1．设 $M=(E,\mathcal{I})$ 是拟阵，$B_1, B_2$ 是两个不同的基。对任意 $e \in B_1 \setminus B_2$，以下哪个结论由圈-基互换定理保证？
Q2．图 $G$ 有 5 个顶点，7 条边，有 2 个连通分量。图拟阵 $M(G)$ 的秩 $r(E)$ 是多少？
Q3．以下关于次模函数的说法，哪个是错误的？
⚠️ 高频易错点诊断
易错点 1：误以为 I3 要求所有元素都可扩张
I3 说的是"存在 $x \in B \setminus A$"，不是"所有 $x$ 都可以"。只要有一个元素能加入并保持独立即可。
易错点 2：混淆"基"与"极大独立集"
在拟阵中，所有极大独立集都是基（等势性），但在一般独立集系统中不成立。这正是 I3 保证的关键。
易错点 3：误以为贪心总对所有集合系统最优
Rado-Edmonds 定理的方向：仅当系统 是 拟阵时，贪心对所有权重都最优。反之，非拟阵必然存在某个权重使贪心失败。
易错点 4：秩函数次模性与凸性混淆
次模 $r(A\cup B)+r(A\cap B)\le r(A)+r(B)$ 是集合函数的性质，与实值函数的凸性定义不同，但类比"边际递减"。
🟢 基础层：概念辨认
给定 $E=\{1,2,3,4\}$，$\mathcal{I}=\{$ 所有大小 $\le 2$ 的子集 $\}$，验证这是拟阵，并写出所有基和所有圈。
🟡 提升层：秩计算
图 $G$ 由两个三角形共享一条边组成（4顶点，5边）。写出图拟阵 $M(G)$ 的所有基，计算 $r(\{e_1,e_2,e_3,e_4\})$ 对任意4条边子集的取值，验证次模性。
🔴 挑战层：证明题
证明：若 $M=(E,\mathcal{I})$ 是拟阵，则对任意权重函数 $w$，存在最大权重基可由贪心算法找到（利用 I3 和反证法）。
🔗 向前连接
拟阵交（Matroid Intersection）：两个拟阵的共同独立集的最大化，是多项式可解的，但不能用简单贪心。思考：为什么交破坏了扩张性？
📈 应用方向
次模函数最大化（非单调）：NP难但有 $\frac{1}{2}$-近似算法。拟阵约束下的次模最大化：$(1-\frac{1}{e})$-近似。这是现代理论计算机科学的前沿。
拟阵在组合优化知识体系中的位置：
卡在哪里了？描述你的困惑，AI 学伴会先诊断你的理解误区，再给最小提示——不直接给答案。
自定义问题：