韋爾奇-鮑威爾（Welch-Powell）點著色算法

按照點的度數(shù)非嚴格遞減的方式進行排序。

對第一個點著色，并找到與之不相鄰的、在序列中與它最近的點，著相同的顏色。依次類推，對序列中與以著色頂點不相鄰的點按照此步驟依次進行下去。

刪去第一次著色的點，對剩余的頂點采取步驟2的方法繼續(xù)著色。

直到所有頂點已著色，算法結束。

韋爾奇-鮑威爾（Welch-Powell）點著色算法并不總能得到最小點著色數(shù)目。比如二部圖中最小點著色是2，但是此算法可能會得到大于2的結果。

Reference：Duo L., 2018.離散數(shù)學及應用.2nd.Beijing: Tsinghua University.

總結

以上是生活随笔為你收集整理的着色近似算法——韦尔奇-鲍威尔（Welch-Powell）点着色算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。