隨機(jī)圖的色和可區(qū)別染色算法研究.pdf

1、現(xiàn)實(shí)生活中許多復(fù)雜的問(wèn)題都可通過(guò)分類、抽象、簡(jiǎn)化的思想轉(zhuǎn)化成圖論問(wèn)題進(jìn)行研究解決，如最大支配集、加工調(diào)度、任務(wù)分配、排課表等典型的組合類問(wèn)題，而圖染色作為圖論中一個(gè)重要的研究分支，是解決實(shí)際問(wèn)題的一個(gè)重要途徑。近些年來(lái)，一些經(jīng)典的智能算法被用來(lái)研究和嘗試解決圖染色問(wèn)題，如粒子群算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法等，但目前這些算法普遍僅應(yīng)用于解決圖的正常點(diǎn)染色和正常邊染色，而對(duì)于圖染色問(wèn)題中多約束條件的染色問(wèn)題，公開(kāi)發(fā)表的文獻(xiàn)中尚不多見(jiàn)，因此尋

2、求新的智能算法來(lái)解決圖的多約束條件染色問(wèn)題是國(guó)內(nèi)外圖論研究者都感興趣的一個(gè)重要課題。
　　圖的鄰點(diǎn)色和可區(qū)別染色問(wèn)題，在已公開(kāi)發(fā)表的文獻(xiàn)中對(duì)它們的研究都局限于如正則圖、星圖、完全圖等的特殊圖，尚無(wú)解決一般圖的鄰點(diǎn)色和可區(qū)別染色、點(diǎn)和可區(qū)別染色問(wèn)題的方法。本文根據(jù)兩種圖的色和可區(qū)別染色的定義，分別設(shè)計(jì)了基于多目標(biāo)優(yōu)化的染色算法，對(duì)算法的正確性、收斂性和復(fù)雜度進(jìn)行了分析，并通過(guò)大量的實(shí)例測(cè)試，得到了一些很有意義的結(jié)果。本文的具體工作如

3、下：
　?、沤榻B了一些基本染色概念及相關(guān)猜想，并同時(shí)給出有關(guān)內(nèi)容的研究背景及目前國(guó)內(nèi)外的研究動(dòng)態(tài)。
　?、平榻B了兩個(gè)經(jīng)典的智能算法（粒子群算法、遺傳算法）的基本思想、流程，及其在圖染色中的應(yīng)用，并對(duì)這些算法在解決圖染色問(wèn)題的性能上進(jìn)行了分析。
　?、墙o出了隨機(jī)圖的生成算法和生成有限點(diǎn)數(shù)所有偽非同構(gòu)圖的算法，詳細(xì)描述了算法步驟，并分別對(duì)這兩種算法進(jìn)行了算法測(cè)試，為之后染色算法的研究提供了基礎(chǔ)數(shù)據(jù)支持。
　?、仍O(shè)計(jì)并

4、實(shí)現(xiàn)了圖的色和可區(qū)別染色問(wèn)題中的鄰點(diǎn)和可區(qū)別邊染色、鄰點(diǎn)和可區(qū)別全染色、點(diǎn)和可區(qū)別邊染色和點(diǎn)和可區(qū)別全染色四個(gè)智能優(yōu)化算法。四個(gè)算法的整體思路都是將其染色問(wèn)題分解為多個(gè)特定功能模塊的子問(wèn)題，依次按序通過(guò)對(duì)子問(wèn)題的逐步迭代調(diào)整直到子問(wèn)題解決成功，之后以不改變前一子問(wèn)題的成功狀態(tài)為前提解決后一個(gè)子問(wèn)題，當(dāng)所有子問(wèn)題都成功解決后，即代表該染色成功，算法結(jié)束。文中給出了算法的詳細(xì)流程及測(cè)試案例，分析了算法的正確性、收斂性和時(shí)間復(fù)雜度，測(cè)試實(shí)例為