图论中的树(四)

6 最小权部分树设G=（V,E）是一个无向连通图,G中每一条线e∈E,有一个实数权w（e）,它可以表示该线的长度,费用或通过该线所需要的时间等。G的一个部分树的权,定义为该树中所有线的权之和。若部分树T的权记为W（T）     

网络中的最优控制树问题

众所周知,从通讯网络建设中提出著名的最优支撑树问题,即在一个赋权连通图中求一个包含所有顶点而权(费用)最小的连通子图(支撑树).进而,在交通、通讯、供销系统的干线设计中,考虑的连线(干线)不一定连接网络的所有顶点,但被连接的顶点必须构成一个控制集,即其余任一顶点都有一条边直接与此主干部分相连.这就提出了最优控制树问题.似乎此问题与最优支撑树问题十分类似,但我们将证明它是NP-困难的,并给出一个分枝定界算法及相关性质.     

一类有容量限制的最优连接问题

以油气收集系统设计为背景,研究如下的网络优化问题,在一个加权有向图G中,根点r代表收集中心,其他顶点代表具有给定容量的油井,每条边的权表示运输距离.问题是求G的一个支撑树,满足容量约束,使得到r的传输半径最小.主要结果是问题的NP-困难性证明及等容量情形的多项式时间算法.同时,讨论一般情形的精确算法及启发式算法.     

复杂网络中连通支配中心性的计算

分析了现实生活中对重要节点的需求背景,对连通的网络模型提出了一种新型中心性评价指标,连通支配中心性。该中心性利用网络连通支配集的"连通"和"支配"两大特性,通过循环构建点导出支配子图的连通支配集,生成一棵支配关系扩展有向树。然后基于各节点在该有向树中的支配层次数,支配数和支配边权值3方面的属性,设计了反映节点支配能力强弱的中心性计算公式。最后以合作关系图为例进行相应实验,发现连通支配中心性比较高的节点不仅构成了网络的骨干网,能较好地维持网络基本形态,而且能桥接几个不同研究分区,起到一定的中介作用,体现了网络中节点的组织控制能力。     

完全赋权树的第n优场址问题

在实际中,有序地求出完全赋权图的第一优,第二优,第n优场址有时是非常必要的。本文对完全赋权树给出了这样的方法,称为n优场址法。并证明了第k优场址必与第一优,第二优,…,第(k-1)优场址相邻。     

赋权有向图最小生成树的表上作业法

每一赋权有向图可用一个赋权表来表示。本文在借助于赋权表而不是赋权有向图本身讨论圈和生成树的基础上,给出了一种求解赋权有向图最小生成树的新方法——表上作业法,证明了方法的最优性。该方法简单易行,借助于计算机Ｓｐｒｅａｄｓｈｅｅｔ软件,如ＭｉｃｒｏｓｏｆｔＥｘｃｅｌ,可很方便地进行大规模复杂问题的求解。     

无线传感器网络中多移动代理分组优化算法

在基于多移动代理的无线传感器网络中,源节点的编组方法是区别于单移动代理系统的核心研究问题。基于跳数的最小生成树原理,提出一种基于最小生成树算法的规划编组方式,通过对无向全连通图中边权值的测量和选取,简单而有效地控制网络中能量消耗与任务延迟间的平衡,从而获得高效的综合性能。最后通过大量的OPNET仿真实验验证了算法的可靠性。

Abstract：

In contrary to the single mobile agent system,the grouping methodology for source nodes is the key issue in multi-agent itinerary planning for wireless sensor networks.A novel approach was proposed based on hop-oriented minimum spanning tree.The scheme achieves flexible trade-off control between energy cost and task duration by dynamically selecting edge weights in the total connected graph.Extensive simulations have shown that the approach outperforms the existing works.     

无冲突可重复网极小活标识的配置

