论文部分内容阅读
近三十年，随着计算机科学的迅猛发展，图论作为一门新兴的交叉学科也得到长足的进步.其中，发展最快的分支之一当数控制参数的研究.距离控制参数既是对经典控制参数的推广，也是度量网络性能的重要参数.在数学的其他学科，理论计算机科学，运筹学，化学，生物学和社会学的研究中也有相当重要的作用.这些参数自Chang和Nemhauser(1984)，Hattingh和Henning(1994)，以及Flandrin和Li(1994)提出以来，除少数结果外，研究进展比较慢.其原因可能有两个：一是这些概念还不为众多人所了解；二是在于确定一般图的经典控制参数问题已经是NPC的，所以距离控制参数的研究难度是大于经典控制参数的.对距离控制参数进行深入研究，并利用它们来进一步揭示网络的结构性质，分析它们的性能是有很大的理论和应用意义的.
本文研究的主要内容就是图中的距离控制数问题.全文共分五章.主要得到了以下几个结果：
第一章首先给出距离控制数的一个更优上界：对于任何给定的正整数k，令G是一个阶数为n(n≥k+1)，最大度为△=△(G)的连通图，则γk(G)≤[n-△+k-1/k]；其次应用概率方法给出距离控制数，连通距离控制数的上界：对于一个阶数为n，最小度为δ的非平凡连通图G，有γk(G)≤n1+1nq/q，γck(G)≤(1+0δ(1))nlnq/q，其中，q=m(δ+1)+2-t，m=[k/3]和t=3[k/3]-k.
第二章是本文的主要部分.共分为两部分，主要讨论了距离控制数和其他图论参数之间的关系.
1.给出图中连通距离控制数和距离不可约数之间的关系：对于正整数k≥2，G是irk(G)≥2的连通图，则γck(G)≤{5/2iγk(G)k-3k+2,max{(2k+1)iγk(G)-2k,5/2iγk(G)k-7/2k+2}，若iγk(G)是偶数；若iγk(G)奇数.并且上界是可以达到的.
2.给出图中距离控制数和平均距离之间的关系：令G是阶数为n的连通图.当k控制数满足γk≤[n/2k+1]时，则有μ(G)≤{n+1/3-(n-(2k+1)γk)(n-(2k+1)γk+2)(2n+(2k+1)γk-7)/6n(n-1)若γk≤n/2k+1和n-γk是奇数；n+1/3-(n-(2k+1)γk)(n-(2k+1)γk+2)(2n+(2k+1)γk-7)-3((2k+1)γk-3)/6n(n-1),若γk≤n/2k+1和n-γk是偶数；n+1/3若γk=[n/2k+1].}当k控制数满足γk＞[n/2k+1]，且(2k+1)γk-n≡t(modk)时.一方面，若γk-n-t是偶数，则有μ(G)≤n+1/3-B/6n(n-1)[((2k+1)γk-n-t-2k)(C-2(k+1))+3t(D-2)]-2t(k-t)(A+t-k-1/n(n-1))另一方面，若γk-n-t/k是奇数，则有μ(G)≤n+1/3-B-k-1/6n(n-1)[((2k+1)γk-n-t-3k)(C-(k+1))+3t(D+2k)+3(kD+(k-1)t-k(k+1))]-2t(k-t)(A+t/n(n-1))，其中，A=-(2k+1)n-(k+1)(2k+1)γk+t/k，B=(2k+1)(k+1)γk-(k+1)n-(k+1)t/kC=(4k+1)n-(k+1)(2k+1)γk+(k+1)t/kD=(3k+1)n-(2k+1)(k+1)γk-(k-1)t/k.并且这些上界都是可以达到的.
第三章考虑了距离控制临界图，得出这类图的一些新性质：令图G是阶数为n的γk临界图.则n≤(△k(G)+1)(γk(G)-1)+1，且当等号成立时，对于任何x∈V(G)，|Nk(x)|=△k(G)；当γk≥2时，直径diam(G)≤2k(γk-1).特别地，当k=2时，直径diam(G)≤3(γ2-1).
第四章研究广义deBruijn和Kautz有向网络的距离控制数：令n和d是满足d≥2，n≥d的正整数，且令m=[n/1+d+d2].若存在一个顶点x∈V(GB(n，d))满足下面两个方程(d-1)x-(m-e1)≡0(modn)(d2-d)x-(dm-e2)≡0(modn)其中，非负整数e1≤dm，e2≤d2m满足0≤e1+e2≤(1+d+d2)m-n，则γ2(GB(n，d))=m.若存在一个顶点x∈V(GK(n，d))满足下面两个方程(d+1)x+(d+1)m-e1≡0(modn)d(d+1)x+e2≡0(modn)其中，非负整数e1≤dm，e2≤d2m满足0≤e1+e2≤(1+d+d2)m-n，则γ2(GK(n，d))=m.
第五章对本文的工作进行总结，并且提出了准备研究的几个问题.