林躍峰

(漳州城市職業(yè)學(xué)院經(jīng)濟(jì)管理系，中國(guó)漳州 363000)

一個(gè)紐結(jié)是指三維歐氏空間的一條簡(jiǎn)單閉曲線.一個(gè)鏈環(huán)是指有限個(gè)互不相交的紐結(jié)纏繞在一起的圖，每一個(gè)紐結(jié)稱為鏈環(huán)的一個(gè)分支，一個(gè)鏈環(huán)包含的紐結(jié)的個(gè)數(shù)稱為鏈環(huán)分支數(shù).盡管鏈環(huán)圖是三維歐氏空間圖，我們總可以用鏈環(huán)投影圖(即滿足在每個(gè)二重投影點(diǎn)的鄰近兩短線上下互相穿越交叉的規(guī)則投影的投影圖)來(lái)刻畫鏈環(huán).

平面圖的平面嵌入稱為平圖，即無(wú)符號(hào)平圖.一個(gè)符號(hào)平圖指每條邊都標(biāo)有±號(hào)的平圖.在紐結(jié)理論中，鏈環(huán)投影圖與符號(hào)平圖有著一一對(duì)應(yīng)關(guān)系.這種對(duì)應(yīng)被應(yīng)用于構(gòu)造鏈環(huán)圖表［1］.將鏈環(huán)投影圖的交叉點(diǎn)置換成相交點(diǎn)，所得到的圖對(duì)應(yīng)于無(wú)符號(hào)平圖的中間圖.

文獻(xiàn)［2］研究平圖G 的左右回路數(shù)，即平圖G 對(duì)應(yīng)的中間圖M(G)的直走閉跡回路數(shù)［3］，也就是平圖G通過(guò)中間圖M(G)構(gòu)造所對(duì)應(yīng)的鏈環(huán)圖L(G)的鏈環(huán)投影圖D(G)的連通分支數(shù).平圖G 對(duì)應(yīng)的鏈環(huán)分支數(shù)［4-5］，記為μ(D(G)).研究平圖的鏈環(huán)分支數(shù)，是研究通過(guò)平圖的中間圖構(gòu)造對(duì)應(yīng)的鏈環(huán)圖的基本問(wèn)題之一.文獻(xiàn)［4，6］研究了一類鏈環(huán)，其分支數(shù)不小于對(duì)應(yīng)的平圖的基圈數(shù).文獻(xiàn)［7，8］分別研究了二維方格圖Lm×n=Pm×Pn(如圖1(a)所示)和三角格圖Tm×n(如圖1(b)所示)的鏈環(huán)分支數(shù).文獻(xiàn)［9］研究了扇圖和輪圖的鏈環(huán)分支數(shù).關(guān)于圖的結(jié)構(gòu)和平圖的鏈環(huán)分支數(shù)有關(guān)的工作，見(jiàn)文獻(xiàn)［10～14］.

由二維方格圖Lm×n的每個(gè)小方格內(nèi)分別增加一條對(duì)角邊(如圖1(c)所示)，其左起奇數(shù)(偶數(shù))列的小方格內(nèi)增加的對(duì)角邊以該小方格左下(上)角和右上(下)角的頂點(diǎn)為兩端點(diǎn)，所得的m×n 交錯(cuò)三角格圖記為ATm×n.本文研究交錯(cuò)三角格圖ATm×(2m－2)(m≥2)和ATm×n(2≤m≤4)的鏈環(huán)分支數(shù).

圖1 (a)方格圖Lm×n;(b)三角格圖Tm×n;(c)交錯(cuò)三角格圖ATm×nFig.1 (a)Quadrilateral lattices Lm×n;(b)Triangular lattices Tm×n;(c)Alternating triangular lattices ATm×n

1 幾個(gè)已知的引理

下面是關(guān)于無(wú)符號(hào)平圖的3 類Reidemeister 變換(以下簡(jiǎn)記為R-變換).無(wú)符號(hào)平圖的R-變換對(duì)應(yīng)于紐結(jié)理論中的鏈環(huán)投影圖的3 類Reidemeister 變換.

Ⅰ變換:刪除一個(gè)環(huán)或收縮一條割邊.分別見(jiàn)圖2 的Ⅰ(a)和Ⅰ(b);

Ⅱ變換:刪除一對(duì)平行邊或收縮一對(duì)序列邊.分別見(jiàn)圖2 的Ⅱ(a)和Ⅱ(b);

Ⅲ變換:YΔ-變換或ΔY-變換.見(jiàn)圖2 的Ⅲ.

圖2 平圖的R-變換Fig.2 Plane graphical Reidemeister moves

令G1∪G2表示2 個(gè)圖G1和G2的不交并.

