（运筹学与控制论专业论文）论确定图的最小亏格.pdf

北京交通大学博士学位论文中文摘要 中文摘要 摘要：图在曲面上的可嵌入性是拓扑图论的主要问题其中图的最小亏格问题是 n p - 困难的，所以对解决任意图的最小亏格仍需很长的一段距离基于此，本文 主要是在刘彦佩提出的联树模型的基础上，选择考虑了有趣且有意义的图类来研 究其最小亏格问题除此之外还计算了特定图类的可定向嵌入的亏格分布本文 所考虑的图类对已研究最小亏格或亏格分布的图类有一定的推广作用，所用方法 提升了计算技巧，从而为更广泛图类的最小亏格及亏格分布问题的研究提供了更 广阔的前景 对图的最小亏格的研究，主要是在联树模型的基础上，通过一个图在曲面上 的嵌入可用其联树，进一步其关联曲面来表示，然后把关联曲面逐层分段，在层 分割上建立调位运算通过对任一关联曲面作一系列调位。从而可得最小亏格的 关联曲面，此亏格即为所求图类的最小亏格进一步依据给定图类的特点，通过 关联曲面之间的关系可求得其最小亏格的表达式而众所周知，对称性比较弱的 图类用已知商嵌入的方法来解决却是不可能这部分内容主要集中在前五章 第一章首先对这两方面的研究背景作了简要的介绍随后，给出了一些与之 相关的定义和性质 第二章首先利用异于以前的方法得到了完全二部图的最小亏格然后基于完 全二部图关联曲面的特点进行推广，构造了对称性比较弱的新图类j ( m ，n ) 且得 其最小亏格，最后对完全二部图不同最小亏格嵌入的数目作了估算 第三章构造了对称性比较弱的新图类r ( n ，z ，m ) 且得其最小亏格作为推论 得到了完全三部图 j ( f n 2 ) 的最小亏格最后对完全三部图 l 不同 最小亏格嵌入的数目作了估算 第四章研究了边合并图的最小亏格文献【1 ，2 】分别讨论了完全图与完全图， 完全二部图与完全二部图边合并的最小亏格问题，本章给出了，1 个特定图边合并 的最小亏格 第五章讨论了几类图与一节点的联图的最小亏格而平面图与一节点的联图 亦为a p e x 图众所周知，a p e x 图是拓扑图论中比较重要的一类图，在图的最小 亏格问题研究中具有强大的作用m o h a r 证明了a p e x 图的最小亏格问题是n p 一 困难的本章考虑了几类平面图与一节点的联图，即为a p e x 图，以及两类未必是 平面的图与一节点联图的最小亏格 北京交通大学博士学位论文 中文摘要 第二部分表述在第六章，推广了【2 1 】中“珠子”的类，构造了异于目前已知 亏格分布的图类所用方法主要是根据给定图类的特点，选择确切的支撑树，把 关联曲面集合进行分类，建立递推关系式，进而得给定图类的可定向嵌入亏格分 布的显式表达式由此可进一步考虑具有任意多节点且其度大于3 和4 的此类正 则图的可定向嵌入亏格分布 第六章首先构造了推广的项链图，循环项链图以及推广的另三类图，其次得 其可定向嵌入亏格分布的显式表达式最后把上面图类进一步推广，得到了一类 更一般的图，并对其可定向嵌入的亏格分布进行了刻画 第七章介绍了图的最小亏格及亏格分布领域中一些需要更进一步研究的问 题，如如何利用联树模型计算完全图的最小亏格，以及如何通过刻画最小亏格关 联曲面的特性来确定更广泛图类，乃至任意图类的最小亏格问题等等 关键词：曲面；联树；最小亏格；亏格分布；可定向嵌入 分类号：0 1 5 7 5 a b s t r a c t a b s t r a c t ：t h ee m b e d d a b i l i t yo fag r a p ho nas u r f a c ei sam a j o rt h e m eo f t o p o l o g i c a lg r a p ht h e o r y s i n c et h em i n i m u mg e n u sp r o b l e mi sn p c o m p l e t e ，o n e d o e sn o th o p et of i n dam i n i m u mg e n u sf o r m u l af o ra na r b i t r a r yg r a p h c o n s i d e r - i n gt h eh a r d n e s si nc o m p u t a t i o n a lc o m p l e x i t y , i n t h i sp a p e r ，b ya p p l y i n gt h ej o i n t t r e em o d e li n t r o d u c e db yy a n p e il i u ，w es e e kt oi s o l a t ei n t e r e s t i n ga n ds i g n i f i c a - t i v ef a m i l i e so fg r a p h sf o rw h i c ht h ef o r m u l a eo fm i n i m u mg e n e r ae a r lb ed e r i v e d i na d d i t i o n g e n u sd i s t r i b u t i o n so fo r i e n t a b l ee m b e d d i n g sf o rg i y e ng r a p h sa r ep r o - v i d e d t h i sp a p e rm u c ha d v a n c e st h ea r to fc a l c u l a t i n gg e n u sp r o b l e m s t h e m e t h o du s e dh e r eo f f e r sc o n s i d e r a b l ep r o m i s eo fa p p l i c a t i o nt oa d d i t i o n a lf a m i l i e s o fg r a p h sb e y o n dt h eo n e sf o rw h i c hi ty i e l d sf o r m u l a eh e r e f o rs t u d y i n gt h em i n i m u mg e n u so fag r a p h ，b a s e do nt h ej o i n tt r e e s ，a n e m b e d d i n go fag r a p ho i las u r f a c ec a nb er e p r e s e n t e db yaj o i n tt r e e ，f u r t h e rb y a na s s o c i a t e ds u r f a c eo fi t d i v i d et h ea s s o c i a t e ds u r f a c ei n t os e g m e n t sl a y e rb y l a y e ra n dd e f i n ea no p e r a t i o nc a l l e da ne x c h a n g e r i nt h el a y e rd i v i s i o n h e n c et h e a s s o c i a t e ds u r f a c eo fm i n i m u mg e n u sc a nb eg o tb yd o i n gas e q u e n c eo fe x c h a n g e r s o ns o l ea s s o c i a t e ds u r f a c e f u r t h e r ，a c c o r d i n gt ot h ep r o p e r t i e so fg i v e ng r a p h s ， t h ee x p r e s s i o n so fm i n i m u mg e n e r ao ft h e s eg r a p h sa r eo b t a i n e d t h e s ea r ea p - p a r e n t l yn o te a s i l yo b t a i n e du s i n gq u o t i e n te m b e d d i n g s t h ec o n t e n to ft h i sp a r t i sc o n c e n t r a t e do nt h ef i r s tf i v ec h a p t e r s i nc h a p t e r1 ，f i r s t l y , w eg i v eab r i e fi n t r o d u c t i o na b o u tt h eb a c k g r o u n do ft w o p a r t s t h e ns o m ed e f i n i t i o n sa n dp r o p e r t i e s ，r e l a t e dt ot h e m ，a r ep r o v i d e d c h a p t e r2 ，o b t a i n st h em i n i m u mg e n u so fc o m p l e t eb i p a r t i t eg r a p h sw i t ha d i f f e r e n tm e t h o da sb e f o r e b a s e do nt h ep r o p e r t i e so fa s s o c i a t e ds u r f a c e sf o r c o m p l e t eb i p a r t i t eg r a p h s ，an e wt y p eo fg r a p hj ( m ，竹) w i t hw e a ks y m m e t r yi s c o n s t r u c t e d a tt h es a m et i m e ，t h em i n i m u mg e n u so fi ti sd e r i v e d f i n a l l y , t h e n u m b e ro fg e n u se m b e d d i n g so fc o m p l e t eb i p a r t i t eg r a p h si se a s i l ye s t i m a t e d i nc h a p t e r3 ，w ec o n s t r u c tan e wt y p eo fg r a p ht ( n ，2 ，m ) w i t hw e a ks y m m e t r y a n dc o m p u t et h em i n i m u mg e n u so fi t a sac o r o l l a r y , t h em i n i m u mg e n u so f c o m p l e t et r i p a r t i t eg r a p h j ( f 住2 ) i sa l s od e r i v e d f i n a l l y , t h en u m b e ro f g e n u se m b e d d i n g so fc o m p l e t et r i p a r t i t eg r a p hj 厶 li se a s i l ye s t i m a t e d m c h a p t e r4 ，d i s c u s s e st h em i n i m u mg e n e r ao fe d g ea m a l g a m a t i o n so fg i v e n g r a p h s l i t 【1 ，2 】s t u d yt h em i n i m u mg e n e r ao fe d g ea m a l g a m a t i o n sf o rc o m p l e t e g r a p h sa n dc o m p l e t eb i p a r t i t eg r a p h s ，r e s p e c t i v l y h e r e ，t h em i n i m u m g e n e r ao f e d g ea m a l g a m a t i o n sf o rng i v e ng r a p h sa r eo b t a i n e d i nc h a p t e r5 ，w es t u d yt h em i n i m u m g e n u so fj o i n so fs e v e r a lt y p e so fg r a p h s w i t hav e r t e x a n dt h ej o i u so fp l a n a rg r a p h sw i t hav e r t e xa r e a p e xg r a p h s i ti s w e l lk n o w nt h a ta p e xg r a p h sa r ef a rm o r ei m p o r t a n tg r a p h so ft o p o l o g i c a lg r a p h t h e o r ya n dp l a ya l li m p o r t a n tr o l ei nr e s e a r c ho fm i n i m u m g e n u so fag r a p h m o h a r p r o v e dt h a tm i n i m u mg e n u sp r o b l e mi sn p - h a r d h e r e ，t h em i n i m u m g e n e r ao f j o i n so fs e v e r a lt y p e so fp l a n a rg r a p h sw i t hav e r t e x ，n a m e l ya p e xg r a p h s ，a n dt w o t y p e so fg r a p h sw i t hav e r t e x ，a r ep r o v i d e d ，w h e r et h et w ot y p e so fg r a p h sm a y n o tb ep l a n a r t h es e c o n dp a r tw h i c hi n c l u d e sc h a p t e r6 ，m a i n l yg e n e r a h z e st h ec l a s so f “b e a d s 。，b e y o n dt h o s ea p p e a r i n gi n 2 l 】，f o rw h i c hg e n u sd i s t r i b u t i o nc a l c u l a - t i o u sa r et r a c t a b l e b yb a s i n gt h ec a l c u l a t i o no nt h ee x p l i c i tc h o i c eo fas p a n n i n g t r e ea n dc l a s s i f y i n gt h ea s s o c i a t e ds u r f a c e sa c c o r d i n gt o t h ep r o p e r t i e so fg i v e n g r a p h s ，s o m ee q u a t i o n sa r eo b t a i n e dt oc o m p u t et h ee x p l i c i te x p r e s s i o n so fg e n u s d i s t r i b u t i o n sf o rt h eg i v e ng r a p h s f u r t h e r ，t h i sp e r m i t so n et oo b t a i nf b 咖l 】l a e f o ri n f i n i t ef a m i l i e so fr e g u l a rg r a p h sw i t hd e g r e eg r e a t e rt h a n3a n d4a n dw i t h a r b i t r a r ym a n yv e r t i c e s c h a p t e r6 ，f i r s t l y , c o n s t r u c t sg e n e r a l i z e dn e c k l a c e s ，c i r c u l a n tn e c k l a c e sa n da n - o t h e rt h r e et y p e so fg r a p h sb yg e n e r a l i z i n gn e c k l a c e s ，t h e no b t a i n st h ee x p l i c i te x - p r e s s i o n so f o r i e n t a b l ee m b e d d i n gd i s t r i b u t i o n sb yg e n u sf o rt h e m f i n a l l y , f u r t h e r g e n e r a l i z e st h eg i v e ng r a p h st oo b t a i nan e wt y p eo fg r a p ha n dg i v e sad e s c r i p t i o n a b o u tg e n u sd i s t r i b u t i o no fo r i e n t a b l ee m b e d d i n g sf o rt h i st y p eo fg r a p h c h a p t e r7 ，d i s c u s s e ss o m eu n r e s o l v e dp r o b l e m sa b o u tm i n i m u mg e n u sa n d g e n u sd i s t r i b u t i o no fo r i e n t a b l ee m b e d d i n g sf o rag r a p h ，s u c ha sb a s e do nt h ej o i n t t r e em o d e l ，c a l c u l a t i o no fm i n i m u mg e n u so fc o m p l e t eg r a p h s ，d e t e r m i n a t i o no f m i n i m u mg e n e r af o rf u r t h e rt y p e so fg r a p h so re v e na r b i t r a r yg r a p h s ，e t c k e y w o r d s ： s u r f a c e ；j o i n tt r e e ；m i n i m u mg e n u s ；g e n u sd i s t r i b u t i o n ；o f f - e n t a b l ee m b e d d i n g l v 北京交通大学博士学位论文英文摘要 c l a s s n o ：0 1 5 7 5 v 0 p q gvv o g h s l s 2 o ( s 1 一y ( g ) o g 8 它 _ s ( _ ) ) o m i 。( s ( _ ) ) ) g i ( g ) n g ( g ) g l 宰cg 2 f 口1 【口】 符号说明 亏格为p 的可定向曲面 亏格为q 的不可定向曲面 图g 与节点如的联图 图g 与图日的笛卡尔乘积 曲面研与曲面等价 曲面s 的亏格 图g 的最小亏格 图g 的旋 b e t t i 数 联树 调位 把关联曲面s 调位得所有关联曲面的集合 s ( 一) ) 中最小亏格关联曲面的亏格 图g 可定向嵌入亏格为i 的曲面的数目 图g 的不同最小亏格嵌入的数目 图g 1 与图g 2 的边合并图 大于等于a 的最小整数 小于等于a 的最大整数 北京交通大学博士学位论文独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位论文作者签名t 签字日期。年月日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：导师签名： 签字日期：年月日签字日期：年月日 致谢 本论文是在刘彦佩教授的悉心指导下完成的，正是刘老师辛勤的培养和无微 不至的关怀使我在成长中不断进步刘老师为人宽厚，待人诚恳，知识渊博，治学 严谨，勤恳敬业，是我学习的楷模在此对刘老师的帮助与鼓励表示衷心的感谢 感谢常彦勋教授、冯衍全教授、修乃华教授、郝荣霞教授以及何卫力副教授， 对于我的科研工作和论文他们都提出了许多宝贵意见，使我受益匪浅 感谢杨艳、董广华，许燕、阎爱玲，冯涛、周进鑫、罗自炎以及王小苗等同 学，在论文完成过程中的巨大帮助 感谢父母对我培养及教育，正是他们多年来的支持与理解才使我得以顺利完 成学业，深深地感谢他们 第一章预备知识 这一章中，为了便于大家对所研究图的最小亏格及亏格分布理论有一个清楚 的认识，首先对其由来及发展过程给予系统的介绍随后，为了能从数学上准确 地描述这一理论，我们对一些与之相关的基本概念，性质以及所采用的研究方法 进行了简要地叙述 1 1 研究背景 图的最小亏格，亦称亏格，是指它所能可定向嵌入曲面的最小亏格 图的可嵌入性理论是拓扑图论中基本且比较难的问题 1 8 7 8 年，c a y l e y 公 布了四色问题后，图的平面可嵌入性问题便开始引起人们的关注图的曲面可嵌 入性起源于h e a w o o d 地图着色猜想1 8 9 0 年，h e a w o o d 把四色猜想推广到更高 曲面上，并得到非平面的曲面色数的上界，即x ( s ) 【z 型! ；= 丝】，其中c 是曲面s 的欧拉示性数h i l b e r t 和c o h n - v o s s e n 将它的解决归结为引线问题，即k 。的最 小亏格问题借助于g u s t i n 引进的电流图以及y o u n g s 作得重要改进，在众多学 者的努力下，此问题的最后部分直至1 9 6 8 年由r i n g e l 和y o u n g s 6 0 1 给以完全解 决，此问题的解决使拓扑图论成为个主要的研究领域，从而也激起了广大学者的 研究兴趣图的最小亏格问题已被t h o m a s s e n 6 6 1 证明是n p - 困难的，所以到目 前为止已知结果并不是很多，主要解决了一些特殊图类以及经过特殊图类运算得 到的图类的最小亏格问题，参看文献 1 4 ，7 ，1 0 - 1 6 ，2 4 ，2 5 ，4 二4 6 ，5 8 - 6 3 ，7 0 - 7 2 ，7 4 】 等证明的方法主要是利用商嵌入以电压图( 或对偶地，电流图) 的形式来构造最 小亏格嵌入此方法对解决其它图类，特别是对称性比较弱的图类的最小亏格问 题有很大的局限性为此寻求行之有效的方法来解决更广泛图类，乃至一般图类 的最小亏格，成为迫切要解决的问题 求个图的最小亏格的同时，却鲜有考虑估算最小亏格嵌入数目的问题直 至最近，在特殊图类，如完全图，部分完全二部图等方面才有一些进展 5 ，6 ，2 8 ， 2 9 ，3 0 ，3 1 ，3 5 ，3 6 ，3 8 ，5 6 ，5 7 】 1 9 6 6 年，d u k e 证明了下面的插值定理 定理1 1 11 1 4 j 若一个图g 可嵌入到亏格分别为， 和t 的曲面母和& 上，则 图g 必存在曲面& 上的嵌入，其中，k t 第 一章预备 知识 图的可定向嵌入亏格分布，是指图在各种不同亏格曲面上可定向嵌入的数目 此概念是在1 9 8 7 年由g r o s s 和f u r s t 引入的已知结果主要有。f u r s t ，g r o s s 和 s t a t m a n 1 7 计算了c l o s e d - e n dl a d d e r s 和c o b b l e s t o n ep a t h s 的嵌入亏格分布的表 达式 m c g c o c h 5 2 1 得到了c i r c u l a rl a d d e r s 和m s b i u sl a d d e r s 的亏格分布的表 达式 k w a k 和l e e 3 2 】得到了d i p o l e s 的亏格分布t e s a r 6 5 】考虑了r i n g e l l a d d e r s 的亏格分布g r o s s ，r o b b i n s 和t u c k e r 2 0 1 提供了b o u q u e t so fc i r c l e s 的 亏格分布的递推式c h e n ，g r o s s 和r i e p e r 2 1 得到了n e c k l a c e s 的亏格分布表达 式所用方法主要有组合的方法，j a c k s o n 公式法和m o h a r 覆盖矩阵法【2 6 ，5 4 】 总体而言，这些方法对解决其它图类的嵌入亏格分布仍存在很大的局限性 2 0 0 3 年刘彦佩提出了图的嵌入联树模型( 1 9 7 9 年的文章【3 9 ，4 0 】体现了这 种思想) ，建立了图的联树和嵌入之间的一一对应关系，把拓扑问题转化为组合问 题，从而为求图的最小亏格及亏格分布提供了更有效的理论基础并且更广泛图 类的亏格分布已得到，见文献【9 ，3 7 ，6 8 ，6 9 ，7 0 ，7 5 ，7 7 】 纵观图的亏格问题的由来及发展过程，可以看出它与组合数学，地图计数理 论等学科有着紧密的联系，对其进行研究必将对数学整个学科的发展起到推动作 用，有其一定的理论意义和实际意义 1 2 相关的定义与性质 个线性序x = 曲z 是指个具有关系a 一b - 4z 的字母序列x 的 倒序表示为x 且戈= z 阮设y 是线性序，若对任意的a y 有n x 且对 y 中的a 2 其中，m 为图中i 次节点的数目 下面对本文研究问题所依赖的联树模型给以介绍 图g = ( ve ) 的子图设为树t ，若i y ( t ) i = l v ( c ) i ，则称t 为g 的支撑树， ( k e e ( t ) ) 称为g 的余树余树边的数目，被称为此图的b e t t i 数，用p 表示 给定图g 的支撑树t ，把每条余树边( u t ，v i ) 劈分为两条半边( 札t ，魂) 和，晚) ， 其中1 i p ，从而构成g 上的一新树，记为t = ( v + ，s ( t ) + e 1 ) ，其中 e 1 = 【( 仳t ，砚) ，( 忱，雷i ) 1 1 i p ) 且k = 砚，砚1 1 i p 令盯= 【l 讹y ) 为图g 的旋，其中表示与节点 关联的边的循环序，则已决定了t 在平面 上的一个嵌入 设6 = ( 6 l ，如，如) 为个二元向量，用带有由5 i 所确定的指标t + ( 常略 之不计) 或一的字母啦来标注( “i ，砚) 和( 仇，诜) ，其中文= 0 意味两个指标不同， 否则，相同给乃的半边标注带指标的字母得到的图称为g 的一个联树 4 9 】，记 作霉 在弯上，依照给定方向( 顺时针或逆时针) 记录标注半边的带指标的所有字 母a j 或0 7 ，其中j 【l ，2 ，p ) 且1 j p ，所得到的是由2 p 个字母形成的 4 北京交通大学博士学位论文 循环序，它表示曲面，故称为图g 的关联曲面 5 0 】两个关联曲面若具有相同的 循环序以及指标6 ，则称为相同的否则，不同的 鉴于本文只考虑可定向嵌入的情况，则有6 = 0 ，即关联曲面中每个字母的两 次出现带有不同的指标 设g 口为图g 由旋盯决定的嵌入令( ，于) = 霉l 盯) ，其中是图g 的旋的集合 引理1 2 6 对于盯1 0 2 ，嵌入g 旷。和，连同露和砭c x 同 引理1 2 7 【4 9 】设乃和乃是图g 的两个不同的支撑树，是图g 的旋的集 合，则( ，五) 和( ，t 2 ) 之间存在一一对应关系 引理1 2 81 5 0 给定图g 的一支撑树，则g 的嵌入与关联曲面之间存在一一对应 关系 基于此，图在曲面上的嵌入可用其联树，进而其关联曲面来表示从而求图 的最小亏格问题可转化为在所有关联曲面中寻求最小亏格关联曲面的问题，求图 的可定向嵌入亏格分布的问题转化为将关联曲面集合按初等等价分类的问题 为了得到最小亏格的关联曲面，则把关联曲面进行逐层分段，从而在层分割 上建立一种运算，可把一个曲面变换到另一个曲面，直至最小亏格的关联曲面 为描述方便，首先令v 是支撑树t 的节点且满足出( 口) 1 ，关联曲面s 用( ) 表示且称为层段对t 的任意节点缸，t 和秽由唯一的路连接且用型来表 示m i 器d ( w ，牡) 若n ( v ) = v l ，晚，仇) ，则层段可被分成( & 。) ，其 中& ，( 1s 歹七) 被称为关联节点口的层段对任意节点加，若n ( w ) = 妣 型，1 i t ) ，则& = ( 。s 圪& 。) ，其中。( 1 i t ) 亦称为关联节点 伽的层段每一层段皆可分为其它层段直至层段& k 为止，其中是丁的满足 如( ) = 1 的节点且s 蠢由标注与关联的半边的字母组成，且此处每一字母亦 称关联节点的层段依照给定图g 的旋，与同一节点关联的任两个层段皆可 交换其前后位置，使得每次交换都可使一关联曲面变换到另关联曲面则在层 分割上的这种运算被称为调位【5 0 】，以s _ 表示把关联曲面s 作一系列调位运 算变换到关联曲面 注：用符号0 来标注层段，只表示内部层段可交换前后位置，并不会改变关联曲 面本身当层段中只含个字母时，0 通常省略 5 第 一 章预备知识 引理1 2 9 删图的一个关联曲面的层分割，经过一次调位，所得到的是另一关联 曲面的层分割反之。后一个曲面的层分割，再经过一次这个调位，又确定前一 个曲面的原来的层分割 引理1 2 1 0 在图的关联曲面中，调位运算满足封闭性 因此最小亏格的关联曲面可通过对任一关联曲面作一系列调位运算得到 为了更加明晰联树等定义，参看示例完全二部图凰4 ，其支撑树在图1 1 ( a ) 中用黑线表示及其联树见图1 1 ( b ) 用一1 标注余树边仇呦，其中i = 1 ，2 ，3 且 j = 2 ，3 ，则其关联曲面可表示为 爵= n 1 1 “2 l “3 l “2 1 u 2 2 u 3 2 u 1 1 一口5 一n ；一o ；一前一0 3 _ u 11 ) 2t ，3 ( a ) 图1 1 ：恐，4 ( a ) 及其一联树( b ) f i g 1 1 k 3 4 ( a ) a n daj o i n tt r e eo fk 3 ，4 ( b ) 设鹾= ( 。) 则蹬= ( 瓯。) = ( & m 鼠，) = ( ( ：瓯。) 鼠。s 恐鼠) ，其中 。= ( o i o ；口i ) ，。= ( 畦o ；n ；) ，& 。= ( n i o ；一) ，= ( 0 2 。一o ；一) ，& = ( n 3 - n ；一) 显然，给定一联树，弱4 的关联曲面亦可表示为 霹= ( ( o i n ；d 2 ) ( o 搦0 2 ) ) ( ( o i o ；一) ( 0 2 - 一) ( 0 3 - 谴一) ) 经过一系列调位运算后， 霹一野= ( ( o ；o i 口i ) ( 口；n 5 0 2 ) ) ( ( 碹一n 3 _ ) ( n i 一畦一) ( n ；一口 ) ) ， 即具有最小亏格的关联曲面利用同样的方法，可以得到恐4 的所有最小亏格的 关联曲面 6 北 京交通大学博 士 学位论文 为后面章节中表述方便，这里给出一些符号表示 设 s ( _ ) ) 意味着在关联曲面s 上作一系列可能的调位运算得到的所有关联 曲面的集合令o m i n ( s ( _ ) ) ) 2 vs 署乳”。( s ) 且o t2 里。t 6 i 町 用( g ) 表 示图g 不同的最小亏格嵌入的数目 其他未解释的术语，读者可参见刘彦佩专著 4 9 ，5 0 ，4 7 ，4 8 】 基于此，本文研究了给定图类( 第二、三、四、五章) 的最小亏格问题，主要 考虑了新构造的对称性比较弱的图类，边合并图，图与一节点的联图等，由给定 图类的特点，根据其关联曲面的特性得到了最小亏格之间的关系式，从而得其最 小亏格的表达式其次对给定图类( 第六章) 的可定向嵌入的亏格分布问题进行了 研究构造了推广的项链图，循环项链图以及进一步推广的三类图，通过把关联 曲面集合进行分类，然后根据分类情况建立递推关系式，从而得其可定向嵌入的 亏格分布的显式表达式本文问题的解决，为求更广泛图类的最小亏格及可定向 嵌入的亏格分布问题打下基础 7 第二章完全二部图及新图类j ( m ，n ) 的最小亏格 文献【7 ，6 3 】中分别研究了完全二部图的最小亏格问题本章在联树模型的基 础上，采用不同于以前的方法得到了完全二部图的最小亏格，而此处所用方法更 易懂且具有推广性然后根据其关联曲面的特性构造了一类对称性比较弱的新图 并求得其最小亏格而对于最小亏格嵌入数目的问题，只有完全图及部分完全二 部图得到了研究本章最后通过考虑其关联曲面，估算了完全二部图不同最小亏 格嵌入的数目 2 1 完全二部图及新图类j ( m ，n ) 本节中，我们用不同于以前的方法给出了完全二部图的最小亏格然后根据 其关联曲面特性构造了新图类且得其最小亏格 设完全二部图，。的两个部分的节点集为u l ，u 2 ，t 。) 和v l ，睨， 选择与u ，关联的所有边以及与关联的所有边作为支撑树，且用字母嘭一来标 注余树边v i u j ( 1 i n 一1 ，2 j m ) 假设。联树的每一个节点具有顺时 针的旋则其关联曲面可表示为 船= ( n - 1 ) ( 旦翁1 ) 其中， 农：= a p 一1 a 一a 襞：，a 一1 ) = ( 霹o ；啦n 一1 ) ， 酸i 1 = b p 砂以谁一b j 一1 = ( 一一一靠。) ， 1 i 仇一1 ，1 n 一1 设 器= 蝴a a ( n 一- 1 1 一s ( 一m - ，磁= 蜘a m n 一- 1 1 酸n ， 簖= a r 鸳以a 乏：旦黯， 其中i l i 2 i m - x 是 1 ，2 ，m 一1 上的循环置换 引理2 1 1 d 嘲( 踮( _ ) ) ) = d 腑( ( 船( _ ) ) ) = d 嘲( 簖( _ ) ) = o 嘲( 器( _ ) ) ) 9 第 二 章完全二部图及新图类 的最小亏格 证明：v 跚 册( _ ) ) ，不妨假设 辨= ( a n 一a 少一a 一a 黠：) ( 垦罂i 1 ) ， 其中j i 则必有 翰= a p 一1 1 a ，一a 一a 黠：( 酵i 1 ) 砩( _ ) ， 然后把珊中的瓴t 一和噶一( 1 t 佗一1 ) 作调位得到的曲面记为r ，亦可用 砩_ r 表示此时，o ( r ) = d ( 跚) 因此o m i n ( 眙( _ ) ) ) o m ；。( 跚( _ ) ) ) 另一方面， 嘲( 一) ) j s 船( 一) ) ，则 d m ；n ( 姥( _ ) ) ) o m i n ( 珊( _ ) ) ) 所以o m t n ( 姥( _ ) ) ) = o m i n ( 跚( 一) ) ) 同理可得 o m t n ( 【露( _ ) ) ) = d m t 。( 翰( _ ) ) = o m i n ( 器( 一) ) ) 为证明定理方便起见，首先设 色：( 6 。6 2 6 t ) ，鲂：( 6 f 坷酊) ，丌( 互m ) ：fj j 0 1 z 2 册 i ， z m 丌( 鲕) 丛翳) = a 5 ：i a 5 ；a ：，( 丛翁) 一a i “) = a ，a ：2 a 5 2 a 密) ， ( 丛翁( + ) ：纽) = a ，a 妒b 1 a 肄l a 髀l 屹b a 七( n + ) l + i a 髀 一1 ) 1 6 t a 翁) 定理2 1 2 【7 ，删7 ( ，n ) = f 鲤掣1 ，m ，礼2 证明：情形1 ，y ( k 4 件2 ，n ) 一2 ) 亡，其中t 0 ，n 2 鼠2 = ( n - 1 o ( 4 t + 1 ) _ 。b n ( a t + 1 一a ( n - 1 岛d o t + 2 1 ) _ ( b 。( 4 一t + 。一n ，一1 ) 一) a p 一2 ( 丛黢；一a p 一1 ) 倒b ( 。4 一t + 。1 ) ) 一坛( 农；( + ) 2 2 鳓j ( 4 一t + 2 1 ) ( e 1 1 ) 一丌( 亟) 筮搿但矬1 ) q 由引理1 2 1 及引理1 2 2 ，7 ( k 0 + 2 ，n ) st + ，y ( k i 件2 ，n 一1 ) s ( 佗一2 ) t 1 n 北京交通大学博 士 学位论文 情形2 7 ( 托细) 一2 ) ( 一1 ) + 孚1 ，其中t 1 ，n 2 磁= 嬲o ( 4 一t - 1 1 ) _ b ( 4 t - 1 胡b 一( 4 t - 。1 ( 啦! ) 一 ：2 ( 4 t - 一一。a 1 ( n - 1 ) - ，3 。a ( 1 n - 2 ) ( 丛2 j 一a ，一八 。a 4 ( n 一- 1 1 ) 一n 淼三) 醭i 1 ) i 、兰f t ( 4 一t - 3 1 ) 一纭一1 ( 农? ( + ) ；如t - 1 ( + ) i 勤一1 ) 纭一1 、( 圭r 9 4 一t - 3 1 ) ( e 1 1 ) 一7 r ( 红一1 ) 丛( n 一- - ? b ( ，4 t - 一1 ) o 盘- 1 由引理1 2 1 及弓理1 2 2 ，7 ( 心，n ) 2 t 一1 + ，y ( 尬t ，n 一2 ) ( n 一2 ) 一1 ) + 孚 情形3 7 ( 甄蚪1 ，n ) ( n 2 ) 一1 ) + f 警 ，其中t 1 ，几2 跎 l = 篮。( 鲻) _ b 一( 4 t ) 一a ( n 。) b 一( 4 t ) 。、一b ( 4 t ) ， ，n 2 1 一坛一。( 丛嚣j ( + ) ；勤一。( + ) 岛。一。，。4 ( n 。一- 。2 ) 、 。a 。射( n 一1 1 一o 一2 ) 坛一。q 贮：一( 旦黜) 一口2 - 1 ) 一a 2 暑。a 。4 ( n 。- 1 ) 一。箝2 ) 7 r ( 红一2 , ，、a ，( n 。一- 。3 n 5 署一( 兰夥) d 2 t l _ b 一( 4 t ) 。，( n 。- 1 ) - a 4 ( n “- 2 z 1 4 ( n t - 1 ) _ n - 2 ) 7 r ( k 一2 ) 邕2 n 之j 一b 墨( 鱼缌) d 2 一、( 。t 2 。( a t 3 - z ) 。n ( n 一3 ) d ，- 舭( n 一- 以一4 1 d - a 0 4 ( 丌( 至4 。一2 ) 。垒2 薯一a 5 = i 一3 ) n 。( n 。一- - 1 2 一上棼i 一( n 5 留一n 乏：一) 坛一2 d f a 5 署a 一舢d t ( 丌( 1 1 4 。一2 ，、兰a 簟( n 。一- 2 4 ( + ) ；b 一：一a ! n - 一4 。) a 茳： n 眨；卜。s n n ( 4 一t ) 4 、勘了( 4 - 5 ，t ) 。( 3 2 t l 一( n - 3 一( n 缸- 一3 。一) ( ( 7 r ( 厶一2a (