擬陣的獨立集構(gòu)成的偏序集

(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 保定 071002)

雖然擬陣在組合理論中很重要[1-3]，但是這并不意味著擬陣可以覆蓋組合理論的所有方面。組合理論中的許多方面可以用擬陣清晰地解釋。這些解釋成為組合數(shù)學(xué)與更多數(shù)學(xué)主流領(lǐng)域的連接帶。將偏序集理論[4-5]應(yīng)用到擬陣的研究是一條成功之路[1-3,6-14]。此外,借助于偏序集理論,可以建立與擬陣有關(guān)的一些新框架[6-7,14]。擬陣具有幾何格表示，反之，每個幾何格是簡單擬陣；但是并不是每個擬陣都是簡單的，即有些擬陣不能由幾何格給予特征。另外,Welsh[2]指出，擬陣最著名的算法性質(zhì)與貪心算法有密切關(guān)系。貪心算法已被廣泛地應(yīng)用和研究[1,2,15-16]。擬陣的貪心算法特征是由擬陣的獨立集所描述的[2]。為了尋找擬陣的更多算法特征，并將擬陣的應(yīng)用范圍拓廣，考慮到每個格都是偏序集，因此，本文中考慮將貪心算法與偏序集結(jié)合，以用于挖掘擬陣的更多算法結(jié)果，該實現(xiàn)首先需要解決擬陣與偏序集之間的關(guān)系問題，才能進一步探索擬陣新的特征。在開始研究之前,應(yīng)注意以下幾點。1)擬陣由其獨立集族所定義[1-3]。2)Boolean格已經(jīng)用于研究任意基數(shù)集上的擬陣之獨立集的問題[17-19]。3)擬陣是一種特殊的獨立結(jié)構(gòu)[20]。4)因為與獨立集有關(guān),所以Boolean格已被用于擬陣的研究[14],另外，Mpi-空間和獨立空間可以分別用偏序集予以特征化[19,21]。偏序集理論與擬陣也有成功的結(jié)合[1-2,22]。5)對于任意擬陣M=(S,T(M))，其中S為有限集，T(M)為M的獨立集族,可以得到與該擬陣有關(guān)的偏序集(T(M),?)。

上述這幾點蘊含著用擬陣的獨立集對應(yīng)的偏序集探討擬陣的必要性。本文中利用偏序集理論將擬陣特征化，該方法不同于已有的發(fā)現(xiàn)擬陣的特征的研究方法，例如，擬陣的幾何格特征的發(fā)現(xiàn)方法[1-3]。

為了使影響擬陣應(yīng)用的幾何格條件減弱為更廣泛的數(shù)學(xué)結(jié)構(gòu)——偏序集，本文中通過擬陣的獨立集族構(gòu)建偏序集，用偏序集配合Boolean格搭建擬陣，在同構(gòu)意義下實現(xiàn)用偏序集的性質(zhì)將擬陣特征化。首先提出在一定條件下，偏序集P能在同構(gòu)意義下定義擬陣M(P)；在同構(gòu)意義下,挖掘滿足一定條件的偏序集與無環(huán)擬陣之間的關(guān)系，并將結(jié)果與著名的擬陣、幾何格之間的結(jié)果進行比較。

1 預(yù)備知識

1.1 符號

本文中所有討論均為有限。|A|為集合A的基數(shù)；2A為A的冪集；max{|Xi| ∶i=1,2,…,n<∞}為集合{|Xi| ∶i=1,2,…,n<∞}中的元關(guān)于自然序的最大值。

在偏序集P中，Max(P)是P中極大元集合；若x和y是P中不可比元，則記為x‖y。

∨和∧分別為格中的并和交2種運算。

1.2 定義

1)設(shè)S為有限集，T 為S的子集族。如果T 滿足以下條件，那么稱(S,T )為擬陣(matroid)，記為M=(S,T )，T 記為T (M)，其中的元稱為獨立集。

①?∈T。

②若X∈T且Y?X,則Y∈T。

③若U、V是T中的元且|U|=|V|+1,則存在x∈UV滿足V∪{x}∈T。

