李亞寧，劉彬，鄧梓健，王麗煊，火博豐，2，尹君

（1.青海師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，青海 西寧 810008；2.青海省物聯(lián)網(wǎng)重點(diǎn)實(shí)驗(yàn)室，青海 西寧 810008）

0 引言

擬陣的概念最早是由Whitney［1］在1935年提出的。它是矩陣的向量空間和圖的圈空間及鍵空間的推廣。1942年Rado［2］提出了有關(guān)擬陣的一些性質(zhì)，Tutte［3-7］發(fā)展了這一概念，并研究了擬陣和圖的性質(zhì)以及擬陣的連通性等問(wèn)題。1972年Holzmann和Haray［8］研究并證明了擬陣基圖的一致哈密頓性。Alspach等［9］研究得到了擬陣基圖中路和圈的性質(zhì)，并證明了簡(jiǎn)單擬陣的基圖是哈密頓連通的邊泛圈圖。在此之后鄧漢元和李榮珩［10］與夏方禮［11］先后研究了擬陣基圖的1-哈密頓性與P3-哈密頓性，進(jìn)一步證明基之間的關(guān)系。一個(gè)擬陣的基圖能夠反映該擬陣的不同基之間的變換關(guān)系。因此，研究擬陣的基圖有助于更好了解擬陣的性質(zhì)。為了研究連通擬陣中圈的性質(zhì)，李萍［12］提出擬陣圈圖的概念，得出了擬陣圈圖的哈密頓性［13-16］、連通度［17］和圈圖中圈和路的性質(zhì)［18］，并把圈圖的概念推廣為n階圈圖，從而得到了n階圈圖的一些性質(zhì)。對(duì)于一階圈圖的哈密頓性，已經(jīng)有了一般性的結(jié)果：設(shè)G=G(M)是一個(gè)連通擬陣M的圈圖，而且B是M的一個(gè)基，則G的連通度［7］κ(G)≥2|E-B|-2。設(shè)G=G(M)是一個(gè)連通擬陣M的圈圖，而且G的最小度是δ(G)，則G的邊連通度κ′(G)=δ(G)。設(shè)G=G(M)是一個(gè)連通擬陣M的圈圖，而且M含有至少4個(gè)圈，則G是一致哈密頓的［14］。為研究一般連通擬陣的二階圈圖的哈密頓性，本文在擬陣的一階圈圖已有結(jié)果基礎(chǔ)上，探究了完全二部圖K2，n和K3，n的圈擬陣的二階圈圖的哈密頓性。

1 基礎(chǔ)知識(shí)

定義1［19-20］一個(gè)擬陣M是一個(gè)有序?qū)?E，?)，其中E是有限集合，??2E是E中子集的集合，滿足以下的公理：

（I2）若I∈?，及I?I′，則I′∈?；

（I3）若I1，I2∈?，且|I1|＞|I2|，則存在e∈I2-I1使得I1∪e∈?。

集合?中的獨(dú)立元素成為擬陣M的獨(dú)立集。設(shè)M(E，?)是一個(gè)擬陣，若子集X??，則令X稱為M的一個(gè)相關(guān)集。極小的相關(guān)集為極小圈。令C(M)表示由擬陣M的全體極小圈組成的集合。

定義2［19］對(duì)于擬陣M，如果存在某個(gè)圖G，使得擬陣M同構(gòu)于圖G的圈擬陣，那么稱M為可圖擬陣。

定義3［12］設(shè)擬陣M圈圖為G，其中頂點(diǎn)集V(G)=C，邊集E(G)={CC′|C，C′∈C，|C∩C′|≠0}，這里C和C′既代表G的頂點(diǎn)，也代表擬陣M的圈。設(shè)擬陣M的二階圈圖為G，其中頂點(diǎn)集V(G)=C，邊集E(G)={CC′|C，C′∈C，|C∩C′|≥2}，這里C和C′既代表G的頂點(diǎn)，也代表擬陣M的圈。

