關(guān)于圖的最大虧格.pdf

1、圖的可嵌入性的概念源于平面性，早在30年代初，波蘭數(shù)學(xué)家K．Kuatowski和其后美國數(shù)學(xué)家H．Whitney，S．Maclane在圖的可嵌入性方面做過精湛的研究。他們在該方面都創(chuàng)立了各自的理論。50年代，中國數(shù)學(xué)家吳文俊基于代數(shù)拓?fù)鋵W(xué)中的理論揭示了判定圖的平面性的一個(gè)判斷準(zhǔn)則，其后又得到許多學(xué)者的改進(jìn)，提出了更好的算法，如劉彥佩基于確向樹，使算法的復(fù)雜性上達(dá)到了線性頂峰，在圖的平面性和平面嵌入上做出很大的貢獻(xiàn)。隨著研究的深入，到70

2、年代，Nordhuas E，Stewart B，White A等人提出了圖在曲面上的可嵌入性問題，其中最大虧格問題及圖的上可嵌入性是重要的組成部分。 虧格是圖的一個(gè)拓?fù)洳蛔兞?，本文主要總結(jié)和研究了圖在曲面上嵌入的最大虧格，揭示了圖的某種屬性或含有一定特征的圖對其最大虧格的影響。全文分為三部分： 在第一章中，首先介紹了圖論中圖的參數(shù)的基本定義，綜述了圖的嵌入性理論的基本知識(shí)，從圖的平面嵌入引出了圖在曲面上的嵌入，重點(diǎn)敘述了

3、圖的最大虧格理論，兩個(gè)確定最大虧格的基本定理，一個(gè)是Xuong的理論，一個(gè)是Nebesky理論，兩者都是圍繞著與圖的最大虧格十分密切的參數(shù)Betti虧數(shù)的大小，揭示了最大虧格的計(jì)算方法。之后，黃元秋在Nebeski7理論的基礎(chǔ)上，給出了參數(shù)Betti虧數(shù)與圖的特征結(jié)構(gòu)的關(guān)系，為從圖的結(jié)構(gòu)上來研究圖的最大虧格開辟了一個(gè)新的途徑。 在第二章中，介紹了一些目前已得到的關(guān)于圖的最大虧格與某些圖的參數(shù)的理論結(jié)果，這些參數(shù)包括頂點(diǎn)的度，圖的

4、連通度，直徑，圍長，割點(diǎn)，獨(dú)立數(shù)，嵌入的面的度數(shù)，著色數(shù)，正則性，2-因子等．對于圖的直徑，黃元秋和劉彥佩得到了一類直徑為4的不含K<,3>子圖的簡單連通圖的最大虧格的下界，但是該下界并非是緊的下界．在第二節(jié)中，通過分析和證明改進(jìn)了他們的結(jié)果，并發(fā)表了文章，文章中得出改進(jìn)的結(jié)果為緊的下界。最后，對于任意的有限無向的無環(huán)圖，給出了一種構(gòu)造上可嵌入圖的方法。 第三章為結(jié)束語，對最大虧格的某些方面的研究，文中提出了自己的看法，希望所指