區間值模糊圖的圖塔分解與表示定理

李紅霞, 鞏增泰, 劉 坤

(1. 隴東學院 數學與統計學院, 甘肅 慶陽 745000; 2. 西北師范大學 數學與統計學院, 甘肅 蘭州 730070)

模糊圖(可視為歐拉圖的推廣)是1975年由Rosenfeld[1]定義的,并且給出了與圖對應的模糊概念(如模糊橋、路、圈、樹以及連通性)及其性質;之后文獻[2-3]給出模糊圖的笛卡爾乘積、合成及并與聯運算；Bhattacharya[4]給出模糊割點、橋及連通性等概念；有關模糊圖的運算及相關性質可參閱文獻[5-7];Ju等[8]給出區間值模糊圖的概念;接著Akram等[9]定義區間值模糊圖的笛卡爾積、合成、并、聯與補運算,并且討論了它們的一些性質;Talebi等[10]討論了自補和自弱補區間值模糊圖及其運算;文獻[11]給出完全區間值模糊圖的一些相關運算.同時,楊文華等[12-13]就區間值模糊圖的運算性質給出補充研究;趙衍才等[14]給出模糊圖的(α,β)-截圖,借助于截圖來研究模糊圖.對于圖G=(V,E)上的區間值模糊圖,一方面有類似于區間值模糊集的性質,另一方面,由于[0,1]上區間集和圖集的偏序關系,使得區間值模糊圖的結構更為復雜.本文利用偏序集的同構關系研究區間值模糊圖的圖塔分解與表示.對于給定的區間值模糊圖,唯一確定[0,1]上區間集的1個劃分,同時得到模糊圖的圖集表示,并證明區間劃分與圖集有相同的序結構,同時給出區間值模糊圖的圖塔分解及運算法則,建立區間值模糊圖塔與區間值模糊圖的同構關系.作為模糊圖運算及其應用的基礎性研究,得到圖集與區間值模糊圖的轉換定理.

1 基本知識

設I={[a,b]|0≤a≤b≤1}(即[0,1]中所有閉區間構成的集合),I中的序關系定義為：[a1,b1]≤[a2,b2]?a1≤a2且b1≤b2,?[a1,b1],[a2,b2]∈I.

設λ∈I-{[1,1]},若對I的任意有限子集J,當λ≥∧J時,有μ∈J,使得λ≥μ,則稱λ為素元,I中素元的全體記作Pr(I)[15].

設λ∈I-{[0,0]},若對I的任意有限子集J,當λ≤∨J時,有μ∈J,使得λ≤μ,則稱λ為余素元,I中余素元的全體記作CPr(I)[15].

定義1.1[11]1) 設X是一個非空集合,稱映射A:X→I為X上的區間值模糊集,記A(x)=[A-(x),A+(x)](x∈X),顯然,A-、A+均為X到[0,1]的映射,且滿足

A-(x)≤A+(x)(x∈X).

2) 對于任意的集合V,在V×V-{(x,x)|x∈V}上定義等價關系～如下：

(x1,y1)～(x2,y2)?(x1,y1)=(x2,y2)或者x1=y2,x2=y1,

定義1.2[16]設G1=(V1,E1),G2=(V2,E2)是圖.

1) 稱圖G=(V1∪V2,E1∪E2)為圖G1與G2的并,可記為G=G1∪G2;

2) 稱圖G=(V1∩V2,E1∩E2)為圖G1與G2的交,可記為G=G1∩G2;

3) 若V1?V2,E1?E2,則稱G1是G2的子圖.

則稱序對G=(A,B)是圖G=(V,E)的區間值模糊圖.記圖G上的區間值模糊圖的集合為IF(G).

對于G1=(A1,B1),G2=(A2,B2)∈IF(G),定義運算如下:

G1∨G2=(A1∨A2,B1∨B2),

