發(fā)布時(shí)間：2020-05-17 09:36

【摘要】：圖論是數(shù)學(xué)的一個(gè)重要分支,也是計(jì)算機(jī)等基礎(chǔ)學(xué)科的基礎(chǔ),它是以圖作為研究對(duì)象,現(xiàn)實(shí)中很多問題都可以抽象為圖,從而轉(zhuǎn)化為圖論的應(yīng)用問題來解決,例如由著名的數(shù)學(xué)家哈密爾頓提出的周游世界的問題,旅行商問題、數(shù)獨(dú)游戲;在工程上,經(jīng)常遇到的資源分配與調(diào)度問題、組合優(yōu)化問題;通信領(lǐng)域的通信信道分配、電路布線問題等,這些問題都可以利用圖論的知識(shí)來解決。隨著社會(huì)的發(fā)展、科學(xué)技術(shù)的進(jìn)步,圖論的研究不僅僅限于數(shù)學(xué)上的推理與證明,而是與眾多學(xué)科交叉融合發(fā)展,近年來圖論研究取得了很大的發(fā)展,廣泛的應(yīng)用于計(jì)算機(jī)科學(xué)、通信網(wǎng)絡(luò)、信信息科學(xué)、人工智能、圖像處理、物理以及化學(xué)等領(lǐng)域,并取得了很多重要的研究成果。圖論的一個(gè)常用應(yīng)用就是在有機(jī)化學(xué)領(lǐng)域,早在半個(gè)多世紀(jì)前Gunthard和Primas在研究化學(xué)中的Huckel理論時(shí)提出了'哪些圖是譜確定的?',這一問題的解決涉及到圖譜理論,主要通過圖矩陣的數(shù)量特征來確定圖是否由譜唯一確定,否則尋找其同譜偶的問題。后來,著名的數(shù)學(xué)化學(xué)家Gutman提出了圖能量的理論,就是借助于譜來研究化學(xué)分子的相關(guān)性質(zhì)的理論。本文設(shè)計(jì)算法求得了兩種特殊圖的同譜圖和給定點(diǎn)數(shù)下的非完全-拉普拉斯界能圖。圖的染色問題是圖論的一個(gè)重要研究方向,而且具有極強(qiáng)的應(yīng)用性。傳統(tǒng)的染色是利用數(shù)學(xué)的方法進(jìn)行染色,隨著計(jì)算機(jī)的逐漸發(fā)展,利用計(jì)算機(jī)設(shè)計(jì)算法實(shí)現(xiàn)染色,這是圖染色問題的一大飛躍。例如傳統(tǒng)的智能算法:遺傳算法、粒子群優(yōu)化算法、神經(jīng)網(wǎng)絡(luò)等應(yīng)用于圖染色問題,但是這些智能算法一般僅能解決單目標(biāo)的染色。雖然近年來出現(xiàn)了新的染色算法,但是僅能實(shí)現(xiàn)規(guī)模較小的圖染色。隨著社會(huì)的發(fā)展,為了滿足日常研究需要大規(guī)模圖出現(xiàn)了,此時(shí),已有的算法已經(jīng)不能滿足需求,本文針對(duì)此問題設(shè)計(jì)了算法,求得了大規(guī)模圖的鄰點(diǎn)可區(qū)別全染色,經(jīng)過大量的實(shí)驗(yàn)得出了確切的結(jié)論,為以后圖論的發(fā)展奠定了基礎(chǔ)。論文分為三大部分,文章的主要內(nèi)容如下:(1)第一部分介紹了圖論和圖染色的基本概念、相關(guān)理論以及圖論在化學(xué)領(lǐng)域的應(yīng)用,如同分異構(gòu)問題和能量問題。同時(shí)對(duì)已有研究方法的優(yōu)缺點(diǎn)進(jìn)行了總結(jié)。(2)在第二部分中包含兩類,第一類給出了兩種特殊圖(Π-型圖和星圖)的生成算法以及同譜偶求解算法,具體思想是第一步輸入頂點(diǎn)數(shù)目,按照基本規(guī)則生成連通圖,然后根據(jù)本文需要設(shè)計(jì)規(guī)則和判斷函數(shù),生成Π-型圖和星圖;第二步設(shè)計(jì)求譜算法,并對(duì)第一步所生成的Π-型圖和星圖求譜,求得譜后進(jìn)行比較,最后得出譜相同的圖的結(jié)構(gòu);第二類給出了固定階數(shù)下的所有圖的生成算法和拉普拉斯能量求解算法,具體思想是首先生成給定階數(shù)下的所有圖;然后設(shè)計(jì)拉普拉斯能量算法,針對(duì)所生成的所有圖求能量,最后找出本文所需要的圖。這兩大部分算法為后續(xù)圖論在其他學(xué)科領(lǐng)域的研究和證明提供基礎(chǔ)研究數(shù)據(jù),尤其為圖論在化學(xué)領(lǐng)域的研究奠定良好的基礎(chǔ)。(3)在第三部分中,設(shè)計(jì)并實(shí)現(xiàn)了大規(guī)模圖的生成算法和分割算法、鄰點(diǎn)可區(qū)別全染色算法,同時(shí)設(shè)計(jì)了正常全染色算法、染色沖突調(diào)整算法等子算法。具體思想是生成隨機(jī)連通圖,然后按照分割規(guī)則將大圖分割為多個(gè)子圖,在對(duì)子圖進(jìn)行鄰可區(qū)別全染色,最終確保相鄰頂點(diǎn)的顏色不同,相鄰邊的顏色不同,相鄰頂點(diǎn)與邊的顏色不同,相鄰頂點(diǎn)的色集合不同。本文通過大量的實(shí)驗(yàn)驗(yàn)證了算法的正確性,同時(shí)得到了一定數(shù)量的結(jié)果。
【圖文】：

