《完美匹配的性質》是依託鄭州大學，由王秀梅擔任項目負責人的面上項目。
基本介紹
- 中文名：完美匹配的性質
- 項目類別：面上項目
- 項目負責人：王秀梅
- 依託單位：鄭州大學
項目摘要,結題摘要,
項目摘要
匹配理論是圖論與組合最最佳化的核心研究課題之一。匹配多面體是整數規劃與圖論的完美結合。本項目從多面體和結構性質兩個方面探討完美匹配的性質，目的是做出創新的成果並促進多面體理論在圖論中的套用。主要圍繞Fan-Raspaud猜想（2-連通三正則圖中存在三個完美匹配其交集為空）和Norine-Thomas猜想（存在正數a使得在每個極小磚圖中度為3的頂點數至少是a|V|）從以下方面展開研究：（1）特定多面體的線性不等式組表示及其整性。 如果描述Fan-Raspaud猜想的不等式組有整解猜想即得證。（2）三正則磚圖的結構性質及極小磚圖度為3的頂點數目的上界。（3）三正則圖完美匹配多面體的遞歸性：包括多面體的分數點及各種刻面的性質等。（4）具有特殊完美匹配多面體的三正則圖類的刻畫：包括平坦的、直徑為1的、簡單的和單純的多面體等。進而擴展遞歸基礎，並開拓多面體理論的研究領域。
結題摘要
圖論與組合最最佳化是兩個交融滲透，互相促進發展的研究領域。匹配理論是圖論與組合最最佳化的核心課題之一。而匹配多面體是整數規劃與圖論的完美結合。本項目研究Fan-Raspaud猜想（任一無割邊的三正則圖中都存在三個完美匹配其交集是空集）、與完美匹配多面體和圈結構相關的完美匹配問題。研究成果如下：受本項目資助共發表學術論文19篇，其中16篇論文發表於SCI期刊上。此外，關於該項目的研究內容投稿在審3篇論文。本項目取得的代表性成果如下：（1）對完美匹配多面體組合直徑為1的實心磚圖（solid brick）給出了完全刻畫。在這個結果的基礎上進一步對Birkhoff-von Neumann圖和完美匹配多面體組合直徑為1的圖的交集的給出了完全的刻畫。論文投稿《SIAM Journal on Discrete Mathematics》，審稿人的一審意見是小的修改（minor revision），目前二審中。這個成果對於我們進一步刻畫完美匹配多面體組合直徑為1的圖和Birkhoff-von Neumann圖這兩類圖具有重要意義。（2）對Fan-Raspaud猜想，含有有四個奇圈構成的2-因子的無橋三正則圖，1-哈密爾頓圖和2-哈密爾頓圖，我們證明猜想成立。 此外，我們把猜想中的“存在三個完美匹配其交為空集”的性質放在更大的圖類匹配覆蓋圖上研究，得到具有這種性質的匹配覆蓋圖的一個充分必要條件，利用這個條件刻畫了一些圖類。這開闢了關於完美匹配性質研究的一個新專題。（3）在研究過程中，我們注意到完美匹配交錯圈與完美匹配的研究有著密切的關係。對圈強迫的二部圖、三正則無爪圖給出了刻畫，對導出圈友好的三正則無爪圖，對圈友好的平面無爪圖、弦圖給出了刻畫。
