最多叶子生成树问题的核化算法

对算法领域的最多叶子生成树问题进行了深入研究,提出了对简单连通图2度节点的化简规则,并证明了不含2度节点的图的生成树的叶子节点数的下限为(N+6)/4,给出了构造这样一棵生成树的构造性方法.基于上述化简规则和所证明的结论,给出了最多叶子生成树问题的核化算法,该核化算法可以在O(n2)时间内得到一个4k-6大小的线性核.对于这样一个较小的核,将大大提高相关的参数算法和近似算法的性能.

(μ+λ)EA算法关于最多叶子生成树问题的近似性能

为了更好地理解演化算法的运行机制及其在求解NP难问题上的性能,研究了基于种群的(μ+λ)演化算法((μ+λ)EA)在NP难的最多叶子生成树问题(MLST)上的近似性能,证明了对于最多叶子生成树问题,(μ+λ)EA算法从任意初始解出发,能够分别在期望多项式时间O((μ/λ)nm^2+μmlogn+n)和O((μ/λ)nm^4+μmlogn+n)内获得5和3近似比.并证明了如果选取λ>2μ,基于种群的(μ+λ)EA算法要优于基于单个个体的(1+1)EA算法.

有向图最多叶子生成树问题研究

为求解有向图最多叶子生成树(出分枝)问题,提出了一些规约规则,对有向图实施这些规约规则能降低原图的规模;随后设计了近似算法在规约后的图中求解指定根节点的最多叶子出分枝问题。对于用近似算法求得的出分枝,又结合前面的规约规则设计了优化规则,以进一步通过优化变换增加出分枝的叶子节点。仿真实验表明,规约规则、近似算法和优化规则是有效的。

基于最多叶子生成树的中国航空网络轴辐结构构建

航空网络的轴辐(Hub-Spoke)结构是实现规模经济发展的重要交通运输网络结构,本文为此提出了一种全新的航空网络轴辐结构构建方法。该方法从图论和地理学的角度出发,引入地理距离约束,改进了传统的最多叶子生成树(Maximum Leaf Spanning Tree)算法,直接从现有的中国航空网络中抽取树形轴辐结构形成航空支线网络,然后选取支线网络中度前10的节点作为航空枢纽点,并将枢纽点之间在原图中的航线抽取为航空干线网络,最后将支线网络和干线网络合并形成中国航空网络的轴辐结构。在与相关研究的对比分析中,本文方法虽是从图论角度出发,但构建的中国航空轴辐结构符合实际地理环境,划分支线网络距离阈值的选择更加客观合理,所选的航空枢纽点地理意义更为明显,干支线网络的覆盖度更为全面。

一种高效的多跳无线网络广播协议

广播操作是无线网络中一种常用的、重要的操作,通常采用泛洪来实现.无控制的泛洪会引起严重的竞争、冲突和拥塞,称为广播风暴问题.鉴此,本文提出了一种高效的无线网络广播协议.该协议通过根据网络拓扑图的最多叶子最短生成树来确定路由选择.分析和仿真结果说明,本文所提出的广播协议不仅能够避免冲突而且能够大大减少冗余的广播消息和减小广播延时.

一类确定型的小世界等级指数型复杂网络模型

小世界效应在实际生活中是随处可见的,例如复杂网络中的六度分离理论。本论述为了更好地研究小世界网络的拓扑结构,采用完全三部图K3,6为基本元素,通过循环迭代的算法程序,设计了一类小世界网络模型。首先,分析了它的重要拓扑参数:聚类系数、直径和平均距离,得证该模型具有小世界效应,而后通过计算机仿真还获知该模型具有等级结构。其次,通过计算其顶点的累积度分布得知,该模型拥有指数分布特性。最后,利用特殊的演化过程,得到了其最多叶子生成树的叶子数目。