r-正則模糊圖的運算及其性質(zhì)

更芷拉毛，索南仁欠

(1.青海師范大學 數(shù)學與統(tǒng)計學院，青海 西寧 810016；2.青海師范大學 研究生院，青海 西寧 810008)

基于模糊集理論，Rosenfeld于1975年提出了模糊圖，建立了模糊圖的理論結(jié)構(gòu).隨后許多學者對模糊圖進行了深入細致的研究，定義了模糊圖的強積、直積和字典乘積等運算,并總結(jié)出了模糊圖乘積運算相關(guān)的分解定理和同構(gòu)定理.本文將定義r-正則模糊圖的交、并、補、笛卡爾積、直積、強乘積、字典乘積運算，并探討r-正則模糊圖在以上運算下是否滿足封閉性等相關(guān)的性質(zhì).

1 預(yù)備知識

定義1.1[1]對于任意給定的集合V，在V×V-{(x，x)|x∈V}上定義等價關(guān)系～如下：

(x1，y1)～(x2，y2)?(x1，y1)=(x2，y2)或者(x1，y1)=(y2，x2).

定義1.2[1]稱任意映射A：V→[0，1]為V上的模糊集.suppA={x∈V|A(x)>0}(稱為A的承載集)，rangA={A(x)|x∈V}(稱為A的值域).

定義1.4[3]模糊圖是一個有序三元組G=(G*，σ，μ)(更多時候為了方便G*略去不寫)，其中G*=(V，E)是一個無向簡單圖，稱為基圖.σ：V→(0，1]，μ：E→(0，1]，且?e∈E，μ(e)≤σ(u)∧σ(v)，這里u，v是e的端點.

定義1.5[4]若X的兩個模糊集μ和τ滿足μ(x)≤τ(x)(?x∈X)，則記μ≤τ.若兩個模糊圖H=(σ1，μ1)和G=(σ，μ)滿足σ1≤σ和μ1≤μ，則稱H是G的偏模糊子圖.

定義1.8[6]模糊圖G=(σ，μ)中點u的度數(shù)(degree)為dG(u)=∑uv∈Eμ(uv)(?u∈V).

定義1.9[7]設(shè)G=(σ，μ)是以圖G*=(V，E)為基圖的一個模糊圖，如果dG(v)=r(?v∈V，r>0)，即G中所有頂點的度數(shù)為r，則稱G為一個r-正則模糊圖(r-regularfuzzygraph).

定義1.10[8]設(shè)G=(σ，μ)是以圖G*=(V，E)為基圖的模糊圖，對?e∈E，μ(e)=σ(u)∧σ(v)(這里u，v是e的端點)，則稱G=(σ，μ)為強模糊圖.

2 主要結(jié)果

其中:σ1∩σ2：V1∩V2→(0，1]，μ1∩μ2：E1∩E2→(0，1].

具體定義為：

(σ1∩σ2)(v)=σ1(v)∧σ2(v)(?v∈V1∩V2)，

(μ1∩μ2)(e)=μ1(e)∧μ2(e)(?e∈E1∩E2).

證明：設(shè)Gi為ri-正則模糊圖(i=1，2)，μi(e)=Ci(?e∈Ei)，C1、C2為常數(shù).

設(shè)(G1∩G2)*為r-正則圖，則對于任意的v∈V1∩V2有

因此G1∩G2為正則模糊圖.

反之，設(shè)G1∩G2=(σ1∩σ2，μ1∩μ2)為正則模糊圖，V1∩V2中任取兩點v和w，有

dG1∩G2(v)=dG1∩G2(w)

?C1·d(G1∩G2)*(v)=C1·d(G1∩G2)*(w)

?d(G1∩G2)*(v)=d(G1∩G2)*(w)(當C1≤C2時)

或C2·d(G1∩G2)*(v)=C2·d(G1∩G2)*(w)

?d(G1∩G2)*(v)=d(G1∩G2)*(w)(當C1>C2時)

由于v和w在V1∩V2中的任一性，(G1∩G2)*為正則圖.

