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

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

本站小编 Free考研考试/2021-12-27

基于遗传算法的图的划分度量维数计算武建^1,2, 赵海霞³, 杨卫华⁴1. 山西财经大学应用数学学院, 太原 030006;
2. 太原理工大学信息与计算机学院, 太原 030600;
3. 山西财经大学统计学院, 太原 030006;
4. 太原理工大学数学学院, 太原 030600 Computing the Partition Metric Dimension of Graphs Based on Genetic Algorithm WU Jian^1,2, ZHAO Haixia³, YANG Weihua⁴1. School of Applied Mathematics, Shanxi University of Finance and Economics, Taiyuan 030006, China;
2. School of Information and Computer Science, Taiyuan University of Technology, Taiyuan 030600, China;
3. School of Statistics, Shanxi University of Finance and Economics, Taiyuan 030006, China;
4. School of Mathematics, Taiyuan University of Technology, Taiyuan 030600, China

摘要
图/表
参考文献
相关文章(11)
点击分布统计
下载分布统计
-->

全文: PDF(803 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

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

服务

加入引用管理器

E-mail Alert

RSS

收稿日期: 2018-12-11

PACS:

O157.5

基金资助:国家自然科学基金（11671296）资助项目.

引用本文:

武建, 赵海霞, 杨卫华. 基于遗传算法的图的划分度量维数计算[J]. 应用数学学报, 2020, 43(6): 1013-1028. WU Jian, ZHAO Haixia, YANG Weihua. Computing the Partition Metric Dimension of Graphs Based on Genetic Algorithm. Acta Mathematicae Applicatae Sinica, 2020, 43(6): 1013-1028.

链接本文:

http://123.57.41.99/jweb_yysxxb/CN/或 http://123.57.41.99/jweb_yysxxb/CN/Y2020/V43/I6/1013

[1]	Bondy B A, Murty U S R. Graph Theory. London:Springer, 2008
[2]	Chartrand G, Eroh L, Johnson M A, et al. Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics, 2000, 105 (1):99-113
[3]	Zhu E Q, Taranenko A, Shao Z H, Xu J. On graphs with the maximum edge metric dimension. Discrete Applied Mathematics, 2018. DOI.10.1016/j.dam.2018.08.031
[4]	Chartrand G, Salehi E, Zhang P. The partition dimension of a graph. Aequationes Mathematicae, 2000, 59 (1-2):45-54
[5]	Estrada-Moreno A. On the k-partition dimension of graphs. arXiv, 2018, 1805.04966
[6]	Maritz E C M, Vetrík T. The partition dimension of circulant graphs. Quaestiones Mathematicae, 2018:1-15
[7]	Grigorious C, Stephen S, Rajan B, et al. On the partition dimension of a class of circulant graphs. Information Processing Letters, 2014, 114 (7):353-356
[8]	Fredlina K Q, Baskoro E T. The Partition Dimension of Some Families of Trees. Procedia Computer Science, 2015, 74:60-66
[9]	Rodríguezvelázquez J A, Yero I G, Kuziak D. The partition dimension of corona product graphs. Ars Combinatoria, 2010
[10]	Shapiro J L. Genetic Algorithms in Machine Learning. Machine Learning & Its Applications, Advanced Lectures, DBLP, 2001
[11]	王小平, 曹立明. 遗传算法理论应用与软件实现. 西安:西安交通大学出版社, 2002 (Wang Xiaoping, Cao Liming. Theorem, Application and Software Realization of Genetic Algorithm. Xi'an:Xi'an Jiaotong University Press, 2002)
[12]	Rudolph G. Convergence analysis of canonical genetic algorithms. IEEE Transactions on Neural Networks, 1994, 5(1):96
[13]	Khuller S, Raghavachari B, Rosenfeld A. Landmarks in graphs. Discrete Applied Mathematics, 1996, 70 (3):217-229
[14]	Andersen P, Grigorious C, Miller M. Minimum weight resolving sets of grid graphs. Discrete Mathematics, Algorithms and Applications, 2016, 8(3):22
[15]	Imran M, Ahtsham U H B S, Baig A Q. On families of convex polytopes with constant metric dimension. Computers & Mathematics with Applications, 2010, 60 (9):2629-2638

[1]	武建, 赵海霞, 李璇. 广义Corona积图的度量维研究[J]. 应用数学学报, 2017, 40(6): 915-930.
[2]	贺飞, 李斌. 含有推广的P-距离的不动点定理[J]. 应用数学学报, 2015, 38(6): 961-967.
[3]	张赛茵, 张忠占. 应力中带有误差的破坏性加速退化试验分析[J]. 应用数学学报(英文版), 2012, 35(5): 829-844.
[4]	赵建昕, 徐兴忠. 一类相合的分位点型检验[J]. 应用数学学报(英文版), 2012, (1): 168-188.
[5]	侯丽霞, 左连翠. 龙虾树的多级距离标号[J]. 应用数学学报(英文版), 2011, 34(5): 838-852.
[6]	高锁刚步玉恩. 具有性质$c_{r+1}=3,a_{r+1}=3a+1$或$4a$的$(a+1,3)$型距离正则图[J]. 应用数学学报(英文版), 2008, 31(1): 164-172.
[7]	徐宗本, 聂赞坎, 张文修. 父代种群参与竞争遗传算法几乎必然收敛[J]. 应用数学学报(英文版), 2002, 25(1): 167-175.
[8]	朱仲义, 韦博成. 半参数非线性模型的统计诊断与影响分析[J]. 应用数学学报(英文版), 2001, 24(4): 568-581.
[9]	王仰贤, 李凤高, 霍元极. 有限典型空间的对偶极图的次成分I[J]. 应用数学学报(英文版), 2001, 24(3): 433-440.
[10]	陈文德, 孙旭顺. 三维七元线性码的重量谱与改进的遗传算法[J]. 应用数学学报(英文版), 2001, 24(3): 384-390.
[11]	武清. 度量方程应用于Krause定理的推广[J]. 应用数学学报(英文版), 1999, 22(3): 376-382.

PDF全文下载地址:

http://123.57.41.99/jweb_yysxxb/CN/article/downloadArticleFile.do?attachType=PDF&id=14835