魏白

摘要利用嵌入聯(lián)樹模型和組合計數(shù)的相關(guān)方法，獲得了由鵝卵石路圖添加一條邊所得到的一類圖Gn在球面及射影平面上的嵌入個數(shù)，它們分別為2n-1（n≥2）和（3n-3）2n-1（n≥2）.

關(guān)鍵詞曲面；虧格；嵌入；聯(lián)樹

中圖分類號O1575 文獻標識碼A 文章編號10002537（2012）05002406

研究圖在不同虧格曲面上不等價的嵌入個數(shù)，可以歸結(jié)為圖的虧格分布和圖的完全虧格分布.自從Gross和Furst［1］引入相關(guān)概念以來，相關(guān)學者得到了某些圖類的虧格分布［213］.由于圖的虧格分布的研究是一個NP難問題，因此目前有關(guān)虧格分布及完全虧格分布的結(jié)果較少.對于大部分圖類，我們尚不能確定其虧格分布，尤其是完全虧格分布.然而圖在不同虧格曲面上的嵌入通常是有相關(guān)關(guān)系的，所以研究圖在球面，環(huán)面，射影平面，Klein瓶等小虧格曲面上的嵌入結(jié)構(gòu)以及不等價的嵌入個數(shù)是一項有意義的工作.

本文中曲面均為無邊緣的緊閉二維流形，并且分為可定向曲面和不可定向曲面.在球面上增加p個“手柄”得到虧格為p的可定向曲面Op；在球面上增加q個“交叉帽”得到虧格為q的不可定向曲面Nq.其中，安“手柄”運算是指由球面分別挖去兩個不相交的圓盤，其邊界分別記為C1和C2，然后用一根圓柱筒的兩端分別與C1和C2黏合而成；安“交叉帽”運算是指在球面上挖去一個圓盤，其邊界記為C，然后用一條mbius帶的邊界與C黏合而成.圖G在曲面S上的一個嵌入是指一個1-1連續(xù)映射h：G→S，若S-h（G）的每一個連通分支都同胚于一個開圓盤，則稱之為一個2胞腔嵌入.本文中的嵌入均為2胞腔嵌入.圖G在曲面S上的2個嵌入h：G→S和g：G→S稱為等價的，是指存在一個保定向的同胚映射f：S→S，使得fh=g.

直觀上，任何一個曲面S都可以由一個正2n邊形黏合而成.把正2n邊形的邊分成n組，每組2條邊，其中同一組的2條邊用同一字母表示（如aa），然后分別給每條邊規(guī)定一個方向，并用上標“+”（通常省略）和“-”區(qū)分（如aa或aa-）.按某一方向（順時針或逆時針）依次記錄正多邊形的邊，得到帶上標的字母的循環(huán)序，這稱為曲面的多邊形表示.同一組中的2條邊按相同方向黏合，即可得到曲面S.平面，環(huán)面，射影平面和Klein瓶可分別表示為O0=aa-，O1=aba-b-，N1=aa，N2=aabb.一般地，分別用Op=∏pi=1aibia-ib-i，Nq=∏qi=1aiai.表示虧格為p和q的可定向和不可定向曲面，其中p≥1，q≥1，并稱之為曲面的標準型代數(shù)表示.如果用字母a表示的一組邊的方向相反（即aa-或a-a），則按上述規(guī)則經(jīng)過黏合后得到的邊a稱為非扭邊.如果用a表示的一組邊的方向相同（即aa或a-a-），則按上述規(guī)則經(jīng)過黏合后得到的邊a稱為扭邊.

以下3種運算不改變曲面的類型：運算1.Aaa-A；運算2.AabBabAcBc；運算3.AB（Aa）（a-B）.在這3種運算中，括號表示循環(huán)序，A，B均為字母的線性序.除運算2中的A和B允許為空集外，其余均為非空集合.事實上，以上運算確定了一類拓撲等價，記為“～”.由此可以導出下面3種拓撲等價關(guān)系： 劉彥佩教授創(chuàng)建的嵌入聯(lián)樹模型［10］，對研究圖的虧格分布和完全虧格分布在方法上有著全新的突破：給定圖G=（V，E）的一棵生成樹T，然后將每條余樹邊賦予一個字母，并將每余樹邊（不妨設(shè)為ei）從中間切斷，得到2條用同一字母表示的半邊，這2條半邊分別用ei，ei或ei，e-i表示，此時所得到的圖形叫做G的聯(lián)樹.設(shè)余樹邊的數(shù)目為β，從任一節(jié)點出發(fā)沿樹T和旋系走遍聯(lián)樹的所有邊，依次記錄余樹邊的字母（生成樹T的邊不用記錄），得到一個有2β個帶上標的字母的循環(huán)序，這個循環(huán)序所對應的曲面即為圖G的關(guān)聯(lián)曲面.由于圖的關(guān)聯(lián)曲面和圖的嵌入之間存在一一對應，因此我們可以用圖的關(guān)聯(lián)曲面的結(jié)構(gòu)來分析圖在曲面上的嵌入.近年來，相繼有學者得到一些圖類的射影平面等小虧格曲面上的嵌入個數(shù)［1113］，本文亦在聯(lián)樹模型的基礎(chǔ)上得到了一類圖在球面和射影平面上的嵌入個數(shù)及結(jié)構(gòu)特征.

