隨機圖的正常均勻全染色算法
大小：0.83 MB 人氣： 2018-01-04 需要積分：3
標簽：染色算法(1629)
目前對圖的均勻全染色的研究僅限于一些如完全圖、正則圖等特殊圖，還沒有發現用于研究一般簡單連通圖的正常均勻全染色的算法。為了研究一般圖的正常均勻全染色，根據正常均勻全染色的點約束、邊約束、點邊約束和均勻約束四個約束規則，設計了一種新的啟發式智能算法。首先，該算法確定四個子目標函數和一個總目標函數；然后，在每個子目標函數內借助染色矩陣及色補集合矩陣逐步迭代交換，直到子目標函數值為0時，子目標染色完成；最后，當每個子目標函數值都為0時，總目標函數值為0，染色成功。實驗結果表明，該算法可以生成8個點以內的所有簡單連通圖，并能對每個生成圖進行正常均勻全染色，得到其均勻全色數，且驗證得對任意的正整數后，當3≤K≤9時，隨機圖G都有K一均勻全染色。同時在20到400個點之間選取了72個圖，用所提算法對其進行均勻全染色，并依據染色結果繪制了它們的點數一邊密度一所需色數關系圖。
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%