论文部分内容阅读
Cayley图是许多互联网络的底层拓扑，研究网络拓扑结构的容错能力，对于提高网络的鲁棒性、保证网络的可靠性具有重要意义。根据对换树的不同，Cayley图可分为泡形图，星图和一般对换树对应的Cayley图。本文分别针对上述Cayley图结构，研究了图的（条件）匹配排除数和分层网络中子网络的（边）排除数等度量网络容错能力的参数，完成的主要研究工作及结果如下: 第二章主要研究对换树对应的Cayley图的条件匹配排除数，得到了任意对换树对应的Cayley图条件匹配排除数为2n-4。本章首先定义了一个图的条件匹配排除数，接着给定一个算法，对于任意给定的一棵非星非路的n(≥5)阶树T，使之阶数逐渐降低并变成一个星;对于其逆算法，可以通过给星添加一度点方式使其变成非路非星的对换树;利用此算法与已有主要定理相结合即得Cayley图条件匹配排除数为2n-4的结论。第三章研究了星加一叶图对应的Cayley图的最优条件匹配排除集，得出星加一叶图对应的Cayley图的最优条件匹配排除集都是平凡的之结论。首先由于任意对换树对应的Cayley图条件匹配排除数为2n-4，可以得到当n≥5时Cayley图的条件匹配排除数是2n-2;将此Cayley图按照固定最后一位的方式划分成低一维的子结构，而子结构之间的交叉边形成了一个完美匹配，故交叉边中至少有一条故障边;利用已有定理可以得到每个子结构中故障边边数的下界，最终通过遍历的方法讨论得出结论。第四章研究了分层网络中子网络的（边）排除。首先给出了分层网络的一种简明的表示方式，通过划分得到了分层网络中所有不相交和不相同的子图的个数;随后得到了相同维度的子图的排除数和边排除数的粗略关系;最后通过构造映射，用尽量少的点（边）破坏全部相应的子图，得到了一些子图的（边）排除数特定值和改进上界。 本文通过对Cayley图容错能力的研究，得到了网络容错能力参数的一些定性结果，对于认识Cayley图的内在结构具有理论意义，对于保证网络拓扑结构的可靠性具有实际指导意义;同时文中利用对称树研究Cayley图网络的方法对于研究相关网络结构具有推广和借鉴意义。