模糊團的一個注記

孫峰，屈小兵，汪天飛，張之鶴

模糊團的一個注記

孫峰1，2，屈小兵1，汪天飛1，張之鶴1

(1.樂山師范學院數學與信息科學學院，四川樂山614004;2.四川師范大學數學與軟件科學學院，四川成都610066)

模糊圖論中的模糊團推廣圖論中的團，在圖論中，團導出的子圖是完全的，然而根據現有模糊團的定義，模糊團導出的模糊子圖不一定是完全的.這篇注記修正模糊團的概念，以保證其導出的模糊子圖是完全的，并給出模糊團和極大模糊團的刻畫.

模糊圖;模糊團;完全性

圖論中的圖由若干給定的點及連接2點的邊構成，是對象集合及對象與對象之間關系的數學表示.在圖論中，這些對象以及對象間的關系都是分明的，然而在實際問題中，對象或對象間的關系往往存在不清晰、不確定的情形，因此需要模糊化的數學表示.自L.A.Zadeh［1］提出模糊集的概念以來，模糊集及其理論得到長足發展［2－3］.基于模糊集的定義，J.N.Mordeson［4］提出了模糊圖的概念.隨后研究者從理論和應用方面，不斷豐富模糊圖論.至今，模糊圖論已經取得豐碩的成果［5］.應用方面，模糊圖在信息科學［6］、神經網絡［7－8］等方面有著重要的應用.理論方面，一些經典的圖論概念及定理被推廣到模糊圖中［9－11］.眾所周知，圖論中的團是一個兩兩之間有邊的頂點集合，即是說團導出的圖是完全的.然而根據P.S.Nair等［12］對模糊團的定義，模糊團所導出的模糊子圖并不是完全的(見例2.1).在這篇注記中，對模糊團的概念作了修正，以保證其導出的模糊子圖是完全的.此外，還定義了模糊極大團和最大團，并討論了它們的性質及刻畫.

1 預備知識

首先，介紹一些符號與定義.對矩陣A，記其轉置為AT，其第i行第j列的元素為Aij.令N={1，2，…，n}.記|X|為集合X的基數，對于任意2個集合X與Y，記X－Y={x∈X:x?Y}，當Y={y}時，X－Y表示X－y.對區間［0，1］上的x、y，x∨y=max{x，y}，x∧y=min{x，y}.

定義1.1［13］設G=(V，E)為無向圖，其中V是頂點的集合，E是邊的集合，記連接頂點vi與vj的邊為(vi，vj).頂點vi與vj相鄰當且僅當(vi，vj)∈E.若圖G=(V，E)中的任何2個頂點都是相鄰的，則稱G是完全圖.圖G'=(V'，E')稱為圖G=(V，E)的子圖，若V'?V，E'?E.以圖G的頂點集V的非空子集V1為頂點集，以兩端點均在V1中的所有邊為邊集的G的子圖稱為由V1導出的子圖.互不相同的頂點和邊交替出現的序列v1，(v1，v2)，v2，(v2，v3)，v3，…，(vn－1，vn)，vn(簡記為v1，v2，…，vn)稱為從v1到vn的路徑，路徑中的邊數稱為路徑的長度.起止頂點相同且長度大于等于3的路徑稱為圈.

定義1.2［13］設G=(V，E)為無向圖，C為V的非空子集，若C中頂點兩兩相鄰，則稱C為團.若一個團不是其它任何團的子集，則稱這個團是極大團.若一個團滿足基數最大，則稱這個團為最大團.

由定義1.2可知，圖論中的團導出的子圖是完全的.在一些文獻中，研究者將完全圖與團視為等同，在此區別對待二者.

記論域X上的所有模糊集合為F(X)={S:X→［0，1］}，X×Y上的所有模糊關系為F(X×Y)={R:X ×Y→［0，1］}.

定義1.3［5］設V是一個非空集合，δ∈F(V)，μ∈F(V×V)，若對任何x，y∈V有μ(x，y)≤δ(x)∧δ(y)，則稱FG=(V，δ，μ)為模糊圖，并稱δ為FG的模糊頂點集合，μ為FG的模糊邊的集合.

在本文中，所有涉及的模糊圖FG=(V，δ，μ)均是無向的，即μ是對稱的，且對任何x∈V有μ(x，x)=0.簡便起見，記FG=(V，δ，μ)=(δ，μ)(除非特別指明，V代指n元集).記模糊圖FG的底圖為FG*=(δ*，μ*)，其中δ*={x∈V:δ(x)＞0}，μ*= {(x，y)∈V×V:μ(x，y)＞0}.對任意t∈［0，1］，定義模糊圖FG=(δ，μ)的t－截集為FGt=(δt，μt)，其中δt={x∈V:δ(x)≥t}，μt={(x，y)∈V×V:μ(x，y)≥t}.