首先给出无冲突可重复网的定义,并证明无冲突可重复网是结构活的.然后将无冲突可重复网的极小活标识的配置化为强连通T_图极小活标识的配置.文[2]虽然给出T_图极小活标识的判断方法,但是对于一个比较复杂的T_图的极小活标识的配置是无法实现的.本文通过求解强连通T_图的m-n+1个线性无关的极小S_不变量的支集,找出m-n+1个线性无关的有向回路组,然后给出构造强连通T_图以任一变迁为根的有向生成树,最后给出配置强连通T_图极小活标识的有效算法.     

无向双环网络等价生成树及仿真研究

提出一种新的研究双环网络G（N;±1,±s）的直径求解模型--等价生成树模型,研究了基于该模型的双环网络G（N;±1,±s）寻径策略,给出了等价生成树模型的仿真算法,并研究了等价生成树模型中与路由相关的一些性质。利用C#作为编程语言对等价生成树的结构模型进行了仿真实现.仿真结果表明,利用该模型不仅可在有限时间内求出G（N;±1,±s）的所有直径,而且可方便地得到源结点到所有其他结点的最短路径。     

连通、几乎局部连通无爪图是完全圈可扩的

设Ｇ是一个图,Ｂ ＝ ｛ｖ ∈Ｖ（Ｇ）｜〈Ｎ（ｖ）〉不连通｝．如果Ｂ是独立集,并且ｖ ∈Ｂ,ｕ ∈Ｖ（Ｇ）, 使〈Ｎ（ｕ） ∪｛ｕ｝〉连通,则称Ｇ是几乎局部连通图．本文证明：连通、几乎局部连通无爪图是完全圈可扩的．     

最小顶点覆盖问题的DNA分子算法

最小顶点覆盖问题是找给定图G中覆盖每条边的最小顶点子集,这个问题即是一个著名的NP 完全问题。给出了基于分子生物技术的图的顶点覆盖问题的DNA算法。算法的关键是数学问题到DNA链的映射,对图中的顶点进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离。依据分子生物学的实验方法,提出的算法是有效和可行的。最后指出了该算法的优点、存在问题及下一步的研究方向。     

数据包络分析在网络容量扩张方案的决策与有效性评价中的应用

给定一个网络G(V,E,-C),其中,V是顶点集合,E是边的集合,-C是边集的容量向量。若要将文中定义的网络容量cap(F)扩张到容量为R的水平,存在n种扩张方案。应用数据包络分析(DEA)方法对n种方案的有效性进行评价,选取相对有效的扩张方案,再根据实际的资源限制选取最优方案。     

求解度约束最小生成树的快速近似算法

针对带有度约束的最小生成树问题,给出了一种快速近似算法.首先给出了快速近似算法的核心思想:在不违反度约束和不形成圈的前提下,每次加入权最小的边.其次给出了实现快速近似算法的具体步骤,并且证明了该算法的计算时间复杂度是图的顶点数的多项式函数,证明了算法的有效性定理.大量的数值试验表明该近似算法性能良好.最后在此算法的基础上,给出了求解TSP问题的一种快速近似算法.     

基于树结构RDF闭包生成算法研究

RDF闭包是提高RDF数据查询效率的一种有效途经,目前大部分闭包生成算法依据推理规则间的触发实现推理,推理规则多次重复使用,闭包生成效率比较低。利用树的层次结构思想,根据RDF(S)语义推理规则的特点,提出基于树的闭包生成算法,将RDF(S)推理规则数据结构化,构造两棵分别对应RDF属性和概念的属性树和概念树,树的节点存储RDF三元组。然后根据映射机制将存储在树节点中的三元组映射为RDF闭包。仿真显示此方法有效地提高了闭包生成效率。     

一种基于语言判断矩阵的群决策方案排序新方法

针对群决策中基于语言判断矩阵形式偏好信息的方案排序问题,提出一种新的排序方法。给出有关语言判断矩阵的完全一致性、满意一致性、LOW A算子及图论的连通图和树等若干定义,得出构造具有完全一致性或满意一致性的语言判断矩阵满足的条件。根据图论的无向连通图理论,给出基于语言判断矩阵的群决策的方案排序方法。通过一个算例说明本文提出的分析方法。     

