幾個(gè)特定圖類的嵌入虧格.pdf

1、本論文主要研究的是一些圖類的曲面嵌入虧格.曲面在拓?fù)鋵W(xué)中，就是無邊緣的緊2-維流形，分為可定向曲面和不可定向曲面.圖G在曲面上的一個(gè)嵌入是指存在一個(gè)1-1連續(xù)映射h:G→ S，即G的每個(gè)頂點(diǎn)對(duì)應(yīng)S上不同的點(diǎn)，然后將圖G的邊作為連接S上相應(yīng)端點(diǎn)之間的連續(xù)曲線，使得所有代表邊的曲線自身無重點(diǎn)，且除端點(diǎn)外不與其它曲線相交.若S-G中每個(gè)連通部分都同胚于一個(gè)開圓盤，則圖G嵌入到曲面S上稱為2-胞腔嵌入.一個(gè)圖G的虧格是指圖G可嵌入的所有可定向（

2、不可定向）曲面中最小的曲面的虧格，記為γ(G)((γ)(G)).相似的，有圖G的最大虧格γM(G)((γ)M(G)).記gi((g)i）為圖G在可定向曲面Si（不可定向曲面Ni）上的不等價(jià)的嵌入個(gè)數(shù)，i≥0(i≥1)，則序列g(shù)γ(G)，gγ(G)+1，…，gγM(G)((g)(γ)(G)，(g)γ(G)+1，…，(g)(γ)M(G))為圖G的（不可定向）虧格嵌入分布.虧格作為研究網(wǎng)絡(luò)復(fù)雜性的重要依據(jù)，能夠指示出網(wǎng)絡(luò)設(shè)計(jì)的效率，虧格越小，

3、設(shè)計(jì)越有效率.
　　下面簡(jiǎn)要介紹本文各章的內(nèi)容.
　　第一章:簡(jiǎn)要回顧了圖的嵌入理論的起源和發(fā)展，之后介紹了一些相關(guān)的基本概念，以及文章涉及的已有結(jié)論.
　　第二章:首先，基于對(duì)平衡超立方體圖的研究，算出它的最小虧格.其次，分析了折疊超立方體的結(jié)構(gòu)，優(yōu)化其最小虧格的上界，它們的最大虧格由四邊連通性直接得到.
　　第三章:利用覆蓋矩陣，導(dǎo)出一類類循環(huán)圖在可定向曲面上的虧格分布.
　　第四章:給出兩類圖，廣義p