圖的整譜性理論及其解的計算機搜索.pdf

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

2、時，探索如何有效地使用高性能計算機這一強有力的工具，快捷、及時、準確地得到圖的譜的整數(shù)解。 本論文主要研究了“圖的整譜性理論及其解的計算機搜索”，選題屬于本學科前沿，是國內外非常活躍的研究領域。其主要研究內容和主要研究成果如下：·本論文的主要研究內容為：1、主要研究直徑為4，5，6和8整樹及其解的計算機搜索。2、主要研究整譜圖的幾種新的構造方法和一些特定圖的整譜性問題。3、主要研究完全r部整圖及其解的計算機搜索。4、主要研究正則

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

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

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

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

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