关于环面网格和对角网格网络的对剖宽度

On Bisection Width of Digonal and Toroidal Mesh Networks

Ｔａｎｇ和Ｐａｄｕｂｉｄｒｉ在１９９４年曾指出：ｎ×ｋ（ｎ，ｋ为奇数且３≤ｎ≤ｋ）的环面网格网络（ＴｏｒｏｉｄａｌＭｅｓｈＮｅｔｗｏｒｋｓ，ＴＭ）ＴＭ（ｎ，ｋ）和对角网格网络（ＤｉａｇｏｎａｌＭｅｓｋＮｅｔｗｏｒｋｓ，ＤＭ）ＤＭ（ｎ，ｋ）的对剖宽度分别为ｂ（ＴＭ（ｎ，ｋ））＝２ｎ＋２和ｂ（ＤＭ（ｎ，ｋ））＝４ｎ．本文证明了前一等式确实成立但后一等式不然：当ｎ＝ｋ时，ＤＭ（ｎ，ｎ）与ＴＭ（ｎ，ｎ）同构，从而ｂ（ＤＭ（ｎ，ｎ））＝ｂ（ＴＭ（ｎ，ｎ））＝２ｎ＋２；当３≤ｎ＜ｋ＜２ｎ时，ｂ（ＤＭ（ｎ，ｋ））≤２ｋ；当２ｎ≤ｋ时，ｂ（ＤＭ（ｎ，ｋ））≤４ｎ．

In 1994 Tang and Padubidri indicated that for an n×k network ( n,k are odd and 3≤n≤k ), the toroidal mesh has a bisection width b (TM( n,k ))=2 n +2; whereas the bisection width for the diagonal mesh is b (DM( n,k))=4n . The present work shows the first assertion is indeed true but the second one is not so. In fact it is proved that DM (n,n )TM( n,n ), hence b( DM (n,n))=2n+2 for odd n ≥3; b (DM( n,k))≤2k for 3≤ n<k<2n; and b (DM( n,k))≤4n for k≥2n .