0 引言及预备知识

拟阵论^[1]是组合数学的一个重要分支, 是一种同时推广了图论和线性代数的数学理论.由于实际的需求和数学工作者的努力, 拟阵理论已经具有比较完善的公理系统, 在组合优化、算法设计、整数规划、信息编码、密码学等领域有广泛的应用.随着模糊集理论^[2]的建立以及模糊集思想向许多研究领域的渗透, 模糊拟阵理论的深度研究也相继出现.文献[3-10]定义并系统地研究了模糊拟阵, 通常称为GV模糊拟阵, 它是拟阵与模糊集概念相结合的产物, 史福贵在文献[11]中定义了(L, M)-拟阵, 它是分明拟阵和GV模糊拟阵的一般化, 并且推广了分明拟阵的一些结果.其他学者在此基础上进一步研究了特殊GV模糊拟阵或特殊(L, M)-拟阵的性质^[12-20].实际上, 所有这些模糊拟阵都与分明拟阵(简称拟阵或有限拟阵)有很大的联系, 本文将探究这些联系.首先定义拟阵的瘦基运算和弃基并且研究它们的性质, 然后用所得结果刻画正则GV状模糊拟阵.

文中出现的主要记号：

设(E上模糊集的全体), r∈[0, 1], X⊆E.

(1) 称μ_[r]={x∈E|μ(x)≥r}为模糊集μ的r水平截集.

(2) 称supp μ={x∈E|μ(x)＞0}为模糊集μ的支撑集.

(3) 记R⁺(μ)={μ(x)|x∈supp μ}.

(4) 记m(μ)=infR⁺(μ), M(μ)=supR⁺(μ).

(5) 称在点e处取值r(r＞0), 在其它点取值0的模糊集S_e^r为尖.

(6) 用r_X表示在X上取值r(r＞0), 在其它点取值0的模糊集.

(7) 称为模糊集μ的势.

文中将要用到的一些概念:

定义1^[1]  设E是一个有限集, ⊆2^E(即E的全体子集), 若满足下述3个条件:

(I₁) ∅∈ ,

(I₂)若I∈ 且I′⊆I, 则I′∈ ,

(I₃)若I₁, I₂∈ 且|I₁|＜|I₂|, 则∃e∈I₂-I₁, 使得I₁∪{e}∈ ,

则称是E上的一个拟阵独立集系, 且称中的元素为独立集, 称2^E-中的元素为相关集, 序对(E, )为拟阵, E上的拟阵独立集系的全体记为I(E).

定义2^[1]  设E是一个有限集, 若⊆2^E满足下述条件:

(B₁) ≠∅,

(B₂)若B₁, B₂∈ 且x∈B₁-B₂, 则必有y∈B₂-B₁使得(B₁-{x})∪{y}∈ ,

则称是E上的一个拟阵基系, E上的拟阵基系的全体记为B(E).

命题1^[1]  (1)设E为有限集, 对于每个∈ B, 令, 则得到一个一一对应F : B(E)→ I(E), 其逆映射G : I(E)→ B(E)定义为G ()=Max(), 即(, ⊆)的极大元的全体(∀ ∈ I(E)).

(2) (强交换定理)设B₁, B₂∈ (E), 且e∈B₁-B₂, 则∃f∈B₂-B₁, 使得B₁∪{f}-{e}∈ (E), 且B₂∪{e}-{f}∈ (E).

定义3^{[11, 21]}  设E为有限集, L为完全分配格, 若⊆L^E(即从E到L的映射的全体)满足以下3个条件:

(LI₁) 0_E∈ (其中0为L中的最小元),

(LI₂)若λ∈ 且μ≤λ(μ∈L^E), 则μ∈,

(LI₃)若λ, μ∈ 且b=‖μ‖(n)‖λ‖(n)对某个n∈ N成立, 则∃y∈μ_[b]-λ_[b]使得b_λ[b]∨b_{y}=b_λ[b]∪{y}∈ , 其中N为非负整数集, ‖λ‖, ‖μ‖: N→L为映射, 具体定义为‖λ‖(n)=∨{a∈L||λ_[a]|≥n}(∀n∈ N), ‖μ‖(n)=∨{a∈L||μ_[a]|≥n}(∀n∈ N).

则称是E上的一个L-拟阵独立集系, 且称(E, )是带独立集系的L-拟阵.

若还满足

则称L-拟阵(E, )是完全的.

文中约定L={0, 0.5, 1}⊆[0, 1].

命题2^{[16, 21]} (完全L-拟阵的等价条件)设E为有限集, ⊆L^E, 则(E, )是完全L-拟阵, 当且仅当(, ≤)是非空的下集, 且满足下面条件(因此也称完全L-拟阵为GV状模糊拟阵):

