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

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

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

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

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