《三正則圖的嵌入性質及其套用》是依託中國人民大學，由魏二玲擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：三正則圖的嵌入性質及其套用
- 項目類別：青年科學基金項目
- 項目負責人：魏二玲
- 依託單位：中國人民大學
項目摘要,結題摘要,
項目摘要
三正則圖是非常重要的一類圖。本項目擬對三正則圖的曲面嵌入理論及其套用進行研究。我們已知圖的最大虧格的計算存在多項式算法，但限制在三正則圖上，劉彥佩曾提出猜想：三正則圖的最大虧格的計算存線上性算法。本項目擬對這個問題進行研究。對應於最小虧格，問題難度增加，因為圖的最小虧格的計算是NP困難的。本項目擬對具有特殊結構，對稱性比較強的三正則圖，計算其最小虧格，豐富最小虧格領域的研究內容。對對稱性強的三正則圖，計算其虧格分布，強虧格分布。在理論研究的基礎之上，套用圖的曲面嵌入理論，擬對圖的消圈數進行探討。消圈數在計算機理論中有重要的實際意義。我們將研究Xuong樹與消圈數之間的關係，以及正則圖，平面圖的消圈數的顯性求解，推動消圈數問題的研究。這些結果大大超越了目前這方面的已有結果。
結題摘要
本項目對三正則的嵌入性質及其套用進行了研究。項目的重要結果之一是對圖的消圈數的研究，區別於以往從組合角度的研究，我們得到了從拓撲角度來刻畫的結果。與刻畫圖的嵌入相類似，Xuong樹在圖的消圈數的刻畫中也可以起到很重要的作用。另一方面，我們得到了圖的以化學指標的研究。最後，我們還對三正則的頂點特殊劃分進行了研究。
