隨機(jī)圖的正常均勻全染色算法

　　目前對圖的均勻全染色的研究僅限于一些如完全圖、正則圖等特殊圖，還沒有發(fā)現(xiàn)用于研究一般簡單連通圖的正常均勻全染色的算法。為了研究一般圖的正常均勻全染色，根據(jù)正常均勻全染色的點約束、邊約束、點邊約束和均勻約束四個約束規(guī)則，設(shè)計了一種新的啟發(fā)式智能算法。首先，該算法確定四個子目標(biāo)函數(shù)和一個總目標(biāo)函數(shù)；然后，在每個子目標(biāo)函數(shù)內(nèi)借助染色矩陣及色補集合矩陣逐步迭代交換，直到子目標(biāo)函數(shù)值為0時，子目標(biāo)染色完成；最后，當(dāng)每個子目標(biāo)函數(shù)值都為0時，總目標(biāo)函數(shù)值為0，染色成功。實驗結(jié)果表明，該算法可以生成8個點以內(nèi)的所有簡單連通圖，并能對每個生成圖進(jìn)行正常均勻全染色，得到其均勻全色數(shù)，且驗證得對任意的正整數(shù)后，當(dāng)3≤K≤9時，隨機(jī)圖G都有K一均勻全染色。同時在20到400個點之間選取了72個圖，用所提算法對其進(jìn)行均勻全染色，并依據(jù)染色結(jié)果繪制了它們的點數(shù)一邊密度一所需色數(shù)關(guān)系圖。