均勻擬陣四階圈圖的哈密頓性

吳亞平,馮麗珠

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

Whitney[1]在1935年和Rado[2]在1942年分別提出擬陣的概念。后來，Tutte[3]擴展了這一概念。二十世紀擬陣論得到了很大的發(fā)展，成為一個重要的數學分支。擬陣論成為了組合優(yōu)化和算法設計強有力的工具， 它主要研究基圖、超平面、和圖、連通性、格結構和模性等內容。李萍和劉桂真[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結論成立。