论文部分内容阅读
图经常被用来模拟互联网络.图的Hamilton性和边连通性是与互联网络稳定性紧密相关的两类性质.本文的第二章和第三章研究了图的Hamilton性，第四章到第六章研究了图的边连通性.详细内容如下: 第一章介绍了一些与图相关的基本概念以及论文内容的安排. 第二章首先介绍了Hamilton圈问题的起源和一些经典结果.然后证明了n≥8阶有向图D是Hamilton的若D中每对有公共内邻或公共外邻的不相邻点对x，y有d(x)+d（y）≥5n/2-11/2. 第三章研究了图的一种新的Hamilton性质-k-顺序Hamilton性.1997年NgLenhard和Schultz Michelle提出了k-顺序图、k-顺序Hamilton图和k-顺序Hamilton连通图的概念.我们将这些概念推广到有向图.一个有向图D称为是k-顺序的如果对D中任意k个不同的顶点组成的序列S,D中存在一个顺次经过S中顶点的有向圈.称有向图D是k-顺序Hamilton的如果对于D中每一个k个顶点的序列S,D中存在一个顺次经过S中顶点的Hamilton有向圈.称有向图D是k-顺序Hamilton连通的如果对于D中每一个k个顶点的序列S:v1，…,vk，D中存在一条从v1到vk的Hamilton有向路P使得P顺次经过S中的顶点.我们研究了k-顺序Hamilton有向图的充分条件和必要条件并证明了下面的结果.设D是一个n阶有向图.(1)若对每一对使得uv(∈)A(D)的顶点u,v有d+(u)+d-（v）≥ n+2k-4（n≥4.2≤k≤n/2）,则D是k-顺序的.(2)若D的最小半度δ0(D)≥n/2+k-2（2≤k≤n/2+1）,则D是k-顺序Hamilton的.(3)若D的每对不相邻的点对u,v有d(u)+d(v)≥3n-4,则D是k-顺序Hamilton的当且仅当D是k-顺序的（k≥2）.(4)若对每一对使得uv(∈)A(D)的顶点u，v有d+（u）+d-(v)≥n+2k-4（n≥4，n/4+1≤k≤n/2），则D是k-顺序Hamilton的.另外，我们还研究了局部半完全有向图的k-顺序Hamilton性.证明了强连通k-顺序局部半完全有向图是k-顺序Hamilton的;每个2k强连通圆周可分解的局部半完全有向图是k-顺序Hamilton的，最后，我们研究了k-顺序Hamilton连通有向图的性质和充分条件. 第四章讨论了二部图的k限制边连通性.对于一个连通图G，边集合S(∈)E(G)称为是一个k-限制边割如果G-S不连通并且G-S的每个分支至少包含k个顶点.G的k-限制边连通度λk(G)是指G的一个最小k-限制边割所包含的边数.对两个不相交的顶点集U1, U2(∈)V(G)，用[U1，U2]表示一个端点在U1另一个端点在U2的边的集合.定义ξk(G)=min{|[U,V(G)U]|:U(∈) V(G)，|U|=k≥1且U的导出子图连通}.一个连通图G称为是λk-最优的如果λk(G)=ξk(G).进一步，如果G的每个最小k-限制边割都是由某个连通的k阶子图相邻的边组成，即G的每个最小k-限制边割恰好分离出G的一个k阶连通子图，则称G是超级k-限制边连通的或简记为超级-λk的.设k是一个正整数且设G是一个n≥4阶二部图，X，Y是它的一个二分类.我们证明了(a)如果G有一个饱和X或Y中所有顶点的匹配且对于任意的u,v∈X和任意的u,v∈Y有|N（u）∩N(v)|≥3，则G是超级-λ2的;(b)若G的最小度δ(G)≥n+2k/4,则G是λk-最优的;(c)若最小度δ(G)≥n+2k+3/4,则G是超级-λk的. 第五章定义了与Chen等定义的网络[Applied Mathematics and Computation140(2003)245-254]类似的两类网络.设t，n(t≤n)是两个正整数， G0和G1是两个顶点集分别为V（G0）={a0,…，an-1}和V(G1)={b0，…，bn-1}的互不相交的图.图G(G0.G1:Mt)是一个顶点集为V(G0)∪V(G1)，边集为E(G0)∪E(G1)∪Mt的图，其中Mt={aibj:j-i(mod n)≤t-1.i，j=0,1,…，n-1}.设r.t.n(r≥3.t≤n)是三个正整数， G0,G1,…,Gr-1是顶点集V(Gi)={ai0, ai1,…,ai（n-1）}的r个互不相交的图，且设Mi，i+1(mod r)={aijai+1(mod r)j:j-j(mod n)≤t-1.j，j∈{0,1,…，n-1}},其中i∈{0,1,…,r-1},定义图H=G（G0，G1，…，Gr-1;Mt）是一个顶点集V(H)=V(G0)∪ V(G1)∪…∪ V(Gr-1)，边集E(H)=Mt∪∪r-1i=0 E(Gi)的图，其中Mt=∪r-1i=0Mi，i+1(mod r).许多著名的网络包括超方体，纽方体，递归循环图和m元n方体等都是上面定义的两种网络的特例.我们研究了这两类网络的k(k=2.3)-限制边连通性.特别的，作为结果的应用，我们给出了递归循环图和m元n方体的k(k=2,3)-限制边连通度. 第六章讨论了定向图的超级弧强连通性.一个有向图D称为超级弧强连通的若它的每个最小的弧割都是D中某个顶点的所有出弧或入弧.不包含长为2的圈的有向图称为定向图.设D是一个n阶强连通定向p-部图(p≥2)，δ+(D)和δ-(D)分别为D的最小出度和最小入度.我们证明了若δ+(D)+δ-(D)≥(p-1)(n+2)+1/2p，则D是超级弧强连通的.设u是D中一点.u的半度是d+(u)和d-(u)的最小值，记作d0(u).设D是一个n阶强连通定向图，d01≥d02≥…≥d0n=δ0是D的半度序列.我们还证明了若存在整数k（1≤k≤2δ0）使得k∑i=1（d0i+d0n+i-2δ0）≥k(n-k-1)+2δ0+1，则D是超级弧强连通的.