圖的整譜性理論及其解的計(jì)算機(jī)搜索.pdf

1、圖論是一門(mén)充滿(mǎn)生機(jī)的學(xué)科。它與理論計(jì)算機(jī)科學(xué)有密切的關(guān)系，圖論為研究理論計(jì)算機(jī)科學(xué)提供了強(qiáng)有力的數(shù)學(xué)工具，高速發(fā)展的計(jì)算機(jī)技術(shù)又促進(jìn)了圖論學(xué)科的發(fā)展。圖論在以信息為特征的知識(shí)經(jīng)濟(jì)時(shí)代具有重要的前瞻性和廣泛的應(yīng)用前景。本論文選擇圖論及其應(yīng)用中的重要課題“圖的整譜性理論及其解的計(jì)算機(jī)搜索”作為研究對(duì)象，旨在對(duì)圖的整譜性理論做深入的研究，并推廣和發(fā)展國(guó)內(nèi)外著名圖論專(zhuān)家的重要結(jié)果。為圖的整譜性理論的研究開(kāi)辟一些新的研究方向，增添新的研究活力。同

2、時(shí)，探索如何有效地使用高性能計(jì)算機(jī)這一強(qiáng)有力的工具，快捷、及時(shí)、準(zhǔn)確地得到圖的譜的整數(shù)解。 本論文主要研究了“圖的整譜性理論及其解的計(jì)算機(jī)搜索”，選題屬于本學(xué)科前沿，是國(guó)內(nèi)外非?；钴S的研究領(lǐng)域。其主要研究?jī)?nèi)容和主要研究成果如下：·本論文的主要研究?jī)?nèi)容為：1、主要研究直徑為4，5，6和8整樹(shù)及其解的計(jì)算機(jī)搜索。2、主要研究整譜圖的幾種新的構(gòu)造方法和一些特定圖的整譜性問(wèn)題。3、主要研究完全r部整圖及其解的計(jì)算機(jī)搜索。4、主要研究正則

3、拉普拉斯整圖和正則整圖及其生成樹(shù)數(shù)目的計(jì)算問(wèn)題。 ·本論文的主要研究成果為：1、通過(guò)粘接兩棵樹(shù)的中心，構(gòu)造了幾類(lèi)新的直徑為4的整樹(shù)K1，·T(m，t)和直徑為6的整樹(shù)K1,s·T(r，m，t)，并利用數(shù)論知識(shí)，以計(jì)算機(jī)為工具，證明了這些直徑為4和6的整樹(shù)新類(lèi)都有無(wú)窮多個(gè)。所得結(jié)果與已有文獻(xiàn)中所給出的結(jié)果都不相同。這對(duì)在此基礎(chǔ)上構(gòu)作直徑更大的整樹(shù)會(huì)有所幫助。 2、給出了一些直徑為4，6和8的整樹(shù)新類(lèi)，并利用經(jīng)典數(shù)論，以計(jì)算

4、機(jī)為工具，證明了這些整樹(shù)新類(lèi)都有無(wú)窮多個(gè)。也證明了尋找這樣的整樹(shù)問(wèn)題等價(jià)于去求一些特定的不定方程解的問(wèn)題。并用不同的方法獨(dú)立地證明了P.Híc和R.Nedela在1998年首次證明的存在無(wú)窮多個(gè)直徑為8的平衡整樹(shù)的結(jié)論，而且我們所給出的直徑為8的整樹(shù)與他們所給出的完全不同。 3、從新的角度構(gòu)造了直徑為4的所有樹(shù)的一般特征多項(xiàng)式。得到了幾類(lèi)新的直徑為4的整樹(shù)。它們與已有文獻(xiàn)中的結(jié)果都完全不同。這為徹底解決直徑為4的整樹(shù)提供了新的思

5、路。 4、利用計(jì)算機(jī)搜索，并分析結(jié)果，從而得到了幾類(lèi)新的直徑為4，6和8的整樹(shù)。這些整樹(shù)類(lèi)中絕大多數(shù)都有無(wú)窮多個(gè)。這對(duì)在此基礎(chǔ)上構(gòu)造別的整樹(shù)會(huì)有所幫助。 5、利用連邊和粘接的方法構(gòu)造了直徑為5和6的整樹(shù)新類(lèi)，并利用計(jì)算機(jī)、數(shù)論知識(shí)及其相關(guān)的理論得到這些整樹(shù)新類(lèi)都有無(wú)窮多個(gè)。這些結(jié)果與已有文獻(xiàn)中的結(jié)果都不同。構(gòu)造的直徑為5和6的整樹(shù)具有新的結(jié)構(gòu)，使在此基礎(chǔ)上構(gòu)造直徑為7乃至更大直徑的整樹(shù)有可能實(shí)現(xiàn)。 6、用幾種新的

6、方法構(gòu)造了一些整圖新類(lèi)，并證明了這些整圖新類(lèi)有無(wú)窮多個(gè)。同時(shí)證明了尋找這樣的整樹(shù)問(wèn)題與求解一些特定的不定方程的問(wèn)題等價(jià)。 7、給出了完全r部圖是整圖的一個(gè)充分必要條件，并巧用計(jì)算機(jī)和數(shù)論知識(shí)給出了構(gòu)造任意多個(gè)這樣的整圖新類(lèi)的方法。并證明了尋找這樣的整圖問(wèn)題與求一些不定方程的解的問(wèn)題等價(jià)。這些完全r部整圖的發(fā)現(xiàn)是對(duì)尋找這樣的整圖的一個(gè)新的貢獻(xiàn)。推廣了M.Roitman關(guān)于完全三部整圖的結(jié)論。 8、利用矩陣的理論給出了圖Kp

7、[Kp-1]的譜及其特征多項(xiàng)式，同時(shí)也得到了其補(bǔ)圖、線(xiàn)圖、線(xiàn)圖的補(bǔ)圖及補(bǔ)圖的線(xiàn)圖的特征多項(xiàng)式。也給出了這些圖的生成樹(shù)數(shù)目的計(jì)算公式。并證明了這些圖不僅是整圖而且是拉普拉斯整圖。拉普拉斯整譜圖是圖的整譜性研究方面又一新的研究方向。這些結(jié)果推廣了國(guó)際圖論大家F.Harary和A.J.Schwenk的一個(gè)重要結(jié)果。同時(shí)這些整圖的發(fā)現(xiàn)是對(duì)尋找這樣的整圖的一個(gè)新的貢獻(xiàn)。 最后，我們對(duì)本論文的結(jié)果加以總結(jié)，并對(duì)進(jìn)一步的研究給予展望。