拟阵实例
常见拟阵模型:均匀、图、余图、双循环、线性、代数、划分、层、横截与 Gammoid,以及非拟阵例子。标签 数学 / 拟阵 / 组合结构 / 图 / 线性空间
本页承接 拟阵 的定义,列举常见模型。基统一定义为极大独立集;基的等势性与交换性见 拟阵基定理。
均匀拟阵
取 ,。独立集为
这是均匀拟阵 ,基是全部 元子集,秩为 。 是自由拟阵,所有子集都独立; 是空拟阵,只有空集独立。
图拟阵
设 是图。底集为 ,独立集为无圈边集,即森林。基是极大森林;当 连通时,基就是生成树。这正是 最小生成树 的拟阵结构。
余图拟阵
图拟阵的 对偶 称为余图拟阵。连通图时,它的基是生成树的补,即余树;独立集是某个余树的子集。
双循环拟阵
底集仍是图 的边集。独立集是伪森林:每个连通分量至多含一个圈。极大伪森林是基。双循环拟阵是拟阵,但一般不是图拟阵。
线性与代数拟阵
线性拟阵取某个域 上矩阵 的列为底集;一组列独立,当且仅当它们线性无关。基是列空间的一组基,秩为 的列秩。能表示成线性拟阵的称为可表示拟阵;图拟阵是正则拟阵,因而也是线性拟阵。
代数拟阵取域扩张 在基域 上的有限子集 为底集; 独立,当且仅当 在 上代数独立。秩为对应子集的超越次数。
划分与层拟阵
设 且各块两两不交,容量为 。独立集满足
这是划分拟阵;基从每块取恰好 个元素。均匀拟阵是只有一个块的划分拟阵。
把划分换成层族 :任意 要么不交,要么一个包含另一个。给每个 配相容容量 ( 时 ),独立集满足
这是层拟阵。划分拟阵是层族中所有集合两两不交的特例。
横截拟阵与 Gammoid
设 是二分图。取底集为 ; 独立,当且仅当存在匹配把 饱和到 。这定义横截拟阵,基是最大可匹配子集,秩为最大匹配大小。
Gammoid 把匹配换成路径:给定有向图 、源集 和目标集 ,取底集为 ; 独立,当且仅当存在 条从 出发、终点为 中元素的顶点不交路径。横截拟阵是 Gammoid 的特例。
运算构造
对偶、删除、收缩、直和与截断都保持拟阵性。余图拟阵就是图拟阵的对偶;从已知拟阵出发,可以用这些运算得到新模型。