交錯三角格的鏈環(huán)分支數(shù)的幾個結(jié)論

林躍峰

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

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

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

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

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

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

1 幾個已知的引理

下面是關(guān)于無符號平圖的3 類Reidemeister 變換(以下簡記為R-變換).無符號平圖的R-變換對應于紐結(jié)理論中的鏈環(huán)投影圖的3 類Reidemeister 變換.

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

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

Ⅲ變換:YΔ-變換或ΔY-變換.見圖2 的Ⅲ.

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

令G1∪G2表示2 個圖G1和G2的不交并.

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

引理2［7］設(shè)G 是平圖，則μ(D(G))=k 當且僅當G 能通過有限次無符號平圖的R-變換變換為空圖Ok.

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

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

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

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

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

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

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

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

對于交錯三角格圖ATm×(2m－2)(m≥2)，記D(ATm×(2m－2))中圍繞ATm×(2m－2)的外部面的6m－8 個頂點的在ATm×(2m－2)的外部面的6m－8 條短弧邊依次為a1，a2，…，am=b2m－2，…，b2，b1=e1，e2，…，em=d2m－2，…，d2，d1=a1，見圖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))的同一個分支Ci(2≤i≤m)，其余的短弧屬于D(ATm×(2m－2))的分支C1，且Ci兩兩不同(i=1，2，…，m).而且，ATm×(2m－2)的每條邊被這些Ci的1 條或2 條恰好穿過2 次.故μ(D(ATm×(2m－2)))=m.

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

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

本節(jié)研究并證明交錯三角格圖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 個圖.由引理3 和定理1 知，μ(D(ATm×n))=μ(D(G1)).又G1可經(jīng)平圖的R-變換變換為G2，見圖6，由引理1 知μ(D(G1))=μ(D(G2)).因圖G2經(jīng)垂直翻轉(zhuǎn)180°變換為ATm×(n－2m+1)，又平圖的垂直翻轉(zhuǎn)變換不改變其所對應的鏈環(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 是非負整數(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 個圖.由推論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ù).則

證對正整數(shù)n 用歸納法證明.當n=1 時，1=1(mod 3)，μ(D(AT2×1))=μ(D(P2))=1.當n=2 時，2=2(mod 3)，由定理1 知μ(D(AT2×2))=2.當n=3 時，3=0(mod 3)，由引理6 知μ(D(AT2×3))=1.故當n=1，2，3 時，結(jié)論成立.假設(shè)對于所有的n≤k(k≥3，k 為正整數(shù))，結(jié)論成立.則當n=k+1 時，由引理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 交錯三角格圖ATm×n(m≥2)的鏈環(huán)分支數(shù)的一個假命題

基于定理2～4，猜想交錯三角格圖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，見圖7.將圖F1與圖L3×3之間按圖7所示連以3 條邊，得圖F2.又F2可經(jīng)平圖的R-變換變換為圖AT5×5，見圖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 的一簇反例.

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

［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］湯自凱，侯耀平.恰有兩個主特征值的三圈圖［J］.湖南師范大學學報自然科學版，2011，34(4):7-12.

［11］袁名焱，羅秋紅，湯自凱.由星補刻畫的一類廣義線圖［J］.湖南師范大學學報自然科學版，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ù)學研究，2011，44(3):257-269.

［13］陳 紅，梁文忠，許成章，等.刻畫NP－C 問題復雜程度的一個模型——對計算Paley 圖團數(shù)的實踐做出預測［J］.湘潭大學學報自然科學版，2011，33(4):7-11.

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