圖的路匹配.pdf

1、作為匹配和擬陣交的共同推廣，Cunningham和Geelen在1996年引入了圖的路匹配的概念.他們指出許多領域的問題都可以轉化為路匹配問題，也就是說，利用路匹配可以解決例如匹配、擬陣、多面體以及代數(shù)等很多方面的問題.作為路匹配的應用，他們給出了可匹配集合多面體的強多項式分離算法，并證明了最大路匹配的值就等于給定圖所確定的匹配擬陣中項點集合的秩，同時也等于Tutte矩陣的秩等等. 本文共分為六章，第一章著重介紹了路匹配的應用背

2、景以及路匹配自引入以來的主要研究成果，并且在此基礎上概述了本文得到的主要結論.第二章和第三章主要是通過最大路匹配來刻畫圖的結構，在最后的三章中我們考慮了給定圖的最大路匹配的大小以及完美路匹配的可擴性等問題. 在2004年，Spille和Szego給出了與通常匹配意義下的Gallai-Edmonds分解{A，C, D}類似的一種項點分解{A1，C1，D1｝，并且給出了相應的結構定理.我們已經(jīng)知道集合A就等于圖中所有極大障礙集合的交

3、集.在第二章中，我們將這一著名結果推廣到了路匹配的框架中，從而得到了關于A1的一個表達式. 在Gallai-Edmonds結構定理中，由D所導出的圖的每個分支都是因子臨界的(即刪去任意一點后都有完美匹配).對于這類圖的刻畫在匹配理論中已經(jīng)得到了.而路匹配分解中的D1所導出的圖不一定是因子臨界的.因此，在第三章中我們刻畫了由D1所導出的圖，并且討論了D1所導出的圖中兩類分支之間的內(nèi)在關系. Frank和Szego給出了一般

4、圖中有完美路匹配的一個刻畫，事實上這個結果是Tutte定理的一個直接推廣.但是從這個結果中得到的一個圖有完美路匹配的充分條件卻非常強，很難滿足.因此，在第四章中我們集中考慮了完美路匹配在一般圖以及一些特殊圖類中存在的條件.對于一般圖給出了極集合條件和聯(lián)接數(shù)型條件，并且更進一步地證明了這些聯(lián)接數(shù)型條件在某種意義下是最好的.對于特殊圖，我們考慮了正則圖和以t+1個項點的星作為禁止子圖的無K1，t圖，得到了在這兩類圖中存在完美路匹配的條件.

5、 一個圖G=(V，T1,T2;E)的路匹配數(shù)val(G)是描述G中最大路匹配大小的一個參數(shù).在第五章中，我們用兩種不同的方式給出了val/(G)的界.第一個界是用關于聯(lián)接數(shù)b，│V│，和│Ti│的一個函數(shù)給出來的，這里i=1，2.并且從這個結果可以得到Woodall關于圖的最大匹配所含邊數(shù)的界.第二個界所考慮的是無K1,t圖，我們用關于t,連通度m，│V│，和│Ti│的某個函數(shù)給出了val/(G)的界. 在第四章中，我們已

6、經(jīng)討論了一個圖有完美路匹配的充分條件.那么如果我們加強這些條件是否就能夠使得任意一個值為n的正常路匹配都可以通過某種擴張成為完美路匹配呢?在本文的最后一章中，我們給出了關于路匹配n-可擴的定義，這種定義從本質(zhì)上講是匹配可擴的一個推廣.我們得到了一個圖在項點數(shù)│V│和n+k有相同的奇偶性，或k>n時n-可擴的聯(lián)接數(shù)型充分條件(這里k是圖G中端集合的大小)，并且說明了這些充分條件在某種意義下是最好的.由此產(chǎn)生的一個推論將Chen關于匹配可擴