定義1.4［5］稱模糊圖FH=(ρ，ν)為模糊圖FG=(δ，μ)的模糊子圖，若ρ≤δ且ν≤μ.進一步，若ρ=δ，則稱FH是FG=(δ，μ)的生成子圖.

定義1.5［5］稱模糊圖FH=(P，ρ，ν)為模糊圖FG=(V，δ，μ)由P導出的模糊子圖，若P?V，ρ(x) =δ(x)，?x∈P且ν(x，y)=μ(x，y)，?x，y∈P.稱FG的模糊子圖FH=(V，ρ，ν)為由ρ導出的模糊子圖，若FH是以ρ為模糊頂點集合的極大模糊子圖，即ν(x，y)=ρ(x)∧ρ(y)∧μ(x，y)，?x，y∈V.

定義1.6［5］模糊圖FG=(δ，μ)中的路徑P是由不同的頂點v1，v2，…，vn(n≥2)構成的序列且滿足μ(vi，vi+1)＞0.路徑中的邊數稱為路徑的長度.FH =(ρ，ν)稱為圈當且僅當(ρ*，ν*)是圈.FH=(ρ，ν)稱為模糊圈當且僅當FH是圈且不存在唯一的(x，y)∈μ*使得μ(x，y)=∧{μ(u，v):(u，v)∈μ*}.

定義1.7［14］設FG=(δ，μ)為模糊圖，若對任意(x，y)∈μ*有μ(x，y)=δ(x)∧δ(y)，則稱FG是強的;若對任何x，y∈δ*(x≠y)有μ(x，y)=δ(x)∧δ(y)，則稱FG是完全的.

顯然，模糊完全圖是強的，但反之不然.

定義1.8［12］設FH=(ρ，ν)為模糊圖FG=(δ，μ)的模糊子圖，若FH*是團且FH中的每一個圈都是模糊圈，則稱FH為模糊團.

P.S.Nair等［12］將模糊團視為模糊子圖，并給出了模糊團的如下刻畫.

引理1.1［12］模糊圖FG=(δ，μ)的模糊子圖FH=(ρ，ν)是模糊團當且僅當FH中的每一個長度為3的圈都是模糊圈.

定義1.9［15］設Q∈F(X×Y)，S∈F(Y×Z)，則∨－∧合成Q⊙S∈F(X×Z)定義為

2 模糊團的修正及其刻畫

圖論中的團導出的圖是完全的.然而根據定義1.8，模糊團所導出的模糊子圖(即模糊團本身)并不是完全的.

例2.1考慮V={v1，v2，v3，v4}上的模糊圖FG =(δ，μ)，其中δ(v1)=δ(v2)=δ(v3)=δ(v4)=1，μ(v1，v2)=0.5，μ(v1，v3)=0.8，μ(v1，v4)=0.8，μ(v2，v3)=0.5，μ(v2，v4)=0.5，μ(v3，v4)=0.7，如圖1所示.

考慮如圖2所示的模糊子圖FH=(ρ，ν).

從引理1.1可知，FH是模糊團，但是0.8= ν(v1，v3)≠ρ(v1)∧ρ(v3)=1，即FH是不完全的.

下面對模糊團的概念進行修正.

定義2.1設FG=(δ，μ)為模糊圖，ρ為δ的非空子集，若由ρ導出的模糊子圖是完全的，則稱ρ為模糊團.

注2.1P.S.Nair等［12］定義的模糊團本質上是模糊圖，而定義2.1中的模糊團是模糊集，即模糊圖頂點集合的子集.

例2.2考慮例2.1中的模糊圖FG=(δ，μ)，容易驗證ρ={ρ(v1)=0.8，ρ(v2)=0.5，ρ(v3)=0.8，ρ (v4)=0.7}是FG的模糊團，其導出的模糊子圖FH =(ρ，ν)見圖3.

為避免定義1.8與定義2.1混淆，將定義1.8中的模糊團稱為NC－模糊團.下面討論NC－模糊團，模糊團及模糊完全圖之間的關系.

定理2.1模糊完全圖是NC－模糊團.