定義4［21］設(shè)G是一個(gè)圖，如果V(G)可以被劃分為集合U和W，使得uw是G的邊當(dāng)且僅當(dāng)u∈U且w∈W，則稱圖G為完全二部圖。如果|U|=s且|W|=t，那么這個(gè)完全二部圖有（s+t）個(gè)頂點(diǎn)和st條邊且可以由Ks，t（或Kt，s）表示。

定義5［20］設(shè)G是一個(gè)圖，包含圖G的每個(gè)頂點(diǎn)的路稱為圖G的一條哈密頓路；包含圖G的每個(gè)頂點(diǎn)的圈稱為圖G的一個(gè)哈密頓圈；如果圖G存在一個(gè)哈密頓圈，則稱之為哈密頓的。如果圖G中的每對(duì)頂點(diǎn)u，v都存在一條u到v的哈密頓路，則稱圖G是哈密頓連通的。

定義6［20］對(duì)于任意的整數(shù)k，且滿足3≤k≤n，圖G的每對(duì)頂點(diǎn)含有長(zhǎng)度為k的圈，那么圖G就是泛圈圖。

定義7［22］設(shè)G是一個(gè)圖，如果G中的任意兩個(gè)頂點(diǎn)都相鄰，則稱G是完全圖。

定義8［23］設(shè)G是一個(gè)圖，如果對(duì)于所有v∈V(G)，有d(v)=k，則圖G是k-正則圖。

引理1［24］設(shè)G是n(n≥3)階簡(jiǎn)單圖，w是最小度的頂點(diǎn)，如果則G是哈密頓的。

引理2(Menger定理)［21］G是一個(gè)頂點(diǎn)數(shù)≥k+1的圖，圖G是k-連通的當(dāng)且僅當(dāng)圖中任意兩個(gè)不同的頂點(diǎn)都被至少k條內(nèi)部不相交的路連接。

2 主要定理

定理1完全二部圖K2，n(n≥2)的圈擬陣的一階和二階圈圖相同，是一個(gè)個(gè)頂點(diǎn)的(2n-4)-正則圖，并且連通度是(2n-4)。

證明顯然，在完全二部圖K2，n中的圈，是個(gè)數(shù)恰好等于在這n個(gè)點(diǎn)中取兩個(gè)點(diǎn)的組合數(shù)的4-圈，且如果圈與圈之間存在公共邊，則公共邊的數(shù)目為2，因此K2，n(n≥2)的圈擬陣的一階和二階圈圖是具有個(gè)頂點(diǎn)的相同的圖。

將K2，n中有兩個(gè)點(diǎn)的分部中的兩個(gè)點(diǎn)分別設(shè)為O和O′，另一分部中的n個(gè)點(diǎn)分別設(shè)為1，2，…，n。將經(jīng)過(guò)O，i，O′，j四點(diǎn)的圈標(biāo)記為{i，j}。則二階圈圖的頂點(diǎn)集合為V(C2(K2，n))={{i，j}|i，j=1，2，…，n，i≠j}。二階圈圖中任何兩點(diǎn){i，j}與{k，l}相鄰當(dāng)且僅當(dāng)|{i，j}∩{k，l}|=1。對(duì)于其中任意一個(gè)頂點(diǎn){i，j}它的鄰點(diǎn)為{i，s}，s≠i，j；{j，t}，t≠i，j；s，t∈{1，2，…，n}，共[ ]2(n-2)個(gè)。因此完全二部圖K2，n(n≥2)的圈擬陣的二階圈圖是(2n-4)-正則圖。

對(duì)于二階圈圖中任何兩點(diǎn){i，j}與{k，l}，如果它們不相鄰，即i，j，k，l各不相同，則有如下（2n-8）條長(zhǎng)為3的路連接{i，j}與{k，l}：

{i，j}→{i，s}→{k，s}→{k，l}|；{i，j}→{j，s}→{l，s}→{k，l}|，s∈{1，2，…，n}，s≠i，j，k，l。另有4條長(zhǎng)為2的路：

