基于变邻域搜索算法的混合度量维数问题研究

发布时间：2021-06-30 06:42

　　设G=（V,E）为图.顶点v称为是区分元素（顶点和边）x和y的,如果d（x,v）≠d（y,v）,这里d（x,v）,d（y,v）分别表示元素x,y与顶点v之间的距离.顶点集V的一个子集W称为G的一个混合度量生成集,如果对G的任意两个元素x,y,都存在顶点v∈W使得v区分x,y.含有最少元素的混合度量生成集的基数称为图G的混合度量维数.图的混合度量维数问题是图论与组合优化中的一个重要问题.确定图的混合度量维数是一个NP-难问题,因此对大规模求解混合度量维数的实例,我们需要考虑它的有效算法.本文给出了两种关于该问题的整数线性规划模型,设计了混合度量维数问题的变邻域搜索算法,并利用此算法给出了一些图的混合度量维数的界. 

【文章来源】：河北师范大学河北省

【文章页数】：38 页

【学位级别】：硕士

【部分图文】：

图1

sun图

4


本文编号：3257253