1引理和定義

引理1［10］設(shè)曲面S1是可定向曲面且虧格為p，曲面S2是不可定向曲面且虧格為q.

證由關(guān)系1，S=AxByCx-Dy-～ADCBExyx-y-.不妨設(shè)S1=ADCBE，這里E是空集.則S～S1xyx-y-.由于S為不可定向曲面，則S1為不可定向曲面，且其虧格至少為1.由引理1知，S的虧格至少為3.

引理3設(shè)S為不可定向曲面，若S=AxByCyDx或S=AxByCxDy-，則S的虧格至少為2.

證若S=AxByCyDx，由關(guān)系2，S=AxByCyDx～AxBC-Dxyy～AD-CB-yyxx，由引理1知，S的虧格至少為2；若S=AxByCxDy-，由關(guān)系2，S=AxByCxDy-～AC-y-B-Dy-xx～AC-D-Bxxy-y-，由引理1知，S的虧格至少為2.

定義1若曲面S=AxByCx（x）Dy（y），則稱邊x和y在曲面S中交錯；若曲面S=AxBx（x）CyDy（y），則稱x和y在曲面S中平行，其中（x）和（y）分別表示邊x和邊y的上標（即“+”或“-”）.

引理4設(shè)S是射影平面，則其多邊形表示中的任意2條邊，若都是扭邊，則必定交錯，否則必定平行.

證由引理2和引理3易得.

定義2設(shè)A是一個字母循環(huán)序，則由A中的某些字母按原來的相對順序組成的字母的循環(huán)序，稱為A的子列.

引理5在曲面S的多邊形表示中，若其子列也是某個曲面S1的多邊形表示，則S1的虧格必定不大于S的虧格.

證由引理1易得.

引理6若A是a1，a2，…，an的帶上標的線性序，則曲面S=a1a2…anA為球面當且僅當A=a-n…a-2a-1.

證必要性：由于曲面S為球面，是可定向曲面，因此A必為a-1，a-2，…，a-n的線性序.若存在1≤i＜j≤n，使得A=…a-i…a-j…，則ai與aj必交錯.由引理1知，曲面S的虧格必定大于或等于1，這與S是球面矛盾.因此A=a-n…a-2a-1….充分性顯然.

2主要結(jié)論

如果n個頂點的路的每條邊都是雙重邊，并且兩端點都各自有一個環(huán)，那么這樣的圖稱之為鵝卵石路圖（cobblestonepath），長度為n，記為Jn。文獻［6］已經(jīng)得到了鵝卵石路圖Jn的完全虧分布.分別用兩頂點（不妨設(shè)為u，v），剖分Jn兩端的環(huán)，并且用一條邊a連接u和v，得到的圖記為Gn+2（見圖1）.

21Gn在球面S上的嵌入

首先在Gn中選定一棵生成樹（如圖1中粗邊所示），設(shè)其n個點分別為u1，u2，…，un，且ei=uiui+1（1≤i≤n-1），a=u1un.將每條余樹邊從中間切斷，即可得到Gn的一棵聯(lián)樹（如圖2）.

由Gn是在球面S上的嵌入，可得到下列3個斷言：

斷言1所有的余樹邊均為非扭邊.

證由引理6易得.

斷言2余樹邊中，任意一條非扭邊的2條半邊必須在生成樹的同側(cè).

證余樹邊中，若存在非扭邊ei，它的2條半邊ei，e-i在生成樹的異側(cè)，由于a也為非扭邊，則非扭邊ei與a交錯.由引理5知，Gn嵌入曲面S的虧格必定大于或等于1，這與S是球面矛盾.

斷言3任意2條余樹邊，若均為非扭邊，則必定平行.

證余樹邊中，若存在非扭邊ei與ej交錯，則由引理5知，Gn嵌入曲面S的虧格必定大于或等于1，這與S是球面矛盾.

定理1Gn在球面S上的嵌入個數(shù)為2n-1（n≥2）.

證由斷言1～3知，對于任意的余樹邊ei（1≤i≤n-1），它的2條半邊ei，e-i都有擺放在生成樹的上側(cè)及下側(cè)2種選擇.并且一旦ei的擺放方法確定，e-i也就確定了.由于Gn中共有n條余樹邊，而余樹邊a的2條半邊的擺放方法已經(jīng)包含在e1，e2，…，en-1的余樹邊的擺放方法中.因此由組合計數(shù)原理知，Gn在球面S上的嵌入個數(shù)為2n-1（n≥2）.