推論2.1 設(shè)G=(σ，μ)是以圖G*=(V，E)為基圖的模糊圖，若μ為常值函數(shù)且G*為正則圖，則G=(σ，μ)為正則模糊圖.

命題2.1 設(shè)Gi=(σi，μi)是ri-正則模糊圖(i=1，2).若G2為G1的偏模糊子圖，則G1∩G2為r2-正則模糊圖.

證明：G2為G1的偏模糊子圖，則σ1與σ2為非空結(jié)點集V上的兩個模糊集，且有σ2(x)≤σ1(x)(?x∈V)和μ2(xy)≤μ1(xy)(?x，y∈V)，則：

(σ1∩σ2)(x)=σ2(x)(?x∈V)，(μ1∩μ2)(xy)=μ2(xy)(?xy∈E)

故有G1∩G2=(σ1∩σ2，μ1∩μ2)=(σ2，μ2)=G2,因此G1∩G2為r2-正則模糊圖.

其中:σ1∪σ2：V1∪V2→(0，1]，μ1∪μ2：E1∪E2→(0，1].

具體定義為：

證明：設(shè)Gi為ri-正則模糊圖，μi(uv)=(μ1∪μ2)(uv)=C(?uv∈Ei，C為常數(shù)，i=1，2).

設(shè)(G1∪G2)*為r-正則圖，任取v∈V1∪V2，

因此G1∪G2為正則模糊圖.

反之，設(shè)G1∪G2為正則模糊圖，V1∪V2中任取兩點v和w，有

dG1∪G2(v)=dG1∪G2(w)

?C·d(G1∪G2)*(v)=C·d(G1∪G2)*(w)

?d(G1∪G2)*(v)=d(G1∪G2)*(w)

由于v和w在V1∪V2的任一性，(G1∪G2)*為正則圖.

命題2.2 設(shè)Gi=(σi，μi)是ri-正則模糊圖(i=1，2).若G2為G1的偏模糊子圖，則G1∪G2為r1-正則模糊圖.

證明：G2為G1的偏模糊子圖，則σ1與σ2為非空結(jié)點集V上的兩個模糊集，且有σ2(x)≤σ1(x)(?x∈V)和μ2(xy)≤μ1(xy)(?x，y∈V)，則:

(σ1∪σ2)(x)=σ1(x)(?x∈V)，(μ1∪μ2)(xy)=μ1(xy)(?xy∈E)，

故G1∪G2=(σ1∪σ2，μ1∪μ2)=(σ1，μ1)=G1

因此G1∪G2為r1-正則模糊圖.

具體定義為：

其中:

σ1×σ2：V1×V2→(0，1]，μ1×μ2：E→(0，1];

E={(x，x2)(x，y2)|x∈V1，x2y2∈E2}∪{(x1，z)(y1，z)|z∈V2，x1y1∈E1}.

具體定義為：

(σ1×σ2)(x1，x2)=σ1(x1)∧σ2(x2)(?(x1，x2)∈V1×V2);

(μ1×μ2)((x，x2)(x，y2))=σ1(x)∧μ2(x2y2)(?(x，x2)(x，y2)∈E);

(μ1×μ2)((x1，z)(y1，z))=σ2(z)∧μ1(x1y1)(?(x1，z)(y1，z)∈E).

證明：設(shè)σ1(v)=C1(?v∈V1)，σ2(u)=C2(?u∈V2)，C1、C2為常數(shù).|V1|=n，|V2|=m.

任取一點(x1，x2)∈V1×V2，

=∑x1=y1∈V1，x2y2∈E2σ1(x1)∧μ2(x2y2)+∑x2=y2∈V2，x1y1∈E1σ2(x2)∧μ1(x1y1)

當σ1≥σ2時，dG1×G2((x1，x2))=∑x2y2∈E2μ2(x2y2)+∑x1y1∈E1σ2(x2) (σ1=μ1，σ2=μ2)

=C2·(m-1)+C2·dG1*(x1)

=C2·(m+n-2).

當σ2>σ1時，dG1×G2((x1，x2))=∑x2y2∈E2σ1(x1)+∑x1y1∈E1μ1(x1y1) (σ1=μ1，σ2=μ2)