證明令FH=(ρ，ν)為模糊完全圖.設abca(a，b，c∈ρ*)為FH中長度為3的圈，因FH是完全的，則有ν(a，b)=ρ(a)∧ρ(b)，ν(b，c)=ρ(b)∧ρ(c)，ν(a，c)=ρ(a)∧ρ(c).從而ν(a，b)∧ν(b，c)∧ν(a，c)=ρ(a)∧ρ(b)∧ρ(c).不失一般性，假設ρ(a)=ρ(a)∧ρ(b)∧ρ(c)，于是ν(a，b)=ν(a，c)=ρ(a)，即abca是模糊圈.由引理1.1知FH是NC－模糊團.

推論2.1模糊團導出的模糊子圖是NC－模糊團.模糊團導出的模糊子圖是完全的，從而是NC－模糊團.

定理2.2強NC－模糊團是完全的.

證明令FH=(ρ，ν)為強NC－模糊團.顯然FH*是團，則對任意a，b∈ρ*，有(a，b)∈ν*.因FH是強的，故有ν(a，b)=ρ(a)∧ρ(b).從而ν(a，b)= ρ(a)∧ρ(b)，?a，b∈ρ*，即FH是完全的.

注2.2由定理2.2知，強NC－模糊團的頂點集合是模糊團.

定理2.3設FG=(δ，μ)為模糊圖，ρ為δ的非空子集.ρ是模糊團當且僅當對任意x，y∈ρ*(x≠y)有ρ(x)∧ρ(y)≤μ(x，y).

證明設ρ是FG的模糊團，FH=(ρ，ν)是由ρ導出的模糊子圖.顯然，FH是完全的.從而由定義1.5與1.7，有ρ(x)∧ρ(y)=ν(x，y)=ρ(x)∧ρ(y)∧μ

(x，y)≤μ(x，y)，?x，y∈ρ*.

反之，設ρ是δ的子集且滿足ρ(x)∧ρ(y)≤μ(x，y)，?x，y∈ρ*，x≠y.令FH=(ρ，ν)為由ρ導出的模糊子圖.由定義1.5知，對任意x，y∈ρ*有ν(x，y)=ρ(x)∧ρ(y)∧μ(x，y)，則從假設ρ(x)∧ρ(y)≤μ(x，y)可知ν(x，y)=ρ(x)∧ρ(y).故FH是完全的，即ρ是模糊團.

