2r-正则图连通圈网络的Hamilton分解

互连网络是超级计算机的重要组成部分。互连网络通常模型化为一个图,图的顶点代表处理机,图的边代表通信链路。2010年师海忠提出互连网络的正则图连通圈网络模型,设计出了多种互连网络,也提出了一系列猜想。文中证明了2r -正则图连通圈网络可分解为边不交的一个Hamilton圈和一个完美对集的并,从而证明了当原图为2r-正则连通图时,这一系列猜想成立。

Hamiltonian Decomposition of 2r-regular Graph Connected Cycles Networks

An Interconnection network is an important part of a supercomputer.The interconnection network is often modeled as an undirected graph,in which the vertices correspond to processor/communication parts,and the edges correspond to communication channels.In 2010,Hai-zhong Shi proposed the model of 2r-regular graph connected cycles,for designing analyzing and improving such networks,and proposed many conjectures.In this paper,we proved that any 2r-regular graph-connected cycles network is a union of edge-disjoint Hamiltonian cycle and a perfect matching.Therefore,we proved that the conjectures are true when primitive graphs are 2r-regular connected graph.