一类图在小亏格曲面上的嵌入

摘　要　利用嵌树模型和组合计数的相关方法，获得了由鹅卵石路图添加一条边所得到的一类图Gn在球面及射影平面上的嵌入个数，它们分别为2n-1（n≥2）和（3n-3）2n-1（n≥2）.

关键词　曲面；亏格；嵌入；联树

中图分类号　O1575 文献标识码　A 文章编号　10002537（2012）05002406

研究图在不同亏格曲面上不等价的嵌入个数，可以归结为图的亏格分布和图的完全亏格分布.自从Gross和Furst［1］引入相关概念以来，相关学者得到了某些图类的亏格分布［213］.由于图的亏格分布的研究是一个NP难问题，因此目前有关亏格分布及完全亏格分布的结果较少.对于大部分图类，我们尚不能确定其亏格分布，尤其是完全亏格分布.然而图在不同亏格曲面上的嵌入通常是有相关关系的，所以研究图在球面，环面，射影平面，Klein瓶等小亏格曲面上的嵌入结构以及不等价的嵌入个数是一项有意义的工作.

本文中曲面均为无边缘的紧闭二维流形，并且分为可定向曲面和不可定向曲面.在球面上增加p个“手柄”得到亏格为p的可定向曲面Op；在球面上增加q个“交叉帽”得到亏格为q的不可定向曲面Nq.其中，安“手柄”运算是指由球面分别挖去两个不相交的圆盘，其边界分别记为C1和C2，然后用一根圆柱筒的两端分别与C1和C2黏合而成；安“交叉帽”运算是指在球面上挖去一个圆盘，其边界记为C，然后用一条mbius带的边界与C黏合而成.图G在曲面S上的一个嵌入是指一个1-1连续映射h：GS，若S-h（G）的每一个连通分支都同胚于一个开圆盘，则称之为一个2胞腔嵌入.本文中的嵌入均为2胞腔嵌入.图G在曲面S上的2个嵌入h：GS和g：GS称为等价的，是指存在一个保定向的同胚映射f：SS，使得fh=g.

直观上，任何一个曲面S都可以由一个正2n边形黏合而成.把正2n边形的边分成n组，每组2条边，其中同一组的2条边用同一字母表示（如aa），然后分别给每条边规定一个方向，并用上标“+”（通常省略）和“-”区分（如aa或aa-）.按某一方向（顺时针或逆时针）依次记录正多边形的边，得到带上标的字母的循环序，这称为曲面的多边形表示.同一组中的2条边按相同方向黏合，即可得到曲面S.平面，环面，射影平面和Klein瓶可分别表示为O0=aa-，O1=aba-b-，N1=aa，N2=aabb.一般地，分别用Op=∏pi=1aibia-ib-i，Nq=∏qi=1aiai.表示亏格为p和q的可定向和不可定向曲面，其中p≥1，q≥1，并称之为曲面的标准型代数表示.如果用字母a表示的一组边的方向相反（即aa-或a-a），则按上述规则经过黏合后得到的边a称为非扭边.如果用a表示的一组边的方向相同（即aa或a-a-），则按上述规则经过黏合后得到的边a称为扭边.

以下3种运算不改变曲面的类型：运算1.　Aaa-A；运算2.　AabBabAcBc；运算3.　AB（Aa）（a-B）.在这3种运算中，括号表示循环序，A，B均为字母的线性序.除运算2中的A和B允许为空集外，其余均为非空集合.事实上，以上运算确定了一类拓扑等价，记为“～”.由此可以导出下面3种拓扑等价关系： 刘彦佩教授创建的嵌树模型［10］，对研究图的亏格分布和完全亏格分布在方法上有着全新的突破：给定图G=（V，E）的一棵生成树T，然后将每条余树边赋予一个字母，并将每余树边（不妨设为ei）从中间切断，得到2条用同一字母表示的半边，这2条半边分别用ei，ei或ei，e-i表示，此时所得到的图形叫做G的联树.设余树边的数目为β，从任一节点出发沿树T和旋系走遍联树的所有边，依次记录余树边的字母（生成树T的边不用记录），得到一个有2β个带上标的字母的循环序，这个循环序所对应的曲面即为图G的关联曲面.由于图的关联曲面和图的嵌入之间存在一一对应，因此我们可以用图的关联曲面的结构来分析图在曲面上的嵌入.近年来，相继有学者得到一些图类的射影平面等小亏格曲面上的嵌入个数［1113］，本文亦在联树模型的基础上得到了一类图在球面和射影平面上的嵌入个数及结构特征.

1　引理和定义

引理1［10］　设曲面S1是可定向曲面且亏格为p，曲面S2是不可定向曲面且亏格为q.

证　由关系1，S=AxByCx-Dy-～ADCBExyx-y-.不妨设S1=ADCBE，这里E是空集.则S～S1xyx-y-.由于S为不可定向曲面，则S1为不可定向曲面，且其亏格至少为1.由引理1知，S的亏格至少为3.

引理3　设S为不可定向曲面，若S=AxByCyDx或S=AxByCxDy-，则S的亏格至少为2.

证　若S=AxByCyDx，由关系2，S=AxByCyDx～AxBC-Dxyy～AD-CB-yyxx，由引理1知，S的亏格至少为2；若S=AxByCxDy-，由关系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　设S是射影平面，则其多边形表示中的任意2条边，若都是扭边，则必定交错，否则必定平行.

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

定义2　设A是一个字母循环序，则由A中的某些字母按原来的相对顺序组成的字母的循环序，称为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　主要结论

