關(guān)于圖的最大虧格的一些新研究.pdf

1、拓撲圖論最初是研究怎樣把圖畫在曲面上使得任何兩條邊互不相交，這個直觀的幾何問題隨著其它數(shù)學(xué)分支，特別是代數(shù)拓撲、群論、組合計數(shù)理論以及算法分析等的介入而變得豐富多彩，目前拓撲圖論的研究領(lǐng)域可分為兩個主流：一是研究圖在曲面上嵌入的性質(zhì)；另一個研究地圖計數(shù)問題.本文研究屬第一個方面，即研究圖的嵌入的最大虧格問題. 連通圖G在緊的閉曲面S上的嵌入指存在一個同胚映射φ：G→S使得S→φ（G）的每個連通分支都同胚于一個開圓盤，這樣的嵌入稱

2、為胞腔嵌入.根據(jù)S是可定向曲面或者是不可定向曲面，這樣的嵌入又分別稱為可定向嵌入或不可定向嵌入，圖G的最大虧格指圖G所能嵌入曲面的虧格中最大的那一個.因為圖的任何嵌入必至少含有一個面，由歐拉公式易得圖的最大虧格的一個上界：其中符號（）指不超過α的最大整數(shù)，｜E（G）｜-｜V（G）｜+1被稱為圖G=（V（G），E（G））的Betti數(shù)并用符號β（G）表示.如果γM（G）=（），則圖G被稱為上可嵌入的.最大虧格問題起源于Nordhaus、S

3、tewart和White1971年的文章[31]，劉彥佩[21]和Xuong[38]于1979年分別獨立地得到了關(guān)于圖的嵌入的最大虧格的經(jīng)典定理，隨后，由于諸多學(xué)者對這一問題的關(guān)注與研究使得這一問題取得重大進展.其研究分為兩個方面：一是圖的上可嵌入性的研究；二是對非上可嵌入圖的最大虧格的界的研究.因為任意圖在不可定向曲面上總是上可嵌入的，因此最大虧格問題只討論圖在可定向曲面上的嵌入. 在本論文中，一方面，借助已有的研究成果對圖的

4、最大虧格問題進行了深入地研究，得出了一些新結(jié)果，改進了一些已知結(jié)果；另一方面，借助劉彥佩提出的聯(lián)樹法，對最大虧格問題從另一個方面進行了一些嘗試性的研究，并取得一些初步進展，本文可分為以下幾個部分： 第一章介紹圖的最大虧格問題的背景知識以及一些基本概念和術(shù)語， 第二章研究了直徑-3圖中的加邊運算與最大虧格. 第三章結(jié)合圖的圍長以及相鄰頂點或非鄰頂點的度和研究圖的上可嵌入性。 第四章研究非上可嵌入圖的最大虧格