蘭州交通大學(xué)碩士學(xué)位論文 00010110001001010000101101110100011010010101101010111000010000008765432112345678vvvvvvvvvvvvvvvv圖 5.7 分割后子圖2G 的鄰接矩陣斷，，分割后的兩個(gè)子圖大小滿足分割要求，因此大圖分割成功，完成 2，程序運(yùn)行結(jié)果及文本輸出結(jié)果如下：

圖 5.9 分割程序文本輸出結(jié)果.4 算法分析(1) 算法正確性本算法是尋找圖中的二度及以上的點(diǎn)斷開，符合分割的基本思想，由分割測(cè)試達(dá)到了無損分割的要求，分割后的子圖能重新還原為大圖，證明了分割的正確(2) 算法實(shí)用性算法能夠?qū)崿F(xiàn) 5000 個(gè)點(diǎn)的大圖的無損分割，解決了大圖無法處理的問題，降復(fù)雜度，提高了處理效率，為圖論的研究提供了很好的思路，同時(shí)在復(fù)雜網(wǎng)絡(luò)物理等學(xué)科的應(yīng)用提供了基礎(chǔ)研究數(shù)據(jù)。 大規(guī)模圖的鄰點(diǎn)可區(qū)別全染色算法.1 鄰點(diǎn)可區(qū)別全染色的定義及相關(guān)概念定義 5.1 對(duì)于一個(gè)簡(jiǎn)單連通圖 G (V ,E)，其階數(shù)不小于 2， V (G)是圖的頂點(diǎn)集)是 圖的邊 集 合。其 k 正常全染色是指對(duì)于圖 , 存在一個(gè)
【學(xué)位授予單位】：蘭州交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：O157.5

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李敬文;賈西貝;董威;李小慧;閆光輝;;圖的鄰點(diǎn)可區(qū)別全染色算法[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2015年02期

2 馬春燕;王治文;陳祥恩;楊芳;姚兵;;若干完全四部圖的可區(qū)別正常邊染色[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2013年21期

3 李敬文;張?jiān)坪?陳志鵬;孫亮;;圖的點(diǎn)可區(qū)別邊染色算法研究[J];計(jì)算機(jī)應(yīng)用研究;2014年03期

4 陳祥恩;王治文;趙飛虎;魏甲靜;姚兵;;若干強(qiáng)積圖及合成圖的鄰點(diǎn)可區(qū)別一般邊染色[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2013年06期

5 趙煥平;李冬梅;李敬文;;一種應(yīng)用于完全圖的點(diǎn)可區(qū)別強(qiáng)全染色新算法[J];計(jì)算機(jī)應(yīng)用與軟件;2013年03期

6 趙煥平;劉平;李敬文;;完全圖的點(diǎn)可區(qū)別強(qiáng)全染色算法[J];計(jì)算機(jī)工程;2012年17期

7 陳祥恩;王治文;趙飛虎;姚兵;;幾類弱積圖的鄰點(diǎn)可區(qū)別一般邊染色[J];蘭州大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年01期

8 王忠;;一種由鄰接譜確定的樹[J];青海師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年03期

9 吳寶豐;袁西英;;圖的能量的幾個(gè)可達(dá)下界(英文)[J];華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年04期

10 劉翼舉;侯耀平;;一些由它的鄰接譜和角確定的圖[J];邵陽學(xué)院學(xué)報(bào)(自然科學(xué)版);2009年02期

相關(guān)博士學(xué)位論文 前1條

1 計(jì)省進(jìn);關(guān)于圖能量的若干問題的研究[D];南開大學(xué);2012年

相關(guān)碩士學(xué)位論文 前2條

1 王倩;隨機(jī)圖的Smarandachely點(diǎn)可區(qū)別染色算法研究[D];蘭州交通大學(xué);2014年

2 寧媛媛;圖論在化學(xué)能量和網(wǎng)絡(luò)方面的應(yīng)用[D];廣東工業(yè)大學(xué);2008年

本文編號(hào)：2668316