赋权Hamilton路的DNA计算模型

DNA计算是一种基于生化反应的新型计算方式 ,目前已成为一个非常热门的研究领域。首先简单介绍了DNA分子的结构、计算机理及实现方式。然后 ,在Adleman工作的基础上 ,给出了赋权 (有向与无向 )型Hamil ton路问题的DNA计算模型。通过权值的转换方式 ,指出此模型对于任意实数权值的赋权图均适应。最后 ,指出了该模型存在的问题及进一步研究的方向。研究结果进一步证实了DNA计算的可行性。     

Vague集和熵综合赋权可拓评价模型及其工程应用

工程项目的风险评价是其建设和运营的关键。针对评价过程中指标权重确定问题,构建一种基于Vague集和熵综合赋权的方法,通过Vague集理论设计主观权值的计算方法,结合熵权法求得的客观权值,以偏差平方和最小化为判断标准进行指标最优赋权,在此基础上结合可拓评价法建立综合赋权评价模型并应用于工程项目的稳定性评价中。实例结果表明,综合权值能够合理表征各指标的影响程度,可拓评价模型对储气库稳定性的判断结果符合实际情况,并且能够得出造成储气库不稳定的缺陷指标,便于运营机构进行针对性的整改,该模型可以为工程项目的评价管理提供有效的参考。     

逆一般中心选址问题的算法研究

主要讨论了逆一般中心选址问题的算法研究。对于实例是树且U为整数的情况,逆一般中心选址问题转化为逆中心选址问题。对于实例是一般简单图的情况,本文给出了一个逆一般中心选址问题转化为权重为1的S te iner树问题的拟多项式算法。并对于权w=1的S te iner树问题,本文也给出了一个近似界为43的近似算法。     

反馈系统发展对策生成的顶点赋权反馈图法——-以鄱阳湖区德邦生态能源经济反馈系统发展为例

德邦规模养殖生态能源经济区是国家战略《鄱阳湖生态经济区规划》农业产业区,是要求实现规模养殖和种植循环经济的开发区,是要求实现开发沼气能源减少污染物排放(节能减排) 的低碳生态产业区,是由大学、公司、农户、地方政府等共同参加建设的有普遍意义的创新基地.此规模养种循环与节能减排系统是一个反馈复杂系统, 对此,创建系统动力学三步顶点赋权反馈图的管理对策生成法进行研究. 首先,通过对德邦牧业实地发展进行深入分析,建立了两个增长正反馈环和一个制约负反馈环构成的2005-2009年五个规模养殖生态能源经济区增长制约顶点赋权反馈图,定量揭示现行系统发展的优势和存在的问题. 其次,围绕五个顶点赋权反馈图中两个增长正反馈环和一个制约负反馈环的内涵再提出系统可持续发展实现规模养种循环与节能减排的3条管理对策.最后, 通过五个顶点赋权反馈图顶点值的反馈变化规律,证明了系统发展中必须实施以猪尿资源为原料养殖场开发沼气工程并周边养种结合开发沼液资源,必须实行以养殖场的猪粪资源为原料促进全乡户用沼气池开发且全乡实施沼液种植,必须加大投入实施规模经营改变生产方式3条管理对策的正确性.此三步顶点赋权反馈图法及研究结果有重要理论和普遍实际意义,且为后续定量仿真管理对策未来实施效应评价中仿真方程的建立提供了积累.     

蚁群算法在全局最优路径寻优中的应用

移动机器人路径规划是机器人学的一个重要研究领域。针对移动场地的特点对其进行了建模与存储,然后将场地处理成简单的连通图,在此基础上对TSP模型进行了改进以应用到机器人全局最优路径中来,然后利用蚁群算法的基本原理在所建立的模型上进行全局最优路径搜索。为了更好的寻找到全局最优路径,对基本蚁群算法也做了一定的改进。不同的实验结果表明这种方法的确可以准确地找出全局最优路径。