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