局部紐立方體和交叉立方體容錯(cuò)性研究.pdf

1、眾所周知，使用圖論來(lái)構(gòu)建網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是建模常見(jiàn)的形式，而且已經(jīng)被越來(lái)越多的學(xué)者應(yīng)用到研究之中。泛圈性和路徑嵌入作為衡量網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)容錯(cuò)性的一項(xiàng)重要指標(biāo)，變得越來(lái)越受學(xué)者的關(guān)注。研究容錯(cuò)性不僅具有很強(qiáng)的學(xué)術(shù)價(jià)值而且還有很大的實(shí)際意義，它可以有效地改善和優(yōu)化一個(gè)大型網(wǎng)絡(luò)出現(xiàn)不可預(yù)見(jiàn)的故障時(shí)的情況，通過(guò)合理的規(guī)劃使其能夠在多線路和元件同時(shí)發(fā)生故障時(shí)，仍然可以保證網(wǎng)絡(luò)的正常使用。當(dāng)網(wǎng)絡(luò)中出現(xiàn)錯(cuò)誤時(shí)，用F表示網(wǎng)絡(luò)結(jié)構(gòu)圖中錯(cuò)誤的集合。
　　局

2、部紐立方體LTQn和交叉立方體CQn都是超立方體Qn的變形網(wǎng)絡(luò)結(jié)構(gòu)，它們具備Qn現(xiàn)有的優(yōu)點(diǎn)，同時(shí)改進(jìn)了Qn的缺點(diǎn)，如泛圈性等。在點(diǎn)數(shù)一樣時(shí)，它們的直徑長(zhǎng)度是Qn的一半。容錯(cuò)性在衡量一個(gè)拓?fù)浣Y(jié)構(gòu)的標(biāo)準(zhǔn)中占有很重要的比重，也引起了科學(xué)工作者對(duì)容錯(cuò)性研究的興趣和重視。本文通過(guò)在n比較小的情況下進(jìn)行計(jì)算機(jī)程序搜索和在n較大的情況下進(jìn)行數(shù)學(xué)歸納法的方法，研究局部紐立方體網(wǎng)絡(luò)和交叉立方體網(wǎng)絡(luò)的容錯(cuò)性質(zhì)，得出了下面的結(jié)論:
　　(1)給出弱點(diǎn)對(duì)

3、的概念，并得出結(jié)論:對(duì)于任意n(n≥5），F(xiàn)(∈)V(LTQn)∪ E(LTQn)，當(dāng)|F|≤n-2時(shí)，對(duì)于LTQn-F中的任意兩點(diǎn)（弱點(diǎn)對(duì)中的兩點(diǎn)除外）在LTQn-F中存在一條長(zhǎng)為2n-1-1≤l≤|V(LTQn-F)|-1的路徑連接這兩點(diǎn)。
　　(2)對(duì)于任意F(∈)V(LTQn)∪E(LTQn)且|F|≤n-3，點(diǎn)v是LTQn(n≥3)中的任意一個(gè)正確點(diǎn)，在LTQn-F中存在包含點(diǎn)v且長(zhǎng)為l的正確圈，其中4≤l≤2n-|F|