若S的子集X不屬于T,則稱X為M的相關(guān)集。M的基是M的極大獨立集。M的秩函數(shù)是函數(shù)ρ∶ 2S→，定義為ρ(A)=max{|X| ∶X?A,X∈T }，A?S。S的秩稱為擬陣M的秩，記為ρ(M)。[2]

2)擬陣M的環(huán)(loop)是S的元素x，若{x}為相關(guān)集；稱S的2個元x、y為平行的(parallel)，若它們均不是環(huán)，但是{x,y}為相關(guān)集。

稱無環(huán)、無平行元的擬陣為簡單擬陣(simple matroid)。

2個擬陣M1=(S1,T1)和M2=(S2,T2)稱為同構(gòu)的(記為M1?M2)，如果存在雙射f∶S1→S2滿足A∈T1?f(A)∈T2。[2]

3)若偏序集P有唯一的最小元，通常將該元記為0,則將覆蓋0的元稱為原子(atom)。P的全序子集稱為P的鏈(chain)，即{x0,x1,…,xk}是一個鏈當且僅當x0

4)格L稱為Boolean的當且僅當L為含最小元以及最大元的有補分配格。[4]

2 偏序集與擬陣的獨立集

本節(jié)將研究擬陣的獨立集族由包含關(guān)系所構(gòu)成的結(jié)構(gòu)，并探討偏序集與擬陣之間的關(guān)系。這些關(guān)系的意義和價值在于它們可以將擬陣框架下的結(jié)果與偏序集框架下的內(nèi)容相互轉(zhuǎn)化。

令M為S上的擬陣，T (M)為其獨立集族,B(M)為其基族。令P (M)代表(T (M),?)。

性質(zhì)11)P (M)以{?}為其最小元。

2)P (M)的原子集是M中秩等于1的獨立集的全體。

3)a∈Max[P (M)]當且僅當a∈B(M)。

4)X在P (M)中覆蓋Y的充要條件是X,Y∈P (M),Y?X并且|X|=|Y|+1。

引理11)在P (M)中所有的極大鏈有相同的長|B|,此處B∈B(M)。

2)P (M)中的每個元素I以M的秩函數(shù)ρ(I)為其高度。

3)對于任意基B∈B(M),在P (M)中的區(qū)間[0,B]是Boolean格，此處0={?}。另外,對任意的I∈P (M),I是P (M)的一些原子的并。

4)對于任意的I,J∈P (M),如果|J|=|I|+1成立,那么存在j∈JI滿足I∪{j}∈P (M)。

證明：由M中基的定義以及M中秩函數(shù)的定義，易得1)、2)和4)。根據(jù)性質(zhì)1中的3),可以導(dǎo)出B∈P (M)。對于任意的X?B，有X∈P (M)，因此，得到 (2B,?)?P (M)和(2B,?)=({Y∈T (M)∶Y?B},?)，從而,3)成立。引理1證畢。

引理1的3)表明Boolean格將會揭示偏序集與擬陣之間的一些內(nèi)在關(guān)系。為了驗證該結(jié)論,需要下面的引理。

引理21)有限偏序集P有最小元0。設(shè)h為P的高函數(shù),Θ為P中的原子集。對于x∈P，設(shè)Xx={a∈P∶a∈Θ且a≤x}。若P滿足如下條件2)— 4)，則存在定義在Θ上的滿足(T (M(P)),?)?P的擬陣M(P),并且M(P)無環(huán)。

3)對于任意b∈Max(P)，[0,b]?(2{y∈Θ ∶y≤b},?)成立。

4)對于任意z,t∈P,若h(t)=h(z)+1成立,則存在y∈XtXz滿足z∨y∈P和Xz∪{y}={a∈P∶a∈Θ且a≤z∨y}。

證明：根據(jù)條件1),h和Θ二者都有意義。設(shè)I(P)={X?P∶存在x∈P，使得X= {y∈P∶y是P的原子，并且y≤x} }。

首先證明(Θ,I(P))是擬陣。

