用选边法求最优树

设图G=(V,E)是一个有限的无向连通图,这里V表示图G的顶点集,E表示图G的边集。每条边e_i∈E,还有一定的长度l_i,称l_i为边e_i的权。这种每条边标有权的连通图称为赋权连通图。如果图T是一个不包含有回路的连通图,则称图T是一棵树。如果图T是图G的一个生成子图,而且T又是一棵树。则称T是图G的一棵生成树。一棵生成树T的权W(T)是指图T中各条边权的总和,其中具有最小权的生成树称为最优树。赋权连通图的最优树往往是图论中具有较广泛地实际应用价值的。例如在若干城市之间修公路,铺铁路,或架通信线路等,都需要求出城市之间的最短连通线路,使修建成本降到最低。这种求出若干城市之间最短连通线路就是一个求出赋权连通图最优树的问题。     

数据传输选择问题:算法设计和复杂性分析

数据和信息传输业务对网络的要求越来越高，在满足实时性、可靠性的同时，还要求充分利用网络资源，降低传输成本．文章首先建立了数据传输网络选择的最小成本模型，给出了有效支撑树代表集的概念，并给出了一个时间复杂性为O(mlogn)的算法产生代表集，其中m，n分别代表网络的边数和顶点数．然后对静态数据传输支撑树问题和动态数据传输支撑树问题，分别给出了一个时间复杂性为O(mlog n)和O(m^2 mlogn)的多项式时间的好算法．     

基于全条件独立的贝叶斯网络MPD-JT构造算法

针对求解贝叶斯网络最大主子图存在的NP(non-deterministic polynomialtine)难问题,提出了一种基于全条件独立结构的最大主子图连接树（maximal prime sub graph decomposition junction tree, MPD-JT）构造算法。该算法通过道义图上的全条件独立结构得到贝叶斯网络最大主子图,并利用构成这些最大主子图的节点作为簇节点构造连接树,避免了三角化过程,而且在求解过程中通过删除一些符合条件的点,大大降低了算法复杂度。给出了算法的理论证明,通过具体案例分析验证了算法的有效性。     

无人飞行器Ad hoc网络中基于容错的中继节点配置

针对无人飞行器Ad hoc网络的容错设计需求,采用增加中继节点的方法实现。在二维平面同构网络中,将容错问题转化为边长受限条件下最少数量Steiner点的Steiner树问题。提出了两种基于最小成本子图的中继节点配置算法,以求解最少数量的中继节点及其位置,使改变后的网络拓扑图为顶点2-连通,实现容错。第一种为多项式时间的8-近似算法;第二种为随机近似算法,采用文化基因算法,搜索需要新增加的最小成本强化边组合。仿真结果表明了所提算法的有效性,当网络规模较小和中等时,随机近似算法得到的中继节点数量较少,平均情况下性能较优。     

严格第k最小支撑树问题

提出了严格第 k最小树的概念 .利用定长支撑树问题的复杂性 ,证明了求支撑树的长度分布L( G)问题是 NP-C的 ,从而证明了严格第 k最小支撑树问题也是 NP-C的 .对于 k=2的情况 ,给出了一个多项式时间算法 ,其时间复杂性为 $O( | EX| n^2 )$ ,其中 EX是正交换的集合 ,n是顶点数.     

网络中的优势有效点与选址问题

一、引言 设N=(V,A)为一个有限、简单、无向的连通网络,其顶点集为V,连杆集为A。 设U={u_1,u_2,…,u_p}V,每个u_i对应一个定义在N中点集上的函数d_i(i=1,2,…,p),其定义如下: 这里d(x,u_i)表示x与u_i之间在网络中的最短距离(即连接x与u_i的任一条最短路径的长度)。 我们的问题是求x~*N,使每个函数d(x,u_i)在x~*都取“极小”值(i=1,2,…,p)。这显然是一个多目标决策问题。     

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

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

基于联结树的贝叶斯网的推理结构及构造算法