推論2.2設ρ是模糊圖FG=(δ，μ)的模糊團，則對任何t∈(0，1］，ρt是圖FGt中的團.

證明設ρ是模糊圖FG=(δ，μ)的模糊團.由定理2.3知ρ(x)∧ρ(y)≤μ(x，y)，?x，y∈ρ*，x≠y.從而對任意2個頂點x，y∈ρt有μ(x，y)≥ρ(x)∧ρ(y)≥t，即(x，y)∈μt，故ρt是圖FGt中的團.

推論2.3設ρ是模糊圖FG=(δ，μ)的模糊團，則ρ的任意非空子集Q是FG的模糊團.

證明設ρ是模糊圖FG=(δ，μ)的模糊團，Q為ρ的任意非空子集，則對任何x∈V有Q(x)≤ρ(x)，由定理2.3知結論成立.

對于模糊圖FG=(δ，μ)，定義n×n的模糊矩陣MFG為

對于δ的非空子集ρ，定義n×1的模糊向量Vρ，

記XFG={X=(xi)，xi∈［0，1］:X⊙XT≤MFG}.

定理2.4若ρ是模糊圖FG=(δ，μ)的模糊團，則Vρ∈XFG.反過來，對任意X=(xi)∈XFG，ρ(ρ(vi)=xi，?i∈N)是模糊團.

證明設ρ是FG的模糊團，則由定理2.3知，對任何i，j∈N(i≠j)有(Vρ⊙)ij=(Vρ)i∧(Vρ)j=ρ(vi)∧ρ(vj)≤μ(vi，vj)=(MFG)ij，對任何i∈N有(Vρ⊙)ii=(Vρ)i∧(Vρ)i=ρ(vi)≤δ(vi)= (MFG)ii.從而Vρ∈XFG.

反過來，對任何X=(xi)∈XFG，構造ρ使得ρ(vi)=xi，?i∈N.因為對任何i∈N，有ρ(vi)=xi≤(MFG)ii=δ(vi)，所以ρ≤δ.進一步，對任何i，j∈N(i≠j)，有ρ(vi)∧ρ(vj)=xi∧xj≤(MFG)ij=μ(vi，vj)，從而由定理2.3知ρ是FG的模糊團.

推論2.3說明模糊團的任意非空子集仍是模糊團.自然地，會考慮最大模糊團和極大模糊團.

定義2.2設ρ是模糊圖FG=(δ，μ)的模糊團，若不存在模糊團σ使得ρ＜σ，則稱ρ是極大的.進一步，稱具有最大基數|ρ*|的極大模糊團ρ為最大模糊團.

例2.3考慮如圖4所示的模糊圖FG=(δ，μ).

不難驗證σ={σ(v1)=0.7，σ(v2)=0.3，σ(v3)= 0.4，σ(v4)=0.5}，Q={Q(v1)=0.7，Q(v2)=0.5，Q (v3)=0.4，Q(v4)=0.3}和ρ={ρ(v1)=0.4，ρ(v2)=0.3，ρ(v3)=0.8，ρ(v4)=0.4}都是FG的模糊團，并且都是最大的，而模糊團φ={φ(v1)=0.7，φ(v3)=0.4，φ (v4)=0.5}僅是極大的，而非最大的.

基于定理2.4，得到極大模糊團的如下刻畫:

定理2.5設ρ是模糊圖FG=(δ，μ)中δ的非空子集，ρ是極大模糊團當且僅當Vρ是XFG的極大元.

證明由定理2.4知ρ是模糊團當且僅當Vρ∈XFG.進一步，若ρ是極大的，則Vρ是XFG的極大元，反之亦然.

定理2.6設ρ是FG=(δ，μ)的極大模糊團，則

證明設ρ是FG=(δ，μ)的極大模糊團.由定理2.3知，ρ(x)∧ρ(y)≤μ(x，y)，?x，y∈ρ*，從而有.下證ρ(vk)=μ(vi，vj).現設ρ(vk)＜μ(vi，vj)，定義模糊集σ使得除σ(vk)=μ(vi，vj)外有σ=ρ.顯然σ＞ρ.此外，對任何z∈ρ*有σ(z)≤δ(vk)，即σ≤δ.下證σ是模糊團，即σ(y)∧σ(z)≤μ(y，z)，?y，z∈ρ*.當vk?{y，z}時，有σ (y)∧σ(z)=ρ(y)∧ρ(z)≤μ(y，z).若vk∈{y，z}，不失一般性，假設vk=z，則σ(y)∧σ(z)=ρ(y)∧μ.由此可知σ是模糊團，這與ρ的極大性矛盾.從而

推論2.4設ρ是FG=(δ，μ)的極大模糊團，FH=(ρ，μ)是由ρ導出的模糊子圖且=μ(vi，vj)，則μ(vi，vj)=μ(vi，vj).

證明顯然ν(vi，vj)≤μ(vi，vj).若ν(vi，vj)＜μ (vi，vj)，則ρ(vi)∧ρ(vj)=ν(vi，vj)＜μ(vi，vj).從而這與定理2.6相悖，于是ν(vi，vj)=μ(vi，vj).

定理2.7設ρ是FG=(δ，μ)的極大模糊團，則至少存在一x∈ρ*使得ρ(x)=δ(x).

證明設ρ是FG=(δ，μ)的極大模糊團.顯然，ρ(x)≤δ(x)，?x∈ρ*.假設對任何x∈ρ*有ρ(x)＜δ，則有ρ*=V1∪V2.一方面，若V1=ρ*，任取x0∈V1構造模糊集σ使得當x≠x0時σ(x)=ρ(x)且σ(x0)=δ(x0)，則知σ＞ρ.進一步，當x∈V1－x0時，有σ(x)∧σ(x0)=ρ(x)∧σ(x，x0);對任何x，y∈V1－x0有σ(x)∧σ(y)=ρ(x)∧ρ(y)≤μ(x，y)，故由定理2.3知σ是模糊團.而σ＞ρ，這與ρ是極大的矛盾.另一方面，若V1≠ρ*，即V2≠?，取x0∈V2使得ρ(x0)=max{ρ(x):x∈V2}，構造模糊集Q使得除Q(x0)=δ(x0)外有Q(x)=ρ (x)，則有Q＞ρ.下證Q是模糊團.當x∈V1時，有Q (x)∧Q(x0)=ρ(x)∧δ(x0)≤≤μ(x，x0)∧δ(x0)≤μ(x，x0);當x∈V2時，有Q (x)∧Q(x0)=ρ(x)∧δ(x0)=ρ(x)=ρ(x)∧ρ(x0)≤μ(x，x0);當x，y∈ρ*－x0時，有Q(x)∧Q(y)= ρ(x)∧ρ(y)≤μ(x，y)，從而由定理2.3知，Q是模糊團且Q＞ρ，矛盾!所以ρ(x)＜δ(x)對所有x∈ρ*并不成立.于是至少存在一x∈ρ*使得ρ(x)=δ(x).

在這里我們指出定理2.6、2.7和推論2.4的逆命題并不成立，見例2.4.

例2.4考慮例2.3中的模糊圖FG=(δ，μ).易知φ={φ(v1)=0.7，φ(v2)=0.3，φ(v3)=0.3，φ(v4)= 0.3}是模糊團.設FH=(φ，ν)為由φ導出的模糊子圖.不難發現μ(y，z)=μ(v2，v3)，ν(v2，v3)=μ(v2，v3)，φ(v1)=δ (v1).然而，σ={σ(v1)=0.7，σ(v2)=0.3，σ(v3)=0.4，σ(v4)=0.5}和Q={Q(v1)=0.7，Q(v2)=0.5，Q(v3)=0.4，Q(v4)=0.3}均為比φ大的模糊團，也即是說φ并非極大的.

致謝樂山師范學院科研項目(Z1402)對本文給予了資助，謹致謝意.

［1］ZADEH L A.Fuzzy sets［J］.Information and Control，1965，8:338－353.

［2］ZIMMERMANN H J.Fuzzy Set Theory and Its Applications［M］.Berlin:Springer－Verlag，2001.

［3］莫智文，舒蘭，許彪.模糊數學理論及其應用評述［J］.四川師范大學學報(自然科學版)，1998，21(3):330－335.

［4］MORDESON J N.Fuzzy graphs［C］//Fuzzy Sets and their Applications to Cognitive and Decision Processes.New York:Academic Press，1975:77－95.

［5］MORDESON J N，NAIRP S.Fuzzy Graphs and Fuzzy Hypergraphs［M］.Berlin:Springer－Verlag，2000.

［6］GOMEZ D，MONTERO J，YANEZ J.A coloring fuzzy graph approach for image classification［J］.Information Sciences，2006，176:3645－3657.

［7］BHATTACHARYYA M，BANDYOPADHYAY S.Solving maximum fuzzy clique problem with neural networks and its applications［J］.Memetic Computing，2009，1:281－290.

［8］SUNITHA M S，KJUMAR A V.Fuzzy graphs in fuzzy neural networks［J］.Proyecciones J Mathematics，2009，28:239－252.

［9］MATHEW S，SUNITHA M S.Types of arcs in a fuzzy graph［J］.Information Sciences，2009，179:1760－1768.

［10］MATHEW S，SUNITHA M S.Node connectivity and arc connectivity of a fuzzy graph［J］.Information Sciences，2010，180:519－531.

［11］MATHEW S，SUNITHA M S.Menger’s theorem for fuzzy graphs［J］.Information Sciences，2013，222:717－726.

［12］NAIR P S，CHENG S C.Cliques and fuzzy cliques in fuzzy graphs［C］//Joint 9th IFSA World Congress and 20th NAFIPS International Conference，2001，4:2277－2280.

［13］WEST D B.Introduction to Graph Theory［M］.Upper Saddle River:Prentice Hall，2001.

［14］SUNITHA M S，KUMAR A V.Complements of fuzzy graphs［J］.Indian J Pure Appl Math，2002，33:1451－1464.

［15］NOLA A D，SESSA S，PEDRYCZ W，et al.Fuzzy Relation Equations and Their Applications to Knowledge Engineering［M］.Boston:Kluwer Academic Publishers，1989.

A Note on Fuzzy Cliques

SUN Feng1，2，QU Xiaobing1，WANG Tianfei1，ZHANG Zhihe1
(1.College of Mathematics and Information Science，Leshan Normal University，Leshan 614004，Sichuan; 2.College of Mathematics and Software Science，Sichuan Normal University，Chengdu 610066，Sichuan)

Fuzzy cliques in fuzzy graphs generalize cliques in graphs.In graph theory，a subgraph induced by a clique is complete.However，according to the existing definition of fuzzy cliques，the fuzzy subgraph induced by a fuzzy clique may not be complete.In this note，we modify the definition of a fuzzy clique so that the fuzzy subgraph induced by each fuzzy clique is complete.Then，fuzzy cliques and maximal fuzzy cliques are characterized.

fuzzy graphs;fuzzy cliques;completeness

O159

A

1001－8395(2016)03－0309－05

10.3969/j.issn.1001－8395.2016.03.001

(編輯鄭月蓉)

2015－08－11

四川省教育廳科研項目(16ZB0297和16TD0029)

孫峰(1985—)，男，博士生，主要從事模糊關系、模糊算子、格上關系方程理論等研究，E－mail:sunfeng1005@163.com

2010 MSC:03E72;05C72