循環圖C_2n（1，2n/3）的k—偶匹配可擴性

趙偉　王忍

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

【關鍵詞】循環圖；完美匹配；偶匹配

一、引 言

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

二、循環圖C2n1，2n/3的k-偶匹配可擴性

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

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

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

證明：取循環圖C24（1，8）的一偶匹配M，根據這一偶匹配M的基數進行分類討論：

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

綜上所述，根據偶匹配可擴的定義知，循環圖C24（1，8）任一基數2的偶匹配M，都可擴充為圖C24（1，8）中一個完美匹配，得證循環圖C24（1，8）是2-偶匹配可擴的.

【參考文獻】

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

[2] 惠志昊，李建民.步長為1 和 3 的2n 階循環圖的導出匹配可擴性[J].河南科學，2010，28（10）：24-26.

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