其中?x∈V,yz∈E,(A1∨A2)(x)=A1(x)∨A2(x),(B1∨B2)(yz)=B1(yz)∨B2(yz).

G1∧G2=(A1∧A2,B1∧B2),

其中,?x∈V,yz∈E,(A1∧A2)(x)=A1(x)∧A2(x),(B1∧B2)(yz)=B1(yz)∧B2(yz).

定理1.4[12]設G=(V,E)是1個圖,G=(A,B)是G上的區間值模糊圖當且僅當對于任意的λ∈I,Gλ=(Aλ,Bλ)是圖,其中

Aλ={x∈V|A(x)≥λ},

Bλ={xy∈E|B(xy)≥λ}.

2 區間值模糊圖的劃分區間及圖表示

類似于模糊集的分解定理與表示定理,區間值模糊圖可用其水平截集—子圖集來表示.由于[0,1]上的區間集是偏序集,可以將其分解為素元或余素元,從而得到相應于區間值模糊圖的[0,1]上區間集的劃分,區間值模糊圖用圖集表示,且圖集與[0,1]上區間集的劃分有相同的鏈式結構.反之，劃分有相同序結構的圖集和[0,1]上區間集,可以確定一個區間值模糊圖.

定理2.1設G=(A,B)是G=(V,E)上的區間素元值模糊圖(即?x∈V,yz∈E,A(x),B(yz)∈Pr(I)),則有

Gλ∧μ=Gλ∪Gμ, ?λ,μ∈I,

證明只需證明Aλ∧μ=Aλ∪Aμ,Bλ∧μ=Bλ∪Bμ對λ,μ∈I成立.?λ,μ∈I,若Aλ∧μ=Φ,結論是顯然的.否則?x∈V且x∈Aλ∧μ,有A(x)≥λ∧μ,由A(x)∈Pr(I),則A(x)≥λ或者A(x)≥μ,于是x∈Aλ或者x∈Aμ,即x∈Aλ∪Aμ.另一方面,若x∈Aλ∪Aμ,有A(x)≥λ或者A(x)≥μ,則A(x)≥λ∧μ,也就有x∈Aλ∧μ.

類似地,可以得到Bλ∧μ=Bλ∪Bμ.

定理2.2設G=(A,B)是G=(V,E)上的區間值模糊圖,則對λ,μ∈I,有

Gλ∨μ=Gλ∩Gμ.

證明只需證明Aλ∨μ=Aλ∩Aμ,Bλ∨μ=Bλ∩Bμ對λ,μ∈I成立.?x∈V且x∈Aλ∨μ,有A(x)≥λ∨μ,則A(x)≥λ且A(x)≥μ,即x∈Aλ且x∈Aμ,于是x∈Aλ∩Aμ.另一方面,對x∈Aλ∩Aμ,有A(x)≥λ且A(x)≥μ,即A(x)≥λ∨μ,于是

x∈Aλ∨μ.

類似地,可得到Bλ∨μ=Bλ∩Bμ.

?λ∈CPr(I),

類似地,可得

例2.4設G=(A,B)是G=(V,E)上的區間值模糊圖,其中

V={vi}，i=1,2,3,4,

E={v1v2,v2v3,v1v4,v1v3,v3v4},

將G分解為區間值模糊圖G1=(A1,B1)與G2=(A2,B2)的并,其中

于是

G[a,a]=(G1)[a,a]∪(G2)[a,a]=

G[0,b]=(G1)[0,b]∪(G2)[0,b]=

于是

Gλ=G[a,a]∩G[0,b]=

進一步,根據GI對I進行劃分,所得的劃分與GI是同構的.

設G=(A,B)是G=(V,E)上的區間值模糊圖.記H(G)={λ∈I|A(x)=λ或B(yz)=λ,x∈V,yz∈E}.I上的一個二維關系“≈”定義為:對于λ,μ∈I,λ≈μ當且僅當Gλ=Gμ,顯然“≈”是I上的一個等價關系.記λ≈={μ∈I|λ≈μ},則I/≈是I的商集.