如果n个顶点的路的每条边都是双重边，并且两端点都各自有一个环，那么这样的图称之为鹅卵石路图（cobblestone　path），长度为n，记为Jn。文献［6］已经得到了鹅卵石路图Jn的完全亏分布.分别用两顶点（不妨设为u，v），剖分Jn两端的环，并且用一条边a连接u和v，得到的图记为Gn+2（见图1）.

21　Gn在球面S上的嵌入

首先在Gn中选定一棵生成树（如图1中粗边所示），设其n个点分别为u1，u2，…，un，且ei=uiui+1（1≤i≤n-1），a=u1un.将每条余树边从中间切断，即可得到Gn的一棵联树（如图2）.

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

断言1　所有的余树边均为非扭边.

证　由引理6易得.

断言2　余树边中，任意一条非扭边的2条半边必须在生成树的同侧.

证　余树边中，若存在非扭边ei，它的2条半边ei，e-i在生成树的异侧，由于a也为非扭边，则非扭边ei与a交错.由引理5知，Gn嵌入曲面S的亏格必定大于或等于1，这与S是球面矛盾.

断言3　任意2条余树边，若均为非扭边，则必定平行.

证　余树边中，若存在非扭边ei与ej交错，则由引理5知，Gn嵌入曲面S的亏格必定大于或等于1，这与S是球面矛盾.

定理1　Gn在球面S上的嵌入个数为2n-1（n≥2）.

证　由断言1～3知，对于任意的余树边ei（1≤i≤n-1），它的2条半边ei，e-i都有摆放在生成树的上侧及下侧2种选择.并且一旦ei的摆放方法确定，e-i也就确定了.由于Gn中共有n条余树边，而余树边a的2条半边的摆放方法已经包含在e1，e2，…，en-1的余树边的摆放方法中.因此由组合计数原理知，Gn在球面S上的嵌入个数为2n-1（n≥2）.

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

Gn是在射影平面S上的嵌入.选定与图2所示的相同的生成树，下面就余树边a是否为扭边，分2种情形进行讨论：

嵌入情形1　a为非扭边.

断言1　余树边中，对于任意的非扭边ei，它的2条半边ei，e-i都必须在生成树的同侧.

证　余树边中，若存在非扭边ei，它的2条半边ei，e-i在生成树的异侧，则非扭边ei与a交错.由引理4，这与S是射影平面矛盾.

断言2　余树边中，对于任意的扭边ei，它的2条半边ei，ei都必须在生成树的同侧.

证　余树边中，若存在扭边ei，它的2条半边ei，ei在生成树的异侧，则扭边ei与非扭边a交错.由引理4，这与S是射影平面矛盾.

断言3　余树边e1，e2，…，en-1中至少有一条扭边.

证　由于Gn所嵌入的曲面S是不可定向的，则必定至少存在一条扭边，结论显然.

断言4　若余树边ei（3≤i≤n-3）为扭边，则对于任意的j＜i-1及j＞i+1，余树边ej均为非扭边.

证　事实上，由断言3知，e1，e2，…，en-1中至少有一条扭边，不妨设这条扭边为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中至少有一条扭边，不妨设为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与它的一条邻边（不妨设为ei-1，2≤i≤n-1）为扭边，其余的余树边均为非扭边.

证　由引理4知，扭边ei-1与ei（2≤i≤n-1）必定交错.由于ei-1与ei均为扭边，由断言2知，扭边ei-1与ei各自的2条半边均在生成树的同侧.因此由ei-1与ei所构成的Gn的子列只有图3～4所示2种情形.

参考文献：

［1］　GROSS　J　L，　FURST　M　L.　Hierarchy　for　imbeddingdistribution　invariants　of　graph［J］.　J　Graph　Theory，　1987，11（2）：205220.

［2］　CHEN　Y　C，　LIU　Y　P，　WANG　T.　The　total　embedding　distributions　of　cacti　and　necklaces［J］.　Acta　Math　Sinica，　2006，22（5）：15831590.

［3］　TESAR　E　H.　Genus　distribution　of　ringel　ladders［J］.　Discrete　Math，　2000，216（13）：235252.

［4］　WAN　L　X，　LIU　Y　P.　Orientable　embedding　distribution　by　genus　for　certain　type　of　nonplanar　graphs（I）［J］.Ars　Combin，　2006，79：97105.

［5］　WAN　L　X，　LIU　Y　P.　Orientable　embedding　distribution　for　certain　types　of　graphs［J］.　J　Combin　Theory，Ser　B，　2008，98（1）：1932.

［6］　CHEN　J，　GROSS　J　L，　RIEPER　R　G.　Overlap　matrices　and　total　imbedding　distributions［J］.　Discrete　Math，　1994，128（13）：7394.

［7］　GROSS　J　L，　ROBBINS　D　P，　TUCKER　T　W.　Genus　distributions　for　bouquets　of　circles［J］.　J　Combin　Theory，　Ser　B，　1989，47（3）：292306.

［8］　杨　艳，刘彦佩.两类四正则图的完全亏格分布［J］.数学学报，　2007，50（5）：11911200.

［9］　赵喜梅，刘彦佩.类圈图的亏格分布［J］.数学物理学报，　2008，28（4）：757767.

［10］　刘彦佩.地图的代数原理［M］.北京：高等教育出版社，　2006.

［11］　YANG　Y，　LIU　Y　P.　Flexibility　of　embeddings　of　bouquets　of　circles　on　the　projective　plane　and　Klein　bottle［J］.　Electron　J　Combin，　2007，14：#R80.

［12］　刘新求，黄元秋，王　晶，等.两类项链图在射影平面上的嵌入［J］.数学物理学报，　2011，31A（3）：602610.

［13］　刘新求，黄元秋，王　晶.多重圈梯图在射影平面上的嵌入个数［J］.应用数学学报，　2010，33（2）：317327.