网络边连通性的最优化

出版时间：2009-9  出版社：科学出版社  作者：王世英，林上为 著  页数：170  

前言

　　组合数学，或广言之，离散性数学，主要研究“状态模式”的存在、计数、构造和优化。所谓状态模式，就是一个集合中各个元素赋予状态的方式。常见的状态模式有连接、选取、匹配、排序、划分、覆盖、装填等方式。对一个离散系统而言，各元素之间的联系，即连通性，应该是最基本的模式。特别对图与网络这样具有典型意义的组合构形，连通性是首要的研究专题。　　图论历史悠久，其应用范围已遍及自然科学与系统科学等领域。之所以受到普遍重视，与它的简洁清晰而富有表现力是分不开的。在图论的经典发展时期，人们往往用图来表示日常生活的事理关系，如游历过桥、连线选点、染色划分等。其中问题的提法都比较简单明白（求解不一定容易）。随着学科的发展，图所描写的关联关系越来越复杂，从游戏规则到物质结构和工程系统，研究层面不断向纵深推进。　　20世纪电子计算机的出现，引发了信息科学的突飞猛进。大量离散问题的涌现，使图论获得了新的生长点和肥沃的土壤，推动图论进入繁荣发展的新阶段。尤其是计算机系统互联网络的兴起，带来许多新概念和新课题。可以用网络把众多的计算机连接起来，相互配合，发挥更强的功能。比如说，已有的计算机系统（分布式或并行式计算系统）用一个图H来表示，称为“主图”；而互联网络用一个图G来表示，称为“客图”。那么设计互联网络就是把图G嵌入图日中，使得嵌入方式的某些性能指标达到最优。这些性能指标主要是指交换信息的有效性、可靠性、容错性以及电路布线上的其他指标，如延伸、拥挤、转折、交叉等。简单地说，一个好的互联网络应该有尽可能大的“连通度”和尽可能小的“直径”。进而，还要对称性好，传输延迟小，布线与路由算法简单，容易嵌入其他拓扑结构等。由此提出一系列重要的研究课题，形成现代图论中十分活跃的研究方向“通信网络理论”，吸引着众多的图论学者。

内容概要

本书对网络边连通性的最优化问题提供了一个统一的理论框架，其中许多内容和方法是作者的研究成果。内容包括：  给出极大k限制边连通图和超级k限制边连通图的各种充分条件；确定一些著名网络的k限制边连通度和超级k限制边连通性；同时，还提出一些问题供有兴趣的读者进一步研究。    本书可供高等院校计算机应用、网络通信、应用数学等相关专业研究生和高年级本科生学习，也可作为相关领域研究人员的参考用书。

书籍目录

序前言第一章  引言和基本概念  1.1  图论的一些基本概念和记号  1.2  k限制边连通度的应用背景和研究进展第二章  超级k限制边连通图的邻域充分条件  2.1  相关概念和结果  2.2  准备工作  2.3  极大k限制边连通图的邻域条件  2.4  超级k限制边连通图的邻域条件  2.5  极大和超级k等周边连通图第三章  直径为2的图的超级限制边连通性  3.1  相关概念和结果  3.2  准备工作  3.3  超级限制边连通图的邻域条件  3.4  结果的相互独立性第四章  二部图的超级k限制边连通性  4.1  相关结果  4.2  超级限制边连通二部图  4.3  极大k限制边连通二部图  4.4  超级k限制边连通二部图第五章  用直径和围长表示的超级k限制边连通图的充分条件  5.1  相关概念和结果  5.2  准备工作  5.3  超级限制边连通图的直径围长条件  5.4  极大k限制边连通图的直径围长条件  5.5  超级k限制边连通图的条件直径围长条件第六章  线图的超级k限制边连通性  6.1  相关概念和结果  6.2  k限制边连通度与(1，k)限制连通度相等时图的性质  6.3  k限制边连通度与(1，k)限制连通度相等时超级k限制边连通图的充分条件第七章  两类互联网络的k限制边连通度  7.1  相关概念和结果  7.2  G(Go，G1；Mt)的k限制边连通度  7.3  G(G0，G1，，Gr-1；Mt)的k限制边连通度第八章  无向Kautz图的极大k限制边连通性  8.1  相关概念和结果  8.2  准备工作  8.3  无向Kautz图的超级限制边连通性  8.4  无向Kautz图的k限制边连通度第九章  一类无向Kautz图的k限制边连通度  9.1  相关结果  9.2  一类无向Kautz图的k限制边连通度的上界  9.3  一类无向Kautz图的超级4限制边连通性第十章  定向图的超级弧连通性  10.1  相关概念和结果  10.2  超级弧连通定向图的最小度条件  10.3  超级弧连通定向图的半度序列条件第十一章  有向de Brujn图的强限制弧连通度  11.1  相关概念和结果  11.2  准备工作  11.3  有向de Bruijn图的强限制弧连通度第十二章  极大限制弧连通有向图  12.1  相关概念和结果  12.2  极大限制弧连通有向图的定义和性质  12.3  极大限制弧连通有向图的充分条件参考文献主要符号表

用户评论 (总计1条)

•   专业性比较强，是做这方面工作值得看的书。