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

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

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

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

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

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