矩陣胚

簡介

矩陣胚亦稱擬陣。向量獨立性概念的一種推廣，由美國數學家惠特尼（Whitney，H.)於1935 年提出，其定義如下：如果 E 為有限集，𝒫為 E 的某些子集的集合，並滿足條件：

1、空集

𝒫 。

2、若

𝒫，則

𝒫。

3、若

𝒫，|X|=|Y|+1，則存在

，使

𝒫（這裡 |X| 表示 X 中元素個數）

則稱（E，𝒫）為一個擬陣即矩陣胚。

滿足上述條件 1 和 2 的（E，𝒫）稱為一個獨立系，擬陣首先在圖論研究中引起注意，它使圖論中某些概念易於理解，產生了許多新的結果，並使原有若干證明大為簡化，在組合最佳化中也有重要套用，特別是三個以上擬陣交的獨立系統問題至今仍是難題。它的研究對於最短路問題、最小樹形問題、旅行商問題等均有重要意義。

上面三個定義保證了獨立子集具有如下屬性：

1.獨立子集至少有一個（空集）

2.獨立子集是“遺傳”的。

3.只要一個獨立子集不是最大（元素最多）的，我們總可以把它變得更大。

定義：把 S 中的元素加非負的權，我們可以得到一個加權矩陣胚。

貪心的擴展加權矩陣胚可以得到最優子集。

證明：設貪心法得到的獨立子集是 B ，最優獨立子集為 T（如果有多個 T ，選擇使 B 交 T 最大的那個），那么：

i)如果 B=T ，則成功；

ii)否則，設 x 為不在 T 中的第一個被貪心法選擇的元素，則 T 並 x 為非獨立集（否則與 T 最大矛盾）。

設 C 為 T 並 x 的子集中的最小的非獨立集，則 x 屬於 C （否則 C 就為 T 的子集，與屬性 2 矛盾）。這樣，我們取 C中任意不屬於 B 的元素 y ，又條件 3 ， C-{y} 為獨立集。

下面從 C-{y} 出發構造一個最優獨立子集 T₁，使 B 交 T₁ 比 B 交 T 更大。

對於 C-{y} ，我們把 T 中不屬於其中的元素依次加到裡面（根據屬性 3 ），則最後我們得到一個T₁，其中T₁=T-{y}+{x}。

下面來說明 w(x)=w(y) 。

1.T是最優的，因此 w(T₁)≤w(T)，即 w(x)<=w(y) ；

2.假設貪心算法選擇 x 之前選擇過的元素集合為 X ，那么： X 為 T 的子集，且 X 並 {y} 也是 T 的子集。那么，在選擇 x 的時候， y 也是可以選的。但是貪心算法選擇的是 x ，必有 w(x)≥w(y) ，故 w(x)=w(y)。

這樣，T₁也是最優獨立子集，但是 T₁比 T 多一個在 B 中的元素 x ，與 T 的選擇矛盾。故貪心法能夠選擇最優獨立子集。