性質2.5設G=(A,B)是G=(V,E)上的區間值模糊圖,λ,μ∈I,則λ≈μ當且僅當↑λ∩H(G)=↑μ∩H(G)(↑λ={h∈I|h≥λ}).

證明對λ,μ∈I,λ≈μ當且僅當Gλ=Gμ,即Aλ=Aμ,Bλ=Bμ,當且僅當對x∈V,yz∈E,有

A(x)≥λ?A(x)≥μ,B(yz)≥λ?B(yz)≥μ,

當且僅當{x∈V|A(x)∈↑λ}={x∈V|A(x)∈↑μ},{yz∈E|B(yz)∈↑λ}={yz∈E|B(yz)∈↑μ},當且僅當

↑λ∩H(G)=↑μ∩H(G).

由I中的≤可誘導I/≈的一種序關系:對λ,μ∈I,λ≈≤μ≈當且僅當↑μ∩H(G)?↑λ∩H(G).

性質2.6設G=(A,B)是G=(V,E)上的區間值模糊圖,則λ≈≤μ≈當且僅當Gμ?Gλ.

證明對λ,μ∈I,λ≈≤μ≈當且僅當↑μ∩H(G)?↑λ∩H(G),當且僅當

{x∈V|A(x)∈↑μ}?{x∈V|A(x)∈↑λ},

{yz∈E|B(yz)∈↑μ}?{yz∈E|B(yz)∈↑λ},

當且僅當Aμ?Aλ,Bμ?Bλ,也就是Gμ?Gλ.

性質2.7設G=(A,B)是G=(V,E)上的區間值模糊圖,則對x∈V,yz∈E,A(x)=∨[A(x)]≈,B(yz)=∨[B(yz)]≈.

證明?x∈V,λ∈[A(x)]≈,則A(x)≥λ.又A(x)∈[A(x)]≈得A(x)為[A(x)]≈的上確界.類似地,對yz∈E,B(yz)=∨[B(yz)]≈.

由此,對于例2.4中的區間值模糊集,可以得到它的規范表示:

反之,根據以上圖G=(V,E)的子圖集和區間級I的劃分,很容易得到圖G=(V,E)上的區間值模糊圖.

性質2.10設{Gi=(Vi,Ei)}(i=1,2,…,m)為圖的子圖集,{[ai,bi]≈}(i=1,2,…,m)為I的商集,且滿足Gi?Gj當且僅當[ai,bi]≈≥[aj,bj]≈,那么G=(A,B)是G=(V,E)上的區間值模糊圖,其中,A(x)=∨{[ai,bi]≈|x∈Vi},B(yz)=∨{[ai,bi]≈|yz∈Ei}.

3 區間值模糊圖與圖塔

定義3.2對任意的f,g∈T(G),規定T(G)的運算如下:

(f∪g)(λ)=f(λ)∪g(λ),λ∈I,

(f∩g)(λ)=f(λ)∩g(λ),λ∈I.

定理3.4設f∈T(G),則?λ1,λ2∈I,λ1≤λ2,有f(λ1)?f(λ2).

所以f(λ1)?f(λ2).

定理3.5設f∈T(G),G=(V,E).令

1) 對λ1,λ2∈I,λ1<λ2,有lf(λ2)?uf(λ1);

2) 對任意的λ∈I,uf(λ)?f(λ)?lf(λ);

證明只需證lf(λ)=lf′(λ)等價于uf(λ)=uf′(λ).

1) 首先證明σ是雙射.

uf(λ)=uf′(λ)?f′(λ)?lf′(λ)=lf(λ),

且uf(λ)?f(λ)?lf(λ),于是?x∈V,有

2) 其次證明σ是同態的.

致謝隴東學院博士科研啟動資金資助項目(XYBY05)和隴東學院青年科技創新項目(XYZK1708)對本文給予了資助,謹致謝意.