矩陣胚
矩陣胚的定義是：
M={S,I}
其中S為有限集，I為S的一個子集族，滿足下面條件：
1.{}屬于I
2.如果集合X屬于I，則X的所有子集都屬于I。
3.如果集合W，V都屬于I，且|V|>|W|,則V中存在一個不在W中的集合z，使W并{z}屬于I。 I中的集合叫做矩陣胚的獨立子集。上面三個定義保證了獨立子集具有如下屬性：
1.獨立子集至少有一個（空集）
2.獨立子集是“遺傳”的。
3.只要一個獨立子集不是最大（元素最多）的，我們總可以把它變得更大。
定義：把S中的元素加非負的權(quán)，我們可以得到一個加權(quán)矩陣胚。
定理1：貪心的擴展加權(quán)矩陣胚可以得到最優(yōu)子集。
證明：設貪心法得到的獨立子集是B，最優(yōu)獨立子集為T(如果有多個T，選擇使B交T最大的那個)，那么：
i)如果B=T,則成功
ii)否則，設x為不在T中的第一個被貪心法選擇的元素，則T并x為非獨立集（否則與T最大矛盾）。
設C為T并x的子集中的最小的非獨立集，則x屬于C(否則C就為T的子集，與屬性2矛盾)。這樣，我們?nèi)
中任意不屬于B的元素y，又條件3，C-{y}為獨立集。
下面，我們從C-{y}出發(fā)構(gòu)造一個最優(yōu)獨立子集T_1，使B交T_1比B交T更大。
對于C-{y}，我們把T中不屬于其中的元素依次加到里面（根據(jù)屬性3），則最后我們得到一個T_1,
其中T_1=T-{y}+{x}。
下面，我們來說明w(x)=w(y)。
1.T是最優(yōu)的，因此w(T_1)<=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_1也是最優(yōu)獨立子集，但是T_1比T多一個在B中的元素x,與T的選擇矛盾。故貪心法能夠選擇最優(yōu)
獨立子集。
定理2：如果F關(guān)于子集運算是封閉的，而對于任何權(quán)函數(shù)(F,w),貪心法都適用，則F為某個矩陣胚的
獨立子集族。
這里略去定理的證明，想知道證明的朋友可以來信問我。
兩個常用的獨立子集的例子是：
1.有限個n維向量集合中個線性無關(guān)的向量 。
2.某個圖中沒有圈的邊集。
根據(jù)定理一，我們?nèi)绻梢园褑栴}歸結(jié)成在加權(quán)矩陣胚中求最優(yōu)獨立子集的問題（需要驗證問題的結(jié)構(gòu)滿足矩陣胚
的三個定義），我們就可以采用貪心法。也就是每次選取權(quán)值最優(yōu)的元素加到獨立子集中，最后得到的最大獨立子
集必然是最優(yōu)的。