摘要
连通非平凡图 Ｇ 的核度，记作 ｈ（ Ｇ），定义为 ｈ（ Ｇ） ＝ ｍ ａｘ｛ω（ Ｇ － Ｓ） － ｜ Ｓ｜； Ｓ∈ Ｃ（ Ｇ）｝，其中 Ｃ（ Ｇ） 表示图 Ｇ的全体点割集构成的集合，ω（ Ｇ － Ｓ） 表示 Ｇ－ Ｓ的连通分支数．若 Ｓ ∈ Ｃ（ Ｇ） 且满足 ｈ（ Ｇ）＝ ω（ Ｇ－ Ｓ ） － ｜ Ｓ ｜，则称 Ｓ 是图 Ｇ的一个核．本文引入子核的概念并讨论了子核的一些基本性质；在子核概念及有关结果的基础上给出了一般连通非平凡图 Ｇ 的核度的计算公式．
Let G be a non trivial connected graph.The coritivity of G-S ,denoted by h(G) ,is defined as h(G)= max {ω(G-S)-｜S｜;S∈C(G)} ,where ω(G-S) denotes the number of components of G-S,C(G) denotes the collection of vertex cut sets in G.S *∈C(G) is called a core of G if it satisfies h(G)=ω(G-S *)-｜S *｜ .The notion of subcore is introdued and some basic properties are studied in this paper.Based on some results of subcore,the recursion formula of coritivity of arbitrary non trivial connected graph is given in this paper.
出处
《系统工程学报》
CSCD
1999年第3期243-246,257,共5页
Journal of Systems Engineering
基金
国家自然科学基金
关键词
核度
子核
递推公式
系统
coritivity,subcore,recurison formula
