设G=（V，E）是简单连通图，Π={S1，S2，…，Sk}是对顶点集V的一个划分.顶点v∈V与非空顶点子集S⊆V的距离为dG（v，S）=min{dG（v，x）|x∈S，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-困难问题.本文基于遗传算法研究一般图的划分维数计算问题，刻画了图的分辨划分内在的拓扑结构；采用个体离散实值编码技术，个体划分分裂修补技术，设计了能够计算图的划分维数和分辨划分的遗传算法；数值计算表明，算法在二维网格图上计算准确率较高，并为凸多胞形的划分维数找到了最优上界，在随机图上运行较为有效.
Abstract
Let G=(V, E) be a simple and connected graph with a partiton Π={S1, S2, …, Sk} of V. The distance between a vertex v∈V and a non-empty subset S⊆V is defined as dG(v,S)=min{dG(v,x)|x∈S, S⊆V}. Let rG(v|Π)= (dG(v,S1), dG(v,S2), …, dG(v,Sk)) denote the k-distance vector of v∈V to the partition Π. For any two vertices u, v∈V, if rG(u|Π)≠rG(v|Π), then we say that each vertex of V has an unique k-distance vector representation, and Π is a resolving partition of G. The resolving partition with the minimum number of subsets of V is a partition base of G, accordingly the minimum number is the partition dimension of G. The resolving partition and partition dimension problem is an NP-hard problem proposed by Chartrand in 2000. Based on the genetic algorithm, we study the method to compute the partition dimension of general connected graphs. In this paper, we characterise the internal topology structure of a resolving partition. Using the technique of discrete real-value coding and the technique of individual repairation, a genetic algorithm which can provide partition dimension and resolving partition for graphs is designed. The algorithm is executed on two dimensional grids, convex polytopes and random graphs, the results of which show that the algorithm has a good performance on the two-dimensional grid with a hither computation accuracy, and can find the optimal upper bound of partition dimension for convex polytopes. The algorithm runs on random graphs well and effectively with shorter average iteration time, computing the optimal partition dimensions and resolving partition for graphs.
关键词
距离 /
分辨划分 /
划分维数 /
遗传算法 /
个体修复
{{custom_keyword}} /
Key words
distance /
resolving partition /
partition dimension /
genetic algorithm /
individual repairation
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[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
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金（11671296）资助项目.
{{custom_fund}}
PDF(803 KB)
