论文摘要
随着信息网络的飞速发展，许多与之相关的理论性问题越来越引起人们的重视，其中之一即为网络可靠性。通信网络的可靠性分析与高可靠性能网络的设计问题是可靠性研究的核心。图作为网络拓扑结构最有效模型，图的各种连通性指标被先后用来研究网络可靠性问题。通常情况下，网络是连通的，从而代表它的图也是连通的，也就是说，图中任意两点间都存在一条路。但是，有时网络的某个元素被破坏，也就是其对应的图被去掉一些边和点时。这时我们希望被破坏的网络尽可能的连通。图的经典参数边连通度λ（G）是指要使得一个图不连通所需要去掉的最少的边数，点连通度κ（G）是指要使得一个图不连通所需要去掉的最少的点数。边连通度和点连通度是衡量网络可靠性的一个重要参数。作为经典连通度的推广，人们提出了高阶的连通度，例如极大（边）连通的，上（边）连通的，超连通的等。另一方面，笛卡尔积和字典式积是从一些较小的图来构造较大的图的一种有效的方法，从而在设计网络和分析网络方面有着重要的作用。在本文中，主要是研究图的笛卡尔积和字典式积的高阶连通性的问题。我们给出了两个图的笛卡儿积及字典式的积为max-λ，max-κ，super-λ，super-κ及hyper-κ的充分条件，同时证明了其中一些条件也是必要的。此外，对这两种积的局部割集和广义割集的性质也进行了考虑。对于两个图的笛卡尔积，我们有以下的主要结果：（1）如果G1和G2是极大边连通的，则G1×G2是极大边连通的。（2）假设λi≥2或λ1=1，2≤λ2＜n-1。如果G1和G2是极大边连通的，则G1×G2是上边连通的。（3）如果G1和G2是极大连通的，则G1×G2是极大连通的。（4）假设κi≥2或κ1=1，2≤κ2＜n-1。如果G和G是极大连通的，则G1×G2是上连通的。（5）假设κi≥2或κ1=1，2≤κ2＜n-1。如果G和G是极大连通的，则G1×G2是超连通的。（6）若G1，G2满足下列条件之一，则有G1×G2的每一个最小广义割集都是一个局部割集：（a） G和G是极大连通的，并且δ（G1）≥2和δ（G2）≥2，（b） G1（?）K2，2≤δ（G2）＜n-1并且G2（?）K3。对于两个图的字典式积，我们有以下的主要结果：（1）如果X和Y是极大边连通的，则X[Y]是上边连通的。（2） X[Y]是极大连通的当且仅当X是完全图并且Y是极大连通的。（3） X[Y]是上连通的当且仅当X是完全图并且Y是上连通的。（4） X[Y]是超连通的当且仅当X是完全图并且Y是超连通的。（5）如果X是完全图，并且Y的每一个最小广义割集都是一个局部割集，则X[Y]的每一个最小广义割集都是一个局部割集。