拟阵实例

常见拟阵模型:均匀、图、余图、双循环、线性、代数、划分、层、横截与 Gammoid,以及非拟阵例子。

标签 数学 / 拟阵 / 组合结构 / 图 / 线性空间

本页承接 拟阵 的定义,列举常见模型。基统一定义为极大独立集;基的等势性与交换性见 拟阵基定理。

均匀拟阵

取 𝐸={1,…,𝑛},0≤𝑟≤𝑛。独立集为

ℐ︀={𝐼⊆𝐸:|𝐼|≤𝑟}.

这是均匀拟阵 𝑈𝑟,𝑛,基是全部 𝑟 元子集,秩为 𝑟。𝑈𝑛,𝑛 是自由拟阵,所有子集都独立;𝑈0,𝑛 是空拟阵,只有空集独立。

图拟阵

设 𝐺=(𝑉,𝐸) 是图。底集为 𝐸,独立集为无圈边集,即森林。基是极大森林;当 𝐺 连通时,基就是生成树。这正是 最小生成树 的拟阵结构。

余图拟阵

图拟阵的 对偶 𝑀∗(𝐺) 称为余图拟阵。连通图时,它的基是生成树的补,即余树;独立集是某个余树的子集。

双循环拟阵

底集仍是图 𝐺 的边集。独立集是伪森林:每个连通分量至多含一个圈。极大伪森林是基。双循环拟阵是拟阵,但一般不是图拟阵。

线性与代数拟阵

线性拟阵取某个域 𝐾 上矩阵 𝐴 的列为底集;一组列独立,当且仅当它们线性无关。基是列空间的一组基,秩为 𝐴 的列秩。能表示成线性拟阵的称为可表示拟阵;图拟阵是正则拟阵,因而也是线性拟阵。

代数拟阵取域扩张 𝐾 在基域 𝐹 上的有限子集 𝐸⊆𝐾 为底集;𝐼⊆𝐸 独立,当且仅当 𝐼 在 𝐹 上代数独立。秩为对应子集的超越次数。

划分与层拟阵

设 𝐸=𝐸1∪…∪𝐸𝑚 且各块两两不交,容量为 𝑘1,…,𝑘𝑚。独立集满足

|𝐼∩𝐸𝑖|≤𝑘𝑖(𝑖=1,…,𝑚).

这是划分拟阵;基从每块取恰好 𝑘𝑖 个元素。均匀拟阵是只有一个块的划分拟阵。

把划分换成层族 ℒ︀:任意 𝐿1,𝐿2∈ℒ︀ 要么不交,要么一个包含另一个。给每个 𝐿 配相容容量 𝑘𝐿(𝐴⊆𝐵 时 𝑘𝐴≤𝑘𝐵),独立集满足

|𝐼∩𝐿|≤𝑘𝐿(𝐿∈ℒ︀).

这是层拟阵。划分拟阵是层族中所有集合两两不交的特例。

横截拟阵与 Gammoid

设 𝐺=(𝐿,𝑅,𝐸) 是二分图。取底集为 𝑅;𝐼⊆𝑅 独立,当且仅当存在匹配把 𝐼 饱和到 𝐿。这定义横截拟阵,基是最大可匹配子集,秩为最大匹配大小。

Gammoid 把匹配换成路径:给定有向图 𝐷=(𝑉,𝐴)、源集 𝑆 和目标集 𝑇,取底集为 𝑇;𝐼⊆𝑇 独立,当且仅当存在 |𝐼| 条从 𝑆 出发、终点为 𝐼 中元素的顶点不交路径。横截拟阵是 Gammoid 的特例。

运算构造

对偶、删除、收缩、直和与截断都保持拟阵性。余图拟阵就是图拟阵的对偶;从已知拟阵出发,可以用这些运算得到新模型。

非拟阵

  • 一般加工时间下的可准时任务族不构成拟阵,见 最小逾期任务。
  • 两个拟阵的交一般不是拟阵;见 最大拟阵交。
  • 图的匹配边集一般不构成拟阵。横截拟阵取的是可匹配的顶点子集,不是匹配边集本身。
源码位置