趙偉　王忍

【摘要】本文主要根據(jù)Tutte定理、循環(huán)圖的BM-可擴(kuò)性、Hamilton圖等完美匹配理論系統(tǒng)證明了循環(huán)圖C2n（1，2n/3）的k-偶匹配可擴(kuò)性.

【關(guān)鍵詞】循環(huán)圖；完美匹配；偶匹配

一、引 言

匹配理論是圖論的核心內(nèi)容之一，它包含一系列內(nèi)容豐富而深刻的理論問題，作為新的和更一般的組合方法的催化劑，具有很強(qiáng)的生機(jī)和活力，而且應(yīng)用廣泛，如：“人員分配問題”中的完美匹配問題和“最優(yōu)分配問題”中的最大匹配問題.人類在研究匹配問題中，誕生了一系列傳世之作，如：刻畫偶圖具有完美匹配的Hall定理、刻畫一般圖具有完美匹配的Tutte定理、不具有完美匹配圖的GallaiEdmonds結(jié)構(gòu)定理、求偶圖最大權(quán)匹配的匈牙利方法、求非偶圖最大權(quán)匹配的開花算法等.本文主要證明了循環(huán)圖C2n（1，2n/3）當(dāng)n=3，6，9，12時(shí)的k-偶匹配可擴(kuò)性.

二、循環(huán)圖C2n1，2n/3的k-偶匹配可擴(kuò)性

由原晉江給出的C2n（1，2）和C2n（1，n）的導(dǎo)出匹配可擴(kuò)性[1]和李建民、惠志昊給出的循環(huán)圖C2n（1，3）的2-偶匹配可擴(kuò)性[2][3]理論，容易證明：循環(huán)圖C6（1，2）是1-偶匹配可擴(kuò)的.

根據(jù)Tutte定理、循環(huán)圖的BM-可擴(kuò)性、Hamilton圖我們可以證明：循環(huán)圖C12（1，4），C18（1，6），C24（1，8）都是2-偶匹配可擴(kuò)的.

下面我們僅給出“C24（1，8）是2-偶匹配可擴(kuò)的”證明.

證明：取循環(huán)圖C24（1，8）的一偶匹配M，根據(jù)這一偶匹配M的基數(shù)進(jìn)行分類討論：

如果|M|=1，且M中是步長(zhǎng)為1的邊xixi+1，則循環(huán)圖C24（1，8）中的偶圈x0x1…x23x0去掉兩個(gè)相鄰的頂點(diǎn)xi，xi+1后仍完美匹配，若M的步長(zhǎng)為8的邊xixi+8，則H=xi+1xi+2…xi+7xi-1…xi+9xi+1 為所求的哈密頓圈，故存在完美匹配.因此，循環(huán)圖C24（1，8）是1-偶匹配可擴(kuò)的.

綜上所述，根據(jù)偶匹配可擴(kuò)的定義知，循環(huán)圖C24（1，8）任一基數(shù)2的偶匹配M，都可擴(kuò)充為圖C24（1，8）中一個(gè)完美匹配，得證循環(huán)圖C24（1，8）是2-偶匹配可擴(kuò)的.

【參考文獻(xiàn)】

[1] Yuan J J.Induced matching extendable graphs[J].Journal of Graph Theory，1998，28：203-213.

[2] 惠志昊，李建民.步長(zhǎng)為1 和 3 的2n 階循環(huán)圖的導(dǎo)出匹配可擴(kuò)性[J].河南科學(xué)，2010，28（10）：24-26.

[3]李建民，惠志昊.Harary圖的偶匹配可擴(kuò)性[J].河南大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，40（2），126-129.