吳亞平,馮麗珠

(江漢大學(xué) 人工智能學(xué)院，湖北 武漢 430056)

Whitney[1]在1935年和Rado[2]在1942年分別提出擬陣的概念。后來，Tutte[3]擴(kuò)展了這一概念。二十世紀(jì)擬陣論得到了很大的發(fā)展，成為一個重要的數(shù)學(xué)分支。擬陣論成為了組合優(yōu)化和算法設(shè)計強(qiáng)有力的工具， 它主要研究基圖、超平面、和圖、連通性、格結(jié)構(gòu)和模性等內(nèi)容。李萍和劉桂真[4]給出了擬陣圈圖的概念，并得到了關(guān)于擬陣圈圖的連通度、圈和路結(jié)論。關(guān)于擬陣圈圖的其他性質(zhì)研究參看文獻(xiàn)[5-7]。劉彬等[8]研究在特定條件下均勻擬陣二階圈圖的哈密頓性。吳亞平等[9]研究均勻擬陣三階圈圖的哈密頓性。本文進(jìn)一步考慮均勻擬陣四階圈圖的哈密頓性問題。根據(jù)均勻擬陣k階圈圖定義可知，其k階圈圖是其相應(yīng)l(l

設(shè)E是一個有限集合，I?2E是E中子集構(gòu)成的集合， 一個擬陣M是一個有序?qū)?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的一個相關(guān)集。擬陣M中一個極小的相關(guān)集稱為M的一個極小圈，用C(M)表示擬陣M中所有極小圈構(gòu)成的集合，不產(chǎn)生混淆的情況下記為C。本文中出現(xiàn)但未介紹的相關(guān)擬陣術(shù)語參看文獻(xiàn)[10]，圖論術(shù)語參考文獻(xiàn)[11]。

設(shè)n≥m，n，m∈Z+，有限集合E，|E|=n。令I(lǐng)={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 預(yù)備知識

引理5[8]完全圖Kn是哈密頓連通的，而且是一致哈密頓的。

2 主要結(jié)論

在證明定理1和定理2過程中，將用到下面這個組合恒等式。

(*)

定理1 當(dāng)m+2≤n≤2m-2，m≥4，Um，n的四階圈圖是哈密頓連通的，并且是一致哈密頓的。

可知

即當(dāng)m+2≤n≤2m-2，m≥4，Um，n的四階圈圖是完全圖。由引理5知，Um，n的四階圈圖是哈密頓連通的，并且是一致哈密頓的。

定理2Um，2m-1的四階圈圖是哈密頓連通的，m≥4。

首先我們來證明一個引理6。

因此引理6成立。

根據(jù)引理1，定理2結(jié)論成立。