论文部分内容阅读
图G的边等周问题是指在图G中找到m个点构成的顶点子集,满足从图G中分离出此集合所需要删除的边数是在所有从图G中分离出来任意m个顶点子集所需要删除的边数最少的.图的边等周问题自1964年Harper提出后,在网络可靠性连通度参数估计,图嵌入边阻塞数和全线长参数研究,光网络波分复用技术波长估计以及布尔函数势函数研究中得到了广泛应用.给定一个连通图G =(V,E)和正整数h≤(?)｜V(G)|/2(?),abrega和Foil在1996年首次提出的h-extra边连通度的概念(有时也叫h-限制性边连通度).图G的h-extra边连通度,如果存在的话,记为λh(G),定义为可以删除的最少的边数满足删除这些边图G不再连通,每个连通分支至少有h顶点.本文主要以可用字典序提供边等周问题最优解的图为中心,以h-extra边连通度和图嵌入时边阻塞数和全线长参数的估计为背景展开研究.在第二章中研究了字典序提供幂图边等周问题最优解的情况下,利用数字表示理论和δ(G)-序列精确地给出此时幂图的边等周问题的优解的显示表达式.作为应用,分别研究了以n-维折叠立方体FQn,n-维一一对应连接互连网络Bn和3-元 n-方体Qn3为并行分布式网络计算网络的拓扑结构的h-extra边连通度问题.第三章主要研究FQn的h-extra边连通度λh(FQn).由于FQn具有N= 2n个顶点,λh(FQn)对任意的1≤h<≤2n-1都有定义.我们研究了以下三种情况:(1)当n>6,1 ≤ h≤2(?)n/2(?)+1时,计算λh(FQn)的精确值和确定λh-最优的问题.该结论包含若干当h ≤ n时的已知结论.(2)当2(?)n/2(?)+r-lr≤h≤2(?)n/2(?)+r时,得到λh(FQn)为((?)n/2(?)-r+ 1)2(?)n/2(?)+r,其中r = 1,2,…,(?)n/2(?)-1,当n是奇数时,设lr= 3 当n是偶数时lT=22r+1-2/3.(3)当1≤h≤2n-1时,设计出一个O(log2(N))算法,计算λh(FQn)的精确值和确定λh-最优的问题.该算法使得λh(FQn)的问题完整解决.第四章主要研究Bn的h-extra边连通度λh(Bn).我们研究了以下两种情况:(4)当h≤2n-1时,找到了关于h的满足λh(Bn)=(n-c)2c的充分必要条件,其中c为非负整数c≤ n-1,该结论包含若干当1 ≤ h ≤ 2[n/2]+1和[2n-1/3]≤h ≤ 2n-1时的已知结论;(5)当1≤h≤2n-1时,也设计出一个O(log2(N))算法,计算λh(Bn)的精确值和确定λh-最优的问题.该算法使得λh(Bn)的问题完整解决.第五章研究了 3-元n-方体网络当1 ≤ h≤3[n/2]和h = 3c,0 ≤ c ≤ n-1时,λh(Qn3)的精确值和λh-最优的问题,该结论包含若干当h≤3时的已知结论.在第六章研究了当把彼此不同构的n-维一一对应连接互连网络Bn嵌入在一条路上时,具有共同的最小的边阻塞数EC(Bn,P2n)=[2n+1/3],共同的最小全线长WL(Bn,P2n)= 22n-1-2n-1.并得到在路上能够达到最小的边阻塞数的边的集合构成了一个康托集.