圖的厚度與虧格

《圖的厚度與虧格》是依託天津大學，由楊艷擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：圖的厚度與虧格
• 項目類別：青年科學基金項目
• 項目負責人：楊艷
• 依託單位：天津大學

項目摘要

圖的厚度是指圖的可平面子圖分解中所含子圖的最少個數．圖的(可定向或不可定向)虧格是指圖所能嵌入(可定向或不可定向)曲面的最小虧格．圖的厚度和虧格作為圖的拓撲不變數，是衡量圖的不可平面性的重要指標，同時在超大規模積體電路的布局設計中也有重大的套用價值．但是由於圖的厚度問題是NP-困難的，圖的虧格問題是NP-完全的，目前國內外的已有結果並不多．本項目將以圖的厚度和虧格為研究對象，擬得到一些特殊圖類的厚度和(可定向和不可定向)虧格，改進圖的厚度與可定向虧格間的關係，並得到圖的厚度與不可定向虧格間的關係．這些結果的取得將會豐富拓撲圖論的方法與理論，同時為實際套用打下堅實的基礎．

結題摘要

本項目以圖的厚度與虧格為研究對象，得到了一些完全多部圖的厚度，圖經過各種運算後新圖的厚度，如點聯合，邊聯合圖的厚度，笛卡兒積圖的厚度，聯圖的厚度等，以及一些完全三部圖的四圍長厚度。本項目的研究極大地豐富了厚度研究的結果與方法。