【摘 要】
：
图G的反馈数f（G）是使得G不含圈所需要移去的最小顶点数目。图的反馈数问题在很多领域中同样具有重要的应用价值,比如：在操作系统中资源分配策略以避免死锁的问题；人工智能中的受限满足和贝叶斯推论问题；同步分布式系统中的独占学习问题等都可以转化为图的反馈数问题来研究。但是求解一般图的反馈数已经被证明是NP-hard问题,目前只能得到一些近似算法,并且只有有限几种特殊图得到了反馈数的上界或下界。
论文部分内容阅读
图G的反馈数f（G）是使得G不含圈所需要移去的最小顶点数目。图的反馈数问题在很多领域中同样具有重要的应用价值,比如：在操作系统中资源分配策略以避免死锁的问题；人工智能中的受限满足和贝叶斯推论问题；同步分布式系统中的独占学习问题等都可以转化为图的反馈数问题来研究。但是求解一般图的反馈数已经被证明是NP-hard问题,目前只能得到一些近似算法,并且只有有限几种特殊图得到了反馈数的上界或下界。 广义de Bruijn网络GB（d, n）是由经典的de Bruijn网络发展出的一种网络结构,它在继承了de Bruijn网络诸如小直径,高连通性及其简单路由等优点的同时,克服了deBruijn网络的结点数目限制,将de Bruijn网络扩充到任意结点。这使得广义de Bruijn网络GB（d, n）成为一种非常适合计算机网络的拓扑结构。所以研究广义de Bruijn网络的反馈数具有重要意义。 本文针对广义de Bruijn网络GB（d,n）,设计了一种采用计算机算法中分支限界、回溯思想与并查集结构结合的算法来构造GB（d,n）的反馈点集并寻找规律,将计算机构造结果与数学推理证明相结合,确定了广义de Bruijn网络GB（d, n）的反馈数f（d,n）的上界为：
其他文献
太赫兹波是指频率0.1THz到10THz的电磁波,在电磁波谱中位于红外波段和微波波段之间。以前由于受到缺少产生和探测手段的限制,人们对这个波段的了解非常的有限。现在人们开始对这个特殊的空白处开始研究与探讨,但是产生太赫兹波是THz技术的关键,而非线性光学差频及和频产生太赫兹波可以在没有阈值、低成本的情况下进行,这是这种方法的优点。所以本论文主要论述了差频及和频产生太赫兹波的有关问题。本论文的主要内
研究了Al、Cu两种元素以及热处理工艺对模具钢组织,热导率,腐蚀行为,力学性能的影响规律,以期通过成分设计和热处理获得具有高热导率,尤其是高温高热导率,低成本的模具钢。当Al含量为0.37 wt.%时,热处理后模具钢的组织主要是板条回火马氏体,硬度有所提高。当Al含量提高到1.34 wt.%时,热处理后的组织转变成了回火马氏体-铁素体两相共存,而且硬度明显降低。Al含量增加会降低模具钢在各测试温度
选区激光熔化成型（Selective Laser Melting,简称SLM）工艺制备随形冷却水道模具日益成熟,材料的热导率成为了限制随形冷却模具生产效率的另一个关键因素。针对目前选区激光熔化成型用模具钢材料热导率普遍较低的问题,本文基于低碳低合金化的设计思路,结合Jmat-Pro热导率预测结果设计了6种相同碳含量,不同合金元素含量的选区激光熔化成型用高热导率模具钢。研究对比了6种新型模具钢的组织
对新型Cr3型压铸模具钢进行1 000～1 100℃淬火+2次450～640℃回火处理,使用硬度计、光学显微镜、冲击试验机对试验钢的显微组织、硬度和冲击性能进行分析。结果表明:不同温度淬火态试样的组织均主要为马氏体和未溶碳化物,晶粒尺寸随淬火温度的升高而增加,硬度则先增加后略微降低;1 030～1 080℃淬火+回火后,试样的硬度和冲击功随回火温度的升高均先增后降,在480～520℃之间回火时二次
本文研究了建筑产业互联网平台A公司的发展战略问题。A公司致力于整合建筑行业的人、机、料、法、环的全要素和全过程的平台公司,致力于将建筑行业和互联网、物联网、大数据、5G等新技术相融合并获取自身的商业价值。作为成立国内最早的建筑产业平台公司之一,A公司在成立了五年之际,出现了盈利模式不清晰、关联交易过多、人才流失、战略方向不清晰等问题,严重影响了A公司的健康持续发展。本文分析整理了五十多篇国内外文献
核心素养时代，道德与法治教学和试题命制应从知识立意、能力意转变为素养立意。因此，研究新课标指引下的道德与法治素养立意命题，对于深化义务教育教学改革、巩固“双减”成果具有重要意义。具体来看，命题的素养立意要通过育人功能、开放任务、多元素材及学科大概念等呈现出来。
基于ARM嵌入式系统的GPS接收机在军事领域和民用领域的都具有广泛的应用前景。本文依托实验室单频GPS接收机系统的在研项目,开展基于ARM嵌入式系统的导航解算相关算法研究,并通过仿真和实际应用验证了算法的可行性和有效性。作为软件接收机的重要组成部分,对导航解算模块的工程化研究,不仅对GPS接收机的开发具有重要意义,而且能够为其他卫星接收机的研制提供理论依据和开发经验。 首先,详细介绍了G
随着各种新式武器的不断发展和广泛应用,普通的导航系统无法满足高精度和高可靠性的要求。本论文主要针对如何进一步提高组合导航系统的实时定位精度和可靠性这一问题进行了深入的研究,研究内容包括以下几个方面: 1通过对捷联惯导系统原理的研究,建立了指北方位捷联惯导系统力学编排方程,推导了其误差方程并建立了惯性元件的误差模型,而且对捷联惯导系统做了仿真,包括陀螺仪、加速度计以及载体速度、位置和姿态等
曲面上的特征线具有很好的几何背景。特征线,即曲面上曲率变化剧烈的曲线,是曲面特征的重要标志。由于特征线及其子集在诸如图像分析,人脸识别,曲面分割,网格光顺以及网格补洞等众多领域都有很广泛的应用,因此鲁棒的提取出特征线通常是一件很重要的事情。 近期出现了很多在密集三角网格上提取特征线的算法,而精确的估算三角网格上的离散主曲率是提取特征线的关键所在。估算主曲率的方法有很多,如全局拟合估算主曲
偏微分方程解的存在性和多重性的研究,是偏微分方程理论的重要组成部分。研究带有边值条件的偏微分方程解的存在性和多重性,是偏微分方程理论研究的重要课题。 本文研究了在有界区域上,满足Dirichlet边界条件的一类非线性抛物型方程Lu-Dtu+g（u）=f（x,t）方程解的多重性,同时也讨论了方程解的多重性与非线性扰动项之间的关系。 第一部分,引言。 第二部分,介绍本文将