资源描述：
《系统的核与核度理论_子核与核度的计算》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第14卷第3期系统工程学报Vol.14No.31999年9月JOURNALOFSYSTEMSENGINEERINGSep.1999①系统的核与核度理论(Ï)——子核与核度的计算②许进(西安电子科技大学电子工程研究所,西安710071)摘要连通非平凡图G的核度,记作h(G),定义为h(G)=max{X(G-S)-ûSû;S∈C(G)},其中3C(G)表示图G的全体点割集构成的集合,X(G-S)表示G-S的连通分支数.若S∈C(G)且满足h(G)3)-ûS33=X(G-Sû,则称S是图G的一个核.本文引入子
2、核的概念并讨论了子核的一些基本性质;在子核概念及有关结果的基础上给出了一般连通非平凡图G的核度的计算公式.关键词:核度,子核,递推公式分类号:N94THECOREANDCORITIVITYOFASYSTEM(Ï)—SUBCOREANDANALGORITHMOFCORITIVITYXuJin(ElectronicEngineeringResearchInstitute,XidianUniversity,Xi′an710071)AbstractLetGbeanon2trivialconnectedgraph
3、.ThecoritivityofG-S,denotedbyh(G),isdefinedash(G)=max{X(G-S)-ûSû;S∈C(G)},whereX(G-S)denotesthe3numberofcomponentsofG-S,C(G)denotesthecollectionofvertex2cutsetsinG.S∈C33(G)iscalledacoreofGifitsatisfiesh(G)=X(G-S)-ûSû.Thenotionofsubcoreisintroduedandsomeba
4、sicpropertiesarestudiedinthispaper.Basedonsomeresultsofsubcore,therecursionformulaofcoritivityofarbitrarynon2trivialconnectedgraphisgiveninthispaper.Keywords:coritivity,subcore,recurisonformula0引言述图的连通性的局部性的工具,刻划所谓图的脆弱性上(graphvulnerability).一个刻划图的新的[4210
5、]近年来,图的连通性问题已在通讯网络,电路不变量,称为图G的核度h(G)被提出.业已设计,系统工程,可靠性分析以及人工神经网络等发现,h(G)是一种从整体上刻划图的连通性的新许多邻域的研究中扮演着很重要的角色.90年代工具、新方法和新途径.为了方便,现将系统的核以前,关于图的连通性方面研究的主要工具是点与核度概念引入如下:连通度k(G)(通常简称为连通度)及边连通度仔细观察和思考现实世界中所存在的系统,K(G),这两个图的不变量为图的连通性的研究与无论是自然界还是现实社会,不难发现,几乎每一应用做出了很
6、大的贡献.然而,它们仅仅是用来描个系统,总有一个或者多个主要素占有很重要的①国家自然科学基金资助项目(69602008,69571023).②男,博士,教授,male,Dr.,prof.本文1998年4月28日收到.—244—系统工程学报第14卷第3期位置,如果去掉它们,这个系统将会在诸如结构、本文所言之图皆指无环无重边的有限简单稳定性,甚至在生存上将受到很大的影响.如小麦图.通常用V(G)和E(G)分别表示图G的顶点集花的雄蕊和雌蕊,人的大脑(对人而言),一箱蜜蜂与边集.称顶点数ûV(G)û为图G的阶
7、数,设v∈中的蜂王等.为了对上述现象进行深入的讨论,引V(G),v的邻域是指在图G中与顶点v相邻的顶入系统核与核度的概念,称上述的雄蕊和雌蕊为点构成的图G的顶点子集,并记作N(v).图G的小麦花这个系统的核,类似地,大脑称为人的核,顶点v的度数记作dG(v),是指在图G中与顶点v蜂王是该箱蜜蜂中的核.相关联的边数,自然,图G是简单图时有dG(v)=为了对上述现象进行深入细致的研究,下面ûN(v)û.在不致混淆的情况下,用d(v)代替严格地引入系统的核度与核的概念.dG(v).$(G)和D(G)分别表示图
8、G的最大度和最设X是一个系统,其主要素为x1,x2,⋯,xn.小度.有关系统工程方面的术语及符号见文献如果xi与xj之间有关系且为互相的,就用xixj表[1],图论方面的术语见文献[2].示.由此可构造一个无向网络图G,其顶点集为V(G)={x1,x2,⋯,xn},边集E(G)={xixjû其中1子核的基本概念与基本理论xi与xj在X中有关系}.注意,xi与xj有关系是广3义的概念,可能是相互认识,亦可能是某两个零件对于一个给定的非平凡的连
