【摘 要】
：
对于一个给定的简单图G=（V,E）,F是图G中顶点集的一个子集,若由点集V\F构成的导出子图不存在回路,则F是该简单图的反馈点集,若F的阶数最小,则F是该图的最小反馈点集。记f（G）表示图G的最小反馈点集的阶数,即图G的反馈数。 图的反馈数问题是图论研究的一个重要分支,图的最小反馈点集问题有着重要的应用背景。它能有效的解决操作系统中的死锁问题,有效的保证网络的通信质量,避免网络传输中的广
论文部分内容阅读
对于一个给定的简单图G=（V,E）,F是图G中顶点集的一个子集,若由点集V\F构成的导出子图不存在回路,则F是该简单图的反馈点集,若F的阶数最小,则F是该图的最小反馈点集。记f（G）表示图G的最小反馈点集的阶数,即图G的反馈数。 图的反馈数问题是图论研究的一个重要分支,图的最小反馈点集问题有着重要的应用背景。它能有效的解决操作系统中的死锁问题,有效的保证网络的通信质量,避免网络传输中的广播风暴,保障网络性能等等。 求解一般图的最小反馈点集问题已被证明是NP-困难问题。对于一般图,很难给出一个比较精确的求解算法,只能给出其最小反馈点集的一个近似算法。近年来,很多反馈数的研究都集中在一些特殊的互联网络图上,如超立方体图,折叠立方体图,星图,蝶图,线图等等。 本文通过计算机方法与数学推理相结合的方法,对（n,k）-Star星图Sn,k与（n,k）-Arrangement安排图An,k的反馈点集进行研究,根据其图的性质,得到二者的反馈数下界：及 对于Sn,k,本文给出了当k=2与k=3时的反馈数及最小反馈点集的构造方法。 对于An,k,本文给出了k=2时的反馈数及最小反馈点集的构造方法。
其他文献
本文主要对一类具有Dirichlet边值问题的半线性椭圆型方程组进行讨论,研究正解的存在性和对称性,将文献[1]中的结果进行了推广,其结果与一般的无界区域上椭圆型方程组的结果形成了对比,得到了较好的性质,并且采用对偶变分方法及山路引理得出方程组正解的存在性,应用移动面方法证明了正解的对称性。 第一部分引言 第二部分本文的主要结果 第三部分主要结果的证明 第四
土地信息调查是土地管理中重要的基础工作,是我国土地利用现状数据的有效来源。传统的土地信息调查手段需要耗费大量的人力、物力和财力,且工作效率低下。遥感技术、地理信息系统技术和全球定位系统技术的发展,以及高分辨率卫星影像的出现,为土地信息的调查提供了高效的信息来源。 本文是以泰来县为研究区域,针对其SPOT5遥感数据,对土地信息提取技术进行研究。从控制点数据、重采样方法、正射校正方法等方面对
在不套匹配的线性表示中,弧与弧之间有交点,叫做交叉点,本文主要目的就是对不套匹配中的交叉点进行计数。组合计数的一种常用解决办法就是建立与某种组合事物之间的双射,利用该组合事物已有的计数结论间接得到所求问题的计数。本文也采用了双射的方法,建立不套匹配关于统计量交叉点与Dyck path关于统计量面积之间的双射,通过逆序的概念将二者联系起来。由于Dyck path的计数为Catalan数,根据Cata
非线性科学是非线性领域中的一门学科,混沌是其中的一个重要组成部分。本文主要研究了混沌系统和超混沌系统的几种同步与反同步,并通过理论推导加以证明,数值模拟表明了这些方案的有效性与可行性。本文主要工作如下： （1）采用自适应控制法,研究了参数未知的混沌系统的多开关同步问题。基于Lyapunov稳定理论设计了不同开关状态下的控制器和参数更新规则,证明了一类响应系统的不同状态变量可与驱动系统的状
胰岛素（insilin）和类胰岛素多肽（insulin-related peptides）是调节生长和代谢过程中主要的激素,在脊椎动物和非脊椎动物中均发现了类胰岛素多肽,包括哺乳动物、原索动物、线虫、软体动物和昆虫。这些激素通过类似胰岛素受体（insulin receptor）的异源四聚体跨膜受体酪氨酸蛋白激酶相互作用而发挥其功能。目前,国内外对胰岛素结合蛋白（insulin-related bi
背景与目的： 肿瘤干细胞学说这一概念的提出距今已有30多年的历史,该学说认为肿瘤组织中存在极少数具有自我更新和分化潜能的肿瘤细胞,并且是肿瘤增殖、生长、转移和复发的根源。1992年Reynolds对小鼠脑细胞的研究提出了神经干细胞（Neural stem cells, NSCs）概念,1997年Mckay在Science上发表NSCs的文章得到了公认。而2003年Singh从不同病理类型
粗糙集模型和邻域系统模型是粒计算中两种不同的模型,粗糙集利用不同的关系来建立知识粒,在知识粒的建立过程中,属性的重要程度是不同的,所以属性的约简是粗糙集理论中一类非常重要的问题,传统的方法是基于辨识矩阵.本文首先研究了邻域系统及其性质,得到了邻域系统形成拓扑空间的条件。基于邻域系统的粗糙集模型,给出了关系邻域系统中属性是可约元的充分必要条件,并利用关系邻域系统中所形成的拓扑得到优势关系下属性约简的
近年来,随着人类基因图谱的绘制完成,人类由基因组时代步入后基因组时代。海量激增的蛋白质数据逐渐成为这个时代的特征,生物信息学研究发现蛋白质的功能和结构与亚细胞位置有很大关系,蛋白质转运到不同的位置能发挥不同的作用,在后基因组时代急需一种根据亚细胞的定位来高效地分析蛋白质功能的方法。 通过建立生物模型的方法来提取蛋白质特征信息成为研究的关键,其中氨基酸模型以它的简易性得到了广泛应用,但这种
探讨妊娠期糖耐量异常孕妇的产科门诊护理干预效果。选取来我院就诊的86例妊娠期糖耐量异常孕妇，随机分为观察组和对照组。对照组采用常规护理，包括临床监测、健康教育等;观察组采用产科门诊护理干预，如心理、饮食、运动等多层面的护理干预，对比两组孕妇护理后的血糖变化和预后情况。干预前，两组孕妇的空腹血糖及餐后2 h血糖经对比差异不显著（P＞ 0.05）;干预4周后，观察组的空腹血糖及餐后2 h血糖均显著低于
Korteweg-de Vries（KdV）方程是一类非常重要的非线性偏微分方程,在很多领域中都有重要的应用,其求解方法是国内外研究的热点问题之一.最近几年来,径向基函数（RBF）在微分方程求解中发挥了重要的作用,而Multiquadric（MQ）函数是一类重要的径向基函数.本文利用MQ函数拟插值方法,讨论了带有空间变量三阶导数的KdV方程的一种数值解法.由于这种方法不需要求解线性方程组,所以本文