匹配覆盖图的阈函数(英文)

一个图G是匹配覆盖的(或1-可扩的)如果它是连通的且G的每条边都被包含在一个完美匹配里.我们称一个图G为双因子临界的,如果对于G中的任意两个不同顶点x,y,Gx-y都有一个完美匹配.一个双因子临界图被称为砖块,如果它是3-连通的.本文对于双因子临界图与匹配覆盖二部图确定了它们的阈函数.对于非二部的匹配覆盖图,我们发现了一个概率序列,其表现就像一个阈.此外,我们证明几乎所有的3-连通图均是砖块.

多阶段动态扰动和动态惯性权重的布谷鸟算法

针对布谷鸟仿生智能优化算法存在着的易陷入局部最优、求解精度低以及收敛速度慢等问题,提出了基于多阶段动态扰动和动态惯性权重的布谷鸟搜索算法(MACS)。利用多阶段动态扰动策略对布谷鸟算法的全局位置的最优鸟巢位置根据方差可调的正态随机分布进行扰动,有利于增加种群的多样性和鸟窝位置的灵活性,提高算法全局搜索能力。在局部位置处引入动态惯性权重,使得算法有效克服易陷入局部最优的缺陷,提高局部寻优搜索能力。引入了动态切换概率p代替固定概率,可以动态平衡全局搜索和局部搜索。通过与4种算法相比和11个测试函数的仿真结果表明:改进布谷鸟算法(MACS)的寻优性能明显提高,收敛速度更快,求解精度更高,具有更强的全局搜索能力和跳出局部最优能力。