星图的强连通度

1

作者 张慧英 王世英 《应用数学进展》 2024年第3期1080-1098,共19页

大量数据的处理和复杂问题的解决对多处理器系统的性能要求越来越高,许多多处理器系统都将 互连网络作为底层拓扑结构。 互连网络决定了多处理器系统的性能,在处理器和它们之间通信链 路可能发生故障的系统中,考虑网络的容错性是非常重... 大量数据的处理和复杂问题的解决对多处理器系统的性能要求越来越高,许多多处理器系统都将 互连网络作为底层拓扑结构。 互连网络决定了多处理器系统的性能,在处理器和它们之间通信链 路可能发生故障的系统中,考虑网络的容错性是非常重要的。 传统的点连通性只针对处理器故障, 边连接性只针对通信链路故障的问题。 在此背景下,提出了网络的强连通性,它允许处理器和通 信链路同时故障。 在互连网络的设计中,最基本的考虑因素之一是网络的连通性。 n维星图Sn作为 互连网络的一种有利的拓扑结构,具有许多优良的性质。 因此我们给出了Sn的强连通性以及强自 然连通性。 展开更多

关键词 互联网络 强连通度 强自然连通度 连通性 星图

在线阅读 下载PDF 职称材料

关于循环有向图的强连通度 被引量：3

2

作者 徐俊明 《应用数学》 CSCD 北大核心 1989年第3期1-4,共4页

本文定义的循环有向图D(n;S)在分布式环形计算机互连网络设计中被广泛运用。本文证明了D(n;S)的强连通度k>2/3|S|。

关键词 循环有向图 强连通度 网络

在线阅读 下载PDF 职称材料

有向循环图强连通度的下界 被引量：2

3

作者 黄琼湘 刘新 《应用数学》 CSCD 北大核心 1992年第1期120-121,共2页

为简便计,本文采用文[1]中的定义和符号,而未说明的概念或符号引自[3].本文仅讨论有限、简单有向图. 有向图D=(V,A)称为强连通的,如果对D的任两顶点u与v,在D中同时存在(u,v)—有向路和(v,u)—有向路,C(?)V称为D的点割集,如果D—C非强连... 为简便计,本文采用文[1]中的定义和符号,而未说明的概念或符号引自[3].本文仅讨论有限、简单有向图. 有向图D=(V,A)称为强连通的,如果对D的任两顶点u与v,在D中同时存在(u,v)—有向路和(v,u)—有向路,C(?)V称为D的点割集,如果D—C非强连通或是单点.D的所含点数最少的点割集称为最小点割集,其阶数定义为D的强连通度,记为k(D)或k. 循环有向图D(n,S) 展开更多

关键词 有向循环图 强连通度 下界

在线阅读 下载PDF 职称材料

环网的强连通度与最佳强连通性

4

作者 周永生 林秀琴 李唐芬 《计算机应用》 CSCD 1995年第1期22-24,共3页

本文得到了环网Ｄ（ｎ；ｓ）（ｓ＝（ｓ１，Ｓ２，．．．，ｓｍ｝）的强连通度的求法及构造强连通度Ｋ（Ｄ）≥ω（≤ｍ）的环网Ｄ（ｎ；ｓ）的方法。

关键词 强连通度 最佳强连通性 环网 K原子部分

在线阅读 下载PDF 职称材料

Cayley有向图强连通度的进一步研究

5

作者 简国明 《福州大学学报（自然科学版）》 CAS CSCD 北大核心 2009年第4期486-488,共3页

讨论了Cayley有向图有关强连通的若干性质,应用群方法给出了一般有限群的Cayley有向图的强连通度小于其最小度的充要条件,把文献[3]的结果从循环群推广到一般有限群.

关键词 CAYLEY有向图 强连通度 群方法 陪集

原文传递

有向循环图的强连通度的性质

6

作者 周永生 李唐芬 《甘肃工业大学学报》 1991年第3期102-105,共4页

本文首先证明了连通有向循环图的k原子部分仍为连通有向循环图,并给出了有关连通有向循环图的强连通度的另一些性质。然后利用这些性质得到了基础图是简单图的连通有向循环图的强连通度的下界。

关键词 有向循环图 强连通度 图论 连通图

在线阅读 下载PDF 职称材料

关于有向循环图强连通度下界的推导

7

作者 简国明 谢芳苏 《赣南师范学院学报》 1997年第3期6-7,共2页

本文给出有向循环图强连通度下界的一个简单推导方法

关键词 有向循环图 强连通度 下界 循环图

在线阅读 下载PDF 职称材料

有向循环图的强连通分支数以及强连通度的界

8

作者 简国明 《韶关大学学报》 1998年第3期80-84,共5页

本文应用代数方法，讨论了有向循环图的强连通分支数的几种表达，以及强连通的有向循环图的强连通度的界。

关键词 有向循环图 群论 代数 强连通分支数 强连通度

在线阅读 下载PDF 职称材料

几类有向循环网络的可靠连通性研究

9

作者 黄秀云 《甘肃工业大学学报》 1991年第3期70-76,共7页

本文给出了出度m为4,5,6,7且基础图为简单图的m—有向循环网络具有可靠连通性的充要条件。对出度为4,5,6,7的每一类有向循环网络给出了相应组数的判别式,当且仅当网络满足在每一组判别内式至少有一式不成立的条件时,该网络具有可靠连通性。

关键词 有向循环网络 网络 强连通度 图论

在线阅读 下载PDF 职称材料

Cayley色图的强连通性 被引量：3

10

《云南大学学报（自然科学版）》 CAS CSCD 1997年第5期456-459,共4页

应用群论方法，给出并证明了一般有限群的Ｃａｙｌｅｙ色图Ｄ（Ｆ，Ｓ）的强连通分支数为［Ｆ：（Ｓ）］，以及强连通的Ｃａｙｌｅｙ色图Ｄ（Ｆ，Ｓ）的强连通度的下界为［｜Ｓ｜２］＋１．

关键词 Cayley色图 强连通分支数 强连通度 CAYLEY图

原文传递

一类超欧拉有向图中的超欧拉bypass

11

作者 王新艳 刘娟 《河南科学》 2018年第8期1177-1181,共5页

设D是严格有向图(无环与重弧),λ(D)是有向图D的弧强连通度,α′(D)表示有向图D的匹配数.如果有向图D中含有一个生成欧拉子图反向一条弧的方向所得的子图,则称有向图D含有一个超欧拉bypass.证明了一个强连通有向图D满足λ(D)≥α′(D)... 设D是严格有向图(无环与重弧),λ(D)是有向图D的弧强连通度,α′(D)表示有向图D的匹配数.如果有向图D中含有一个生成欧拉子图反向一条弧的方向所得的子图,则称有向图D含有一个超欧拉bypass.证明了一个强连通有向图D满足λ(D)≥α′(D)≥5,则有向图D含有一个超欧拉bypass. 展开更多

关键词 超欧拉bypass 超欧拉有向图 弧强连通度 最大匹配

在线阅读 下载PDF 职称材料