(*) 对中满足0＜|suppμ|＜|suppμ|的任意μ和ν, ∃λ∈ , 使得

(ⅰ) μ＜λ≤μ∨ν, 其中μ∨ν为μ和μ在(L^E, ≤)中的上确界,

(ⅱ) m(λ)≥min{m(μ), m(ν)}.

定义4^[22]  (正则的L-拟阵)设E为有限集, ⊆L^E, (E, )是GV状模糊拟阵, 若|ξ|=|η|(∀(ξ, η)∈Max()×Max())成立, 则称(E, )是正则的, 且称|ξ|是(E, )的秩(ξ∈Max()), 其中Max()是(, ≤)的极大元的全体.

1 拟阵的瘦基运算

定理1  设(E, )是秩为n(n≥1)的拟阵, =Max().则={D⊆B|B∈ , |D|=n-1}是E上的一个拟阵基系.称从到的运算为拟阵的瘦基运算, 称(resp., )为(resp., )的瘦身, 称(E, )为(E, )的瘦身拟阵, 其中=Low().由此可见={I∈ ||I|≤n-1}.

证明  显然非空.设D₁, D₂∈ (即∃B₁, B₂∈ ，使得D₁∪{x₁}=B₁且D₂∪{x₂}=B₂)且x∈D₁-D₂, 下面只须证明∃y∈D₂-D₁使得(D₁-{x})∪{y}∈ .若x₁=x₂, 则D₁-D₂=B₁-B₂且D₂-D₁=B₂-B₁, 因此由满足(B₂)知∃y∈B₂-B₁=D₂-D₁使得(B₁-{x})∪{y}∈ .由于(D₁-{x})∪{y}⊆(B₁-{x})∪{y}且|(D₁-{x})∪{y}|=|(B₁-{x})∪{y}|-1, 所以(D₁-{x})∪{y}∈ .下面设x₁≠x₂.

情形1   x₂∈B₁且x=x₂.此时D₁-D₂=(B₁-B₂)∪{x₂}-{x₁}, 因此由|D₁-{x}|＜|D₂|和(I₃)知∃y∈D₂-(D₁-{x})使得(D₁-{x})∪{y}∈ .又因|(D₁-{x})∪{y}|=|D₁|, 所以(D₁-{x})∪{y}∈ .

情形2  x₂∈B₁且x≠x₂.此时由D₁∪{x₁}=B₁, D₂∪{x₂}=B₂且x₁≠x₂, 知x∈B₁-B₂.因此由满足(B₂)知∃y∈B₂-B₁使得(B₁-{x})∪{y}∈ .由于B₂-B₁=D₂-D₁-{x₁}, 故y∈D₂-D₁.又因(D₁-{x})∪{y}⊆(B₁-{x})∪{y}且|(D₁-{x})∪{y}|=|D₁|, 所以(D₁-{x})∪{y}∈ .

情形3   x₂∉B₁.此时由D₁-D₂=B₁-B₂-{x₁}和满足强交换定理(即当A, B∈ 且a∈A-B时∃b∈B-A使得(A-{a})∪{b}∈ ，且(B-{b})∪{a}∈)知∃y∈B₂-B₁使得(B₁-{x})∪{y}∈ 且(B₂-{y})∪{x}∈ .由于B₂-B₁=(D₂-D₁)∪{x₂}-{x₁}, 故y∈D₂-D₁或y=x₂.若y∈D₂-D₁, 则因(D₁-{x})∪{y}⊆(B₁-{x})∪{y}且|(D₁-{x})∪{y}|=|D₁|, 所以(D₁-{x})∪{y}∈ .若y=x₂, 则由以上结论知D₂∪{x}=(B₂-x₂)∪{x}=(B₂-{y})∪{x}∈ .因x∈D₁-D₂, 故|D₁|＜|D₂∪{x}|, 所以由拟阵独立集系定义的(I₃)知∃y₀∈D₂∪{x}-D₁=D₂-D₁使得D₁∪{y₀}∈ .由|D₁∪{y₀}|=|D₁|+1=|B₁|知D₁∪{y₀}∈.由(D₁-{x})∪{y₀}⊆D₁∪{y₀}知|(D₁-{x})∪{y₀}|=|D₁|.所以(D₁-{x})∪{y₀}∈ .

推论1   ={D∈ ||D|=n-1}, 且(E, )是(E, )的(n-1)-截短.

