交叉立方体容错路径嵌入和容错边泛圈性研究

摘要

在研究网络拓扑结构时，运用图论来构建模型是常见的方法。而路径嵌入和泛圈性是研究网络拓扑结构容错性时不可回避的内容，从而越来越受人们的关注。提高网络的容错性能够改善大型网络的抗故障性。
　　作为超立方体Qn的变形网络结构，交叉立方体CQn相较于超立方体Qn有许多更优的性能。尽管交叉立方体CQn和普通的超立方体Qn有相同数量的顶点和相同的结点度，但交叉立方体的直径大约是普通超立方体的一半。因此CQn不但具备Qn现有的优点，而且改进了Qn的不足，而容错性是研究网络拓扑结构中必须要考虑的因素，毕竟一个大型网络在运行时总会出现节点和线路或者单独或者同时出现问题的情况。基于此，考虑网络的容错性对于一个大型网络就很重要。令fv表示为CQn中的错误点数，e表示为CQn中的错误边数。本文通过当n较小时运用计算机程序搜索和当n较大时进行数学归纳法这两种方法，研究了CQn容错路径嵌入问题和容错边泛圈性质，得出了如下结果:
　　(1)对于任意n（n≥5），F(c)V(CQn)∪E(CQn)，当|F|≤n-2时，对于CQn-F中的任意两个正确点（与度为2的顶点相邻的一对顶点除外）在CQn-F中存在一条长为l的正确路径连接这两点，其中，l满足2n-1-1≤l≤2n-fv-1。
　　(2)证明了对于任意一条边e=(u，v)∈E（CQn），当0≤fv+fe≤n-2，n≥5时，对于CQn中的任意一个正确边e，CQn都能存在一条长为l6≤l≤2n-fv，l≠7）且包含这个边e的正确圈C。

目录

声明

摘要

引言

1 相关概念及预备知识

1．1 图的基本概念

1．2 图的嵌入

1．3 几种常见的组合网络模型

1．3．1 超立方体网络

1．3．2 M?bius立方体网络

1．3．3 纽立方体网络

1．3．4 局部纽立方体网络

1．4 容错哈密顿性介绍

1．5 交叉立方体CQn的定义及容错性质

1．5．1 交叉立方体的定义

1．5．2 交叉立方体的性质

1．6 本文主要工作

2 交叉立方体的容错路径嵌入研究

2．1 交叉立方体容错的相关结论

2．2 交叉立方体容错路径嵌入证明

3 交叉立方体的容错边泛圈性研究

3．1 交叉立方体容错边泛圈性的相关引理

3．2 交叉立方体容错边泛圈性证明

3．3 交叉立方体容错边泛圈性l≠7的证明

结论

参考文献

攻读硕士学位期间发表学术论文情况

致谢