擬陣 是組合數學 中的一個結構 ,是對向量空間 中線性獨立 這一概念的概括與歸納。擬陣有許多等價的定義,其中最主要的幾個定義分別是基於獨立集、基底、環路、閉集、平坦、閉包算子和秩函數。
擬陣理論從線性代數 和圖論 中借用了大量術語,主要是因為它是對這些領域中很多重要的核心概念的概括。擬陣理論在幾何 、拓撲學 、組合優化 、網絡理論 和編碼理論 中都有應用。
擬陣有很多等價的定義方式[ 1] 。
就獨立集來說, 一個有限的擬陣
M
{\displaystyle M}
是一個二元組
(
E
,
I
)
{\displaystyle (E,{\mathcal {I}})}
, 其中
E
{\displaystyle E}
是一個 有限集 (稱之為 基礎集 ) ,
I
{\displaystyle {\mathcal {I}}}
是一個由
E
{\displaystyle E}
的子集構成的 集族 (稱之為 獨立集 ) 它需要滿足下面的條件:[ 2]
空集 是獨立的, 也就是說,
∅
∈
I
{\displaystyle \emptyset \in {\mathcal {I}}}
. 換個說法就是, 至少有一個
E
{\displaystyle E}
的子集是獨立的, 即:
I
≠
∅
{\displaystyle {\mathcal {I}}\neq \emptyset }
.
每個獨立集的子集是獨立的, 即: 對於每個子集
A
′
⊂
A
⊂
E
{\displaystyle A'\subset A\subset E}
, 如果
A
∈
I
{\displaystyle A\in {\mathcal {I}}}
則
A
′
∈
I
{\displaystyle A'\in {\mathcal {I}}}
. 有時我們稱之為 遺傳特性 .
如果
A
{\displaystyle A}
和
B
{\displaystyle B}
是
I
{\displaystyle {\mathcal {I}}}
的兩個獨立子集,
A
{\displaystyle A}
比
B
{\displaystyle B}
有更多的元素, 則在
A
{\displaystyle A}
中存在一個元素,當其加入
B
{\displaystyle B}
時得到一個比
B
{\displaystyle B}
更大獨立子集. 有時我們稱之為 擴充特性 或者叫 獨立集交換特性 .
頭兩個特性定義了一個公認的組合結構,叫做獨立系統 。
對於有限擬陣
M
{\displaystyle M}
,若其基礎集
E
{\displaystyle E}
的子集
B
{\displaystyle B}
是一個極大的獨立集(即添加任何一個新的元素得到的子集都不是獨立集),則將
B
{\displaystyle B}
稱為一個基底 (英文:basis)。擬陣的一種等價定義為二元組
(
E
,
B
)
{\displaystyle (E,{\mathcal {B}})}
,其中
E
{\displaystyle E}
是一個有限集,
B
{\displaystyle {\mathcal {B}}}
是一個由基底構成的
E
{\displaystyle E}
的子集族,稱為
M
{\displaystyle M}
的基 ,滿足以下條件:[ 1]
B
≠
∅
{\displaystyle {\mathcal {B}}\neq \emptyset }
;(即至少存在一個基底)
對於
B
{\displaystyle {\mathcal {B}}}
中不同的集合
A
,
B
{\displaystyle A,B}
以及任一元素
a
∈
A
−
B
{\displaystyle a\in A-B}
,存在元素
b
∈
B
−
A
{\displaystyle b\in B-A}
使得
A
∪
{
b
}
−
{
a
}
∈
B
{\displaystyle A\cup \{b\}-\{a\}\in {\mathcal {B}}}
。(該條件被稱為交換公理)
可以證明,一個有限擬陣的所有基底的元素個數都相同,這個數被稱為擬陣的秩 。
對於有限擬陣
M
{\displaystyle M}
,若其基礎集
E
{\displaystyle E}
的子集
C
{\displaystyle C}
是一個極小的非獨立集(即去掉其中任一元素得到的子集都是獨立集),則將
C
{\displaystyle C}
稱為一個環路 (英文:circuit)。擬陣的一種等價定義為二元組
(
E
,
C
)
{\displaystyle (E,{\mathcal {C}})}
,其中
E
{\displaystyle E}
是一個有限集,
C
{\displaystyle {\mathcal {C}}}
是一個由環路構成的
E
{\displaystyle E}
的子集族,稱為
M
{\displaystyle M}
的環路集,滿足以下條件:[ 1]
∅
∉
C
{\displaystyle \emptyset \notin {\mathcal {C}}}
;
如果
C
1
,
C
2
∈
C
{\displaystyle C_{1},C_{2}\in {\mathcal {C}}}
且
C
1
⊆
C
2
{\displaystyle C_{1}\subseteq C_{2}}
,則
C
1
=
C
2
{\displaystyle C_{1}=C_{2}}
;
對於
C
{\displaystyle {\mathcal {C}}}
中不同的集合
C
1
,
C
2
{\displaystyle C_{1},C_{2}}
以及元素
a
∈
C
1
∩
C
2
{\displaystyle a\in C_{1}\cap C_{2}}
,存在
C
3
∈
C
{\displaystyle C_{3}\in {\mathcal {C}}}
使得
C
3
⊆
C
1
∪
C
2
−
{
a
}
{\displaystyle C_{3}\subseteq C_{1}\cup C_{2}-\{a\}}
。
可以證明,基礎集的一個子集是獨立集若且唯若它不包含任一環路作為子集。
類似線性代數基底 的性質,擬陣的基底具有類似的性質:
M
{\displaystyle M}
的任意兩個基底具有相同的元素個數。這個數字被稱為擬陣
M
{\displaystyle M}
的秩 。
^ 1.0 1.1 1.2 A standard source for basic definitions and results about matroids is Oxley (1992). An older standard source is Welsh (1976). See Bryzlawski's appendix in White (1986) pp.298–302 for a list of equivalent axiom systems.
^ Welsh (1976 ), Section 1.2, "Axiom Systems for a Matroid", pp. 7–9.