基本介紹
- 中文名：序陣
- 外文名：greedoid
- 所屬學科：數學
- 所屬問題：離散數學（組合序）
- 簡介：帶一定條件的語集
基本介紹,序陣與擬陣的對比,序陣的秩函式,多面體擬陣的序陣,
基本介紹
序陣是帶一定條件的語集，它是滿足下述條件的一類簡單語集G=(E，L)：
1.空集為可行詞；
2.將可行詞α任意分解為因子β和γ，α=βγ，則β為可行詞；
3.對於任意可行詞α，β，若α中元素數目多於β，即|α|>|β|，則在α中有元素e，將其拼接到β之後，βe仍為可行詞。
條件2是序陣G滿足的遺傳性質，而條件3刻畫了替換性質。序陣G對應的組合系統記為
=(E，
)，其中={
={a1，…，ak}|α=a1…ak∈L}，此時，條件2與3的無序形式分別為：
2′.若A∈，則有e∈A，使得A-{e}∈；
3′.若A，B∈，且|A|=|B|+1，則有e∈A-B，使得B∪{e}∈；
反之，若組合系統M=(F，F)滿足1和3，則有惟一的序陣G=(E，L)，使得=F。
序陣與擬陣的對比
由前文所述，在兩種意義上序陣是擬陣的推廣。其一是從無序情形推廣到有序情形；其二是若把它們都視為無序情形的組合系統，則序陣對應的遺傳條件已大大減弱。
對擬陣而言，獨立集的所有子集均仍為獨立集，對序陣而言，只要求一個次級子集仍為可行集。這樣，擬陣的許多良好性質，對於序陣而言均不復存在了。例如，序陣一般不具有對偶結構；序陣的秩函式不再是次模函式，也不具有單一秩增性;；序陣對應的多面體不再具有對偶全整性；貪婪算法對序陣不能奏效等。
然而，序陣在一定程度上刻畫了某些組合問題，例如搜尋序陣，設r為有向圖G=(V，A)上的特定節點，A的子集S為其可行詞，若且唯若S為以r為根的森林，它的基詞相應於G的以r為始點的搜尋，而當G為無向圖時，設可行詞為包含r的連通子圖，這樣得到的序陣稱為線搜尋序陣，再如剝脫序陣，對於圖上的已知的樹T，當T刪除掉節點集X之後仍保持連通，稱此餘留部分T-X為序陣的可行詞對應地亦可從邊集產生剝脫序陣：對於邊集的子集X，當T-X仍保持連通時，稱其為序陣的可行詞，對弦圖實施剝脫，則可獲得弦圖的剝脫序陣。又如耳型分解序陣，e0為2連通圖G=(V，E)上的特定邊，E-{e0}的子集X為可行詞，若且唯若X∪{e0}連通，且X∪{e0}每個不可分離塊均為單一邊組成，否則這塊必包含e0。
序陣的秩函式
1.r(∅)=0；
2.對於E的任意子集X，r(X)≤|X|；
3.對於E的任意子集X，Y，若X⊆Y，則：
r(X)≤r(Y).
4.若r(X)=r(X∪{e1})=r(X∪{e2})，則
r(X)=r(X∪{e1}∪{e2}).
在這裡，本質的條件4表明序陣的秩函式不是次模函式，與擬陣類似，一個序陣由上述四個條件決定的秩函式惟一確定。
多面體擬陣的序陣
多面體擬陣的序陣(polymatroid greedoid)是一種組合構形，它是由多面體擬陣(E，f)派生的序陣G=(E，Lf)，這裡f為符合要求的次模函式。序串a1a2…ak為序陣G的可行詞，若且唯若對於任意的i=1，2，…，k，均有f(a1，a2，…，ai)=i。例如，在偏序集P=(E，≤)上，對於E的任意子集X，設f(X)表示由X產生的理想I(X)包含元素的個數.此時(E，f)為一多面體擬陣.於是，可由(E，f)派生序陣，記為G=(E，F)，X∈F若且唯若X為P上的一個理想，稱G=(E，F)為偏序集序陣，或時間表序陣。
