对偶拟阵

对偶拟阵(dual matroid)亦称正交拟阵，是一种组合构形，它是由拟阵M导出的拟阵M*，当拟阵M以基集族B表示时，M=(E，B)，则M*=(E，B*)，其中B*={E-B：B∈B}。因此，当B为拟阵M的基时，E-B就是对偶拟阵的基，对于拟阵而言，其对偶拟阵总存在，而且M**=(M*)*=M，如此完整的对称性是拟阵特有的重要性质，这一点，在将拟阵应用到组合优化的理论时更为明显1。

定义定义 设M=(E，I)是E上的拟阵， (M)为M的基集，令：

={A⊆E|∃B∈ (M)，使A∩B=∅}，

则称M*=(E， )为M的对偶拟阵或M*为M的对偶。

若M是一拟阵，M*是M的对偶拟阵，则M*的基，秩函数，极小圈，闭包算子称为M的余基，余秩函数，余极小圈，余闭包算子2。

相关定理定理1 设M=(E，I)是E上的拟阵，(M)为M的基集，令

={A⊆E|∃B∈ (M)，使A∩B=∅}，

则M*=(E， )为E上的拟阵，其基集为2

*={E\B|B∈ (M)}.

欲证定理71，需要以下引理2。

引理2(拟阵的基交换性质)设M=(E，I)为一拟阵，B，B'为M的两个基，x∈B，则存在y∈B'，使(B\{x})∪{y}为M的基。

定理3 设M为一分明拟阵，M*为M的对偶拟阵，则：

(M*)*=M。

定理4 设M=(E，I)为一分明拟阵，其秩函数为R，设M*为M的对偶拟阵，M*的秩函数为R*，则∀A⊆E，

R*(A)=|A|+R(E\A)-R(E).

定理5 从对偶拟阵的定义可以推出这些结论：

(i)对所有满足0≤r≤n的整数r，都有 。

(ii)I*∈(M*)当且仅当E-I*∈(M)。

(iii)C*∈(M*)当且仅当E-C*∈(M)。

设G是个图，记M'为G的余圈拟阵，则据定理5(iii)，(M(G))*=M’。 (人们也常常用M*(G)来记(M(G))*。若拟阵M同构于某个图的余圈拟阵，M就称为一个余可图拟阵(cographicmatroid)。)

若拟阵M同构于M*，则称M为一个自偶拟阵(self-dual matroid)。

作为例子，M(K4)是一个自偶拟阵。若(M)=(M*)，则M是一个等自偶拟****阵(identically self-dual)。均匀拟阵Ur,2r就是一个等自偶拟阵，R8也是一个等自偶拟阵。由于E(M(K4))含有一个3元子集，它既是M(K4)的独立子集同时也是M*(K4)极小圈，故M(K4)不是一个等自偶拟阵3。

对偶增广定理 设M=(M，)是个拟阵。若I∈(M)和I*∈(M+)是E(M)中两个不相交的子集，则存在有B∈(M)及B*∈(M*)使得

I∈B，I*⊆B*并且B∩B*=∅。

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学