隨機有向圖的染色算法研究.pdf

1、圖的染色問題一直是圖論領(lǐng)域中的一個重要研究課題，無論在理論上還是在實際中都有著廣泛的應(yīng)用，例如一些典型的組合問題如加工調(diào)度、最大支配集等問題，實際中如停車場、學(xué)校排課表等問題都可以轉(zhuǎn)化為圖的染色問題來研究解決。到目前為止，在圖染色領(lǐng)域中，研究大都針對無向圖來展開，而對于有向圖，因其自身的復(fù)雜性和特殊性，染色研究則涉及較少，甚至為空白。因此，本文將著重針對有向圖的染色問題進行探討和研究。
　　無向圖的染色問題是NP完全問題，目前解決

2、該問題的算法類型主要有順序算法、仿生算法和其他智能算法等。這些算法大都被廣泛應(yīng)用于處理一些較為簡單的染色問題，如無向圖的正常點染色問題、正常邊染色問題等。在應(yīng)用中，我們可以先將一些實際問題轉(zhuǎn)化為無向圖，然后再利用無向圖的正常點染色或正常邊染色方法將其解決。另外，這些算法較多應(yīng)用在無向圖染色的表層領(lǐng)域，對于無向圖更深入的染色問題，則不能給出很好的解決辦法。在有向圖的染色領(lǐng)域內(nèi)，上述算法更是尚未涉獵。本文所做的主要工作就是首先給出幾種有向圖

3、的染色定義，然后設(shè)計出有效的算法來解決這些定義所對應(yīng)的有向圖的染色問題。本文所做的工作是具有開創(chuàng)性的，主要包括以下幾個方面：
　?。?）從無向圖染色的角度切入，根據(jù)具體的情況將染色問題進行分類；介紹一些無向圖的基礎(chǔ)染色概念，如無向圖的正常點染色、邊染色、全染色和在此基礎(chǔ)上衍生出的點可區(qū)別染色和鄰點可區(qū)別染色的概念；以遺傳算法作為經(jīng)典智能算法的代表，介紹其在無向圖染色問題中的應(yīng)用，同時總結(jié)遺傳算法在解決無向圖染色問題中的優(yōu)點和不足，

4、為研究解決有向圖的染色問題提供思路和參考。
　?。?）給出有向圖的四種染色概念。首先對有向圖的染色問題從整體上有個宏觀的了解和把握，其次再結(jié)合具體的染色條件重點研究和討論隨機有向圖的正?；∪旧⒄Ｈ旧?、均勻弧染色以及均勻全染色的相關(guān)理論，同時給出相關(guān)猜想值。
　?。?）根據(jù)相關(guān)定義，針對隨機有向圖進行正?；∪旧⒄Ｈ旧?、均勻弧染色以及均勻全染色算法的設(shè)計。對于每種算法，首先根據(jù)相關(guān)的染色條件，設(shè)計出對應(yīng)的約束函數(shù)和總