图的笛卡尔积及字典式积的连通性

来源 :新疆大学 | 被引量 : 0次 | 上传用户:liongliong522
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着信息网络的飞速发展,许多与之相关的理论性问题越来越引起人们的重视,其中之一即为网络可靠性。通信网络的可靠性分析与高可靠性能网络的设计问题是可靠性研究的核心。图作为网络拓扑结构最有效模型,图的各种连通性指标被先后用来研究网络可靠性问题。通常情况下,网络是连通的,从而代表它的图也是连通的,也就是说,图中任意两点间都存在一条路。但是,有时网络的某个元素被破坏,也就是其对应的图被去掉一些边和点时。这时我们希望被破坏的网络尽可能的连通。图的经典参数边连通度λ(G)是指要使得一个图不连通所需要去掉的最少的边数,点连通度k(G)是指要使得一个图不连通所需要去掉的最少的点数。边连通度和点连通度是衡量网络可靠性的一个重要参数。作为经典连通度的推广,人们提出了高阶的连通度,例如极大(边)连通的,上(边)连通的,超连通的等。另一方面,笛卡尔积和字典式积是从一些较小的图来构造较大的图的一种有效的方法,从而在设计网络和分析网络方面有着重要的作用。在本文中,主要是研究图的笛卡尔积和字典式积的高阶连通性的问题。我们给出了两个图的笛卡儿积及字典式的积为max-λ,max-k,supe-λ,super-k及hyper-k的充分条件,同时证明了其中一些条件也是必要的.此外,对这两种积的局部割集和广义割集的性质也进行了考虑.对于两个图的笛卡尔积,我们有以下的主要结果: (1)如果G<,1>和G<,2>是极大边连通的,则G<,1>×G<,2>是极大边连通的。 (2)假设λ<,i>≥2或λ<,1>=1,2≤λ<,2>和G<,2>是极大边连通的,则G<,1>×G<,2>是上边连通的。 (3)如果G<,1>和G<,2>是极大连通的,则G<,1>×G<,2>是极大连通的。 (4)假设k<,i>≥2或K<,1>=1,2≤K<,2>×G<,2>是上连通的。 (5)假设k<,i>≥2或k<,1>=1,2≤K<,2>×G<,2>是超连通的。 (6)若G<,1>,G<,2>满足下列条件之一,则有G<,1>×G<,2>的每一个最小广义割集都是一个局部割集: (a)G和G是极大连通的,并且δ(G<,1>)≥2和δ(G<,2>)≥2,(b)G<,1>≌K<,2>,2≤δ(G<,2>)≌K<,3>.对于两个图的字典式积,我们有以下的主要结果: (1)如果X和Y是极大边连通的,则X[Y]是上边连通的. (2)X[Y]是极大连通的当且仅当X是完全图并且Y是极大连通的. (3)X[Y]是上连通的当且仅当X是完全图并且Y是上连通的. (4)X[Y]是超连通的当且仅当X是完全图并且Y是超连通的. (5)如果X是完全图,并且Y的每一个最小广义割集都是一个局部割集,则X[Y]的每一个最小广义割集都是一个局部割集.
其他文献
有限元方法是微分方程数值解的一种经典方法,自适应有限元方法专门针对具有奇点解的方程.和经典有限元不同,它是一种非线性逼近,因而在数值计算上取得了巨大的进步.遗憾的是,自适应
本文主要研究两台同类机半在线机器覆盖问题.全文共分为三章. 第一章是绪论部分,主要介绍排序问题,近似算法和竞争比分析等基本概念. 第二章主要研究了两台同类机已知工
期刊
期权是一种基本的衍生金融工具,是持有人在确定时间,按确定价格向出售方购买(出售)一定数量和质量的标的资产的协议,它与远期合约、期货类似,可用来对标的资产进行风险管理.期权定
切换动态系统是一类重要的混合动态系统,它是由几个连续时间子系统或离散时间子系统及作用在其中的切换规则构成的.切换系统不同于一般的连续时间系统或离散时间系统,它具有一
1 放顶煤工作面采出率调查与测算自从放顶煤工作面在生产矿井投产以来,工作面单产得到了大幅度的提高,而对资源采出率的真实情况缺乏实际评价。大多数领导只是从放顶煤现象上认
计算机的广泛使用标志着数字时代的到来,随着科学技术的进步,计算机技术和艺术设计也紧密地结合在一起,我们已步入到数字艺术时代。数字媒体艺术相对于传统艺术而言,它借助于
期刊
算子代数理论产生于20世纪30年代,随着这一学科的迅速发展,它已成为现代数学中的一个热门分支,它与量子力学,非交换几何,线型系统和控制理论,甚至数论以及其他一些重要数学分支都有