隨機圖的正常均勻全染色算法

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