引理1［14］平圖G 在R-變換下:或刪除環(huán)、或收縮割邊、或刪除一對(duì)平行邊、或收縮一對(duì)序列邊、或YΔ－變換或ΔY－變換，不改變其鏈環(huán)分支數(shù).

引理2［7］設(shè)G 是平圖，則μ(D(G))=k 當(dāng)且僅當(dāng)G 能通過(guò)有限次無(wú)符號(hào)平圖的R-變換變換為空?qǐng)DOk.

引理3［7］設(shè)G 和H 是2 個(gè)平圖，x1，x2，…，xn和u1，u2，…，un分別是G 的外部面F 的n 個(gè)頂點(diǎn)和H 的某個(gè)面的n 個(gè)頂點(diǎn).對(duì)于每個(gè)i(i=1，2，…，n)，若dG(xi)≤1，設(shè)Ci是D(G)的圍繞G 的頂點(diǎn)xi且將xi與G中其他頂點(diǎn)分離的分支;若dG(xi)＞1，設(shè)Ci是D(G)的連續(xù)穿過(guò)面F 的邊界上的頂點(diǎn)xi的2 條關(guān)聯(lián)邊且與G 的這2 個(gè)交叉點(diǎn)之間的連邊在面F 內(nèi)的分支.若μ(D(G))=n 且D(G)的分支C1，C2，…，Cn兩兩不同，則μ(D(G(x1，x2，…，xn)∪H(u1，u2，…，un)))=μ(D(H)).

2 交錯(cuò)三角格圖ATm×(2m－2)(m≥2)的鏈環(huán)分支數(shù)

本節(jié)研究并證明交錯(cuò)三角格圖ATm×(2m－2)(m≥2)的鏈環(huán)分支數(shù).

將二維m×m 方格圖Lm×m左起第一列小方格中的每一個(gè)小方格分別都增加一條以該小方格左下角和右上角的頂點(diǎn)為兩端點(diǎn)的對(duì)角邊，且對(duì)最后一行的除左起第一條邊之外的每一條邊分別都新增一個(gè)剖分點(diǎn)，這樣得到的m×m 格圖記為圖Bm(圖3(左邊第1 個(gè)圖)為圖B5).

引理4設(shè)m 是正整數(shù)，且m≥2，則μ(D(Bm))=m.

證對(duì)正整數(shù)m 用歸納法證明.當(dāng)m=2，3 時(shí)，因B2和B3可由平圖的R-變換分別變換為O2和O3.由引理1 和引理2 知，μ(D(B2))=μ(D(O2))=2，μ(D(B3))=μ(D(O3))=3.故當(dāng)m=2，3 時(shí)，結(jié)論成立.現(xiàn)在假設(shè)對(duì)于所有的m≤k(k≥3，k 為正整數(shù))，結(jié)論成立.則當(dāng)m=k+1 時(shí)，因Bk+1可經(jīng)平圖的R-變換變換為Bk∪O1，見(jiàn)圖3.由引理1、引理2 和歸納假設(shè)，知μ(D(Bk+1))=μ(D(Bk))+1=k+1.根據(jù)歸納法原理，引理4 成立.

圖3 Bk+1變換為Bk∪O1Fig.3 Bk+1 is transformed to Bk∪O1

定理1設(shè)m 是正整數(shù)，且m≥2，則μ(D(ATm×(2m－2)))=m.

證當(dāng)m=2 時(shí)，μ(D(AT2×2))=μ(D(B2))=2.當(dāng)m ＞2 時(shí)，ATm×(2m－2)可經(jīng)平圖的R-變換變換為Bm，見(jiàn)圖4.由引理1 和4 知，μ(D(ATm×(2m－2)))=μ(D(Bm))=m.

圖4 當(dāng)m ＞2 時(shí)，ATm×(2m－2)經(jīng)平圖的R-變換變換為BmFig.4 ATm×(2m－2)(m ＞2)is transformed to Bm by applying plane graphical Reidemeister moves

對(duì)于交錯(cuò)三角格圖ATm×(2m－2)(m≥2)，記D(ATm×(2m－2))中圍繞ATm×(2m－2)的外部面的6m－8 個(gè)頂點(diǎn)的在ATm×(2m－2)的外部面的6m－8 條短弧邊依次為a1，a2，…，am=b2m－2，…，b2，b1=e1，e2，…，em=d2m－2，…，d2，d1=a1，見(jiàn)圖5(左).

圖5 (左)D(ATm×(2m－2))的6m－8 條短弧邊.(右)D(AT4×6)的分支C1 和C4Fig.5 (left)(6m－8)small segments of arcs of D(ATm×(2m－2));(right)The components C1 and C4 of D(AT4×6)

