韓友發(fā),張雪嬌,馬野萍,單亞男
(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院,遼寧 大連 116029)
紐結(jié)多項式是紐結(jié)的重要不變量,在紐結(jié)的分類中扮演了重要角色.1928年,美國數(shù)學(xué)家Alexander[1]給出了紐結(jié)的一個多項式不變量.1969年,英國數(shù)學(xué)家Conway在研究Alexander多項式時,對其計算方法稍作改進,形成Conway[2]多項式.1984年,新西蘭數(shù)學(xué)家Jones[3]從關(guān)于算子代數(shù)的定理中引申出紐結(jié)與鏈環(huán)的一個多項式不變量.然而Jones是一位泛函分析學(xué)家,他卻在紐結(jié)理論中取得了重大突破,說明了表面上不同的數(shù)學(xué)分支之間有著深刻的聯(lián)系和內(nèi)在統(tǒng)一性.Kauffman在研究交錯紐結(jié)的方括號多項式時,發(fā)現(xiàn)了方括號多項式與雙色多項式之間存在著某種聯(lián)系,這推動了紐結(jié)理論與圖論之間的探索之路[4-5].
本文共分為三部分,第一部分簡單介紹了紐結(jié)多項式;第二部分簡單介紹本文所需的預(yù)備知識,包括紐結(jié)投影圖的方括號多項式[K(G)]、平面圖的雙色多項式ZG(q,v)的定義,在交錯紐結(jié)投影圖與平面圖之間建立一種聯(lián)系,以及圖論中的相關(guān)定義和性質(zhì);第三部分具體討論ZG(q,v)與[K(G)]的性質(zhì)以及它們之間的關(guān)系,同時研究了平面圖的某些性質(zhì).
紐結(jié)投影圖的方括號多項式[K]是在不定向紐結(jié)上K定義的一個三元多項式,[K]∈Z[A,B,d],滿足以下四個等式:
由上述公理,我們注意到方括號多項式[K]的計算是一種循環(huán)運算,因此我們給出[K]的另一種運算模式[6-8].
定義1.1當(dāng)我們不考慮紐結(jié)投影圖中上、下穿線時,將紐結(jié)投影圖中每個交叉點變成相交點,得到的平面圖形叫做四岔地圖.如圖1.1.
圖1.1
因此,紐結(jié)投影圖的方括號多項式的一般形式為[4]:
[K]=∑SAik(s)Bjk(s)d|s|
其中ik(s)+jk(s)=n為紐結(jié)圖中交叉點的個數(shù),S表示紐結(jié)投影圖K的交叉點按照不同方式打開的所有狀態(tài),共有2n種打開方式.
定義1.2兩個投影圖稱為等價的,或稱為同痕的,如果從一個投影圖出發(fā),經(jīng)過一連串的R1,R2,R3初等變換以及平面變形,可以得到另一個投影圖.
定義1.3在紐結(jié)投影圖中,如果沿著該圖中的每條線,交叉點都是一上一下一上一下地相互交錯出現(xiàn)的,則稱該紐結(jié)為交錯紐結(jié).
定義1.4將交錯紐結(jié)投影圖K轉(zhuǎn)化為四岔地圖,四岔地圖的各個區(qū)域標(biāo)記為陰影部分或非陰影部分,滿足以下兩點:
(1)無邊區(qū)域標(biāo)記為非陰影部分;
(2)擁有一條公共邊的相臨兩區(qū)域的顏色不同;
平面圖Γ(Κ)中的頂點對應(yīng)四岔地圖中陰影部分,Γ(K)中的邊對應(yīng)四岔地圖中的公共交叉點.
因此每個交錯紐結(jié)投影圖都對應(yīng)一個平面圖,若給出平面圖G,滿足定義1.1中的要求,可畫出與其對偶的四岔地圖,所以平面圖與四岔地圖是一一對應(yīng)的關(guān)系.但是若給出一個四岔地圖,我們無法唯一確定其對偶交錯紐結(jié)投影圖.因為每個四岔地圖都對應(yīng)兩個交錯紐結(jié)投影圖,彼此互為鏡面像.
引理1.1[6]互為鏡面像的兩個交錯紐結(jié)投影圖K與K′的方括號多項式[K]和[K′]滿足下面等式:
[K](A,B)=[K′](B,A)
即將[K]中的變量A與B改為B與A,即可得到[K′].
對于平面圖G,我們定義一個二元雙色多項式ZG(q,v)∈Z[q,v],滿足下面三個公理:
(2)Z·G=qZG
(3)Z·=q
當(dāng)v=-1時,雙色多項式特殊化為色多項式KG(q),既ZG(q,-1)=KG(q).由(3)可知,若平面圖含有n個頂點,則色多項式KG(q)為關(guān)于q的一元n次多項式.KG(q)表示用q(≥2)種顏色對平面圖G的頂點進行著色,使擁有公共邊的相鄰兩頂點顏色不同,共有KG(q)種著色方法[9-10].
定義1.6一個平面G圖定義為一個偶對(V,E),記作G=(V,E),其中
(1)V是一個集合,其中的元素稱為頂點;
(2)E是無序積V×V中的一個子集合,其元素稱為邊;
集合V×V中的元素可在E中出現(xiàn)不止一次.在圖論中,若連接同一對頂點的邊數(shù)大于1,則稱這樣的邊為多重邊,其邊數(shù)稱為重數(shù).
引理1.2平面圖G含有多重邊,平面圖G′是將G中的多重邊去掉,則兩個平面圖的色多項式均為KG(q).即多重邊不影響平面圖的頂點著色數(shù)目.
定義1.7平面圖中不含圈的連通圖稱為樹.
定義1.8如果在圖G中刪去一條邊后,圖G的分支數(shù)增加,則稱此邊為G的割邊.
引理2.1[4]令K(G)是與平面圖G對偶的交錯紐結(jié)投影圖G,滿足平面圖的頂點對應(yīng)K(G)的陰影部分(上穿線逆時針旋轉(zhuǎn)掃過的區(qū)域),則由K(G)的方括號多項式可導(dǎo)出G的雙色多項式:
上述引理僅限于部分交錯紐結(jié),具有一定的局限性.但我們知道另外一部分交錯紐結(jié)與此部分交錯紐結(jié)互為鏡面像.由引理2.1可知兩者的方括號多項式之間存在著必然的轉(zhuǎn)換關(guān)系.因此本文涉及到的交錯紐結(jié)均可以與平面圖建立一一對應(yīng)關(guān)系.
q=d2
與方括號多項式[K(G)]比較,每一單項式中缺少變量B.由方括號多項式的計算公理可知,[K]的一般形式為:
[K]=∑SAik(s)Bjk(s)d|s|
其中ik(s)+jk(s)=n為紐結(jié)投影圖中交叉點的個數(shù).如果知道每一單項式中變量A或B的指數(shù),即可求出另一變量的指數(shù).
因此,在多項式f(A,d)中,每一項添加變量B,使得A、B的指數(shù)和為紐結(jié)投影圖中交點總數(shù).
這樣,我們由G的雙色多項式ZG(q,v)導(dǎo)出了K(G)的方括號多項式[K(G)].證畢.
引理2.2[10]如果圖G是子圖H和K的并,且H∩K當(dāng)且僅當(dāng)是一個頂點,那么
通過方括號多項式的計算公理仍能得到上述結(jié)果,但是計算相對繁瑣些.我們注意到,利用平面圖的雙色多項式計算其對偶交錯紐結(jié)投影圖的方括號多項式更便捷一些,這也是研究兩者關(guān)系的重要意義之一.為此我們有必要詳細研究一下有關(guān)平面圖的雙色多項式計算的相關(guān)性質(zhì).
引理2.3[11]樹的雙色多項式的一般形式為:
ZG(q,v)=q(a+v)n
其中n表示樹的樹枝數(shù),與樹枝的排列方式無關(guān).
定理2.2(1)簡單n邊形的雙色多項式的一般形式為:
(2)平面圖G是在簡單n邊形的基礎(chǔ)上,僅多添加一條重邊,則其雙色多項式的計算滿足如下關(guān)系:
ZG(q,v)=ZG′(q,v)+v(v+1)ZG″(q,v)
其中G′表示G去掉重邊后的n邊形,G″表示比G′少一條邊的n-1邊形,當(dāng)n=1時,G″表示一個點.
該定理利用歸納法以及引理2.2、引理2.3可以證明.同時該結(jié)果說明了重邊對于平面圖的頂點著色問題無實質(zhì)影響.
推論2.1平面圖G是在簡單n邊形的基礎(chǔ)上含有一條重邊,則其雙色多項式的一般形式為:
ZG(q,v)=(v+2)
推論2.2平面圖G是在簡單n邊形的基礎(chǔ)上,在其一邊上具有m重邊,則其雙色多項式的計算公式滿足:
其中G′表示G去掉m重邊后的n邊形,G″表示比G′少一條邊的n-1邊形.
定理2.3如果平面圖G是子圖H和K的并,
且H∩K只是一條邊,那么
其中G-1表示平面圖G去掉公共邊后的圖形,H-1表示H收縮公共邊后的圖形,K-1表示K收縮該公共邊后的圖形.
因此,
引理2.4[11]如果圖G是子圖H和K的不交并,那么
ZG(q,v)=ZH(q,v)ZK(q,v).
根據(jù)本引理以及雙色多項式的性質(zhì)可以證明下面的結(jié)果.
定理2.5如果平面圖G是子圖H和K當(dāng)且僅當(dāng)通過一條邊連接,該邊為圖G的割邊,那么
以上是有關(guān)平面圖雙色多項式的計算的相關(guān)性質(zhì),利用這些性質(zhì)可以給出雙色多項式的簡化計算,進而簡化對偶交錯紐結(jié)投影圖的方括號多項式的計算過程.從而可以研究與平面圖著色的相關(guān)問題[12].
[1]J.W.Alexander.Topological invariants of knots and links[J].Trans.Amer.Math.Soc.,1923,30:275~306.
[2]J.H.Conway.An enumeration of knots and links and some of their algebraic properties[J].Computational Problems in Abstract Algebra,Pergamon Press,New York,1970,329~358.
[3]V.F.R.Jones.A new knot polynomial and von Neumann Algebras[J].Notices of AMS,1985.
[4]L.H.Kauffman.New Invariants in the Theory of Knots[J].The American Mathematical Monthly,1988,95(3):195~242.
[5]Xian’an Jin,Fuji Zhang.The Homfly and dichromatic polynomials[J].Proc.Amer.Math.Soc..2012,140(4):1459~1472.
[6]Rolfsen.Dale.Knots and links[M].Publish or Perish,1976.
[7]Han,Youfa;Li,Yang.The bracket polynomial of links[J].Liaoning Norm.Univ.Nat.Sci..2000,23(1)
[8]Itik Mehmet,Banks Stephen P.On the calculation of the Kauffman bracket polynomial[J].Applied Mathematics and Computation,2010,216(2):655~661.
[10]W.T.Tutte.Graph Theory[M].Addison-Wesley,Reading,MA,1969.
[11]B.Bolloba.Modern Graph theory[M].Springer,Berlin,1998.
[12]Han,Youfa;Zhang Da-wei,SUN Sheng.Jones Polynomial of Knots and Laurent Polynomial[J].Jilin Norm.Univ Nat.Sei,2012,33(4):19~31.