{i，j}→{i，k}→{k，l}|，{i，j}→{i，l}→{k，l}|，{i，j}→{j，k}→{k，l}|，{i，j}→{j，l}→{k，l}|。容易看出這些路的內(nèi)部點(diǎn)都是各不相同的，因此得到(2n-4)條內(nèi)部不交的路。

對(duì)于二階圈圖中任何相鄰兩點(diǎn){i，j}與{j，k}，i，j，k各不相同，則有如下（n-3）條長(zhǎng)為3的路連接{i，j}與{j，k}：{i，j}→{i，s}→{k，s}→{j，k}|，s∈{1，2，…，n}，s≠i，j，k。

另 有（n-3）條 長(zhǎng) 為2的 路 連 接{i，j}與{j，k}：{i，j}→{j，s}→{j，k}|，s∈{1，2，…，n}，s≠i，j，k。一 條 長(zhǎng) 為2的 路 連 接{i，j}與{j，k}：{i，j}→{i，k}→{j，k}。一 條 邊 即 長(zhǎng) 為1的 路 連 接{i，j}與{j，k}：{i，j}→{j，k}。容易看出這些路的內(nèi)部點(diǎn)都是各不相同的，因此得到(2n-4)條內(nèi)部不交的路。

根據(jù)引理2得此二階圈圖的連通度為(2n-4)。

定理2完全二部圖K2，n(n≥3)的圈擬陣的二階圈圖是哈密頓的。

證明如圖1所示，K2，n對(duì)應(yīng)的二階圈圖有個(gè)頂點(diǎn)，可表示為V(K2，n)={{i，j}|i，j=1，2，…，n，i≠j}。由擬陣圈圖的定義及以上列出的頂點(diǎn)發(fā)現(xiàn)，其子集Vi={{i，j}|j=1，2，…，n，i≠j}中任意兩個(gè)點(diǎn)之間都有邊相連，因此由Vi所導(dǎo)出的二階圈圖的子圖是完全圖，顯然，完全圖是哈密頓連通的。而i≠j時(shí)點(diǎn)集Vi與點(diǎn)集Vj有公共點(diǎn){i，j}，因此很容易得到此二階圈圖的哈密頓圈。如哈密頓圈表 示 在Vi中{i，j}到{i，s}的一條哈密頓路。因此完全二部圖K2，n(n≥3)的圈擬陣的二階圈圖是哈密頓的。

圖1 完全二部圖K2，nFig.1 Complete bipartite graphs K2，n

定理3完全二部圖K2，n(n≥3)的圈擬陣的二階圈圖是泛圈的。

證明針對(duì)K2，n的情形，對(duì)n用數(shù)學(xué)歸納法證明。當(dāng)n=3時(shí)，K2，n對(duì)應(yīng)的二階圈圖為完全圖K3，顯然是泛圈的。假定結(jié)論對(duì)于n=4，5，…，n-1成立。因此K2，n-1的圈擬陣的二階圈圖是泛圈的。在K2，n-1的二階圈圖中可以找到包含長(zhǎng)度從的圈。由定理1和定理2，K2，n的圈擬陣的二階圈圖有個(gè)頂點(diǎn)，且是哈密頓的。因此存在經(jīng)過(guò)每個(gè)頂點(diǎn)的圈。因?yàn)镵2，n是由K2，n-1增加（n-1）個(gè)頂點(diǎn){1，n}，{2，n}，…，{n-1，n}得到，且K2，n的頂點(diǎn){1，2，3，…，n}具有對(duì)稱性，因此只需要證明對(duì)于所有個(gè)圈頂點(diǎn)存在包含它的長(zhǎng)度從到的圈。

在K2，n-1的二階圈圖基礎(chǔ)之上先增加一個(gè)頂點(diǎn){i，n}(i=1，2，…，n-1)，可找到一個(gè)包含它的長(zhǎng)度為的圈，以此類推，當(dāng)增加到（n-2）個(gè)頂點(diǎn)時(shí)，可以找到包含它們的長(zhǎng)度為的圈，而即存在長(zhǎng)度為的圈。

