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

发布时间：2024-05-25 05:13

　　设G=(V,E)是简单连通图,Π={S₁,S₂,…,S_k}是对顶点集V的一个划分.顶点v∈V与非空顶点子集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-困难问题.本文基于遗传算法研究一般图的划分维数计算问题,刻画了图的分辨划分内在的拓扑结构;采用个体离散实值编码技术,个体划分分裂修补技术,设计了能够计算图的划分维数和分辨划分...

【文章页数】：16 页

【部分图文】：

图１爽１格＆与１＾．多胞形??Ｋｈｕｌｌｅｒ闕Ａｎｔｔｅｓｅｎ．關

阵为输入，通过汁算图的距离矩阵，首先利用算法３．３汁算网??格图和凸多胞形的划分度量维数，并将其对应的最优分辨划分集可视化，其次ｉ十算了??多个二维网格图和凸多胞形的划分维数，并提出了一个尚未解决间题．最后，基于翁??法３．３研究了随机图的划分维数和顶点分类间题．算法运行环境为Ｗ....

图３?＜３ｉ?（？?＝■?１００，?ｐ?＝?０．１）的分辨划分??

武建、赵海霞，杨卫华：？．翁ｊ遗传算法的＿ｗ敢划分度量维数计算??１０２５??６期??表２腐：法３．３＿随机摩上的计算结潘??ｎ??Ｖ??ｐｄ??ｔｉｍｅ??１００??０．１??９??０．２３２２７??１００??０．２??９??０．３１０５２??１００??０．３??１０??０．２....

图４?Ｇ２?（ｎ?＝?１００，?ｐ?＝?０．５）的分辨划分??

１０２６??应用数学学报??４３卷??图４?Ｇ２?（ｎ?＝?１００，?ｐ?＝?０．５）的分辨划分??知＝｛Ｖ（Ｇ２）?－?〇氐｝．根据定理２．１，图Ｇ的度量维数满足ｄｉｍ（Ｇ３）?＜?９．??ｉ＝ｌ??参考文献??［１］?Ｂｏｎｄｙ?Ｂ?Ａ，?Ｍｕｒｔｙ?Ｕ?Ｓ?Ｒ．?Ｇｒａｐｈ....

图1网格图与凸多胞形

4.1二维网格图和凸多胞形的划分维数计算与顶点分类Khuller等[13]和Andersen等[14]分别研究了网格图的分辨集和最小加权分辨集问题.其中二维网格图的顶点按照行,列规则排列.图1(a)给出了一个6行,8列的二维网格图.Imran等[15]研究了含有大量圈结构的凸多....

本文编号：3981756