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