注意到，4 條短弧邊ai、b2i－2、ei和d2i－2屬于D(ATm×(2m－2))的同一個(gè)分支Ci(2≤i≤m)，其余的短弧屬于D(ATm×(2m－2))的分支C1，且Ci兩兩不同(i=1，2，…，m).而且，ATm×(2m－2)的每條邊被這些Ci的1 條或2 條恰好穿過(guò)2 次.故μ(D(ATm×(2m－2)))=m.

圖5(右)粗線和虛線分別為D(AT4×6)的分支C1和C4.

3 交錯(cuò)三角格圖ATm×n(2≤m≤4)的鏈環(huán)分支數(shù)

本節(jié)研究并證明交錯(cuò)三角格圖ATm×n(2≤m≤4)的鏈環(huán)分支數(shù).

引理5設(shè)m，n 是正整數(shù)，m≥2，n ＞2m－1，則μ(D(ATm×n))=μ(D(ATm×(n－2m+1))).

證因m≥2，n ＞2m－1.將ATm×n分離為ATm×(2m－2)和G12 個(gè)圖.由引理3 和定理1 知，μ(D(ATm×n))=μ(D(G1)).又G1可經(jīng)平圖的R-變換變換為G2，見(jiàn)圖6，由引理1 知μ(D(G1))=μ(D(G2)).因圖G2經(jīng)垂直翻轉(zhuǎn)180°變換為ATm×(n－2m+1)，又平圖的垂直翻轉(zhuǎn)變換不改變其所對(duì)應(yīng)的鏈環(huán)圖，故保持其鏈環(huán)分支數(shù)不變，所以μ(D(G2))=μ(D(ATm×(n－2m+1))).因此μ(D(ATm×n))=μ(D(ATm×(n－2m+1))).

圖6 ATm×n(m≥2，n ＞2m－1)分離為ATm×(2m－2)和G1，G1 變換為G2Fig.6 ATm×n(m≥2，n ＞2m－1)is split to ATm×(2m－2) and G1，G1 is transformed to G2

推論1設(shè)m，n 是正整數(shù)，m≥2.若n=2m－2(mod 2m－1)，則μ(D(ATm×n))=m.

證因m，n 是正整數(shù)，m≥2，n=2m－2(mod 2m－1).設(shè)n=(2m－1)q+(2m－2)，(q 是非負(fù)整數(shù)).由引理5 和定理1 知，μ(D(ATm×n))=μ(D(ATm×((2m－1)q+(2m－2))))=μ(D(ATm×(2m－2)))=m.

引理6設(shè)m，n 是正整數(shù)，m≥2.若n=0(mod 2m－1)，則μ(D(ATm×n))=1.

證因m，n 是正整數(shù)，m≥2，n=0(mod 2m－1).則n－1=2m－2(mod 2m－1).將ATm×n分離為ATm×(n－1)和G12 個(gè)圖.由推論1 知μ(D(ATm×(n－1)))=m.由引理3 知μ(D(ATm×n))=μ(D(G1)).易知μ(D(G1))=μ(D(O1))=1.故μ(D(ATm×n))=1，(m≥2，n=0(mod 2m－1)).

定理2設(shè)n 是正整數(shù).則

證對(duì)正整數(shù)n 用歸納法證明.當(dāng)n=1 時(shí)，1=1(mod 3)，μ(D(AT2×1))=μ(D(P2))=1.當(dāng)n=2 時(shí)，2=2(mod 3)，由定理1 知μ(D(AT2×2))=2.當(dāng)n=3 時(shí)，3=0(mod 3)，由引理6 知μ(D(AT2×3))=1.故當(dāng)n=1，2，3 時(shí)，結(jié)論成立.假設(shè)對(duì)于所有的n≤k(k≥3，k 為正整數(shù))，結(jié)論成立.則當(dāng)n=k+1 時(shí)，由引理5，知μ(D(AT2×(k+1)))=μ(D(AT2×(k－2))).由歸納假設(shè)知又k+1=(k－2)(mod 3)，故根據(jù)歸納法原理，定理2成立.

顯然有，

(1)AT3×i(i=1，2，3)都可經(jīng)平圖的R-變換變換為O1，由引理1 和2 知μ(D(AT3×i))=1(i=1，2，3).由定理1 知μ(D(AT3×4))=3.由引理6 知μ(D(AT3×5))=1.

(2)AT4×i(i=1，2，3，4，5)可經(jīng)平圖的R-變換變換為O1，由引理1 和2 知μ(D(AT4×i))=1(i=1，2，3，4，5).由定理1 知μ(D(AT4×6))=4.由引理6 知μ(D(AT4×7))=1.

