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

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

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