網(wǎng)絡(luò)（圖）廣義直徑的研究.pdf

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

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

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

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