1、大連理工大學博士學位論文網(wǎng)絡（圖）廣義直徑的研究姓名：侯新民申請學位級別：博士專業(yè)：計算數(shù)學指導教師：王天明20020301摘 要( 1 1 網(wǎng)絡G 的叫．R a b i n 數(shù)，記為r w ( G ) ，是指最小的f ，使得對任意的w + 1個頂點z ．ⅣH ．，蚰，存在枷條長至多為f 的從r 分別到Y(jié) 1 ．9 2 ，?．Y 。的內(nèi)部點不交的路．左文對一般的≈。正則☆．連通圖的R a b i n 敷作了研究．證明了n個頂點的≈．正則

2、≈璉通圖的k - R a b i n 數(shù)至多為j ．并且當n = 2 k - 3 + i ( k 一2 )時，該上界是不能改進的．f 2 ) 研究了k 一正則≈．連通圖的廣義≈．直徑．給出g d k ( G ) 的一些性質(zhì)并且證明了n 個頂點的％．正則k - 連通圖的廣義≈·直徑至多為n ／2 ，當n =2 ≈一3 + i ( k 一2 ) 時，該上界是可以達到的．4 ．環(huán)網(wǎng)絡廣泛應用于計算機局域網(wǎng)設計和各種并行處理系統(tǒng)．用Ⅳ

3、表示環(huán)網(wǎng)絡節(jié)點的數(shù)目，．記環(huán)網(wǎng)絡為G ( Ⅳ；l 覘，?：日) ，其中每個節(jié)點i 和i + 1 ，i + s 2 ，?，i + s f ( m o dN ) 分別相連．對f = 2 的情形，已經(jīng)有了豐富的結(jié)果．本文重點研究了2 = 3 的情形，即三環(huán)網(wǎng)絡，給出其直徑的上界，并給出Ⅳ不太大時。三環(huán)網(wǎng)絡取得最優(yōu)的一個條件．5 ．網(wǎng)絡的可嵌入性是衡量網(wǎng)絡性能好壞的一個重要標準，因此如何將一個較小的網(wǎng)絡嵌入到大的網(wǎng)絡中去成為網(wǎng)絡設計中需要考慮的

4、一個重要問題．文獻【叫j 中作者證明了如何將環(huán)網(wǎng)絡嵌入到起立方體中，但不幸的是超立方體網(wǎng)絡中不含有長為奇數(shù)的圈，因此不能將長為奇數(shù)的圈嵌入到超立方體中．本文定義了折疊式超立方體F H ( n ) ，證明了折疊式超立方體網(wǎng)絡的直徑約等于超立方體直徑的一半， ( n + 1 ) - 寬直徑為n ，比n - 立方體的n 一直徑小1 ．還證明了F H ( n ) 中包含長為奇數(shù)的圈，并給出了一個嵌入長為奇數(shù)的圈到折疊式超立方體網(wǎng)絡中的方法．1