强乘积图的限制边连通度和限制弧连通度

摘要

多元处理机系统的互联网络拓扑通常以无向（有向）图为数学模型，此时图的顶点表示多处理机系统中的处理机，边（弧）表示系统中处理机之间的通信线路.可靠性是网络设计中必须考虑的一个方面，在大型互联网络中，强乘积法是一种重要的方法.它可用图的边（弧）连通度来度量.此时，图的边（弧）连通度越大，对应网络的可靠性就越好，除边连通度外，限制边连通度目前得到了广泛的关注.本文主要研究了强乘积图的限制边连通度和限制弧连通度，共分为三章.
　　在第一章，我们给出本文将用到的主要术语和记号.
　　在第二章，我们通过引进强乘积无向图的概念，给出强乘积图限制边连通度的上界和下界及一些相关的推论.主要结果如下:
　　(1)设G1和G2是两个连通图，它们的连通度分别是λ1，λ2.则有λ'G1(×)G2≤min{λ1(|V2|+2|E2|)，λ2(|V1|+2|E1|)，ξG1(×)G2(V1)，ξG1(×)G2(V2)}.
　　(2)设G为连通图且|V(G)|＞2，它的边连通度为λ，则λ'（K2(×)G）=4λ.
　　(3)设G1和G2是两个连通图，它们的连通度分别是λ1，λ2.则有λ'G1(×)G2≥min{λ1(|V2|+2|E2|),λ2(|V1|+2|E1|),λ1+2λ2+2λ1λ2,λ2+2λ1+2λ1λ2}.
　　(4)如果G1和G2是极大边连通的且δ1≥2，δ2≥2，那么G1(×)G2是超级边连通的.
　　(5)设D=Cm(×)Cn且m，n≥3，则λ'(D)=14.
　　在第三章，我们研究了强乘积有向图的限制弧连通度.主要结果如下:
　　(1)设Di(i=1，2)是一个阶为ni的非平凡强连通有向图，且弧连通度为λi.令D=D1(×)D2，则λ'(D)≤min{ξ(D),λ2(n1+|A(D1)|),λ1(n2+|A(D2)|)}.
　　(2)设D1是一个非平凡的强连通有向图，且|V(D1)|＞2，δ和λ分别表示D的最小度和弧连通度.如果δ+=δ-=δ，那么λ'((→C)2(×)D1）=4λ.

目录

摘要

引言

第一章 预备知识

第二章 强乘积图的限制边连通度

§2．1 相关概念和结论

§2．2 准备工作

§2．3 主要结论

第三章 强乘积图的限制弧连通度

§3．1 相关概念和结论

§3．2 主要结论

结束语

参考文献

研究成果

致谢

个人简况及联系方式

声明