资源描述:
《(V,R)-semigroup, (V,R)-language, interconnection network and graph theory》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、(V,R)-semigroup,(V,R)-language,interconnectionnetworkandgraphtheoryHaizhongShiCollegeofMathematicsandStatistics,NorthwestNormalUniversity,Lanzhou,GansuProvince,730070,ChinaProblemsShouldtherebesomeconnectionsamong(V,R)-semigoup[1],(V,R)-language[1],interconnection
2、network[2]andgraphtheory[3,4,5]?Thatis,Shouldtherebesomeconnectionsamong(V,R)-semigoup,(V,R)-language,interconnectionnetwork[2],Pseudosimplegraph[3](pseudostrictdigaph[3],hypergraph[4]orrandomgraph[5])?Iftheredoexistcertainconnections,whataretheseconnections?Could
3、weconstructsomeinterchangebridgesamongthesefourfieldssothattheycanbetoolscomutativelyandbringnewresults?Concepts1(V,R)-semigroupFrom1984,HaizongShi,totestsolvingreconstructionconjecture(Everysimplegraphonatleastthreeverticesisreconstructible)[4],to1989,proposedtwo
4、concepts---graphsemigroupanddigraphsemigroup[7],andafter24years,in2013,proposedtwoconcepts---(V,R)-semigroupand(V,R)-language[1].Wedescribetheseconceptsasfollows.Definition1Visanalphabet.FVisafreesemigrouponV[6].LetRbeasubsetofFV,thenF∗RF∗isanideaofF.LetI=F∗RF∗,th
5、enρ=(I×I)∪1beaReescongruence.VVVRVVIRRRFVThenquotientsemigroupFV/ρIRiscalledasa(V,R)-semigroup.TheelementofFVisalsocalledasword.Thestudyofthecombinatorialpropertiesofwordsiscalledasthecombinationofwords[8].1.1Graphsemigroup2Definition1.1[7]LetEbesubsetofVwiththatu
6、v∈Eiffvu∈E.Indefinition1,letR=E=V2−E,then(V,R)-semigroupF/ρiscalledasagraphsemigroupwithVIRvertexsetVandedgesetE,denotedbyFV/ρE,simplycalledgraphsemigroup.1.2DigraphsemigroupDefinition1.2[7]LetAbesubsetofV2.Indefinition1,letR=A=V2−A,then(V,R)-semigroupFV/ρIRiscall
7、edasadigraphsemigroupwithvertexsetVandarcsetA,denotedbyFV/ρA,simplycalleddigraphsemigroup.1.3Hypergraphsemigroup[1]LetX={x1,x2,…,xn},beafiniteset.{E1,E2,…,Em}isasubsetvarietyonXsuchthat(1)Ei≠∅,i=1,2,…,n;(2)mE=X;i=1i(3)Ei⊂Ej⟹i=j;Wherewedonotconsideracnode,thatis,if
8、
9、Ei
10、=1thenEirepresentaloop,i.eset
11、Ei
12、=2.E1,E2,…,EmcanrewriteasE11,…,E1i1,E21,…,E2i2,…,Er1,…,Erir,where0≤kj≤i≤m,1≤j≤r≤n,ri=m,andonlyifi=0thenk=0.jj=1jjjL