ハイパーリング連結機械

概要

論文の詳細を見る
グラフG=(V,E)が,V={0,…,N-1},E={{u,v}|v-u modulo Nが2の冪乗}であるときこのグラフを頂点数Nのハイパーリング(N-HR)という。本稿では,HRの構成法,特性,埋め込み,スパナについて論じる。頂点数Nのハイパーキューブや,a×b格子,頂点数Nの完全二分木を,N-HRに部分グラフとして埋め込む.また,HRのスパナの構成方法を3タイプ紹介する.これらのタイプのスパナの伸び率は,HRの頂点数をNとすると高々[log_2N],任意の1【less than or equal】k【less than or equal】[log_2N]に対し2k-1,任意の2【less than or equal】k【less than or equal】[log_2N]-1に対し2k-1である.また,これらのタイプのスパナを構成する辺の数は,N-1,高々N[log_2N), k],高々N(log_2N-k)/2k+Nkである.最後に,HRのγシンクロナイザに関する伸び率と辺の数の表を示す.
1993-06-25