綜上所述，在K2，n的圈擬陣的二階圈圖中存在長(zhǎng)度為到的圈。即K2，n(n≥3)的圈擬陣的二階圈圖是泛圈的。

定理4完全二部圖K2，n(n≥3)的圈擬陣的二階圈圖是哈密頓連通的。

證明由定理1可得，K2，n對(duì)應(yīng)的二階圈圖有個(gè)頂點(diǎn)，將其頂點(diǎn)集表示為V(K2，n)={{i，j}|i，j=1，2，…，n，i≠j}，其子集為Vi={{i，j}|j=1，2，…，n，i≠j}，在其子集中任意兩個(gè)點(diǎn)之間都有邊相連，因此由Vi所導(dǎo)出的二階圈圖的子圖是完全圖，顯然完全圖是哈密頓連通的。而i≠j時(shí)點(diǎn)集Vi與點(diǎn)Vj有公共點(diǎn){i，j}，所 以 在 其 二 階 圈 圖 中 可 以 找 到{1，2}→{1，3}→…→{2，3}→{2，4}→…{n-2，n-1}→{n-1，n}的哈密頓路，從而可以發(fā)現(xiàn)任意兩個(gè)頂點(diǎn)都有哈密頓路連接，所以K2，n(n≥3)的圈擬陣的二階圈圖是哈密頓連通的。

定理5完全二部圖K3，n(n≥3)的圈擬陣的二階圈圖是哈密頓的。

證明如圖2所示，將K3，n中有三個(gè)點(diǎn)的分部中的三個(gè)點(diǎn)分別設(shè)為a，b，c，另一分部中的n個(gè)點(diǎn)分別設(shè)為1，2，…，n。K3，n的圈都是4-圈和6-圈，4-圈是從a，b，c和這n個(gè)點(diǎn)中分別取兩個(gè)點(diǎn)的組合，所以個(gè)數(shù)恰好等于。6-圈是將a，b，c與另一個(gè)分部中的n個(gè)點(diǎn)中任取三個(gè)點(diǎn)排列，所以個(gè)數(shù)恰好等于從n個(gè)元中任取三個(gè)元的排列數(shù)A3n。隨著圈個(gè)數(shù)的增加，頂點(diǎn)的最小度也在逐漸變化，利用引理證明更為復(fù)雜。

圖2 完全二部圖K3，nFig.2 Complete bipartite graphs K3，n

因此對(duì)n用數(shù)學(xué)歸納法證明。當(dāng)n=3時(shí)，顯然，K3，n對(duì)應(yīng)的二階圈圖是哈密頓的。假定結(jié)論對(duì)于n=4，…，n-1成立。因此K3，n-1對(duì)應(yīng)的二階圈圖是哈密頓的，其二階圈圖的頂點(diǎn)包括了4-圈和6-圈在二階圈圖中所代表的頂點(diǎn)。其4-圈的個(gè)數(shù)為個(gè)，6-圈的個(gè)數(shù)為A3n-1個(gè)。在其4-圈中含(a，b)，(a，c)，(b，c)的圈分別含有另一個(gè)分部的{i，j}(i≠j且i，j=1，2，3，…，n-1)，其6-圈是在一個(gè)分部中含有(a，b，c)，另一個(gè)分部中含有{i，j，k}(i≠j≠k且i，j，k=1，2，…，n-1)。已知其對(duì)應(yīng)的二階圈圖是哈密頓的，所以其4-圈 與6-圈 作 為 圈 頂 點(diǎn) 在 二 階 圈 圖 中 存 在 哈 密 頓 圈{i，j}→{i，j，k}→{i，j}。K3，n與K3，n-1相比，其4-圈個(gè)數(shù)增加了[ 3(n-1)]個(gè)，6-圈個(gè)數(shù)增加了[A3n-A3n-1=3(n-1)(n-2)]個(gè)。在其4-圈中含(a，b)，(a，c)，(b，c)分別增加了{(lán)1，n}，{2，n}，…，{n-1，n}的圈，且此時(shí)在新增的4-圈中，在a，b，c分部相同時(shí)，圈與圈之間有一個(gè)公共元n則有連邊；在a，b，c分部不完全相同時(shí)，圈與圈在{i，n}(i=1，2，…，n-1)中兩個(gè)元均相同時(shí)才有連邊。在其新增的4-圈中可以找到與新增的6-圈中有連邊的圈，例如4-圈(a，1，b，n)與6-圈(a，1，b，n，c，i)(i≠1，n)均有連邊。且6-圈中若在1，2，3，…，n的分部中若有兩個(gè)公共元?jiǎng)t有連邊，即在新增的6-圈中也可以找到連邊。所以K3，n的圈擬陣的二階圈圖中存在哈密頓圈，即K3，n(n≥3)的圈擬陣的二階圈圖是哈密頓的。