例1   设E={3, 5, 7}, =2^E, ={∅, {3}, {7}, {5}, {3, 7}, {5, 7}, {3, 5}}, ={∅, {3}, {5}, {7}}, ={∅}.则(E, )的瘦身拟阵是(E, )(k=1, 2, 3).

例2   均匀拟阵(其中E是n元素集合, ={I∈2^E||I|≤m}, n≥m≥1)的瘦身拟阵是均匀拟阵.

例3   3个顶点的完全图K₃的圈拟阵(与例1中的(E, )同构)的瘦身拟阵不是可图拟阵, 因此可图拟阵的瘦身拟阵不必是可图拟阵.

2 拟阵的弃基

设是E上的一个拟阵基系, B∈ .则称从到 -{B}的运算为拟阵的弃基运算.如果是E上的拟阵基系的瘦身且对每个A∈ , ∃B_A∈ -{B}使得B_A⊆A, 则称从到 -{B}的运算为拟阵的留后代弃基.定理1说明拟阵基系经过瘦基运算后仍然是拟阵基系.然而拟阵基系经过弃基后不必是拟阵基系.

例4   考虑E={3, 5, 7, 9}上的拟阵基系: ={{5, 7, 9}, {3, 7, 9}, {3, 5, 9}, {3, 5, 7}}, ={E}, ={{3, 7}, {5, 7}, {3, 5}}, ={{3}, {5}, {7}}, ={∅}, ={{5, 7}, {7, 9}, {5, 9}, {3, 7}, {3, 9}, {3, 5}}, ={{3, 5}, {7, 9}, {5, 7}, {3, 9}}.则, 和经过弃基后仍然是拟阵基系, 和经过弃基后都不再是拟阵基系. 的瘦身是, 且经过2次留后代弃基后变成了.然而和经过弃基后不一定是拟阵基系.例如, = -{{3, 5}}={{7, 9}, {5, 7}, {3, 9}}不是拟阵基系.事实上, 设B₁={3, 9}, B₂={5, 7}.则B₁-B₂={3, 9}, B₂-B₁={5, 7}.但对于9∈B₁-B₂, 不仅(B₁-{9})∪{5}={3, 5}∉ , 而且(B₁-{9})∪{7}={3, 7}∉ .同理, -{{5, 9}}也不是拟阵基系.

定理2   均匀拟阵基系经过弃基后仍然是拟阵基系.

证明   考虑均匀拟阵, 其中|E|=n, ={I∈2^E||I|≤m}.它的唯一拟阵基系为={I∈2^E||I|=m}.任取B∈并且令= -{B}.设B₁, B₂∈ 且x∈B₁-B₂(由此可知B₂-B₁≠∅), 下面证明存在y∈B₂-B₁使得(B₁-{x})∪{y}∈ 即可.令B₂-B₁={y₁, y₂, …, y_k}(k≥1).若k=1, 则B₁-B₂={x}且(B₁-{x})∪{y₁}∈ .这时(B₁-{x})∪{y₁}=(B₁∩B₂)∪{y₁}=B₂∈ , 因此取y=y₁即可.若k＞1, 则(B₁-{x})∪{y₁}∈ .这时若(B₁-{x})∪{y₁}≠B, 则(B₁-{x})∪{y₁}∈ , 因此取y=y₁即可.但是若(B₁-{x})∪{y₁}=B, 则(B₁-{x})∪{y₂}∈ , 且由y₁≠y₂知(B₁-{x})∪{y₂}≠ (这说明(B₁-{x})∪{y₂}∈ ), 因此取y=y₂即可.

3 应用

文献[22]给出了构造GV模糊拟阵的一种方法(即用拟阵塔生成GV模糊拟阵), 本节将证明, 每一个正则的GV状模糊拟阵都可以从一个拟阵出发经过拟阵的有限次瘦基运算或弃基而得到.

引理1^[1]  设(E, )是一个拟阵, B∈Max(), I∈.则I∈Max()当且仅当|I|=|B|.

引理2^[22]  设(E, )是GV状模糊拟阵, 则下列各条件等价:

(1) (E, )是正则的.

(2) 对于每个A∈Max(), ∃B_A∈Max()使得B_A⊆A.

(3) 对于每个ξ∈Max(), .

定理3   设⊆L^E, 则下面各条件等价:

(1) (E, )是GV状模糊拟阵.

(2) 存在E上的拟阵独立集系以及从出发经过有限次瘦基运算或弃基得到的E上的拟阵独立集系使得={1_A∨0.5_D|A∈ , D∈ , A⊆D}.

