交叉立方體容錯(cuò)路徑嵌入和容錯(cuò)邊泛圈性研究.pdf

1、在研究網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時(shí)，運(yùn)用圖論來(lái)構(gòu)建模型是常見(jiàn)的方法。而路徑嵌入和泛圈性是研究網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)容錯(cuò)性時(shí)不可回避的內(nèi)容，從而越來(lái)越受人們的關(guān)注。提高網(wǎng)絡(luò)的容錯(cuò)性能夠改善大型網(wǎng)絡(luò)的抗故障性。
　　作為超立方體Qn的變形網(wǎng)絡(luò)結(jié)構(gòu)，交叉立方體CQn相較于超立方體Qn有許多更優(yōu)的性能。盡管交叉立方體CQn和普通的超立方體Qn有相同數(shù)量的頂點(diǎn)和相同的結(jié)點(diǎn)度，但交叉立方體的直徑大約是普通超立方體的一半。因此CQn不但具備Qn現(xiàn)有的優(yōu)點(diǎn)，而且改進(jìn)了Q

2、n的不足，而容錯(cuò)性是研究網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中必須要考慮的因素，畢竟一個(gè)大型網(wǎng)絡(luò)在運(yùn)行時(shí)總會(huì)出現(xiàn)節(jié)點(diǎn)和線路或者單獨(dú)或者同時(shí)出現(xiàn)問(wèn)題的情況。基于此，考慮網(wǎng)絡(luò)的容錯(cuò)性對(duì)于一個(gè)大型網(wǎng)絡(luò)就很重要。令fv表示為CQn中的錯(cuò)誤點(diǎn)數(shù)，e表示為CQn中的錯(cuò)誤邊數(shù)。本文通過(guò)當(dāng)n較小時(shí)運(yùn)用計(jì)算機(jī)程序搜索和當(dāng)n較大時(shí)進(jìn)行數(shù)學(xué)歸納法這兩種方法，研究了CQn容錯(cuò)路徑嵌入問(wèn)題和容錯(cuò)邊泛圈性質(zhì)，得出了如下結(jié)果:
　　(1)對(duì)于任意n（n≥5），F(xiàn)(c)V(CQn)∪E