几类重要互连网络拓扑结构图的反馈数研究

发布时间：2018-05-21 03:37

  本文选题：反馈数 + Flower　； 参考：《大连理工大学》2016年博士论文

【摘要】：图的反馈数问题是在实际应用中提出来的。计算机操作系统中解决“死锁”问题、网络攻击中最小攻击点集问题等都可以转化为在图中求一个最小反馈点集的问题。求图的反馈数问题已被证明是NP困难问题,其每一个进展都十分艰辛。到目前为止,只有少数的图类得到了其反馈数,已经得到反馈数界的图类也不多。本文对与互连网络拓扑结构设计方法(笛卡儿乘积方法、线图方法、Cayley方法)密切相关的几个重要的图类的反馈数进行了研究,分别给出了Flower Snark相关图Jn、Knodel图W△,n。和循环图Gn(1,k)的反馈数、增广立方体AQn反馈数的上下界、局部扭立方体LTQn反馈数的上界以及Kautz有向图K(d,n)反馈数的上界。(1)对Flower Snark相关图Jn、Knodel图W3,n和W4,n、循环图Cn(1,K)的反馈数进行了研究。利用Jn、W3,n、W4,n和Gn(1,k)的循环结构,分别找到了相应的带循环节的无圈子图顶点集的构造方法,基于这些顶点集分别得到了如下结论。①给出了Flower Snark相关图Jn反馈数为：f(Jn)=n+1；②给出了W3,n反馈数：f(W3,n)=(?)；③给出了W4,n反馈数：f(W4,n)=(?)；④ 给出了偶数n≥5+1+2(?)+mod3)且3≤奇数kn/2时的Cn(1,k)反馈数：f(Cn(1,k))=(?)(2) 对增广立方体AQn、局部扭立方体LTQn两种变型超立方体网络的反馈数进行了研究。利用AQn和LTQn顶点递推结构和边集性质,分别构造出了相应的可递推的无圈子图顶点集函数,基于这些函数,分别给出如下结论。①给出了AQn反馈数紧的上下界为：2n-3×2n-3≤f(AQ)≤2n-(2n-2+2(?))；②给出了LTQn反馈数的上界为：f(LTQn)≤2n-1。(3)对有向Kautz图K(d,n)的反馈数进行了研究。给出了Kautz有向图K(d,n)的一种新的反馈点集顶点短表达式模式,基于该模式得到了更小的反馈点集,给出K(d,n)渐进估计从O(dn-4)下降到O(d2)。
[Abstract]:The problem of feedback number of graphs is put forward in practical application. The problem of "deadlock" in computer operating system and the problem of minimum attack point set in network attack can be transformed into the problem of finding a minimum feedback point set in graph. The problem of finding the feedback number of graphs has been proved to be NP-hard, and every progress is very difficult. Up to now, only a few graph classes have obtained their feedback numbers, and there are few graph classes which have obtained feedback number bounds. In this paper, the feedback numbers of several important graph classes which are closely related to the design method of topological structure of interconnection networks (Cartesian product method, line graph method) are studied. The Flower Snark correlation graph Jnn Knodel graph is given respectively. The feedback number of the AQn feedback number of the augmented cube, the upper bound of the LTQn feedback number of the local twisted cube and the upper bound of the LTQn feedback number of the Kautz directed graph are studied. By using the cyclic structure of JnGW _ 3N _ 4N _ 4N and G _ n ~ (1) k), the corresponding construction method of vertex set of circular graph with cyclic nodes is found respectively. Based on these vertex sets, the following conclusions are obtained respectively .1 the Flower Snark correlation graph J _ n feedback number is given as: F ~ (n) J _ n _ n ~ (1) ~ 2 and W _ 3n feedback number: W _ 3n feedback number F / W _ 4n feedback number F: W _ 4N ~ (1 / n ~ 4) mod3) and 3 鈮，

本文编号：1917591