网络中的最优控制树问题

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

严格第k最小支撑树问题

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

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

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

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

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

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

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

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

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

PACKING A TREE OF ORDER p WITH A （p,p＋1）—GRAPH

Let G1 and G2 be two graphs of the same order,If G1 is isomorphic to a spanning subgraph of the complement of G2,then we say that G1 and G2 are packable.A graph G is called a (p,m)-graph if G has p vertices and m edges.The main purpose of this paper is to present a necessary and sufficient condition for a tree of order p and a (p,p 1)-graph to be packable.     

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

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

IS γα≤δ FOR GRAPHS WHICH HAVE DIAMETER TWO?

A subset of S of the vertex set of a graph G is called acyclic if the subgraph it induces in G contains no cycles. S is called an acyclic dominating set of G if it. is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by 7a(G), is called the acyclic domination number of G. S. M. Hedetniemi et al. on 2000 introduced the concept of acyclic domination and posed the following open problem: Is -ya(G) < <5(G) for any graph whose diameter is two? In this paper, we give a counterexample which disproves the problem.     

VERTEX-DISJOINT QUADRILATERALS IN BIPARTITE GRAPHS

H. Wang considered the minimum degrees condition that G has large vertex-disjoint cycles in bipartite graphs. Motivated by this, we consider the small vertex-disjoint cycles in bipartite graphs in this paper. We prove the following result: Let m > 3, n > 2 and k >1 be three integers. Let G = (V1,V2;E) be a bipartite graph with | V1| = | V2| =n > 2k 1. If the minimum degreefor any cycle C of G with length 2m, then G contains k vertex-disjoint cycles of length 4. Moreover, the degrees condition is sharp.     

基于最小割序集的独立电力系统可靠性分析

故障树分析方法是对系统进行可靠性评估的有效方法,但在独立电力系统可靠性的计算中存在可靠性参数计算量大、求解困难等问题。对此,采用故障树最小割序集方法求解独立电力系统的可靠性指标,针对求解可靠性指标时存在的组合爆炸问题,提出了基于时间运算符求解最小割序集的方法。运用分层模块的方法简化动态故障树模型,并根据最小割序集的逻辑运算规则得到最小割序集。最后运用失效概率公式求解得到独立电力系统的可靠性指标。以某常规独立电力系统和B787飞机电力系统可靠性分析为例,验证了所提算法的可行性和正确性,为求解独立电力系统的可靠性指标提供了一种新的思路。     

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

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

基于最小生成树与概率松弛结合的谱匹配算法

提出了一种基于最小生成树与概率松弛结合的谱匹配算法。该算法分别对给定的两个待匹配的特征点集构建最小生成树,通过最小生成树构造Laplace矩阵,由奇异值分解该矩阵得到的特征值和特征向量,计算出特征点匹配的初始概率,利用概率松弛迭代法,获得最终匹配结果。用大量的真实序列图像进行比较实验,结果验证了该算法的有效性和准确性。     

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

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

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

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

EXACT VALUE OF THE HARMONIOUS CHROMATIC NUMBER OF A COMPLETE TRINARY TREE

1.IntroductionLetG={VE}beafinite,undirected,simplegraPh,TheharmoniouschromaticnumberofagraPhG,denotedbyh(G),istheleastnumber0fcolorsneededtocol0rtheverticesofGinsuchawaythatanytwoadacelitverticesarec0loredbydmerelltcol0rsandanytwodistinctedgeshavedtherentcolorpairs(Here,ac0lorpairforedgee=uvisthepairofcol0rsusedt0coloruandv).Theharmoniouscol0ringshavebeenstudiedinpaPersl1-10].J.Mitchem[10]0btainedtheexactvalue0ftheharm0ni0uschr0maticnUInber0fthepath,cycleandc0mpleten-nytreewith3or4levels…     

基于最小连通支配集的复杂网络关键节点与连边识别方法

复杂网络关键节点与关键连边在网络中均起着十分重要的作用,目前的识别方法往往无法做到同时识别,并且识别指标角度较为单一。为解决上述问题,提出一种基于最小连通支配集(minimum connected dominatingset,MCDS)的复杂网络关键节点与连边识别方法,通过使用免疫粒子群(immune particle swarm optimization,IPSO)算法寻找网络最小连通支配集,构建核心骨干网,实现对复杂网络关键节点与连边的同时识别。该算法在求解过程中引入免疫机制指导粒子节点搜索方向、加快算法收敛速度,同时优化搜索节点质量。经实验验证表明,所提识别方法能够有效识别网络中的关键节点与关键连边。     

Forbidden Subgraphs, Distance,and Hamiltonicity

ＦｏｒｂｉｄｄｅｎＳｕｂｇｒａｐｈｓ，Ｄｉｓｔａｎｃｅ，ａｎｄＨａｍｉｌｔｏｎｉｃｉｔｙＨＵＺｈｉｑｕａｎＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＨｕａｚｈｏｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ４３００７０Ａｂｓｔｒａｃｔ：Ａｇｒ...     

Lower Semicontinuity of the Effcient Solution Mapping in Semi-In?nite Vector Optimization

This paper establishes some suffcient conditions for the lower semicontinuity of the effcient solution mapping for the semi-in?nite vector optimization problem with perturbations of both the objective function and the constraint set in normed linear spaces. The constraint set is the set of weakly effcient solutions of vector equilibrium problem, and perturbed by the perturbation of the criterion mapping to the vector equilibrium problem.