=C1·dG2*(x2)+C1·(n-1)

=C1·(m+n-2).

因此G1×G2為正則模糊圖.

其中：

σ1*σ2：V1×V2→(0，1]，μ1*μ2：E°→(0，1]；

E°={(x1，x2)(y1，y2)|x1y1∈E1，x2y2∈E2}.

具體定義為：

(σ1*σ2)(x1，x2)=σ1(x1)∧σ2(x2)(?(x1，x2)∈V1×V2，)

(μ1*μ2)((x1，x2)(y1，y2))=μ1(x1y1)∧μ2(x2y2)?(x1，x2)(y1，y2)∈E°.

證明：設(shè)(G1*G2)*為p-正則圖，μ1與μ2為常值函數(shù)，μ1(xy)=C1(?xy∈E1)，μ2(xy)=C2(?xy∈E2)，C1與C2為常數(shù).

任取(x1，x2)∈V1×V2，

=∑x1y1∈E1，x2y2∈E2μ1(x1y1)∧μ2(x2y2)

當μ1≥μ2時，dG1×G2((x1，x2))=∑(x1，x2)(y1，y2)∈E°μ2(x2y2)

=C2·d(G1*G2)*(x1，x2)=C2·p

當μ1<μ2時，dG1×G2((x1，x2))=∑(x1，x2)(y1，y2)∈E°μ1(x1y1)

=C1·d(G1*G2)*(x1，x2)=C1·p

因此G1*G2為正則模糊圖.

反之，設(shè)G1*G2為正則模糊圖，任取兩點(x1，x2)、(z1，z2)∈V1×V2，有

dG1*G2((x1，x2))=dG1*G2((z1，z2))

當μ1≥μ2時，有

?C2·d(G1*G2)*(x1，x2)=C2·d(G1*G2)*(z1，z2)

所以d(G1*G2)*(x1，x2)=d(G1*G2)*(z1，z2)

當μ1<μ2時，有

?C1·d(G1*G2)*(x1，x2)=C1·d(G1*G2)*(z1，z2)

所以d(G1*G2)*(x1，x2)=d(G1*G2)*(z1，z2)

由于(x1，x2)和(z1，z2)在V1×V2中的任一性，(G1*G2)*為正則圖.

其中:

σ1?σ2：V1×V2→(0，1]，μ1?μ2：E?！?0，1].

E。=E∪E°，E和E°分別在定義2.5和定義2.6中給出.

具體定義為：

(σ1?σ2)(x1，x2)=σ1(x1)∧σ2(x2)(?(x1，x2)∈V1×V2),

(μ1?μ2)((x，x2)(x，y2))=σ1(x)∧μ2(x2y2)(?(x，x2)(x，y2)∈E),

(μ1?μ2)((x1，z)(y1，z))=σ2(z)∧μ1(x1y1)(?(x1，z)(y1，z)∈E),

(μ1?μ2)((x1，x2)(y1，y2))=μ1(x1y1)∧μ2(x2y2)(?(x1，x2)(y1，y2)∈E°).

根據(jù)模糊圖的定義，對所有xy∈Ei，i=1，2有μi(xy)≤σi(x)∧σi(y)，因此μi≤maxσi和minμi≤σi，i=1，2.因為σ1≤μ2，maxσ1≤minμ2，因此μ1≤maxσ1≤minμ2≤σ2即σ2≥μ1.

證明：設(shè)(G1*G2)*為p-正則圖，Gi為ri-正則模糊圖(i=1，2)，μ1與μ2為常值函數(shù)，則μ1(xy)=C1(?xy∈E1)，μ2(xy)=C2(?xy∈E2)，C1與C2為常數(shù).

任取(x1，x2)∈V1×V2，

=∑(x1，x2)(y1，y2)∈E(μ1?μ2)((x1，x2)(y1，y2))+∑(x1，x2)(y1，y2)∈E°(μ1?μ2)((x1，x2)(y1，y2))

