交换折叠超立方体的连通度
2019-09-09蔡学鹏任佰通冯苗苗
井冈山大学学报(自然科学版) 2019年4期
关键词:定义
蔡学鹏,杨 伟,任佰通,冯苗苗
(新疆农业大学数理学院,新疆,乌鲁木齐 830052)
0 引言
随着计算机的飞速发展,信息化和数字化技术的不断进步,许多实际问题的数学模型使离散型结构上的数字化技术得到了更多人的关注,图的连通度理论[1-7]作为离散数学的一个重要的组成部分。多处理器系统由两个或两个以上的处理器构成,处理器交换各种信息是用消息协议通过互联网络传播的。在大规模集成(VLSI)技术和圆片规模集成技术(WSI)领域的最新进步已经能使含有非常多的处理器数量的处理器系统实现信息交流。因为增加的多处理器系统中处理器的数量、多处理器系统的可靠性和容错性的研究已经成为一个活跃的热门的研究领域,因此受到了国际数学界与工程界越来越广泛的重视。
本文仅考虑有限的、无向的、简单的并且连通的图[1,8-9]。
设G=G(V,E)是一个图。对于图G中两个子图H和K,记是点集诱导的子图。设NH(K)是在H中且与K中的点相邻的点的集合。特殊地,如果K={v},可记作NH(v)。设是点v在图G中的度,设NG[v]=NG(v)∪{v}。如果不产生歧义,我们可省略下标即记为d(v),N(v),N[v]。δ(G)=表示图G的最小度。
设S⊆V(G)(或者S⊆E(G)),如果G-S是不连通的或者平凡的,则称S是图G的一个点割(或者边割)。连通度(或者边连通度)是衡量网络可靠性的一个重要参数。图G的连通度κ(G)(或者边连通度λ(G))是图G中最小点割(或者边割)的基数。我们知道κ(G)≤λ(G)≤δ(G),并且κ(G)(或者λ(G))越大图G就越可靠。
互联网络的拓扑结构经常被表示成一个连通的图,其中图的点和边分别表示互联网络的处理器和互联网络的连接线[9]。……
登录APP查看全文
