最小圈基的圖運算結構

徐 梅

(淮陰師范學院數(shù)學科學學院,江蘇淮安 223300)

最小圈基的圖運算結構

徐 梅

(淮陰師范學院數(shù)學科學學院,江蘇淮安 223300)

通過兩個2-平面圖的運算結構討論了其最小圈基,得到結果為構成新圖的最小圈基與兩圖相交的節(jié)點有關.

平面圖;圈長;最小圈基

0 引言

本文中的圖均指有限、無向、簡單的2-連通圖.有關圖的拓撲術語可分別參考文獻[1,2].如果一個圖G的子圖H,它的每個頂點的度都是偶數(shù),則稱H是圖G的E-子圖.同時,稱G的每一個E-子圖為一個向量.設X、Y都是圖的邊的集合,在E-子圖上定義如下運算:

則在G F(2)上構成線性向量空間ε,稱為G的圈空間.亦即一個簡單圖G的圈空間是指由G的圈在二元域{0,1}下生成,其加法運算是邊集的對稱差.

我們知道 ,一個圖G的圈空間的維數(shù)β(G)=ε(G)-υ(G)+1,稱為G的Betti數(shù).其中ε(G)和υ(G)分別指G的邊數(shù)和節(jié)點數(shù).更進一步,任意β(G)個線性無關的E-子圖是G的一個圈基.一個圈的長度是指該圈中所含邊的個數(shù).圈基中所有的圈的長度總和稱為該圈基的長度.G的所有圈基中長度最小的稱為G的最小圈基,記為:MCB(minimal cycle base).

圖的圈空間理論最早源于Kirchhoff關于電路理論的研究[3].從理論上看,擬陣理論是其動力之一[4-7].后經(jīng)眾多學者工作,其在結構分析[8],以及生命科學等領域[9]均有應用.對最小圈基的研究也引起研究者的極大興趣,文獻[4]給出了其簡短綜述.尤其是在生命科學領域,隨著交叉學科的發(fā)展的深入,圈基理論得到了越來越廣泛的應用.短圈是區(qū)分不同的分子圖的一個很重要的特征,尤其是在有機化學和結構生物學上.雖然最小圈基往往不是唯一的,但是最小圈基的結構卻引起了生物學家的廣泛關注.有機碳水化合物通常表現(xiàn)為多輪的結構(即大多數(shù)由一些短圈構成),高分子聚合物,例如:DNA、RNA和蛋白質也形成一種我們所熟知的三維結構 ,這種三維結構對它們的生物特性來說是至關重要的.最小圈基的理論將整個圈空間壓縮成一種簡潔的形式,這樣給我們的計算帶來了極大的方便,因而尤其具有實用價值.文獻[10]在更多的一般圖中擴展了前人在計算最小圈基方面的工作.

1 主要結果及其證明

定義1 若2-連通平面圖的所有頂點都位于兩個面圈上,則稱圖G為2-平面圖.

定義2 圖的對稱差運算 G1⊕ G2是指 G1和 G2的并中去掉 G1和 G2的交所得到的圖 ,即

定義3 用“‖"表示長度符號,如:|C|表示 C的長度.

引理1 任意一個2-邊連通平面圖G的最小圈基是由線性無關的圈組成的.

證明 設B＊是圖 G的一個最小圈基,w是B＊中的一個 E-子圖,若w不是圈,它將包含一個作為子跡的圈 C,且圈C不能被B＊中的其它元素線性表示 ,則B=B＊-w+C也是G的一個圈基,且|B|<|B＊|,這與B＊的最小性矛盾.引理得證.

引理2 設 G是2-連通平面圖,則G的面圈數(shù)φ=ε(G)-υ(G)+1(=β(G)),且任意少于φ個面圈在圈空間中是線性無關的.

證明 倘若 G有φ-1個面圈是線性相關的 ,不妨記這些面圈為?f1,?f2,…,?fφ-1.則存在不全為零的一組數(shù) a1,a2,… ,aφ-1,使得

不妨設 a1≠0,則與?f1相鄰的所有面圈前面的系數(shù)都不為零 ,否則,若存在一個面圈?fi,?fi與?f1相鄰 ,但ai=0,則?f1中與?fi相鄰的邊在對稱差運算后將會保留下來,這樣,(＊)式右邊不會等于零.因這 φ-1個面圈依次相鄰接 ,從而推知a1,a2,…,aφ-1都不為零.這樣:

其中?fφ是剩下的那個面圈.這與(＊)式矛盾.所以,G中任意φ-1個面圈是線性無關的.引理得證.

引理3 2-連通平面圖G的φ-1個面圈構成一組基.

