有向循环图寻径控制  

The Routing Control for Circulant Digraphs

作　　者：刘红美[1] 高世臣[2] 

机构地区：[1]三峡大学理学院,湖北宜昌443002 [2]中国地质大学信息工程学院,北京100083

出　　处：《数学的实践与认识》2004年第11期118-123,共6页Mathematics in Practice and Theory

基　　金：国家自然科学基金支持 (批准号 :1 0 3 71 0 48)

摘　　要：有向循环图 G(N ;1 ,s)作为有向双环网的图论模型备受关注 .本文将图的点集分划为几个不交子集 ,找到任意节点对之间路径沿跳长为 1和跳长为 s的边数的上确界 .找到了判断节点对间最短路径的充要条件 ,利用点集的分布特征设计了一个最优寻径算法 .对双环网络的容错路径进行了深入研究 ,给出了容错直径公式 ,提出了一个最优容错路径算法 .This paper partition the vertex set of circulant digraphs into several disjoint subsets and find the upper band of path length between any two vertices. Furthermore, we give a necessary and sufficient conditionn to judge a shortest path, then provide an optimal routing algorithm. Finally, the fault-tolerant routing has been inrestigated.

关 键 词：循环图 点集 分划 容错直径 上确界 边数 子集 算法 最短路径 最优 

分 类 号：O157.5[理学—数学] O144[理学—基础数学]