应用数学学报

作者：武建, 赵海霞, 杨卫华

单位：1. 山西财经大学应用数学学院, 太原 030006;<br>2. 太原理工大学信息与计算机学院, 太原 030600;<br>3. 山西财经大学统计学院, 太原 030006;<br>4. 太原理工大学数学学院, 太原 030600

关键词：距离,分辨划分,划分维数,遗传算法,个体修复

设G=（V，E）是简单连通图，Π={S1，S2，…，Sk}是对顶点集V的一个划分.顶点v∈V与非空顶点子集S&#8838;V的距离为dG（v，S）=min{dG（v，x）|x∈S，S&#8838;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-困难问题.本文基于遗传算法研究一般图的划分维数计算问题，刻画了图的分辨划分内在的拓扑结构；采用个体离散实值编码技术，个体划分分裂修补技术，设计了能够计算图的划分维数和分辨划分的遗传算法；数值计算表明，算法在二维网格图上计算准确率较高，并为凸多胞形的划分维数找到了最优上界，在随机图上运行较为有效.

来源：2020年第6期

《应用数学学报》期刊编辑部

查看应用数学学报杂志2020年第6期