論確定圖的最小虧格.pdf

1、圖在曲面上的可嵌入性是拓撲圖論的主要問題，其中圖的最小虧格問題是NP-困難的，所以對解決任意圖的最小虧格仍需很長的一段距離?；诖?，本文主要是在劉彥佩提出的聯(lián)樹模型的基礎(chǔ)上，選擇考慮了有趣且有意義的圖類來研究其最小虧格問題，除此之外還計算了特定圖類的可定向嵌入的虧格分布。本文所考慮的圖類對已研究最小虧格或虧格分布的圖類有一定的推廣作用，所用方法提升了計算技巧，從而為更廣泛圖類的最小虧格及虧格分布問題的研究提供了更廣闊的前景。本研究分為七

2、個部分： 第一章首先對這兩方面的研究背景作了簡要的介紹.隨后，給出了一些與之相關(guān)的定義和性質(zhì)。 第二章首先利用異于以前的方法得到了完全二部圖的最小虧格.然后基于完全二部圖關(guān)聯(lián)曲面的特點進行推廣，構(gòu)造了對稱性比較弱的新圖類J（m，n）且得其最小虧格，最后對完全二部圖不同最小虧格嵌入的數(shù)目作了估算。 第三章構(gòu)造了對稱性比較弱的新圖類T（n，l，m）且得其最小虧格.作為推論得到了完全三部圖Kn，n，l（l≥n≥2）的最

3、小虧格.最后對完全三部圖Kn，n，l不同最小虧格嵌入的數(shù)目作了估算。 第四章研究了邊合并圖的最小虧格.文獻[1，2]分別討論了完全圖與完全圖，完全二部圖與完全二部圖邊合并的最小虧格問題，本章給出了n個特定圖邊合并的最小虧格。 第五章討論了幾類圖與一節(jié)點的聯(lián)圖的最小虧格.而平面圖與一節(jié)點的聯(lián)圖亦為apex圖.眾所周知，apex圖是拓撲圖論中比較重要的一類圖，在圖的最小虧格問題研究中具有強大的作用. Mohar證明了apex

4、圖的最小虧格問題是NP-困難的，本章考慮了幾類平面圖與一節(jié)點的聯(lián)圖，即為apex圖，以及兩類未必是平面的圖與一節(jié)點聯(lián)圖的最小虧格。 第六章，推廣了[21]中“珠子”的類，構(gòu)造了異于目前已知虧格分布的圖類，所用方法主要是根據(jù)給定圖類的特點，選擇確切的支撐樹，把關(guān)聯(lián)曲面集合進行分類，建立遞推關(guān)系式，進而得給定圖類的可定向嵌入虧格分布的顯式表達式，由此可進一步考慮具有任意多節(jié)點且其度大于3和4的此類正則圖的可定向嵌入虧格分布。