证明   (1)⇒(2).设(E, )是GV状模糊拟阵, 且令=和=.则⊆ 且和都是E上的拟阵独立集系.进一步由(LI₄)可证 ={1_A∨0.5_D|A∈ , D∈, A⊆D}.设(E, )和(E, )的秩分别为m和n.则当m=n时可以从出发经过有限次弃基得到; 当m＞n时先从出发经过m-n次瘦基运算得到E上的秩为n拟阵独立集系₀, 然后从₀出发经过有限次弃基得到.

(2) ⇒(1).(E, )是GV状模糊拟阵, 其中 ={1_A∨0.5_D|A∈ , D∈, A⊆D}.显然是非空下集, 故只需证(, ≤)满足(*).设μ, ν∈ 满足0＜|supp μ|＜|supp ν|, 则由的定义知supp μ=μ_[0.5]∈ 且supp ν=ν_[0.5]∈ ; 由0＜|supp μ|＜|supp ν|及拟阵独立集系公理(I₃)知∃x∈ν_[0.5]-μ_[0.5]使得μ_[0.5]∪{x}∈ .当min{m(μ), (ν)}=1时, 易知λ=μ∨S_x¹满足(*).当min{m(μ), m(ν)}=0.5时, 令λ=μ∨S_x^0.5.则λ_[0.5]=μ_[0.5]∪{x}∈ 且λ_[1]=μ_[1]∈ .从而由λ_[1]⊆λ_[0.5]和λ=1_λ[1]∨0.5_λ[0.5]知λ∈ .由x∉μ_[0.5]知μ＜λ.显然λ≤μ∨μ且m(λ)=0.5≥min{m(μ), m(ν)}.

定理4   设⊆L^E, 则下面各条件等价:

(1) (E, )是正则的GV状模糊拟阵.

(2) 存在E上的拟阵基系以及从出发经过有限次瘦身运算或留后代弃基得到的E上的拟阵基系使得 =∪{↓(1_A∨0.5_D)|A∈ , D∈ , A⊆D}.

证明   由引理2知(2)⇒(1), 故只须证(1)⇒(2).设(E, )是正则的GV状模糊拟阵且令 =Max(), 由引理2知, ∃ ∈Max(), 使得⊆ , 且它们都是E上的拟阵基系.再设(E, _B)和(E, _B1)的秩分别为r和r₁.情形一:r=r₁时, 一方面, ∀B∈ =Max(), 都有B∈⊆, 又因为r=r₁, 所以B∈Max()= , 所以₁⊆ ; 另一方面, ∀A∈ =Max(), 由引理2知, ∃B_A∈Max()= , 使得B_A⊆A, 又因为r=r₁, 所以|B_A|=|A|, 即A=B_A, A∈Max()= , 所以有 ⊆ , 综上, 得当r=r₁时, = .情形二:当r＞r₁时先从出发经过r-r₁次瘦身运算得到的E上的拟阵基系, 此时就转化成了情形一.

接下来还需证明Max()= , 里 =∪{1_A∨0.5_D|A∈ , D∈ , A⊆D}(说明 =∪{↓(1_A∨0.5_D)|A∈ , D∈ , A⊆D}).设μ∈Max(), 则由引理2知μ_[0.5]∈Max()= 且μ_[1]∈Max()= , 从而由μ_[1]⊆μ_[0.5]和μ=1_μ[1]∨0.5_μ[0.5]知μ∈ .说明Max()⊆ .反过来, 设μ=1_A∨0.5_D∈ (其中A∈ , D∈ , A⊆D)但μ∉Max(), 则∃μ∈Max()使得μ＜μ, 从而∃a∈L-{0}使得μ_[a]⊂ν_[a]∈Max(), 这与μ_[a]∈Max()矛盾, 说明 ⊆Max().

设和是E上的满足Low()⊃Low()的拟阵基系, 则由定理4知可以从出发经过有限次瘦基或留后代弃基运算得到.下面给出一个例子.

例5   从E={3, 5, 7, 9}上的拟阵基系 ={E}出发经过一次瘦基运算可得到E上的拟阵基系={{3, 5, 7}, {3, 5, 9}, {3, 7, 9}, {5, 7, 9}}, 再从出发经过一次瘦基运算可得到E上的拟阵基系={{3, 5}, {3, 7}, {3, 9}, {5, 7}, {5, 9}, {7, 9}}, 再从出发经过3次留后代弃基运算可得到E上的拟阵基系={{3, 7}, {5, 7}, {3, 9}}.也可以从 ={E}出发先经过一次瘦基运算得到, 然后由出发经过3次留后代弃基得到E上的拟阵基系={{3, 5, 7}}, 最后由出发经过一次瘦基运算可得到E上的拟阵基系={{3, 7}, {5, 7}, {3, 9}}.