导读:本文包含了反馈数论文开题报告文献综述及选题提纲参考文献，主要关键词:Kautz图,反馈集,无圈子图,消圈数
反馈数论文文献综述
张思佳,徐喜荣,杨元生,尹春[1]（2016）在《一种求解Kautz图K(d,n)反馈数的改进算法》一文中研究指出研究了一类重要的互连网络拓扑结构Kautz网络K(d,n)的反馈数.一个图的反馈集是指使得图G不含圈所需要移去的顶点集合,最小反馈集的阶数称为图G的反馈数.反馈集问题是经典的组合优化问题,在电路测试、操作系统解决死锁、波长转换器安装等领域都有重要的应用.确定一般网络的最小反馈点集问题属于NP问题.由于Kautz图在结点规模、路径长度和容错性上的良好性质,因此适合作为构建高效、容错、可扩展的数据中心网络的拓扑结构,被认为是对超立方体网络的挑战而替代成为下一代的并行计算机互连网络之一.本文通过构造一种算法改进了n≥8时Kautz网络反馈数的渐进公式,同时确定了n=9时Kautz网络的反馈数为精确值.(本文来源于《小型微型计算机系统》期刊2016年10期）
徐喜荣,黄亚真,张思佳,董学智[2]（2016）在《广义Kautz有向图GK(3,n)的反馈数的界》一文中研究指出对于给定的图G的顶点集的子集F,如果删除F使得剩余子图是无圈子图,则称子集F为图G的反馈点集。研究了广义Kautz有向图GK(d,n)的反馈点集。令f(d,n)表示广义Kautz有向图GK(d,n)的所有反馈集合中顶点个数最少的集合的个数(即广义Kautz有向图GK(d,n)的反馈数),给出了GK(3,n)的反馈数的上界,即f(3,n)≤n+[5n/8]-[3n/4]-[4n/7]+3。(本文来源于《计算机科学》期刊2016年05期）
张思佳[3]（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≤奇数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)。(本文来源于《大连理工大学》期刊2016-01-05）
尹春[4]（2015）在《Kautz图K(d,n)和Kn(?)del图W(4,n)的反馈数研究》一文中研究指出对简单图G=(V,E),子集FcV,如果由子集VF导出的子图不含圈,那么称子集F是图G的反馈点集,顶点数最小的子集F的顶点数称为图G最小反馈数。反馈数是互连网络拓扑结构图的一个重要参数,它可以用来估计并行处理器计算机的性能。人们重视确定图的最小反馈点集问题研究,是由于在诸多领域内它都具有广泛的应用。例如,波长改变器在光纤网络中的安装问题、广播风暴在网络传输过程中的避免问题以及图的最小反馈点集问题都可以由计算机操作系统避免死锁问题等转化而来。实践表明,图论在设计和分析互连网络方面发挥着不可替代的作用,因为互连网络的结构可以抽象为图。通过对某些特殊互连网络拓扑结构图的研究,为设计出新一代的计算机系统提供更坚实的理论基础。本文主要采用数学归纳法与计算机算法相结合的研究方法,对以下两种类型图的反馈数的界进行研究：首先,对n≥8,本文将Kautz图K(d,n)的反馈数f(d,n)的渐近公式由改进为其次研究了Knodel图W4,n的反馈数f(n),本文提出一种求W4,n的无圈子图的方法,并利用该方法证明了对于任何大于等于18的正整数n,W4,n的反馈数为：(本文来源于《大连理工大学》期刊2015-04-01）
刘聪[5]（2014）在《若干图的反馈数上下界研究》一文中研究指出图的反馈数问题来源于实际问题,在诸多领域如预防计算机死锁,互连网避免广播风暴以及电子电路检测等问题中有着广泛的应用。已经被证明求图的反馈数问题是NP困难问题,研究它对解决一般NP困难问题有借鉴意义。对简单图G=(V,E),子集F属于V,如果从图G中去掉顶点集F及其关联的所有边产生的子图没有回路,则称顶点集F是图G的反馈点集。我们希望反馈点集越小越好,最小的反馈点集称为图的最小皮馈点集,其对应的点的个数称为图的反馈数。交叉立方体CQn和局部扭立方体LTQn是超立方体Qn的两个重要变形,它们都保留了Qn的一些重要性质,如维数都为n时,其均有2n个顶点,n2n-1条边,且均为n-正则图,同时,CQn和LTQn有比超立方体Qn更好的性质,如同样维数的情况下,CQn和LTQn的直径是Qn的一半,正因为这样的优质特性,所以研究超立方体Qn的变形具有重要意义。本文通过构造剩余子图G[V(CQn)F]的极大无圈子图得到极小反馈集,从而得到反馈数的上界的方法,来研究交叉立方体的反馈数问题,并证明了交叉立方体的反馈数为：根据局部扭立方体顶点集合中最后一位字节不同的特点,将其顶点集合划分为两个不相交的子集,并构造极大无圈子图得到反馈数的上界,从而研究局部扭立方体的反馈数问题,并证明了n维局部扭立方体的反馈数为：花图(Flower Snark)及其相关图是叁正则图,花图及其相关图的定义实质是相同的,只是当其维数n是奇数且有n≥5时称之为花图,当n为其他情况时,则生成的图被称为花图的相关图。本文采用计算机搜索与数学证明相结合的方式得到了花图的反馈数的精确值,即：(本文来源于《大连理工大学》期刊2014-04-01）
张思佳,徐喜荣,刘聪,曹楠,杨元生[6]（2014）在《关于局部扭立方体的反馈数》一文中研究指出确定一般网络(或图)的最小反馈点集问题属NP难问题.n维局部扭立方体网络Qltn是n维超立方体网络Qn的变形且是一类重要的互连网络拓扑结构,其拥有的某些性质优于Qn.根据Qltn顶点集合中最后一位字节不同的特点,将其顶点集合划分为两个不相交的子集,通过构造极大无圈子图得到反馈数的上界,并证明了对任意正整数n≥2,存在常数c∈(0,1)使得反馈数为f(n)=2n-1(1-c/(n-1)).(本文来源于《大连理工大学学报》期刊2014年02期）
王健[7]（2013）在《几类互连网络拓扑结构图的反馈数研究》一文中研究指出随着多核技术的发展,计算机多核处理器的片内互连问题成为系统设计的关键所在,这一问题吸引了越来越多的工作者致力于互连网络拓扑结构理论的研究。人们希望通过比较这些互连网络拓扑结构图的相关参数(如图的直径,连通度等等)来找出一种较优的互连方式,从而设计出更好的计算机系统。一个图G的反馈点集是图G的顶点子集F满足图G-F无圈。图G的所有反馈点集中含有最少顶点个数的反馈点集称为图G的最小反馈点集,并称它的顶点个数为图G的反馈数。反馈数作为互连网络拓扑结构图的一个重要参数,它可以衡量多核系统的死锁避免恢复能力和避免广播风暴的能力。本文作者主要应用计算机算法与数学构造证明相结合的研究方法,给出了以下几类重要的互连网络拓扑结构图的反馈数上下界的估计。用等价类划分的方法得至(?)(n,k)-star图的反馈数的上下界为：其中θ=min{k-1,n-k-1}。用独立集构造方法得到无向kautz图UK(d,2)的反馈数的上下界：用圈划分方法得到广义彼特森图P(n,k)的反馈数的精确值为：在本文中系统发展了是-部图的叁分离集构造方法,用该方法得到了冒泡排序图Bn、广义超立方体Q(d1,d2,…,dn)和扩展超立方体EQn,k的反馈数的上界,其中冒泡排序图Bn的反馈数的上下界为：此外,本文还给出了交错群图AGn、k正则图和是正则二部图的反馈数的上界。(本文来源于《大连理工大学》期刊2013-04-01）
林馨[8]（2012）在《部分具有最小反馈数的叁正则平面网络的结构》一文中研究指出本文讨论了n为奇数时具有最小反馈数的2n阶叁正则平面网络的结构,并结合算法验证了该图类在开关变换下是连通的。(本文来源于《数字技术与应用》期刊2012年06期）
林馨[9]（2012）在《具有最小反馈数的叁正则平面网络的结构》一文中研究指出讨论了具有最小反馈数的2n阶叁正则平面网络的结构,并验证了该图类在开关变换下是连通的。(本文来源于《福建电脑》期刊2012年05期）
徐喜荣,曹楠,吉日木图,董学智,王保才[10]（2011）在《关于折迭超立方体的反馈数》一文中研究指出研究了一类重要的互连网络拓扑结构折迭超立方体网络Qfn的反馈数.设F为Qfn的反馈集,通过构造剩余子图G[V(Qfn)-F]的极大无圈子图得到极小反馈集,从而得到反馈数的上界,用此方法研究折迭超立方体网络Qfn的反馈数问题.根据n维折迭超立方体网络的性质,提出一种新的方法构造无圈子图,改进了已有的n维折迭超立方体网络的反馈数的上界.结果表明,当n为奇数时构造的Qfn+2的无圈导出子图的整体连通性能与已有结论中构造的Qn中无圈导出子图R∪Qfon是一致的.(本文来源于《大连理工大学学报》期刊2011年05期）
反馈数论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
对于给定的图G的顶点集的子集F,如果删除F使得剩余子图是无圈子图,则称子集F为图G的反馈点集。研究了广义Kautz有向图GK(d,n)的反馈点集。令f(d,n)表示广义Kautz有向图GK(d,n)的所有反馈集合中顶点个数最少的集合的个数(即广义Kautz有向图GK(d,n)的反馈数),给出了GK(3,n)的反馈数的上界,即f(3,n)≤n+[5n/8]-[3n/4]-[4n/7]+3。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
反馈数论文参考文献
[1].张思佳,徐喜荣,杨元生,尹春.一种求解Kautz图K(d,n)反馈数的改进算法[J].小型微型计算机系统.2016
[2].徐喜荣,黄亚真,张思佳,董学智.广义Kautz有向图GK(3,n)的反馈数的界[J].计算机科学.2016
[3].张思佳.几类重要互连网络拓扑结构图的反馈数研究[D].大连理工大学.2016
[4].尹春.Kautz图K(d,n)和Kn(?)del图W(4,n)的反馈数研究[D].大连理工大学.2015
[5].刘聪.若干图的反馈数上下界研究[D].大连理工大学.2014
[6].张思佳,徐喜荣,刘聪,曹楠,杨元生.关于局部扭立方体的反馈数[J].大连理工大学学报.2014
[7].王健.几类互连网络拓扑结构图的反馈数研究[D].大连理工大学.2013
[8].林馨.部分具有最小反馈数的叁正则平面网络的结构[J].数字技术与应用.2012
[9].林馨.具有最小反馈数的叁正则平面网络的结构[J].福建电脑.2012
[10].徐喜荣,曹楠,吉日木图,董学智,王保才.关于折迭超立方体的反馈数[J].大连理工大学学报.2011