特殊圖的嵌入分布研究.pdf

1、圖論[Graph Theory]是數(shù)學(xué)的一個(gè)數(shù)學(xué)分支，它的研究對象主要是圖.圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系.隨著研究的深入，拓?fù)鋱D論和代數(shù)圖論逐漸發(fā)展成圖論的兩個(gè)重要分支，本文則屬于拓?fù)鋱D論的研究范疇.
　　 圖的曲面嵌入是拓?fù)鋱D論的一個(gè)重要研究方向.根據(jù)虧格的不同，可以給出圖在球面、歐氏和雙曲空間中

2、無邊交叉的實(shí)現(xiàn).對于虧格為0的圖，可以將其嵌入到球面空間;對于虧格為1的圖，可以將其嵌入到環(huán)面或射影平面;對于虧格大于1的圖，我們將其覆蓋空間嵌入到雙曲圓盤中或者Klein瓶中。這種對圖的量化，也是對于抽象關(guān)系的一種量化，有著非常廣的應(yīng)用價(jià)值。圖的嵌入問題在計(jì)算機(jī)科學(xué)等很多領(lǐng)域都有著非常重要的意義.研究圖在不同虧格曲面上的不等價(jià)的嵌入個(gè)數(shù)成為其中一個(gè)重要的分支，這即是圖的虧格分布和完全虧格分布問題.
　　 聯(lián)樹模型的思想，起源于

3、劉彥佩教授，他吸收了前人用多邊形來表示曲面的思想，形成了一套完整的多面形理論.給定圖G的一棵生成樹，把每條非樹邊從中間切斷為兩條邊，即得到一個(gè)圖的聯(lián)樹.從任意一個(gè)節(jié)點(diǎn)出發(fā)沿T和旋走遍聯(lián)樹所有邊，依次記錄非樹邊的字母，則得到圖G的關(guān)聯(lián)曲面S.圖G的關(guān)聯(lián)曲面與其曲面嵌入之間存在著一一對應(yīng)的關(guān)系.因此，聯(lián)樹模型成為研究嵌入分布的一種非常重要的方式，也是本文主要應(yīng)用的方法。
　　 總所周知，圖的虧格分布是NP-HARD問題，對大部分圖類

4、，我們暫時(shí)還不能得出其虧格分布和完全虧格分布.然而，圖在不同虧格曲面上的嵌入個(gè)數(shù)往往有一定的相關(guān)關(guān)系甚至遞推關(guān)系，從而研究圖在某些類型曲面上的個(gè)別嵌入亦有著重要的意義，特別地，研究圖在球面，環(huán)面，射影平面，Klein瓶等小虧格曲面上的嵌入更加有著顯而易見的實(shí)際意義，本論文利用嵌入的聯(lián)樹模型，專門對一些圖類在小虧格曲面上的嵌入進(jìn)行研究，重點(diǎn)研究了圖在射影平面上的嵌入.下面簡要地介紹本論文各章的主要內(nèi)容:
　　 第一章首先對曲面，曲

5、面嵌入，曲面的多邊形表示等概念進(jìn)行敘述，并對拓?fù)鋱D論中關(guān)于曲面嵌入的重要結(jié)論和理論體系進(jìn)行了介紹，隨后介紹了本論文的研究背景.
　　 第二章首先介紹了嵌入的聯(lián)樹模型理論，并給出或證明了一些本論文要用到的重要引理以及一些基本定理，包括射影平面和Klein瓶的多邊形表示形式等.
　　 第三章通過聯(lián)樹模型，研究了Hn在射影平面的嵌入.其中最關(guān)鍵因素即使對邊序列進(jìn)行分類討論，用組合計(jì)數(shù)思想總結(jié)嵌入個(gè)數(shù)。
　　 第四章通過