對偶擬陣

對偶擬陣(dual matroid)亦稱正交擬陣，是一種組合構形，它是由擬陣M導出的擬陣M*，當擬陣M以基集族B表示時，M=(E，B)，則M*=(E，B*)，其中B*={E-B：B∈B}。因此，當B為擬陣M的基時，E-B就是對偶擬陣的基，對於擬陣而言，其對偶擬陣總存在，而且M**=(M*)*=M，如此完整的對稱性是擬陣特有的重要性質，這一點，在將擬陣套用到組合最佳化的理論時更為明顯。

基本介紹

• 中文名：對偶擬陣
• 外文名：dual matroid
• 所屬學科：數學（組合數學）
• 別名：正交擬陣
• 簡介：一種組合構形

定義

定義 設M=(E，I)是E上的擬陣， (M)為M的基集，令：

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

則稱M*=(E， )為M的對偶擬陣或M*為M的對偶。

若M是一擬陣，M*是M的對偶擬陣，則M*的基，秩函式，極小圈，閉包運算元稱為M的余基，余秩函式，余極小圈，余閉包運算元。

相關定理

定理1 設M=(E，I)是E上的擬陣，(M)為M的基集，令

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

則M*=(E， )為E上的擬陣，其基集為

*={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(K₄)是一個自偶擬陣。若(M)=(M*)，則M是一個等自偶擬陣(identically self-dual)。均勻擬陣U_r,2r就是一個等自偶擬陣，R₈也是一個等自偶擬陣。由於E(M(K₄))含有一個3元子集，它既是M(K₄)的獨立子集同時也是M*(K₄)極小圈，故M(K₄)不是一個等自偶擬陣。

對偶增廣定理 設M=(M，)是個擬陣。若I∈(M)和I*∈(M+)是E(M)中兩個不相交的子集，則存在有B∈(M)及B*∈(M*)使得

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