2n(1,2n/3)的k―偶匹配可扩性'> 循环图C2n(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.