【摘 要】
：
Steiner距离问题是经典的组合优化问题,在现代生产生活中应用十分广泛.设G是一个至少有两个顶点的连通图,S是G的一个非空顶点子集,点集S的Steiner距离dG(S)是指包含S的连通子图的最小边数.图的Steiner k-Wi-ener 指标和 Steiner Harary k-指标分别定义为 SWk(G)=∑S(?)V(G,)|S|=kdG(S)和SHk(G)∑S(?)V(G),|S|=k
论文部分内容阅读
Steiner距离问题是经典的组合优化问题,在现代生产生活中应用十分广泛.设G是一个至少有两个顶点的连通图,S是G的一个非空顶点子集,点集S的Steiner距离dG(S)是指包含S的连通子图的最小边数.图的Steiner k-Wi-ener 指标和 Steiner Harary k-指标分别定义为 SWk(G)=∑S(?)V(G,)|S|=kdG(S)和SHk(G)∑S(?)V(G),|S|=k 1/dG(S).这两类指标都是定义在距离的基础上的拓扑指标,在化学领域,通过图的拓扑指标可以反映出分子的结构特征和性质,方便学者更有利的分析和解决相关问题.用/(G)表示图G的一个不变量,G为G的补图,Nordhaus-Gaddum问题是确定/(G)+/(G)和/(G)·/(G)的界.本文的主要内容是对给定直径的树的SWk(G)进行研究,并且基于图的SHk(G),分析图G的Steiner Harary k-指标的Nordhaus-Gaddum类型结果.本文结果如下:首先,研究直径分别为3,4,n-2的树的Steiner k-Wiener指标,其结论如下:(1)SWk(Tn,3)=(n-2)(n-1 k-1)+(n k)-(a+2 k)-(n-a-2 k),(2)SWk(Tn,4)=(n-l-1)(n-1 k-1)+l(n k)-∑i=1 l(ai+1 k)-∑i=1 l(n-ai-1 k),(3)SWk(Ti)=(k-1)(n k+1)+(k-2)(n k)+(n-1 k-1)+i(n-1 k-1)-(k-1)(i k)+(n-i)(n-i-1 k-1)(k-1)(n-i k).其次,得到SHk(G)指标Nordhaus-Gaddum类型结果的上下界,3 ≤k≤ n.特别地,通过研究发现,当k=n,n-l以及k=3时,其SHk(G)指标Nordhaus-Gaddum类型结果的界会得到进一步的加强.即当k=n时,可直接得到SHn(G)与SH(G)的和与乘积的具体值分别为2/n-1和1/(n-1)2.当k=n-1时,得到具有一定条件图G的SHn-1(G)指标的Nordhaus-Gaddum类型结果的具体值或上下界.对图的阶数和图或其补图的直径有一定的限制,进而改进了SHk(G)指标Nordhaus-Gaddum类型结果中k=3时的界,即得到SH3(G)与SH3(G)的和与乘积紧的上下界,并给出例子说明其结果是不可改进的.
其他文献
本文采用形态特征、生理生化特征、化学分类特征、16S rRNA基因序列系统发育分析和分子分类特征相结合的多相分类方法对分离自红树林环境的稀有放线菌菌株210417进行分类学研
人类的语言有着多种功能,比如:分类、总结、归纳等功能,“比较”和上述三种功能一样是语言基本的功能之一。“比较”又可分为平比、差比。虽然俄语、汉语以及韩语这三种语言都有表达“差比”的手段,但他们之间既有相同之处,又有不同之处。因此,本文将运用对比语言学的理论、邦达尔科的三角形框架理论,利用功能语言学的从“意义-形式”的原则、共时对比原则,使用俄罗斯国家语料库,北京大学中国语言研究中心建立的CCL语料
目的:在医学研究中,对于存在系统结构特征的实际资料,往往采用混合线性模型进行效应估计,但是对于进一步探索患者亚组与治疗方式间复杂的(高阶)交互作用时则效率较低。而决策树模型作为数据挖掘方法中的一种预测模型,具有较强的探索性能,可以同时分析多个预测变量,并且可以自动检测预测变量之间潜在的关系,对于医学疗效评价具有重要的意义。但是对于系统结构数据,传统CART回归树模型估计效率低下,模型构建准确性较低
多目标跟踪领域是目前机器学习领域中一个热门的研究方向,其研究具有重要的军事及民用价值。尤其是随着军事任务的复杂化和多样化,使得多目标打击成为一个重要的发展方向,更
“印太”一词作为地理与地缘政治学概念由来已久,但对其赋予地缘战略的涵义则是从20世纪60-70年代开始,且一开始主要由澳大利亚学者来倡导,影响力有限。2010年1月12日,美国时任国务卿希拉里·克林顿(2009年1月21日——2013年2月1日,第67任)在夏威夷发表了题为《美国在亚太的参与》的演讲。希拉里在她的演讲中表示:美国将会继续深化与印度在太平洋的合作,因为其对印太盆地在全球贸易和商业中的
背景:神经精神性狼疮(Neuropsychiatric systemic lupus erythematosus,NP-SLE)作为系统性红斑狼疮(systemic lupus erythematosus,SLE)一种严重和复杂的并发症,约在95%的狼
为配合油气资源勘探开发的需要,深入挖掘川东北地区油气资源潜力和规避勘探风险,发现潜在有利油气勘探新区块,需要对川东北地区的石炭系黄龙组的地层分布、沉积相特征、储层特征及主控因素等基本问题开展新的研究,从而为川东北石炭系老气田深化勘探提供理论指导。龙会-蒲包山地区作为川东北十分重要的石炭系天然气勘探区,近期在川东北石炭系低渗储层分布区的龙会场构造获得了石炭系勘探新进展;但龙会-蒲包山地区石炭系受多期
目的用线栓法制备的大鼠大脑中动脉栓塞(MCAO)模型,建立HPLC法测定血浆样本中丹参素与川芎嗪的血药浓度测定方法,尾静脉注射给药后进行相关药动学研究,选取乳酸脱氢酶(LDH)为
肠道病毒71型(Enterovirus71,EV71)属于小RNA病毒科肠道病毒属,是引起婴幼儿手足口病主要病原体之一,其感染除引发手足口病症状外,还具有神经噬性,少数的重症感染者会出现严重的中枢神经系统并发症,如无菌性脑膜炎、脑干脑炎、神经源性肺水肿和急性迟缓性麻痹等。但EV71的致病机制尚不完全明确,关于EV71如何侵入神经系统并造成神经损伤的通路也还不清楚,有研究认为EV71病毒可能通过血-
本文考虑具非线性阻尼的非等熵p-方程组初边值问题解的大时间渐近行为。具非线性阻尼的非等熵p-方程组可以用来描述穿过多孔媒介的可压流体的运动模型,具有丰富的物理意义。利用能量方法和细致的能量估计,我们证明了四分之一平面上具非线性阻尼的非等熵p-方程组的初边值问题解渐近收敛到相应的抛物方程的解,并且得到了更好的L∞收敛估计,与Pan(Michigan Mathematical Journal,2001