定理6完全二部圖K3，n(n≥3)的圈擬陣的二階圈圖是哈密頓連通的。

證明當(dāng)n=3時(shí)，顯然，K3，n對(duì)應(yīng)的二階圈圖是哈密頓連通的，利用K2，n的圈擬陣的二階圈圖是K3，n的圈擬陣的二階圈圖的子圖，且在K3，n的6-圈在對(duì)應(yīng)的二階圈圖中所構(gòu)成的圖是完全圖的前提下而證明得出的。但發(fā)現(xiàn)當(dāng)n≥5時(shí)，其6-圈在對(duì)應(yīng)的二階圈圖中所構(gòu)成的圖不是完全圖，因此對(duì)n用數(shù)學(xué)歸納法證明。假設(shè)n=4，…，n-1時(shí)結(jié)論成立，即K3，n-1的圈擬陣的二階圈圖是哈密頓連通的。在K3，n-1的4-圈中含(a，b)，(a，c)，(b，c)的圈分別含有另一個(gè)分部的{i，j}(i≠j且i，j=1，2，3，…，n-1)，將其4-圈簡(jiǎn)記為{i，j}(i≠j且i，j=1，2，3，…，n-1)，其6-圈 是 在 一 個(gè) 分 部 中 含 有(a，b，c)，另 一 個(gè) 分 部 中 含 有{i，j，k}(i≠j≠k且i，j，k=1，2，…，n-1)，將6-圈簡(jiǎn)記為{i，j，k}(i≠j≠k且i，j，k=1，2，…，n-1)。所以在其對(duì)應(yīng)的二階圈圖中可以找到從4-圈對(duì)應(yīng)的圈頂點(diǎn)到6-圈對(duì)應(yīng)的圈頂點(diǎn)的哈密頓路{i，j}→{i，j，k}。

那么K3，n與K3，n-1相比，4-圈中含(a，b)，(a，c)，(b，c)的圈分別新增了{(lán)1，n}，{2，n}，…，{n-1，n}的圈，在新增的4-圈對(duì)應(yīng)的圈頂點(diǎn)中可以找到連邊的頂點(diǎn)，即{1，n}→{2，n}→…→{n-1，n}。在其6-圈中新增了含有n的頂點(diǎn)，6-圈與6-圈在1，2，3，…，n中若有兩個(gè)公共元?jiǎng)t有連邊，且在新增的4-圈與6-圈中若含有n以及其它公共元，則可以找到連邊，所以在K3，n的圈擬陣的二階圈圖中同樣可以找到從4-圈到6-圈的哈密頓路{i，j}→{i，j，k}，此時(shí)i≠j≠k且i，j，k=1，2，…，n。

綜上所述，K3，n的圈擬陣的二階圈圖是哈密頓連通的。

猜想1完全二部圖K2，n和K3，n的圈擬陣的二階圈圖是具有一致哈密頓性的。