拟阵¶
定义¶
\(M = (X, I)\) ，\(X\) 是有限集合，\(I \subseteq \mathscr{P}(X)\)。
如果满足下列条件则称为 拟阵 (Matroid)：
- \(\varnothing \in I\)。
- \(\forall (Y \in I \land Z \subseteq Y),Z \in I\)。
- \(\forall(Y,Z \in I \land |Y| < |Z|),\exists x \in Z \backslash Y,Y \cup \{x\} \in I\) 。
若 \(Y \in I\)，则称 \(Y\) 为这个矩阵的 独立集 (independence)，否则成为 非独立集 (dependence)。
不被其他独立集包含的独立集称为 基 (Basis)。
基本性质¶
- 每一个独立集都被至少一个基所包含。
证明：若存在一个独立集不被任何一个基包含，则根据定义它自己就是基。
- 基是大小最大的独立集，反之亦然，且所有基的大小都一样。最大的基的大小称为拟阵的秩。
证明：若两个基大小不同，根据定义第三条，小的那个基增加一个元素依然属于 \(I\)，说明这个基被其他独立集所包含，这与基的定义矛盾。
- 如果两个基只有一个元素不同，就连一条边，那么所有的基都是连通的。
证明：对于两个基 \(Y\) 和 \(Z\)，若它们不同，则满足 \(|Y \backslash Z| > 0\)，任取 \(y \in |Y \backslash Z|\)，则根据定义第二条，\(Y \backslash \{y\} \in I\)，且 \(|Y \backslash \{y\}| < |Z|\)；再根据定义第三条，存在 \(x\) 使得 \((Y \backslash \{y\}) \cup \{x\} \in I\)，且 \(|((Y \backslash \{y\}) \cup \{x\}) \backslash Z| = |Y \backslash Z|-1\)。重复上述操作，最终可得到一个基 \(S\) 满足 \(|S \backslash Z| = 0\)，即 \(S = Z\)。注意到，这个操作等价于从一个基经过一条边到达另一个基，因为 \((Y \backslash \{y\}) \cup \{x\}\) 和 \(Y\) 仅有一个元素不同，从而所有的基都是连通的。
一个等价定义¶
保持上述定义前两条不变的前提下，第三条定义有另一种等价表述：
- 对于任意 \(Y \subseteq X\)，所有满足 \(Z \in I \land Z \subseteq Y\) 的集合 \(Z\) 称为 \(Y\) 的独立集，\(Y\) 的独立集中不被其他 \(Y\) 的独立集包含的 \(Y\) 的独立集称为 \(Y\) 的基，则所有 \(Y\) 的基大小相同。
证明：
\(\Rightarrow\)：假设存在一个 \(Y \subseteq X\)，\(Y\) 有两个基大小不同，根据原定义第三条，小的那个基增加一个元素依然属于 \(I\)，且是 \(Y\) 的子集，说明这个基被其他独立集所包含，这与基的定义矛盾。
\(\Leftarrow\)：\(\forall(Y,Z \in I \land |Y| < |Z|)\)，由新定义，所有 \(Y \cup Z\) 的基大小相同，由基的定义，\(Y \cup Z\) 的基的大小必然大于等于 \(|Z|\)，从而大于 \(|Y|\)，这说明 \(Y\) 被某个 \(Y \cup Z\) 的基 \(W\) 所包含，则存在 \(x \in W \backslash Y \subseteq Z \backslash Y\)，而 \(Y \cup \{x\} \subseteq W\)，由定义第二条，得 \(Y \cup \{x\} \in I\)。
环¶
-
极小的非独立集称为 环 (Circuit)。
-
若对于拟阵 \(M = (X, I)\)，\(\{x,y\}\) 是环，\(Y\) 是独立集且 \(x \in Y\)，则 \((Y \backslash\{x\}) \cup \{y\}\) 也是独立集。
证明：初始令 \(S = \{y\}\)，不断使用定义第三条得到一个多一个元素的独立集，直到集合大小为 \(|Y|\)：
存在 \(z \in Y \backslash S\) 使得 \(S \cup \{z\} \in I\)，且因为 \(\{x,y\}\) 是环，必然有 \(z \ne x\)，否则因为 \(\{x,y\} \subseteq S \cup \{z\}\)，由定义第二条可得 \(\{x,y\}\) 也是独立集，矛盾。
注意到所有 \(z\) 均是 \(Y\) 中的元素，从而最终得到的独立集即为 \((Y \backslash\{x\}) \cup \{y\}\)。