基于遗传算法的图的划分度量维数计算

作者：武建; 赵海霞; 杨卫华^*

来源：应用数学学报, 2020, 43(06): 1013-1028.

• 距离
• 分辨划分
• 划分维数
• 遗传算法
• 个体修复

设G=(V,E)是简单连通图,Π={S1,S2,…,Sk}是对顶点集V的一个划分.顶点v∈V与非空顶点子集S■V的距离为■.顶点v∈V关于划分Π的表征是一个k-维距离向量rG(v|Π)=(dG(v,S1),dG(v,S2),…,dG(v,Sk)).若对任意两个顶点u,v∈V有rG(u|Π)≠rG(v|Π)成立,则每个顶点具有唯一的k-维向量表征,并称Π是V的一个分辨划分,简称图G的分辨划分.具有最小划分数的分辨划分为图G的一个划分基.划分基所含顶点子集的个数为图G的划分度量维数,简称划分维数.图的分辨划分及划分维数问题是由Chartrand提出的一类NP-困难问题.本文基于遗传算法研究一般图的划分维数计算问题,刻画了图的分辨划分内在的拓扑结构;采用个体离散实值编码技术,个体划分分裂修补技术,设计了能够计算图的划分维数和分辨划分的遗传算法;数值计算表明,算法在二维网格图上计算准确率较高,并为凸多胞形的划分维数找到了最优上界,在随机图上运行较为有效.

• 单位
  太原理工大学; 山西财经大学; 数学学院