由上述(1)和(2)，并根據(jù)歸納法原理和引理5，仿定理2 的證明，可證明下面的定理3 和定理4 成立.

定理3設(shè)n 是正整數(shù).則

定理4設(shè)n 是正整數(shù).則

4 交錯(cuò)三角格圖ATm×n(m≥2)的鏈環(huán)分支數(shù)的一個(gè)假命題

基于定理2～4，猜想交錯(cuò)三角格圖ATm×n(m≥2)的鏈環(huán)分支數(shù)如下.

命題1設(shè)m，n 是正整數(shù).若m≥2，則

我們將構(gòu)造反例證明命題1 不真.

引理7［7］設(shè)m 是正整數(shù)，則μ(D(Lm×m))=m.

命題1不真的證明 由引理5、推論1 和引理6 知，命題1 與“命題※:設(shè)m，n 是正整數(shù).若m≥2 且n≤2m－3，則μ(D(ATm×n))=1”同真假.由定理2 知μ(D(AT2×5))=2.又AT2×5可經(jīng)平圖的R-變換分別變換為圖F1，見(jiàn)圖7.將圖F1與圖L3×3之間按圖7所示連以3 條邊，得圖F2.又F2可經(jīng)平圖的R-變換變換為圖AT5×5，見(jiàn)圖7.由引理1、3 和7，知μ(D(AT5×5))=μ(D(F2))=μ(D(F1))=μ(D(AT2×5))=2.但5 ＜2×5－3.故AT5×5是命題※的反例.故命題1 不真.

圖7 AT2×5變換F1，F(xiàn)1 與L3×3之間連以3 條邊得F2，F(xiàn)2 變換AT5×5Fig.7 AT2×5 is transformed to F1，F(xiàn)1 and L3×3 are connected to three sides to obtain F2，F(xiàn)2 is transformed to AT5×5

不難證明，AT(2+3t)×5(t 是正整數(shù))是命題1 的一簇反例.

致謝:作者的導(dǎo)師金賢安老師提出了格圖的鏈環(huán)分支數(shù)問(wèn)題，并對(duì)本文的研究提出了許多寶貴建議.作者在此表示感謝!

［1］MURASUGI K.Knot theory and its applications［M］.Boston:Birkhauser，1996:34-39.

［2］SHANK H.The theory of left-right paths［J］.Combinatorial Math.Ⅲ，Lecture Notes in Mathematics，1975，452:42-54.

［3］PISANSKI T，TUCKER T W，ZITNIK A.Straight-ahead walks in Eulerian graphs［J］.Discrete Math，2004，281(1-3):237-246.

［4］JIN X A，DONG F M，TAY E G.On graphs determining links with maximal number of components via medial construction［J］.Discrete Appl Math，2009，157(14):3099-3110.

［5］ENDO T.The link component number of suspended trees［J］.Graph Combinator，2010，26(4):483-490.

［6］LIN Y F，NOBLE S D，JIN X A，et al.On plane graphs with link component number equal to the nullity［J］.Discrete Appl Math，2012，160(9):1369-1375.

［7］JIN X A，DONG F M，TAY E G.Determining the component number of links corresponding to lattices［J］.J Knot Theor Ramif，2009，18(12):1711-1726.

［8］JIANG L P，JIN X A，DENG K C.Determining the component number of links corresponding to triangular and honeycomb lattices［J］.J Knot Theor Ramif，2012，21(2)，1250018-1250031.

［9］MPHAKO E G.The component number of links from graphs［J］.Proc Edinb Math Soc，2002，45(3):723-730.

［10］湯自凱，侯耀平.恰有兩個(gè)主特征值的三圈圖［J］.湖南師范大學(xué)學(xué)報(bào)自然科學(xué)版，2011，34(4):7-12.

［11］袁名焱，羅秋紅，湯自凱.由星補(bǔ)刻畫的一類廣義線圖［J］.湖南師范大學(xué)學(xué)報(bào)自然科學(xué)版，2012，35(1):13-20.

［12］JIANG L P，JIN X A.Enumeration of left-right paths of square and triangular lattices on some surfaces［J］.數(shù)學(xué)研究，2011，44(3):257-269.

［13］陳 紅，梁文忠，許成章，等.刻畫NP－C 問(wèn)題復(fù)雜程度的一個(gè)模型——對(duì)計(jì)算Paley 圖團(tuán)數(shù)的實(shí)踐做出預(yù)測(cè)［J］.湘潭大學(xué)學(xué)報(bào)自然科學(xué)版，2011，33(4):7-11.

［14］NOBLE S D，WELSH D J A.Knot graphs［J］.J Graph Theory，2000，34(1):100-111.