《圖的匹配理論的多面體方法》是依託鄭州大學，由王秀梅擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：圖的匹配理論的多面體方法
- 項目類別：青年科學基金項目
- 項目負責人：王秀梅
- 依託單位：鄭州大學
項目摘要,結題摘要,
項目摘要
圖的匹配理論有著廣泛的套用背景、豐富的研究課題及深刻的理論結果。由Edmonds創立的匹配多面體理論被認為是數學規劃理論與圖論的完美結合。本項目旨在探討用多面體方法研究匹配理論，推進若干方面的理論發展。 第一，研究Fan-Raspaud猜想（任意無割邊3-正則圖中存在三個完美匹配其交集為空）。我們已初步確立運用完美匹配多面體證明此猜想的途徑，取得部分結果，並實現了與刻面刻畫、brick分解、可去邊存在性等理論課題的聯繫。第二，對已有匹配可擴結構，尚有不少未解問題，包括Plummer猜想（存在多項式時間算法確定一個圖的可擴度）。這個兼有算法與結構特徵的問題也是本項目的主攻方向之一。第三，關於唯一可擴問題，研究PM-緊鄰圖，即除去一個交錯圈後，具有唯一完美匹配的圖。一方面這是完美匹配多面體具有直徑一的刻畫問題，具有獨立的學術價值，另一方面也是證明Fan-Raspaud猜想的一個難點。
結題摘要
圖論與組合最最佳化是兩個交融滲透，互相促進發展的研究領域。匹配理論是圖論與組合最最佳化的核心課題之一。而匹配多面體是整數規劃與圖論的完美結合。本項目研究與完美匹配多面體相關的匹配問題，包括圖的結構性質和算法。研究成果如下：受本項目資助共發表學術論文22篇，其中16篇論文發表於SCI期刊上，包括1篇發表在數學類一區期刊上。本項目的代表性成果如下：（1）對於圖的匹配覆蓋問題（用最少的匹配覆蓋圖的頂點），給出了多項式時間算法：一般圖的時間界是O(n3)，樹的時間界是O(n)；同時給出匹配覆蓋數的界和樹情形匹配覆蓋數的精確刻畫。該論文2014年發表在數學類一區top期刊Mathematical Programming, Ser. A。（2）對於三匹配交猜想（范-Raspaud猜想），證明當完美匹配多面體的維數小於等於10的情況猜想成立；並把猜想歸到完美匹配多面體是3-平坦的情形；（3）對於有唯一完美匹配的圖，推廣前人的成果給出了一個具有結構特性的充分必要條件，利用該條件對具有唯一完美匹配的一些特殊圖類給出了結構刻畫；（4）關於可去邊的存在性，Carvalho, Lucchesi及 Murty (2002) 證明Lovasz的猜想：在brick中存在兩條邊，對於每一條邊的邊刪子圖其brick-分解只有一個Brick。我們把這個結果推廣到near-brick的情形。
