FC_n的路径问题(英文)

A Routing Solution of FC_n

路径问题是网络理论研究的一个重要课题.我们讨论了FCn这类网络模型中节点间的内点不相连最短路径的数目.由于FCn是凯莱图,利用凯莱图的点传递性计算了FCn中任意点到单位元点之间的所有内点不相连的最短路,并且证明了FCn在内点不相连的最短路径方面达到最大可能,是最优的.

Routing problem is a main topic in the research of interconnection networks.We emphasize on the number of node-disjoint shortest paths（NDSP in abbreviation） between any two vertices in FCn.Because FCn is a Cayley graph which is vertex-transitive,we calculated all the NDSP from each vertex to its identity element.We proved that FCn is optimal in sense of its maximum possibility of NDSP.