22Gn在射影平面S上的嵌入

Gn是在射影平面S上的嵌入.選定與圖2所示的相同的生成樹，下面就余樹邊a是否為扭邊，分2種情形進行討論：

嵌入情形1a為非扭邊.

斷言1余樹邊中，對于任意的非扭邊ei，它的2條半邊ei，e-i都必須在生成樹的同側(cè).

證余樹邊中，若存在非扭邊ei，它的2條半邊ei，e-i在生成樹的異側(cè)，則非扭邊ei與a交錯.由引理4，這與S是射影平面矛盾.

斷言2余樹邊中，對于任意的扭邊ei，它的2條半邊ei，ei都必須在生成樹的同側(cè).

證余樹邊中，若存在扭邊ei，它的2條半邊ei，ei在生成樹的異側(cè)，則扭邊ei與非扭邊a交錯.由引理4，這與S是射影平面矛盾.

斷言3余樹邊e1，e2，…，en-1中至少有一條扭邊.

證由于Gn所嵌入的曲面S是不可定向的，則必定至少存在一條扭邊，結(jié)論顯然.

斷言4若余樹邊ei（3≤i≤n-3）為扭邊，則對于任意的j＜i-1及j＞i+1，余樹邊ej均為非扭邊.

證事實上，由斷言3知，e1，e2，…，en-1中至少有一條扭邊，不妨設(shè)這條扭邊為ei（3≤i≤n-3），對于任意的j＜i-1及j＞i+1，若存在ej為扭邊，則扭邊ei與ej必定平行.由引理4知，這與S是射影平面矛盾.

斷言5余樹邊ei（2≤i≤n-2）的2條鄰邊ei-1與ei+1不能同時為扭邊.

證若ei-1與ei+1（2≤i≤n-2）同時為扭邊，則ei-1與ei+1平行.由引理4知，這與S是射影平面矛盾.

由以上分析可知，余樹邊e1，e2，…，en-1中至少有一條扭邊，不妨設(shè)為ei（3≤i≤n-3），對于任意的j＜i-1及j＞i+1，ej均為非扭邊，且ei-1，ei+1不能同時為扭邊.因此下面對余樹邊ei（2≤i≤n-2）的2條鄰邊ei-1與ei+1是否為扭邊分2種子情形討論：

情形11余樹邊ei與它的一條鄰邊（不妨設(shè)為ei-1，2≤i≤n-1）為扭邊，其余的余樹邊均為非扭邊.

證由引理4知，扭邊ei-1與ei（2≤i≤n-1）必定交錯.由于ei-1與ei均為扭邊，由斷言2知，扭邊ei-1與ei各自的2條半邊均在生成樹的同側(cè).因此由ei-1與ei所構(gòu)成的Gn的子列只有圖3～4所示2種情形.

參考文獻：

［1］GROSSJL，F(xiàn)URSTML.Hierarchyforimbeddingdistributioninvariantsofgraph［J］.JGraphTheory，1987，11（2）：205220.

［2］CHENYC，LIUYP，WANGT.Thetotalembeddingdistributionsofcactiandnecklaces［J］.ActaMathSinica，2006，22（5）：15831590.

［3］TESAREH.Genusdistributionofringelladders［J］.DiscreteMath，2000，216（13）：235252.

［4］WANLX，LIUYP.Orientableembeddingdistributionbygenusforcertaintypeofnonplanargraphs（I）［J］.ArsCombin，2006，79：97105.

［5］WANLX，LIUYP.Orientableembeddingdistributionforcertaintypesofgraphs［J］.JCombinTheory，SerB，2008，98（1）：1932.

［6］CHENJ，GROSSJL，RIEPERRG.Overlapmatricesandtotalimbeddingdistributions［J］.DiscreteMath，1994，128（13）：7394.

［7］GROSSJL，ROBBINSDP，TUCKERTW.Genusdistributionsforbouquetsofcircles［J］.JCombinTheory，SerB，1989，47（3）：292306.

［8］楊艷，劉彥佩.兩類四正則圖的完全虧格分布［J］.數(shù)學學報，2007，50（5）：11911200.

［9］趙喜梅，劉彥佩.類圈圖的虧格分布［J］.數(shù)學物理學報，2008，28（4）：757767.

［10］劉彥佩.地圖的代數(shù)原理［M］.北京：高等教育出版社，2006.

［11］YANGY，LIUYP.FlexibilityofembeddingsofbouquetsofcirclesontheprojectiveplaneandKleinbottle［J］.ElectronJCombin，2007，14：#R80.

［12］劉新求，黃元秋，王晶，等.兩類項鏈圖在射影平面上的嵌入［J］.數(shù)學物理學報，2011，31A（3）：602610.

［13］劉新求，黃元秋，王晶.多重圈梯圖在射影平面上的嵌入個數(shù)［J］.應用數(shù)學學報，2010，33（2）：317327.