隨機(jī)有向圖的染色算法研究.pdf

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

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

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

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