圖染色軟件系統(tǒng)(GCSS)的研究與實(shí)現(xiàn).pdf

1、隨著信息科學(xué)與網(wǎng)絡(luò)技術(shù)的快速發(fā)展，圖論因其直觀的圖形性和嚴(yán)密的邏輯性，在廣大的專(zhuān)家學(xué)者中受到了越來(lái)越多的關(guān)注和研究。許多問(wèn)題都可以找到與之相匹配的圖的模型，例如大規(guī)模信息通訊、社交網(wǎng)絡(luò)、大數(shù)據(jù)采集及分析、物聯(lián)網(wǎng)等問(wèn)題，都有著復(fù)雜的網(wǎng)絡(luò)化、結(jié)構(gòu)化的特點(diǎn)。而圖論具有把復(fù)雜結(jié)構(gòu)問(wèn)題抽象轉(zhuǎn)化成以頂點(diǎn)和邊表示的清晰結(jié)構(gòu)的特性，以圖為工具成為解決這些領(lǐng)域問(wèn)題的新型且有效的方案，進(jìn)而抽象為圖染色的方法予以解決。因此，對(duì)圖染色問(wèn)題的研究與創(chuàng)新是非常有意

2、義的。
　　圖的染色問(wèn)題屬于NP完全問(wèn)題，一些經(jīng)典的智能算法如遺傳算法、粒子群算法、神經(jīng)網(wǎng)絡(luò)算法等被用來(lái)解決圖的染色問(wèn)題時(shí)，僅能解決如正常點(diǎn)染色和正常邊染色等單約束條件染色問(wèn)題，而對(duì)于全染色和可區(qū)別染色等多約束條件染色問(wèn)題則到目前為止也沒(méi)有好的成果發(fā)表。
　　本文首先設(shè)計(jì)并實(shí)現(xiàn)了三個(gè)解決多約束條件染色問(wèn)題的染色算法，然后結(jié)合已公開(kāi)發(fā)表的部分可區(qū)別圖染色算法，設(shè)計(jì)并實(shí)現(xiàn)了圖染色軟件系統(tǒng)(GCSS)。該系統(tǒng)可以為圖論研究的學(xué)者、

3、愛(ài)好者以及應(yīng)用圖染色技術(shù)解決現(xiàn)實(shí)問(wèn)題的科研工作者提供一個(gè)良好的研究平臺(tái)。在該系統(tǒng)中，用戶(hù)只需選擇染色方法、圖的點(diǎn)數(shù)、邊密度等參數(shù)，就能夠正確得到有限點(diǎn)數(shù)（100點(diǎn)）以?xún)?nèi)所有簡(jiǎn)單連通圖的5種可區(qū)別染色結(jié)果。這些結(jié)果為圖染色學(xué)者和愛(ài)好者提供了基礎(chǔ)研究數(shù)據(jù)，也為科研工作者打算采用圖論技術(shù)解決計(jì)算機(jī)通信、排課表、任務(wù)調(diào)度、倉(cāng)儲(chǔ)分配等組合優(yōu)化問(wèn)題提供幫助。本文的具體工作如下:
　　(1)介紹了Kp\E（kl，m）圖的點(diǎn)可區(qū)別邊色數(shù)猜想，針對(duì)

4、該猜想設(shè)計(jì)并實(shí)現(xiàn)了圖的點(diǎn)可區(qū)別邊色數(shù)猜想證明算法。詳細(xì)描述了算法步驟，并對(duì)算法的正確性進(jìn)行了測(cè)試，同時(shí)對(duì)2000個(gè)頂點(diǎn)以?xún)?nèi)的所有Kp\E(kl，m)圖的點(diǎn)可區(qū)別邊色數(shù)進(jìn)行測(cè)試，測(cè)試結(jié)果表明該猜想是成立的。
　　(2)設(shè)計(jì)并實(shí)現(xiàn)了隨機(jī)圖的點(diǎn)可區(qū)別均勻全染色算法。算法的整體思路是根據(jù)約束條件將染色問(wèn)題分解成多個(gè)子目標(biāo)問(wèn)題，當(dāng)所有子目標(biāo)問(wèn)題都被成功解決后，即代表該染色成功，算法結(jié)束。文中給出了算法的詳細(xì)流程及測(cè)試案例，并分析了算法的正確

5、性和時(shí)間復(fù)雜度。
　　(3)基于OpenMP技術(shù)設(shè)計(jì)并實(shí)現(xiàn)了隨機(jī)有向圖弧染色并行算法。算法中通過(guò)多線程并行搜索染色解空間，從而降低染色成功所需要的時(shí)間，提高染色效率。實(shí)驗(yàn)結(jié)果表明該算法能有效的縮短染色所需時(shí)間。
　　(4)基于JNI技術(shù)實(shí)現(xiàn)圖染色算法與Java平臺(tái)的結(jié)合、基于JGraph技術(shù)實(shí)現(xiàn)染色結(jié)果的可視化，進(jìn)而設(shè)計(jì)并實(shí)現(xiàn)了圖染色軟件系統(tǒng)。該系統(tǒng)包括以下六個(gè)功能模塊:圖染色介紹模塊、圖的顯示模塊、圖的生成模塊、圖染色驗(yàn)證