吳亞平，馮麗珠

（江漢大學 人工智能學院，湖北 武漢 430056）

0 引言

擬陣的概念是由Whitney［1］在1935年和Rado［2］在1942年分別提出的，1959年，Tutte［3］發(fā)展了這一概念。二十世紀擬陣論得到了空前的發(fā)展，擬陣論為組合優(yōu)化和算法設計提供了強有力的工具。擬陣主要研究內(nèi)容包含基圖、超平面、和圖、連通性等。2010年，李萍［4］提出了擬陣圈圖的概念，研究了擬陣圈圖的連通度、擬陣圈圖中的圈和路的性質(zhì)。文獻［5-9］研究了擬陣圈圖的其他性質(zhì)。2020年，劉彬等［10］研究了在某些條件下均勻擬陣二階圈圖的哈密頓性。本文將研究均勻擬陣的三階圈圖的哈密頓性。由于均勻擬陣的三階圈圖是其相應二階圈圖的子圖，所以若均勻擬陣三階圈圖是哈密頓的，則其二階圈圖一定是哈密頓的。

關于擬陣的相關術語可參考文獻［11］。一個擬陣M是一個有序?qū)?E,?)，其中E是一個有限集合，??2E是E中子集的集合，它們滿足以下的公理：

(I1)?∈?；

(I2)若I∈? 且I′?I，則I′ ∈?；

(I3)若I1,I2∈? 且|I1|＜|I2|，則存在e∈I2-I1使得I1?e∈?。

其中，集合? 中的元素稱為擬陣M的獨立集。設M(E,?)是一個擬陣，若子集X??，則X稱為M的一個相關集。極小的相關集叫做極小圈，令C(M)表示由擬陣M的全體極小圈組成的集合。

設n≥m≥0 為兩個整數(shù)，E是個n-元集。令? ={X?E:|X|≤m}，則M(E,?)是個均勻擬陣，記作Um,n。均勻擬陣Um,n的k階圈圖為G，其中頂點集V(G)=C，邊集E(G)={CC′|C,C′∈C,|C?C′|≥k}。這里C和C′既代表G的頂點，也代表擬陣M的圈。

關于圖論的術語參考文獻［12］。設G是一個圖，包含圖G的每個頂點的路稱為圖G的一條哈密頓路；包含圖G的每個頂點的圈稱為圖G的一個哈密頓圈；如果圖G存在一個哈密頓圈，則稱之為哈密頓的。如果圖G中的每對頂點u,v都存在一條u到v哈密頓路，則稱圖G是哈密頓連通的。如果對于圖G的任意一條邊，G都有一個包含這條邊的哈密頓圈，則稱G是正哈密頓的；如果對于圖G的任意一條邊，G都有一個不包含這條邊的哈密頓圈，則稱G是負哈密頓的。如果G既是正哈密頓的，又是負哈密頓的，則稱G是一致哈密頓的。

設G是一個圖，如果G中的任意兩個頂點都相鄰，則稱G是完全圖。

1 預備知識

引理1［12］設G是一個n-階圖，其中n≥3。如果G的每個頂點v都有那么G是哈密頓連通的。

引理2U3,n的三階圈圖共有個頂點，并且是正則圖，其中n≥5，且n為正整數(shù)。

證 明令E={x1,x2,…,xn}，C(U3,n)={X?E:|X|= 4}，從n個 元素中 選取4 個 元素可 以作為U3,n三階圈圖的一個頂點，所以U3,n的三階圈圖共有(n)4 個頂點。任取U3,n的三階圈圖的一個 頂 點{xi,xj,xk,xs}，其 中i≠j≠k≠s且i,j,k,s∈{1,2,…,n}。從{xi,xj,xk,xs}中 的 任取3 個元素，剩下的一個元素需從除了xi,xj,xk,xs之外的n- 4 個元素中選擇，故與{xi,xj,xk,xs}相鄰的頂點有個。又由{xi,xj,xk,xs}的任意性知，U3,n的三階圈圖是正則圖。

引理3U4,n的三階圈圖共有個頂點，并且是正則圖，其中n≥6，且n為正整數(shù)。

證明令E={x1,x2,…,xn}，C(U4,n)={X?E:|X|= 5}，從n個元素中選取5 個元素可以作為U4,n三階圈圖的一個頂點，所以U4,n的三階圈圖共有個頂點。

采用與引理2 類似的證明，任取U4,n的三階圈圖的一個頂點A={xi,xj,xk,xl,xs}，其中i≠j≠k≠l≠s且i,j,k,l,s∈{1,2,…,n}。下面我們求與A相鄰的頂點的個數(shù)。如果A的鄰點與它恰好有3 個元素相同，則滿足這個條件A的鄰點個數(shù)為如果A的鄰點與它恰好有4 個元素相同，則滿足這個條件A的鄰點個數(shù)為

所以與A相鄰的頂點共有個。又由頂點A的任意性可知，U4,n的三階圈圖是正則。

引理4Um,n的三階圈圖共有個頂點，并且是正則圖，其中m,n均為正整數(shù)，且m≥3,n≥m+ 2。

證明令C(Um,n)={X?E:|X|=m+ 1}。由定義知Um,n的三階圈圖共有個頂點。下面證明Um,n的三階圈圖是正則圖。

同引理3 證明，任取Um,n的三階圈圖的一個頂點B={xi1,xi2,…,xim+1}，其中ij≠ik，j≠k，ij∈{1,2,…,n},j= 1,2,…,m+ 1。下面求與B相鄰的頂點的個數(shù)。如果B的鄰點與它恰好有k(3≤k≤m)個元素相同，則滿足這個條件B的鄰點個數(shù)為所以B的 鄰點個數(shù)由于B的任意性，可知Um,n的三階圈圖是正則圖。

引理5［10］若G是完全圖，則G是哈密頓連通的，并且是一致哈密頓的。

2 主要結論

在證明主要結論中，需要用到Pascal 公式和下面這個組合恒等式：

定理1當m+ 2≤n≤2m- 1，m≥3，Um,n的三階圈圖是哈密頓連通的，并且是一致哈密頓的。

證明由引理4 可知，Um,n三階圈圖頂點數(shù)是它是正則圖。

根據(jù)式（1），有

當m+ 2≤n≤2m- 1，可知故

可知

即當m+ 2≤n≤2m- 1，m≥3，Um,n的三階圈圖是完全圖。由引理5 可知，Um,n的三階圈圖是哈密頓連通的，并且是一致哈密頓的。

定理2Um,2m的三階圈圖是哈密頓連通的，m≥3。

證明由引理4 可知，Um,2m三階圈圖頂點數(shù)是它是正則的。

首先證明一個斷言。

斷言

因此斷言成立。

根據(jù)式（1）可知，

根據(jù)斷言，則有

即

根據(jù)引理1，可知Um,2m的三階圈圖是哈密頓連通的。