BN(贝叶斯网)被认为是人工智能研究中不确定性知识表示和推理的重要工具，广泛应用到复杂系统的建模等领域，成为人工智能研究的热点问题之一。然而直接在BN上精确推理与近似推理都被证明是NP完全的。因此把在BN上推理转变为在SS(二次结构)上的推理。SS是由JT（联结树)与BP(信念势)组成，构造JT大体分为三步即：把BN对应的有向无环图G转变为一个道义图G^M；把G^M转变为弦化图G^T，识别和选择G^T图的圈；连接圈和边建立JT。因而提出了建立G^M、G^T与JT的方法原理和算法。最后通过案例分析了G^M、G^T与JT构造过程。     

江西新型农村合作医疗制度实施效应反馈仿真分析

农村居民"看病难、看病贵"问题突出,迫切需要解决.实施新型农村合作医疗(以下简称新农合)正是缓解、解决此问题的关键.为此创建系统动力学入树反馈仿真作用力五步分析法,并应用于江西新农合制度实施效应分析.通过深入调研,确定新农合五个核心变量;建立流位流率系和由流位控制流率的五棵新农合系统流率基本入树,通过顶点和弧并运算,建立系统仿真实验流图模型;然后,构建强简化新农合系统流率基本入树模型,将枝向量代数方法应用到新农合系统的反馈环计算;接着,基于反馈环集合与反馈环特性提出了发展新农合解决"看病贵、看病难"的4条管理对策;最后,通过对新农合制度管理对策的定量仿真实验,得出新农合在农村医药卫生体制改革中产生了四大作用力.     

爪心独立图的可扩圈

图Ｇ中的一个与Ｋ１，３同构的导出子图叫做Ｇ的一个爪。爪中的３次顶点叫该爪的爪心。Ｂ表示Ｇ中所有爪心构成的集合。本文将证明：设Ｇ是顶点数≥３的连通、局部连通图，如果Ｇ的爪心集合Ｂ是点独立集，且Ｇ－Ｂ是局部连通的，则Ｇ是完全圈可扩的。     

ON THE INVERSE MINIMUM SPANNING TREE PROBLEM WITH MINIMUM NUMBER OF PERTURBED EDGES

Let G=be a network with the vertex set V,the edge set E and the length vector L, andlet T~* be a prior determined spanning tree of G. The inverse minimum spanning tree problem withminimum number of perturbed edges is to perturb the length vector L to L+δ, such that T~* is one ofminimum spanning trees under the length vector L+δ and the number of perturbed edges is minimum.This paper establishes a mathematical model for this problem and transforms it into a minimumvertex covering problem in a bipartite graph G_0, a path-graph. Thus a strongly polynomial algorithmwith time complexity O(mn~2) can be designed by using Hungarian method.     

度约束最小生成树(DCMST)的竞争决策算法

度约束最小生成树是网络设计和优化中的一个NP难题，介绍了一种基于竞争造就优化和决策左右结果的新型算法——竞争决策算法，利用竞争决策算法的通用模型，给出了一种基于竞争决策思想求解度约束最小生成树的快速求解方法，经过数据测试和验证，并与其它算法的结果进行了比较，得到了较好的结果．     

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

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

启发式交叉求解TSP问题的混合遗传算法

在给出度约束最小生成树的快速生成方法的基础上，设计了一种启发式交叉求解TSP问题的混合遗传算法．该算法在交叉操作的设计上，与其他遗传算法有本质的不同，该交叉操作是在不违反度约束和不形成圈的前提下，每次从父代基因所拥有的边中加入权最小的边，从而形成子代．利用该算法得到了TSP CHN144问题迄今为止最好的解．     

广义最小生成树的遗传算法求解及应用

介绍了最小生成树的概念,分析了最小生成树在实际应用中的局限性。引入了节点的度的定义,据此提出了广义最小生成树的概念。采用遗传算法来求解最小生成树,并针对普通遗传算法求解该问题的不足,提出了自调整的变异算子和限制父代个体数目的混合选择策略。通过一个有线电视网络的建模与仿真,表明了广义最小生成树模型的适用性。分别采用普通遗传算法和改进后的遗传算法进行求解,并将结果进行比较,证明了改进后的遗传算法的有效性。     

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

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

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

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

度限制最小树的蚂蚁算法

针对度限制最小树问题,给出了一种基于蚂蚁系统思想的求解方法,经大量数据测试和验证,并与其它算法相比较,得到了较好的结果以及一系列意义的结论。