【摘 要】
：
设T=(V，E；f，w)是顶点与边都赋权的树，f：V→R，w：E→R．由于T中的任意两个点u，v只有唯一的一条路连结，设为P=vv…v，这里v=u，v=v，则规定u，v间的距离为d(u，v)=∑f(v)+∑w(v，v+1)或者d(u，v)=∑f(v)+
论文部分内容阅读
设T=(V，E；f，w)是顶点与边都赋权的树，f：V→R<+>，w：E→R<+>．由于T中的任意两个点u，v只有唯一的一条路连结，设为P<,uv>=v<,1>v<,2>…v<,l>，这里v<,1>=u，v<,l>=v，则规定u，v间的距离为d(u，v)=∑<,i=l>f(v<,i>)+∑<,i=1>w(v<,i>，v<,i>+1)或者d(u，v)=∑<,i=1>f(v<,i>)+∑<,i=1>w(v<,i>，v<,i+1>)，其中后一种距离d(u，v)定义的前提是v将作为控制集或中心集合中的顶点．本论文研究了这种赋权树中两种距离下的r-控制集问题和k-中心问题．对这种赋权树上的两种距离的r-控制集问题，分别给出了时间复杂性为O(n)的最优算法；而对这种赋权树上的两种距离的k-中心问题分别给出了时间复杂性为O(n<2> log n)的最优算法。
本文包括以下几章：
第一章：回顾了问题的由来，给出了到目前为止的一些研究成果以及本文的一些结果。
第二章：给出了文中所出现的定义、概念和符号。
第三章：讨论了赋权树状网络中的两种距离定义下的r-控制集问题及其最优算法。
第四章：讨论了赋权树状网络中的两种距离定义下的k-中心问题及其最优算法，并研究了r-控制集问题和k-中心问题的关系。
文章最后给出了相关结论以及未来的研究方向。
其他文献
切换系统是一类重要的混杂系统，它有着十分广泛的实际背景。切换系统中连续动态与离散切换信号之间的相互作用使之具有十分复杂的动态行为和丰富的研究内容，这又为信息、控制及
三维形状恢复是计算机视觉领域的一个经典问题，它通过明暗、纹理、立体视觉等线索从一幅或多幅照片恢复目标物体表面高度。作为形状恢复的关键技术之一，基于明暗的形状恢复根据
请下载后查看，本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
Since most of the available component-based software reliability models consume high computational cost and suffer from the evaluating complexity for the softwa
在新课程的改革背景下,如何提高数学课程教学的效果是一个值得研究的问题.目前,很多教师都在寻求适应新课程要求,提高数学课程教学效果的方法.而新课程的要求主要有三个:除旧
以富含花青素的紫山药‘蓣引紫006’为材料,克隆得到花青素生物合成途径中关键酶基因DaF3H(KF561995),其序列全长为1 325 bp,最大开放阅读框为1 089 bp,编码362个氨基酸。DaF
最小支撑树问题是一类经典的组合最优化问题，它已经有很好的解决方法．本文重点研究在支撑树上加点的相关最优化问题，这是对最小支撑树问题的推广．本论文详细讨论了这类在树上加点
请下载后查看，本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
在计算机科学、信息科学的推动下，半群代数理论经过多年的发展，已成为‘代数学’一个独具特色的分支。自半群系统研究至今，正则半群及其子类的研究一直是半群研究的主流方向。近
【摘 要】在人类社会的发展过程中，印刷媒体呈现了人类的思想和精神，对人们的生产和生活产生了巨大的影响。如今新媒体蓬勃发展，印刷媒体受到了巨大的挑战，信息的时效性、海量性、与受众的互动性等方面都不及新媒体。面临新媒体的挑战，印刷媒体必然要提高其核心竞争力，继续发挥它的传统优势、报道的深刻性、印刷媒体的权威性以及纸质媒体所特有的性质，做到在媒体的竞争中长期发展。与此同时，印刷媒体要与新媒体相互结合，取