k_(1,s)─free图的局部Hamiltion连通性(英)

设G是K(1，s)－free图，如果对每一个顶点v∈V（G），有：K（G［N（V）］）≥s—2，（s≥3），那么每一局部导出子图均包含一个Hamiltion路。

有向线图存在Hamilton圈和Hamilton路的一个充要条件

有向图D的有向线图是以A(D)为顶点集,弧集为{(xy,yz),xy∈A(D),yz∈A(D)}的有向图,用L(D)表示D的有向线图。文章证明了连通有向线图存在Ham ilton圈当且仅当它有圈因子;连通有向线图存在Ham ilton路当且仅当它有1-路圈因子。

多目标MIN-MAX度最小树问题及其求解

在多目标最小生成树问题和MIN-MAX度最小树问题的基础上,探讨使生成树最大顶点度数以及总权重都尽可能小的另类多目标MIN-MAX度最小生成树问题。分析了这一特殊的顶点度约束与Hamilton路的关联性质,在此基础上设计了先Hamilton路再MIN-MAX度最小树的独特求解方案。根据初始条件不同,当网络图不存在Hamilton路时,引入改进的蚁群优化算法,将转移概率由基本的指数形式改进为线性形式,在不影响求解质量的前提下,提高计算效率。针对以上策略,设计了相应的求解方案,并在计算机上用Delphi编程实现。大量数值算例验证表明,算法能快速有效地求解多目标情形下的MIN-MAX度最小生成树问题。