圖的嵌入分布的平均虧格.pdf

1、拋未交通義摯博士學(xué)位論文DOCTORALDISSERTATIoN論文題目目的嵌人分布的平均虧格學(xué)科專業(yè)運(yùn)籌學(xué)與控制隆作者姓名陳儀朝指導(dǎo)教師劉彥佩教攫二零零六年六月摘要拓?fù)鋱D論研究的一個(gè)重要內(nèi)容為圖在曲面上的嵌入的性質(zhì)回顧歷史，拓?fù)鋱D論學(xué)家們首先研究的是圖的最小虧格由于確定圖的最小虧格是NP困難的【25】，因此求解圖的最小虧格或者確定圖的最小虧格的界是一類十分困難的問題，在這方面的研究遠(yuǎn)不夠理想隨后也就是上個(gè)世紀(jì)70年代初，Nordhau

2、s，Stewart和Whitef17]等人提出了圖的最大虧格的概念，因此研究也就轉(zhuǎn)向了確定圖的最大虧格的問題和刻劃，由于NHXuong【28l，LiuYanpei【14]等于上個(gè)世紀(jì)70年代未分別獨(dú)立地給出或部分的給出了刻劃圖的最大虧格的示性定理和Nebesky『181于上個(gè)世紀(jì)80年代初又給出了圖的最大虧格的另外一種對(duì)偶形式的刻劃，因此關(guān)于圖的最大虧格的研究取得了很重要的一步關(guān)于圖的最大虧格最近研究可參見黃元秋的博士論文【13】在他的

3、博士論文里對(duì)圖的最大虧格進(jìn)行了進(jìn)一步的研究總結(jié)及簡(jiǎn)化SStahl[21】及JLGross【89i等于上個(gè)世紀(jì)80年代提出了圖的平均虧格的概念對(duì)圖的平均虧格的研究有助于對(duì)圖在曲面上的嵌入有更深入細(xì)致的了解，由于確定一個(gè)圖的最小虧格是NP困難的，而確定一個(gè)圖的平均虧格的值必須先求出最小虧格，因此確定一個(gè)圖的平均虧格是NP困難問題從目前的參考文獻(xiàn)來看，國(guó)際上主要有兩個(gè)人SStahl【21—25I和ChertJianer[27l在圖的平均虧格領(lǐng)

4、域內(nèi)作了深入的細(xì)致的研究其中SStahl側(cè)重于研究一些特殊圖類的平均虧格[21，22]，隨機(jī)圖的平均虧格[24】等ChenJianer側(cè)重于研究任意單個(gè)圖的平均虧格【24，6】，主要考察將圖的平均虧格作為一個(gè)不變量是否為圖同構(gòu)的一個(gè)不變量(后來發(fā)現(xiàn)并不是)雖然他們著眼及出發(fā)點(diǎn)和所用的方法不一樣但從結(jié)果上看起來確是殊途同歸的(最終還是要得到一好的上下界)，他們?cè)趫D的平均虧格的研究成果可參見文獻(xiàn)[2—4，6，21—25】等圖的平均虧格還有一