=∑x1=y1∈V1，x2y2∈E2σ1(x1)∧μ2(x2y2)+∑x2=y2∈V2，x1y1∈E1σ2(x2)∧μ1(x1y1)+∑x1y1∈E1，x2y2∈E2μ1(x1y1)∧μ2(x2y2)

當μ1≤μ2時，dG1?G2((x1，x2))=∑x2y2∈E2μ2(x2y2)+∑x1y1∈E1μ1(x1y1)+∑(x1，x2)(y1，y2)∈E°μ1(x1y1)

=dG2(x2)+dG1(x1)+C1·d(G1*G2)*(x1，x2)=r2+r1+C1·p;

當μ1>μ2時，dG1?G2((x1，x2))=∑x2y2∈E2μ2(x2y2)+∑x1y1∈E1μ1(x1y1)+∑(x1，x2)(y1，y2)∈E°μ2(x2y2)

=dG2(x2)+dG1(x1)+C2·d(G1*G2)*(x1，x2)=r2+r1+C2·p,

因此G1?G2為正則模糊圖.

反之，設(shè)G1?G2為正則模糊圖，則任取兩點(x1，x2)、(z1，z2)∈V1×V2，有

dG1?G2((x1，x2))=dG1?G2((z1，z2))

當μ1≤μ2時，有

dG2(x2)+dG1(x1)+C1·d(G1*G2)*(x1，x2)=dG2(z2)+dG1(z1)+C1·d(G1*G2)*(z1，z2)

r2+r1+C1·d(G1*G2)*(x1，x2)=r2+r1+C1·d(G1*G2)*(z1，z2)

d(G1*G2)*(x1，x2)=d(G1*G2)*(z1，z2)

當μ1>μ2時，有

dG2(x2)+dG1(x1)+C2·d(G1*G2)*(x1，x2)=dG2(z2)+dG1(z1)+C2·d(G1*G2)*(z1，z2)

r2+r1+C2·d(G1*G2)*(x1，x2)=r2+r1+C2·d(G1*G2)*(z1，z2)

d(G1*G2)*(x1，x2)=d(G1*G2)*(z1，z2)

由于(x1，x2)和(z1，z2)在V1×V2中的任一性，(G1*G2)*為正則圖.

定義2.8 設(shè)G=(σ，μ)是以圖G*=(V，E)為基圖的一個r-正則模糊圖.若?e∈E，μ(e)=σ(u)∧σ(v)，這里u，v是e的端點，則稱G=(σ，μ)為強r-正則模糊圖.

任取(x1，x2)∈V1×V2，

=∑(x1，x2)(y1，y2)∈E(μ1?μ2)((x1，x2)(y1，y2))

+∑(x1，x2)(y1，y2)∈E°(μ1?μ2)((x1，x2)(y1，y2))

=∑x1=y1∈V1，x2y2∈E2σ1(x1)∧μ2(x2y2)+∑x2=y2∈V2，x1y1∈E1σ2(x2)∧μ1(x1y1)

+∑x1y1∈E1，x2y2∈E2μ1(x1y1)∧μ2(x2y2)

=∑x2y2∈E2σ1(x1)+∑x1y1∈E1μ1(x1y1)+∑(x1，x2)(y1，y2)∈E°μ1(x1y1)

=C1·p+r1+C1·q

因此同理可得:G1?G2為正則模糊圖.

其中:

σ1°σ2：V1×V2→(0，1]，μ1°μ2：E?！菶′→(0，1].

E。在定義2.7中給出，E′={(x1，x2)(y1，y2)|x1y1∈E1，x2y2?E2},

具體定義為：

(σ1°σ2)(x1，x2)=(σ1?σ2)(x1，x2)(?(x1，x2)∈V1×V2)，

(μ1°μ2)((x1，y1)(x2，y2))=(μ1?μ2)((x1，y1)(x2，y2))(?(x1，y1)(x2，y2)∈E。)，

(μ1°μ2)((x1，y1)(x2，y2))=μ1(x1，x2)∧σ2(y1)∧σ2(y2)(?(x1，y1)(x2，y2)∈E′).

E′={(x1，x2)(y1，y2)|x1y1∈E1，x2y2?E2}=?.

所以G1°G2=G1?G2.