拟阵有很多等价的定义方式[ 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.