论文部分内容阅读
图的反馈数问题是在实际应用中提出来的。计算机操作系统中解决“死锁”问题、网络攻击中最小攻击点集问题等都可以转化为在图中求一个最小反馈点集的问题。求图的反馈数问题已被证明是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≤奇数k<n/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)。