由條件1)可知，0∈P成立，但是0不是原子。根據(jù)條件2)，這意味著?∈I(P)，因此,對于I(P),在1.2節(jié)1)中的條件①成立。

設(shè)U、V∈I(P)且|V|=|U|+1。根據(jù)I(P)的定義，可知u=∨U∈P且v=∨V∈P,另外,Xu=U和Xv=V成立。根據(jù)條件2)和|V|=|U|+1，得到h(v)=h(u)+1。利用條件4)可得y∈XvXu=VU滿足u∨y∈P和Xu∨y=U∪{y}。由此可知，U∪{y}∈I(P)，因此,在I(P)中,1.2節(jié)1)中的條件③成立。

根據(jù)擬陣的定義,(Θ,I(P))是擬陣。為了簡單起見,記(Θ,I(P))為M(P)。

證明(I(M(P)),?)?P。因為I(M(P))是I(P)，所以證明(I(P),?)?P。

事實上，易知I(P)={Xx∶x∈P}。

設(shè)x∈P。由條件2),有且僅有X∈I(P)滿足∨X=x；反之，若∨X=x,則X∈I(P)；因此，定義為x→Xx的映射φ∶P→I(P)是有意義的。根據(jù)I(P)的定義，對于x∈P，有I(P)={Xx∶φ(x)=Xx}。根據(jù)條件2)，φ為雙射。下面證明φ是同構(gòu)。

容易得到a=0∈P的充要條件是φ(a)={?}。

設(shè)x,y∈P，則φ(x)=Xx=X={a∶a∈Θ且a≤x}且φ(y)=Xy=Y={a∶a∈Θ且a≤y}。

若x≤y，由條件2)可知x=∨X以及y=∨Y。根據(jù)x≤y可知，若a∈X,則a∈Y，因此X?Y。反之，設(shè)I,J∈I(P)且I?J，則根據(jù)條件2)和I(P)的定義可得，存在i,j∈P滿足i=∨I和j=∨J。另外，可以確定I={a∈Θ∶a≤i}且J={a∈Θ∶a≤j}。由i∈I?J可得i∈J，進而有i≤j，即x≤y當且僅當X?Y。

類似地,可以證明，在P中x‖y的充要條件是在I(P)中X‖Y，此處∨X=x且∨Y=y。

從而,φ是在P與(I(P),?)之間的同構(gòu)映射。

證明M(P)無環(huán)。由于φ為雙射,因此x∈Θ?Xx={x}∈I(P)。由此可知，M(P)無環(huán)。引理2證畢。

通過分析引理2條件1)— 4)，發(fā)現(xiàn)如果一個偏序集不滿足條件1),則不存在擬陣M滿足(T (M),?)?P，即條件1)對引理2而言是必需的。

定理1有限偏序集P同構(gòu)于一個擬陣的獨立集族所構(gòu)成的偏序集當且僅當P滿足引理2中的條件1)— 4)。

證明:由引理1、2容易得到所需結(jié)論。定理1證畢。

一個擬陣的結(jié)構(gòu)并不能夠由其獨立集的偏序集完全定義。對于不同構(gòu)的2個擬陣,它們的獨立集的偏序集可同構(gòu)。如令M1=({1,2},T(M1)={?,{1}})而M2=({1},T(M2)={?,{1}})，可得(T (M1),?)=(T (M2),?)而M1M2。原因是M1中有環(huán)。事實上,{2}是M1的環(huán)，而M2是無環(huán)的。

無環(huán)擬陣的重要性體現(xiàn)在定理2中。

定理2有限偏序集P與以P為原子集的擬陣M(P)之間的對應(yīng)是滿足引理2中的條件1)— 4)的有限偏序集構(gòu)成的集合與無環(huán)擬陣構(gòu)成的集合之間的雙射。

證明：若P為滿足引理2中的條件1)— 4)的偏序集，則由引理2,可知M(P)為無環(huán)的擬陣，并且在同構(gòu)意義下P (M(P))是P。反之，如果對于無環(huán)的擬陣M，P (M)是其獨立集族,那么利用在引理2中M(P (M))的構(gòu)造和P (M)的結(jié)構(gòu),可以導(dǎo)出M(P (M))?M。定理2證畢。

