CAJ | 학술논문

目前对图的均匀全染色的研究仅限于一些如完全图、正则图等特殊图,还没有发现用于研究一般简单连通图的正常均匀全染色的算法.为了研究一般图的正常均匀全染色,根据正常均匀全染色的点约束、边约束、点边约束和均匀约束四个约束规则,设计了一种新的启发式智能算法.首先,该算法确定四个子目标函数和一个总目标函数;然后,在每个子目标函数内借助染色矩阵及色补集合矩阵逐步迭代交换,直到子目标函数值为0时,子目标染色完成;最后,当每个子目标函数值都为0时,总目标函数值为0,染色成功.实验结果表明,该算法可以生成8个点以内的所有简单连通图,并能对每个生成图进行正常均匀全染色,得到其均匀金色数,且验证得对任意的正整数k,当3≤k≤9时,随机图G都有k-均匀全染色.同时在20到400个点之间选取了72个图,用所提算法对其进行均匀全染色,并依据染色结果绘制了它们的点数-边密度-所需色数关系图.
목전대도적균균전염색적연구부한우일사여완전도、정칙도등특수도,환몰유발현용우연구일반간단련통도적정상균균전염색적산법.위료연구일반도적정상균균전염색,근거정상균균전염색적점약속、변약속、점변약속화균균약속사개약속규칙,설계료일충신적계발식지능산법.수선,해산법학정사개자목표함수화일개총목표함수;연후,재매개자목표함수내차조염색구진급색보집합구진축보질대교환,직도자목표함수치위0시,자목표염색완성;최후,당매개자목표함수치도위0시,총목표함수치위0,염색성공.실험결과표명,해산법가이생성8개점이내적소유간단련통도,병능대매개생성도진행정상균균전염색,득도기균균금색수,차험증득대임의적정정수k,당3≤k≤9시,수궤도G도유k-균균전염색.동시재20도400개점지간선취료72개도,용소제산법대기진행균균전염색,병의거염색결과회제료타문적점수-변밀도-소수색수관계도.