均匀拟阵四阶圈图的哈密顿性

吴亚平,冯丽珠

(江汉大学 人工智能学院，湖北 武汉 430056)

Whitney[1]在1935年和Rado[2]在1942年分别提出拟阵的概念。后来，Tutte[3]扩展了这一概念。二十世纪拟阵论得到了很大的发展，成为一个重要的数学分支。拟阵论成为了组合优化和算法设计强有力的工具， 它主要研究基图、超平面、和图、连通性、格结构和模性等内容。李萍和刘桂真[4]给出了拟阵圈图的概念，并得到了关于拟阵圈图的连通度、圈和路结论。关于拟阵圈图的其他性质研究参看文献[5-7]。刘彬等[8]研究在特定条件下均匀拟阵二阶圈图的哈密顿性。吴亚平等[9]研究均匀拟阵三阶圈图的哈密顿性。本文进一步考虑均匀拟阵四阶圈图的哈密顿性问题。根据均匀拟阵k阶圈图定义可知，其k阶圈图是其相应l(l

设E是一个有限集合，I⊆2E是E中子集构成的集合， 一个拟阵M是一个有序对(E，I)，且满足(Ι1～Ι3):

(Ι1)∅∈I。

(Ι2)如果I∈I，且I′⊆I，则I′∈I。

(Ι3)如果I1，I2∈I且|I1|<|I2|， 则一定存在e∈I2-I1使得I1∪e∈I。

称集合I中的元素为拟阵M的独立集。令M=(E，I)是一个拟阵， 如果子集X∉I， 则称X为拟阵M的一个相关集。拟阵M中一个极小的相关集称为M的一个极小圈，用C(M)表示拟阵M中所有极小圈构成的集合，不产生混淆的情况下记为C。本文中出现但未介绍的相关拟阵术语参看文献[10]，图论术语参考文献[11]。

设n≥m，n，m∈Z+，有限集合E，|E|=n。令I={X⊆E:|X|≤m}，则(E，I)是均匀拟阵，记作Um，n。均匀拟阵Um，n的k阶圈图记为Ck(Um，n)，其顶点集为C，边集为{CC′|C，C′∈C，|C∩C′|≥k}。这里C和C′既代表Ck(Um，n)的顶点，也代表拟阵Um，n的圈。

U4，2(U5，2)的2阶圈图C2(U4，2)(C2(U5，2))见图1(图2)，U5，3的3阶圈图C3(U5，3)见图3。

图2 U5，2的2阶圈图

图3 U5，3的3阶圈图

1 预备知识

引理5[8]完全图Kn是哈密顿连通的，而且是一致哈密顿的。

2 主要结论

在证明定理1和定理2过程中，将用到下面这个组合恒等式。

(*)

定理1 当m+2≤n≤2m-2，m≥4，Um，n的四阶圈图是哈密顿连通的，并且是一致哈密顿的。

可知

即当m+2≤n≤2m-2，m≥4，Um，n的四阶圈图是完全图。由引理5知，Um，n的四阶圈图是哈密顿连通的，并且是一致哈密顿的。

定理2Um，2m-1的四阶圈图是哈密顿连通的，m≥4。

首先我们来证明一个引理6。

因此引理6成立。

根据引理1，定理2结论成立。