根據(jù)定理2，對于無環(huán)的擬陣的研究即為對滿足引理2中的條件1)— 4)的有限偏序集的研究。如果重點研究無環(huán)的擬陣，那么擬陣中許多有趣問題可以在偏序集中延續(xù)。此外,在同構(gòu)意義下,無環(huán)擬陣可以由滿足引理2中的條件1)— 4)的偏序集將其特征化。

根據(jù)引理1、2，再結(jié)合定理2,可以得到簡單擬陣的一個重要結(jié)果。

推論1由Boolean格P到以P為原子集的擬陣M(P)上的映射是有限Boolean格集合與擁有唯一基的簡單擬陣集合之間的雙射。

將擬陣的一些結(jié)果轉(zhuǎn)化到偏序集的框架下的內(nèi)容是很有必要的。

定理3若M=(S,T )為擬陣,k∈且0≤k,Tk={X∶X∈T,|X|≤k}，那么(S,Tk)為擬陣。

反之，令M2=(S2,T2)為擬陣。若S3=S2∪且T3=T2成立，則M3=(S3,T3)為擬陣并且是該擬陣的環(huán)。在下面的證明中僅需要考慮無環(huán)的擬陣。

令M無環(huán)。由定理2可確定偏序集P (M)即(T,?)是對應(yīng)于M的。根據(jù)性質(zhì)1中的1)— 4)和引理1中的1)— 4)可知，P (M)以S為原子集并且滿足引理2中的條件1)— 4)。

令h為P (M)的高函數(shù)，并且對x∈P (M)有Xx={a∈P (M)∶a≤x且a∈S}。由引理2中的2)可知x=∨Xx。

令P (M)k={x∈P (M)∶h(x)≤k}。根據(jù)引理1的2),可知P (M)k={x∈P (M)∶ρ(x)≤k}= {x∈P ∶|x|≤k}，因此P (M)k=Tk成立。

下面證明P (M)k滿足引理2中的條件1)— 4)。

容易得知P (M)k滿足引理2中的條件1)和4)。

若b∈Max[P (M)k]，則a∈Max[P (M)]滿足b≤a。在P(M)中,由引理2中的條件3),可以得到[0,a]是Boolean格并且滿足[0,a]?(2{y∈S ∶y≤a},?)，即[0,b]為Boolean格且[0,b]?(2{y∈S ∶y≤b},?)，從而在P(M)k的區(qū)間[0,b]k表現(xiàn)在P(M)中是區(qū)間[0,b]，因此，[0,b]k為Boolean格并且[0,b]k?(2{y∈S ∶ y≤b},?)，即對于P(M)k,引理2中的條件3)是成立的。

根據(jù)定理1、2，可以得到M(P(M)k)?(S,Tk)。即(S,Tk)為擬陣。定理3證畢。

定理3與文獻[18]中定理1的結(jié)果是相同的，但是得到結(jié)果的方法不同。這表明本文中的方法是成功的。

3 總結(jié)

文獻[20]中的定理2只有簡單擬陣才能夠滿足,但是本文中的定理2對于任何無環(huán)的擬陣都適用。因為一個簡單擬陣一定是無環(huán)的并且無平行元，所以本文中的定理2比文獻[20]中定理 2的適用范圍廣。由此可知，本文中的主要結(jié)果即定理2拓廣了擬陣已有的結(jié)果。事實上，本文中的思想不僅可用于擬陣的其他公理體系結(jié)合另外的數(shù)學(xué)結(jié)構(gòu)，將擬陣特征化，而且也為使更多算法應(yīng)用于擬陣領(lǐng)域、擴大擬陣的適用范圍奠定了理論基礎(chǔ)。

在今后的研究中將借助于偏序集理論和貪心算法揭示擬陣更多的性質(zhì)，并將其應(yīng)用到更廣的范圍，例如,利用擬陣和貪心算法尋找概念格的結(jié)構(gòu)。