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

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

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