基于多目標(biāo)優(yōu)化的染色算法

　　圖的鄰點可區(qū)別均勻V-全染色（AVDEVTC）是指在滿足鄰點可區(qū)別V-全染色的基礎(chǔ)上，還要保證每種顏色的使用次數(shù)相差不超過1，把完成AVDEVTC所用的最少顏色稱為圖的鄰點可區(qū)別均勻V-全色數(shù)（AVDEVTCN）。針對圖的AVDEVTC問題，提出了一種基于多目標(biāo)優(yōu)化的染色算法。設(shè)計了一個總目標(biāo)函數(shù)和四個子目標(biāo)函數(shù)，在染色矩陣上通過每個點的顏色集合的迭代交換操作，使得每個子目標(biāo)函數(shù)都達(dá)到最優(yōu)，進(jìn)而滿足總目標(biāo)函數(shù)的要求，完成染色。經(jīng)過理論分析和實驗對比表明，8個頂點以內(nèi)的所有簡單連通圖都存在AVDEVTC，且圖的AVDEVTCN介于最大度加1與最大度加2之間。實驗結(jié)果表明，該染色算法能夠在較短的時間內(nèi)正確地計算出1 000個頂點以內(nèi)的圖的AVDEVTCN。
?