网络的限制边连通度与弧连通度 PDF下载

编辑推荐

本书的作者长期从事网络的边连通度和弧连通度问题的研究工作，并已经取得一些成果。这些成果包括网络的极大限制连通性和超级限制连通度与其他参数之间的关系。该书蕴含充实、严谨的基础性理论，有助于致力于该领域的同学打下坚实的数学基础，同时，也将为相关专业感兴趣的研究者们提供颇有价值的参考，并在理论与实际问题之间起到桥梁作用。

；

内容简介

图论是研究互连网络拓扑性能的有效方法，本书对于有关网络可靠性参数的问题提供了一个理论框架。内容包括网络的极大k限制边连通性和超级k限制边连通性与其他参数之间的联系；有向图弧连通度的下界。本书是作者的研究成果，可作为高等院校应用数学、数据科学与大数据技术、网络通讯专业研究生以及相关领域研究人员的参考书目。

作者简介

暂无

网络的限制边连通度与弧连通度 PDF下载

前沿

序

在20世纪以前应用数学的基础是微积分，弹性力学、流体力学、电磁学、量子力学都归结为偏微分方程.因而在微积分基础上发展起来的分析学成为数学的主流.20世纪中叶以后，计算机对人类的影响逐渐增强，不仅是科学与工程问题需要高效的计算能力，而且通信与信息储存已进入千万人们的日常生活.计算机科学中，离散数学作为一门研究离散数据及其相互关系的学科，逐渐走进数学舞台的中心，并在计算机科学与技术、信息与通信工程、电子科学与技术、控制科学与工程等诸多学科中得到广泛的应用.由于计算机是一个离散的结构，它虽然很“聪明”，但却只能处理离散的或离散化了的数据，这就注定计算机与离散数学之间有着千丝万缕的联系.图论历史悠久，目前其应用范围已遍及自然科学与系统科学的广阔领域.之所以受到普遍重视，与它的简洁清晰而富有表现力分不开.在图论的经典发展时期，人们往往用图来表示日常生活的事理关系，如游历过桥、连线选点、染色划分等，其中问题的提法都比较简单明白（求解不一定容易）.随着学科的发展，图所描写的关联关系越来越复杂，从游戏规则到物质结构和工程系统，研究层面不断向纵深推进.许多图论与网络概念被推广深化.例如，距离和直径被推广为“宽距离”和“宽直径”.连通度的概念也有很大的发展，众所周知，“连通”是用“截断”来刻画的.在经典定义中，一个图的连通度（边连通度）就是截断这个图所要删除的最小点（边）数.在通讯网络的可靠性分析中，这种简单的概念已不能确切地反映实际的网络性能，以边连通度为例，从同一个顶点引出的多条边，一般不会同时出现故障，所以破坏连通性的边割集应该不包括这种关联于一个顶点的边集.排除这种平凡的边割集，便得到“限制边割集”，从而得到“限制边连通度”，进一步的要求又提出k限制边连通度、k等周边连通度、超边连通性以及一系列推广概念，形成连通性研究的新领地.本书的作者长期从事网络的边连通度和弧连通度问题的研究工作，并已经取得一些成果.这些成果包括网络的极大限制连通性和超级限制连通度与其他参数之间的关系.该书蕴含充实、严谨的基础性理论，有助于致力于该领域的同学打下坚实的数学基础，同时，也将为相关专业感兴趣的研究者们提供颇有价值的参考，并在理论与实际问题之间起到桥梁作用.我们期望，作者能够有更多的既有理论深度又有应用背景的数学著作出版.

王世英

2019年4月于临汾

；

前言

随着信息科学的迅速发展和数据量的不断增多，人们迫切需要速度更快、性能更高的计算机系统.多处理机系统随着处理机数目的增加，可使处理速度进一步加快，而且并行算法的日趋成熟，也为处理的正确性和高速度提供了保证，使多处理机系统的计算速度达到或接近超级计算机.多处理机系统的一个基本特征是处理机之间通过物理连线按照某种互连网络连接起来，使得多个处理器通过信息传输，互相配合、并行处理，从而提高系统的运算能力.

大规模多处理机系统功能的实现很大程度上依赖于系统互连网络的性能.互连网络拓扑结构对网络的性能有着决定性的影响.多处理机系统的互连网络拓扑结构常以图为数学模型，这时图的顶点（即节点）代表处理机，而一对处理机之间的直接通信联系则用连接这对顶点的边来表示.因此，网络拓扑的性能可以通过图的性质和参数来度量.由于大规模多处理机系统中的某些部件发生故障是不可避免的，因此在设计和选择系统的互连网络拓扑结构时，要考虑的一个基本问题是它的可靠性.如果多处理机系统在部分处理机或连线失效时，剩余的子网络中各节点之间仍能正常工作，那么称该系统为容错的系统，这种可靠性称为容错性.

网络容错性的实质是当故障发生时，剩余网络的重组能力.边连通度λ（G）是度量网络可靠性的一个重要参数.通常，边连通度λ（G）越大，网络越可靠.但是用边连通度来考究系统的可靠性有两个缺陷:第一，边连通度不能区别按不同方式去掉λ（G）条边后所产生的不同的连通分支的情况，这说明边连通度不能反映由于通讯信道损坏造成的系统损坏程度，因而边连通度在某些应用上不够精确；第二，在分析和应用边连通度时我们都不言而喻地假定了系统的任何部分都可能同时失灵，也就是说，对边连通度没有加任何限制.然而，这在现实中几乎是不可能的.为了弥补上述缺陷，Harary于1983年提出了条件边连通度的概念.在1988年，Esfahanian和Hakimi通过引进网络中的禁错集的概念，将条件边连通度具体化，提出了限制边连通度的概念.作为限制边连通度的推广，Fàbrega和Fiol提出了k限制边连通度的概念.从最近关于k限制边连通度的研究结果来看，k限制边连通度越大，网络就越可靠.因此人们希望图G的k限制边连通度尽可能大，这需要k限制边连通度的一个上界．

作者近年来一直从事互连网络的可靠性分析的研究工作，阅读了大量相关领域的文献，获得了一些有意义的结果.本书是作者近年来的研究成果的整理、修正和系统化.本书一共分为九章，其中第一章由张磊和王晓丽共同完成，第二～五章由张磊完成，第六～九章由王晓丽完成.本书的基本结构如下：第一章首先介绍多处理机系统的互连网络的背景，并给出本书将用到的图论方面的术语、记号，然后介绍互连网络的设计原则，着重对互连网络可靠性进行介绍，最后综述互连网络的边连通性研究进展.第二章主要研究无（p 1）-团图和围长为g的图的极大k限制边连通性.第三章主要研究了直径为2的连通图的极大k限制边连通性.第四章主要研究极大k等周边连通图的邻域交条件.第五章给出了k限制边连通度存在的充分条件和极大k限制边连通图的邻域交条件和Ore条件.第六章研究了极大k限制边连通图与直径和围长等参数间的关系.第七章给出了超级k限制边连通图的Ore条件和邻域交条件.第八章主要研究图的弧连通性.首先给出了有向图弧连通度的下界，然后给出了非极大弧连通有向图和非极大弧连通定向图弧连通度的下界.第九章给出了图是极大和超级边连通的度序列条件.由于时间仓促，加之作者水平有限，错误之处在所难免，恳请读者批评指正.