《對缺失n可擴圖的研究》是依託華南師範大學，由溫雪蓮擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：對缺失n可擴圖的研究
- 項目類別：青年科學基金項目
- 項目負責人：溫雪蓮
- 依託單位：華南師範大學
項目摘要,結題摘要,
項目摘要
缺失n可擴圖是對n可擴圖在奇數頂點的圖上的擴展。在連通度不小於2的缺失2可擴偶圖頂點數較多的分類中任意刪除一個頂點，剩下的圖是基本圖，而基本圖是匹配理論中的基礎圖類，因此對缺失n可擴圖的研究進展也是對整個匹配理論的貢獻。同時，缺失n可擴偶圖是任務數與資源數相差1的資源可擴分配問題的數學模型。對缺失n可擴圖的研究，有助於解決這類套用問題。此外，從已有的關於缺失n可擴圖的結論可知，缺失n可擴圖的結論並不是n可擴偶圖的已知結論的簡單移植。因此，缺失n可擴圖是值得研究的。現有的對缺失n可擴圖的結論主要集中在缺失1可擴偶圖。本項目擬從缺失n可擴偶圖的結構、刻畫、有效判定算法和圖參數性關係等方面對缺失n可擴偶圖進行研究，進而研究缺失n可擴一般圖的結構和刻畫。研究成果將填補當前對缺失n可擴圖以上方面研究的空白，為進一步研究缺失n可擴一般圖奠定基礎，使可擴圖理論更為充實和完整，促進匹配理論的發展。
結題摘要
缺失n可擴圖是對Plummer提出的n可擴圖在奇數頂點的圖上的擴展，是匹配理論中的基礎圖類，因此，對缺失n可擴偶圖的研究進展也是對整個匹配理論的貢獻。同時，缺失n-可擴偶圖是任務數與可用資源數相差1的可擴資源配置問題的數學模型，對缺失n-可擴偶圖的研究，不但有助於解決這類套用問題，而且對於解決任務書和資源數相差大於1的資源分配問題也有一定的輔助作用。本項目對極小缺失n可擴偶圖的刻畫、有效判定算法、最小點數的缺失n-可擴偶圖的刻畫、平面圖缺失n-可擴圖的性質進行研究。用M-交錯路以及通過刪除割點得到的連通分支的性質分別刻畫了不同連通度和n值的極小缺失n-可擴偶圖，找到了比極小缺失n-可擴偶圖定義更有效判定算法；通過構造圖例證明了連通度為1的平面圖可能為任意缺失n-可擴圖；此外，在對缺失n-可擴圖哈密頓性研究過程中也得到了有向圖存在有向哈密爾頓圈的充分條件以及存在完美對集M的偶圖G包含M-交錯哈密頓圈的充分條件並揭示了1-可擴圖與完美2-對集覆蓋圖之間的關係以及極小1-可擴圖與極小完美2-對集覆蓋圖的關係。研究成果填補了當前對缺失n-可擴圖以上方面研究的空白，為進一步研究缺失n-可擴一般圖以及兩個分類的頂點數相差大於1的可擴圖的研究奠定基礎，使可擴圖理論更為充實和完整。
