圖的路匹配.pdf

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

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

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

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

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

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