跳至內容

擬陣

維基百科,自由的百科全書

擬陣組合數學中的一個結構,是對向量空間線性獨立這一概念的概括與歸納。擬陣有許多等價的定義,其中最主要的幾個定義分別是基於獨立集、基底、環路、閉集、平坦、閉包算子和秩函數。

擬陣理論從線性代數圖論中借用了大量術語,主要是因為它是對這些領域中很多重要的核心概念的概括。擬陣理論在幾何拓撲學組合優化網絡理論編碼理論中都有應用。

定義

[編輯]

擬陣有很多等價的定義方式[1]

獨立集

[編輯]

就獨立集來說, 一個有限的擬陣 是一個二元組 , 其中 是一個 有限集 (稱之為 基礎集) , 是一個由的子集構成的 集族 (稱之為 獨立集) 它需要滿足下面的條件:[2]

  1. 空集 是獨立的, 也就是說, . 換個說法就是, 至少有一個 的子集是獨立的, 即:.
  2. 每個獨立集的子集是獨立的, 即: 對於每個子集 , 如果 . 有時我們稱之為 遺傳特性.
  3. 如果 的兩個獨立子集,有更多的元素, 則在中存在一個元素,當其加入 時得到一個比更大獨立子集. 有時我們稱之為 擴充特性 或者叫 獨立集交換特性.

頭兩個特性定義了一個公認的組合結構,叫做獨立系統

[編輯]

對於有限擬陣 ,若其基礎集的子集是一個極大的獨立集(即添加任何一個新的元素得到的子集都不是獨立集),則將稱為一個基底(英文:basis)。擬陣的一種等價定義為二元組,其中 是一個有限集, 是一個由基底構成的的子集族,稱為,滿足以下條件:[1]

  1. ;(即至少存在一個基底)
  2. 對於中不同的集合以及任一元素,存在元素使得。(該條件被稱為交換公理)

可以證明,一個有限擬陣的所有基底的元素個數都相同,這個數被稱為擬陣的

環路

[編輯]

對於有限擬陣 ,若其基礎集的子集是一個極小的非獨立集(即去掉其中任一元素得到的子集都是獨立集),則將稱為一個環路(英文:circuit)。擬陣的一種等價定義為二元組,其中 是一個有限集, 是一個由環路構成的的子集族,稱為的環路集,滿足以下條件:[1]

  1. 如果,則
  2. 對於中不同的集合以及元素,存在使得

可以證明,基礎集的一個子集是獨立集若且唯若它不包含任一環路作為子集。

秩函數

[編輯]

類似線性代數基底的性質,擬陣的基底具有類似的性質:的任意兩個基底具有相同的元素個數。這個數字被稱為擬陣

閉包

[編輯]

參考資料

[編輯]
  1. ^ 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.
  2. ^ Welsh (1976), Section 1.2, "Axiom Systems for a Matroid", pp. 7–9.