證明 由引理2知:任意少于φ個面圈在圈空間中是線性無關的,故G的φ-1個面圈線性無關的 ,再由引理1知 :引理3得證.

定理1 設 G1和 G2為2-連通的平面圖,若G1∩G2= φ,則G=G1∪G2的最小圈基為 :G1的最小圈基并上 G2的最小圈基.

證明 任取圈 C1∈G,不妨設C1∈G1(C1∈G2同理可證),因G1∩G2= φ,故C1只能由 G1圈基中的面圈(該面圈長度小于|C1|)生成,與G2中面圈無關.且設G1和 G2的面圈數(shù)分別為 φ1和 φ2,則由引理2和引理3可知 :G1和 G2的圈基維數(shù)分別為 φ1-1和 φ2-1.從而G1∪G2的面圈數(shù)為 φ= (φ1-1)+ (φ2-1)+1,其圈基維數(shù)為 φ -1= φ1+ φ2-2= (φ1-1)+ (φ2-1).得證.

定理2 設 G1和 G2為2-連通的平面圖,若G1∩G2={a},則G=G1∪G2的最小圈基為 :G1的最小圈基并上 G2的最小圈基.

證明 類似定理1可證.

定理3 設 G1和 G2為2-連通的平面圖,若G1∩G2={a,b},則G=G1∪G2的最小圈基為 :G1的最小圈基并上 G2的最小圈基并上 a,b所構成的最短圈Cab.

證明 設 G1和 G2為2-連通的平面圖,G1∩G2={a,b},G1和 G2的面圈數(shù)分別為 φ1和 φ2,

G1和 G2的圈基維數(shù)分別為 φ1-1和 φ2-1,則G1∪G2的面圈數(shù)為 φ =(φ1-1)+(φ2-1)+2= φ1+ φ2,其圈基維數(shù)為 φ -1= φ1+ φ2-1= (φ1-1)+ (φ2-1)+1,該處 1 即為 Cab產(chǎn)生.

任取 C ∈G,則:1)若C ∈G1,或C ∈G2類似定理1可證 ;2)若C=Cab,則C就由Cab生成;3)若 C∩G1≠φ,C∩G2≠φ,且C≠Cab,則C=C1⊕ C2⊕ Cab,其中C1可由 G1圈基中面圈生成 ,C2可由 G2圈基中面圈生成.且對G=G1∪G2的圈基中任意的α∈Int(C),均有|α|≤|C|.綜上有G=G1∪G2的最小圈基為 G1的最小圈基并上 G2的最小圈基并上 a,b所構成的最短圈Cab.

[1] Bondy J,Murty U.Graph Theory with Applications[M].Macmilan Press Ltd,1976.

[2] Mohar B,Thomassen C.Graphson Surfaces[M].John HopkinsUniversity Press,2001.

[3] Leydlod J,Stadler P F.Minimal cycle basesof outerplanar graphs[J].Electronic J combin,1998,5(16):14-18.

[4] Cummins R L.Hamilton circuits in tree graphs[J].IEEE Transactions,Circuit Theory,1966,13:82-96.

[5] Downs GD,Gillet V J,Holliday JD,etal.Review of ring perception algorithms for chemical graphs[J].Chem Inf Comput Sci,1989,29:172-187.

[6] Glover F,Klingman D.Findingminimum spanning treewith a fixed number of links at a node[J].Combinatorial Programming:Methods and Applications,1975,12,191-201.

[7] Holzman CA,Harary F.On the tree graph of amatroid[J].SIAM JAppl Math,1972,22:187-193.

[8] Phillip H.On representativesof subsets[J].London Math Soc,1935,10:26-30.

[9] Liu G Z.On the connectivitiesof tree graphs[J].J of Graph Theory,1988,12:453-454.

[10] Gleiss PM,Stadler P F.Relevant Cycles in Biopolymers and Random Graphs[J].Fourth Slovene International Conference in Graph Theory Bled,1999,28:8-22.

Abstract:In this paper,two 2-plane to discuss the computing structureof the smallest circleof its base,obtained the following results:constitute a new map of the smallest circle intersecting the base and the two nodesof the diagram.

Key words:planar graph;cycle length;minimum cycle bases

[責任編輯:李春紅]

Figure Computing Structure of M inimum Cycle Bases

XU Mei

(School of Mathematical Science,Huaiyin Normal University,Huaian Jiangsu 223300,China)

O157.5

A

1671-6876(2010)06-0478-03

2010-08-18

徐梅(1972-),女,江蘇連云港人,講師,碩士,主要從事圖論與組合的研究.