（运筹学与控制论专业论文）关于一些图类的亏格问题.pdf

学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：1 凰飞 签字日期：pi ，年月i 胡 导师签名： 槠 签字日期：b 卜年石月l l 日 中图分类号：0 1 5 7 5 u d c ：5 1 9 1 学校代码：1 0 0 0 4 密级：公开 北京交通大学 硕士学位论文 关于一些图类的亏格问题 o ng e n u sp r o b l e m so fs o m ek i n d so f 伊a p h s 作者姓名：周玎 导师姓名：郝荣霞 学位类别：理学 肿ii iil i lti i ii i i i l l l y 17 8 0 7 4 1 学号：0 8 1 2 2 1 4 9 职称：教授 学位级别：硕士 学科专业：运筹学与控制论研究方向：图论及其应用 北京交通大学 2 0 1 0 年6 月 致谢 本论文的工作是在我的导师郝荣霞教授的悉心指导下完成的，郝荣霞教授学 识渊博，她严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷 心感谢! 年来郝荣霞老师对我的关心和指导。 在这里还要衷心感谢何卫力教授的指导，何卫力老师对于我的科研工作和论 文都提出了许多的宝贵意见，在此表示衷心的感谢。 同时，也要感谢理学院的全体老师们，在交大的6 年时光里，老师们的指导 和帮助一直伴随着我，督促我学习和成长。 在实验室工作及撰写论文期间，张锐、李文俏等同学对我论文中的研究工作 给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。 中文摘要 摘要：本论文主要研究了图的最大亏格的下界问题以及有向图类在可定向曲 面上嵌入的亏格分布。 曲面s 是拓扑学中的无边缘的2 维紧闭流型。亏格为i 的可定向曲面s ：可以通 过在球面上添加f 个手柄得到。图在曲面s 上的嵌入是指把图画在曲面上，使得g 中的边只在公共的端点相交，且它的每个面都同胚于平面上的一个开圆盘。 连通图g 的最大亏格( g ) 定义为使g 在亏格为k 的可定向曲面上有2 一胞腔 嵌入的最大整数k 。显然一个图g 的最大亏格有上界嘞( g ) i 华l ， ( g ) = l e ( g ) l _ p ( g ) | + 1 称为图g 的b e t t i 数，这里l 口j 表示不超过口的最大整数。 e n o r d h a u s 、b s t e w a r t 和a t w h i t e 在文献【1 中引入了连通图g 的最大亏格r m ( g ) 的概念以来，图的最大亏格和上可嵌入性问题引起了广泛关注。但是还有很多图 类( 例如某些2 边连通图、3 边连通图) 都不是上可嵌入的。因此，最大亏格的下 界的问题引起了人们的广泛关注。 另一方而，两个嵌入：g s 和g ：g 专s 是等价的，当存在一个同构映射 h ：sj s ，使得h o f = g ，否则称为不等价的。图的嵌入分布就是要确定图在曲面 上的不等价嵌入的数目。g r o s s 和f u r s t 2 最早提出了亏格的问题。此后，很多学 者围绕这一问题进行了研究并得到了一些结论，但大部分图类的亏格多项式还是 未知的，且许多关于亏格分布问题的结果是对无向图，对于有向图来说，其亏格 分布方面的结果还非常少。 本论文主要研究了连通四正则图的最大亏格的最优下界以及两类有向图在可 定向曲而上嵌入的亏格分布。 第一章对图的最大亏格、在可定向曲面上的嵌入的相关概念及研究背景进行 简要介绍。 第二章利用非上可嵌入图的结构特征对连通4 正则图进行了拆分，然后通过 反证法得到了连通4 正则简单图以及连通4 正则无环图的最大亏格的下界，并举 例证明了此下界的最优性。 第三章把图的嵌入的联树模型推广到了有向图在可定向曲面上的嵌入上，研 究了n 次三连环有向图和n 次四方环有向图在可定向曲面上的有向嵌入，分别得到 了它们的嵌入亏格分布，并由此得到相应的有向嵌入的最大亏格。同时还由递推 关系得到此两类图的亏格分布相同。 关键词：图；最大亏格；亏格分布；联树；曲面 分类号：0 1 5 7 5 j e 塞銮迢态堂亟堂僮途塞旦墨! 壁! a b s t ra c t a bs t r a c t i nt h i sp a p e r , t h el o w e rb o u n dp r o b l e r mo ft h em a x i m u mg e n u sa n dt h eg e n u s d i s t r i b u t i o n so f d i g r a p h si no r i e n t a b l es u r f a c e sa r es t u d i e d i nt o p o l o g i e a lg r a p ht h e o r y , t h es u r f a c esi sac o m p a c t2 - d i m e n s i o n a lr m n i f o l dw i t h o u tb o u n d a r y t h eo r i e n t a b l e s u r f a c eo f g e n u si ，d e n o t e db y s ，i st h es p h e r ew i t h ih a n d l e sa d d e d ag r a p hgi s s a mt ob ee m b e d d e di nas u r f a c esi fi t i sd r a w ni nss ot h a te d g e si n t e r s e c to n l ya t t h e i rc o m m o ne n dv e r t i c e s ，a n de a c hr e g i o ni sh o m e o m o r p h i ct oa no p e nd i s ki nt h e p l a n e t h em a x i m u mg e n u so fac o n n e c t e dg r a p hg = ( y ，e ) ，d e n o t e db y ( g ) ，i s t h em a x i m u mi n t e g e rkw i t ht h ep r o p e r t yt h a tt h e r ee x i s t sa2 - c e l l u l a re m b e d d i n go f g 。nt k 。r 诘n t 曲es u r f a c ew i t hs e n u s 七z tc a nb es e e nt n a t 嘞( g ) l 笪笋l o b v i o u s l y ( g ) = l e ( g ) i l y ( g ) l + 1 i sc a l l e dt h eb e t t in u m b e ro f t h ec o n n e c t e dg r a p h g ，w h e r el 口i i ss a i dt ob eab i g g e s ti n t e g e rw h i c hi sn or l 的r et h a n 口a f t e rt h e c o n c e p to ft h em a x i m u mg e n u so fac o n n e c t e dg r a p hr m ( g ) w e r eg i v e nb y e n o r d h a u s 、b s t e w a r ta n da t w h i t e 1 t h ep r o b l e m so ft h em a x i m a lg e n u sa n d u p p e re m b e d d i n gp r o p e r t i e sh a v er e c e i v e dc o n s i d e r a b l ea t t e n t i o n h o w e v e r , t h e r ea r e m a n yk i n d so fg r a p h s ( f o re x a m p l e ss o m e2 一e d g ec o n n e c t e dg r a p h sa n d3 - e d g e c o n n e c t e dg r a p h ) t h a ta r en o tu p p e r - e m b e d d a b l e t h e r e f o r e , c o n s i d e r a b l ea t t e n t i o ni s g i v e nt ot h el o w e rb o u n d so nt h er m x i m u mg e n u so f g r a p h s o nt h eo t h e rs i d e ，t w oe m b e d d i n g s f ：g j sa n dg ：g j so fgi n t o a s u r f a c esa r es a i dt ob ee q u i v a l e n ti ft h e r ei sah o m e o m o r p h i s mh ：s s ，s u c ht h a t 乃。厂= g o t h e r w i s e ，t h e ya r es a i dt ob en o te q u i v a l e n t t h eg e n u s d i s t r 击u t i o n sm e a n s t h en u m b e ro f d i f f e r e n te m b e d d i n g s ( o f e q u i v a l e n c ec l a s s e s ) o f g r a p h so ns u r f a c e s t h e g e n u sp r o bl e m sw e r e f i r s ti n t r o d u c e db yg r o s sa n df u r s t 2 ，t h e nm a n yp e o p l e i n v e s t i g a t e dt h e s ep r o b l e m sa n do b t a i n e ds o m er e s u l t s b u tg e n u sp o l y n o m i a l sa r e u n k n o w nf o rm o s tg r a p h s ，a n dm o s tr e s u l t sa b o u tg e n u sd i s t r i b u t i o n sg r a p h s ，l i t t l ei s k n o w na b o u tg e n u sd i s t r i b u t i o n so f d i g r a p h s i nt h i sp a p e r , w es t u d i e dt h el o w e rb o u n d so fm a x i m u mg e n u sf o r4 - r e g u l a rg r a p h s v a n dt h eg e n u sd i s t r i b u t i o n so f t w os p e c i a lg r a p h si no r i e n t a b l es u r f a c e s i nc h a p t e r1 ，w ei n t r o d u c et h ec o n c e p t sa n db a c k g r o u n do f t h em a x i m u mg e n u so f g r a p h sa n dg r a p he m b e d d i n gi no r i e n t a b l es u r f a c eb r i e f l y i nc h a p t e r2 ，t h es t r u c t u r a lc h a r a c t e r i z a t i o nf o rar a n - u p p e re m b e d d a b l eg r a p hi s u s e dt os p l i tc o n n e c t e d4 - r e g u l a rg r a p h , t h e nt h el o w e rb o u n d so ft h er m x i m u m g e n u s f o rc o n n e c t e d4 - - r e g u l a rs i m p l eg r a p h sa n dc o n n e c t e d4 r e g u l a rg r a p h sw i t h o u tl o o p sa l e o b t a i n e db yt h ep r o o f o f c o n t r a d i c t i o n , t h et i g h t n e s so f t h el o w e rb o u n d si sp r o v e d i nc h a p t e r3 ，t h ej o i n tt r e em e t h o di s g e n e r a l i z e dt od i g r a p he m b e d d i n g si n o r i e n t a b l es u r f a c e s t h eg e n u sd i s t r i b u t i o n so no r i e n t a b l es u r f a c e so ft w ot y p e so f d i g r a p h s ： t i m e st h r e e - s e r i a l - d i g r p h sa n df o u r - r i n g s d i g r p h s a r ed e t e r m i n e d t h e i r m a x i m u mg e n u so f d i r e c t e de m b e d d i n ga r eo b t a i n e dr e s p e c t i v e l y t h e nf o u n dt h a tt h i s t w ot y p e so f d i g r a p h sh a v es a n g e n u sd i s t r i b u t i o n si no r i e n t a b l es u r f a c e s k e y w o r d s ：g r a p h ；m a x i m u mg e n u s ；g e n u sd i s t r 而u t i o m ：j o i n tt r e e ；s u r f a c e c l a s s n o ：0 15 7 5 目录 中文摘要i i i a b s t r a c t v 第一章绪论1 第二章两类图的最大亏格的下界6 1 连通四正则简单图最大亏格的下界6 2 连通四正则无环图最大亏格的下界9 第三章两类有向图的可定向嵌入亏格分布13 1 三连环有向图的可定向嵌入亏格分布1 3 2 四方环有向图的可定向嵌入亏格分布1 6 参考文献2 0 附录a 2 3 作者简历错误 杀璜尊g 遵睦3 2 - 独创性声明3 3 学位论文数据集3 4 第一章绪论 连通图g 的最大亏格嘞( g ) 定义为使g 在亏格为k 的可定向曲面上可嵌入的 最大整数k 。由于图g 的任何嵌入至少有一个面，根据e u l e r 公式，所以一个图g 的最大亏格有显然的上界嘞( g ) l 笪笋j ，这里( g ) = i e ( g ) i _ 旷( g ) l + 1 称为图g 的b e t t i ，l 口j 表示不超过口的最大整数。 设丁为图g 的一棵支撑树，设k 是g e ( 丁) 的一个连通分支，如果k 有奇数条 边，则k 称为奇度分支；否则髟称为偶度分支。记号孝( g ，乃表示g e ( 丁) 中奇度 分支的个数。 我们称4 ( g ) = n 驷孝( g ，t ) 为g 的b e t t i 亏数，这里m i n 取遍g 的所 有支撑树丁。 设彳ce ( g ) ，则g a 表示将图g 去掉所有彳中的边得到的子图。而c ( g 彳) 定 义为g 么中所有连通分支的个数，6 ( g 么) 定义为g a 中所有b e t t i 数为奇数的连 通分支的个数。 又设互，最，e 为图g 的k 个点不相交的子图( k 2 ) ，记号尾( 巧，互，疋) 表示g 中两端点分别在某两个巧和eo ，1 f ，j k ) 中的所有边。若日为图g 的 一个子图，记号e ( g ，m 表示仅一个端点在日中的g 的边。 自从1 9 7 1 年e n o r d h a u s 、b s t e w a r t 和a t w h i t e 在文献 1 】中引入了连通图g 的最大亏格乃，( g ) 的概念以来，图的最大亏格和上可嵌入性问题引起了广泛关注。 x u o n g 证明了任何4 边连通图都是上可嵌入的。但是还有很多例子都不是上可嵌 入的，例如某类2 边连通图、3 边连通图。因此，最大亏格的下界的问题引起了人 们的广泛关注。1 9 9 6 年，c h e n 在文献 3 中得到了至少有3 个顶点的2 边连通简单 图的最优下界： 定理1 1 设图g 是一个至少有3 个顶点的2 边连通简单图，则有 郴， 竽 1 9 9 2 年，s k o v i e r a 在文献 4 中得到了含有一个三角形2 一因子的连通3 - 正则图 的最大亏格： 定理1 2 设图g 是一个连通的3 正则图。若g 含有一个三角形2 因子，则 y m ( g ) = - 丢+ ( 其中y = i v ( g ) 1 ) 同时，诸多学者对于图的上可嵌入问题，也得到了许多定理以及性质。 关于图的上可嵌入性，1 9 7 9 年n h x u o n g 在文献 5 】中给出了一个充要条件。 定理1 3 ( x u o n g ) 设g 是一个连通图，则： ( 1 ) g 是上可嵌入的当且仅当基g ) 1 ； ( 2 ) 孝( g ) = ( g ) - 2 y m ( g ) 1 9 8 1 年，l n e b e s k y 在文献中 6 】又给出了上可嵌入性的另一个充要条件。 定理1 4 ( n e b e s k y ) 设g 是一个连通图，则 ( 1 ) g 是上可嵌入的当且仅当对任意彳互e ( g ) 有c ( g 彳) + 6 ( g 么) 一2 h ； ( 2 ) 孝( g ) 2 月m 州a x “) c ( g 彳) + 6 ( g 彳) 一1 4 一1 ) 1 9 9 9 年和2 0 0 0 年，黄元秋和刘彦佩在文献 7 中利用定理1 3 和定理1 4 提供 了一个非上可嵌入图的结构特征。 定理1 5 ( h u a n g ) 设g 是一个连通图，如果g 不是上可嵌入的，即孝( g ) 2 ， 则存在g 的边子集彳满足下列性质： ( 1 ) c ( g a ) = b ( g a ) 2 ，且对g a 的任意连通分支f ，有f l ( b 擗 ； ( 2 ) 对g 么的任意连通分支f ，f 是g 的一个点导出子图； ( 3 ) 对g 彳的任意砸2 ) 个连通分支鼻，易，巧，有i e g 假，最，e ) i _ _ _ 2 l - 3 ， 特别地，当，= 2 时，i e g 假，最) i 1 ； ( 4 ) 孝( g ) = 2 c ( g 彳) 一i 么l 一1 许多学者得出了诸多有关3 正则图的定理，自然而然，4 正则图的最大亏格问 题进入了人们的视野。在本文第二章中，将对连通4 正则简单图以及无环连通4 。 正则图的最大亏格的最优下界给出研究证明。 曲面s 就是拓扑学中的无边缘的2 维紧闭流形，可分为可定向曲面和不可定 2 向曲面，本文所涉及曲面均为可定向曲面。可定向曲面s 。( ，l o ) 是由球面添上玎个 手柄得到。它可以视为平面上的一个偶数条边的正多边形。每边分配一个方向， 且成双成对，将同一对边依同方向合而为一所得到的。一个曲面对应一个由若干 字母构成的循环。亏格为i 的可定向曲面可以通过在球面上添加i 个手柄而得到。 详见 8 ，9 ，1 0 对曲面s ，我们在s 上定义三种运算： 运算1 s = ( a b ) s = ( a e ) ( e 一固，其中a g 或b o ； 运算2 s = ( a e i e 2 b e 2 一q 一) 铮s = ( a e b e 一) ，其中e = e l e 2 ，e 一= ( e j e 2 ) 一= e 2 一e l 一； 运算3 s = ( a e e b ) s = ( a b ) ，其中a b 设s ，s 为两个曲面，如果s 可以由s 通过一系列运算1 - 3 得到，则称s 与s 是等价的。记做：s - s 每一个可定向曲面都和下面的一个且只有一个曲面的标准形式等价： l ( a o 一) ， i 三0 印1 ( 血吼百) ，f l lk = l q 是亏格为f 的可定向曲面 图g 在曲面s 上的嵌入是指g 的一个画法，使得g 中不同的点对应s 中不同 的点，g 中的边对应s 中的曲线，这些曲线只在公共节点处相交，且每个面都同 胚于平面上的开圆盘。图g 的亏格g 是g 可以嵌入的曲面亏格中最小的值。 如果存在一个同构映射h ：s s ，使得乃o ，r = 2 ，则称图g 的两个嵌入 厂：g 一鲫g ：g 专s 是等价的否则，称两个嵌入厂：g 专s 和g ：g 专s 是不等价 的。 对一个给定的图g ，一个重要的问题就是要确定其在给定的曲面上有多少个 不等价的嵌入 1 1 。如果用蜀( g ) 表示g 在亏格为f ，( f o ) 的可定向曲面上不等 价嵌入数目，于是g 的嵌入亏格分布序列为g 。( g ) ，蜀( 6 3 ，g ：( g ) ， 图g 的亏格多项式指的是：厶( x ) = g ，( g ) x 设有向图d = ( y ，么) ，其中v 是d 的顶点集，4 是d 的弧集。若口= ( 甜，力为有 向图d 的弧，则称a 从u 连接到1 ，称u 是a 的尾，v 是a 的头。d 中顶点1 ，的入度 靠( v ) 是指以1 ，为头的弧的数目；类似的，d 中顶点v 的出度d ：( v ) 是以1 ，为尾的弧 的数目。出度蝣( ，) 和入度靠( y ) 的和称为1 ，的度，记为如( v ) 从而， d d ( ，) = 面( 谚+ g ( 如果有向图d 中每一个点1 ，的出度和入度相等，则称d 是欧拉的。有向图d 在 可定向曲面s 中的有向嵌入是指d 作为图在s 上的嵌入，使得图对于这个曲面的 补的每一个联通分支都同胚于一个有向开圆盘，即每个面边界的弧的方向是一致 的。 有向图d 的亏格多项式指的是：f o ( x ) = g ，) x ，其中( d ) 表示d 在亏格 为，( f o ) 的可定向曲面上不等价嵌入的数冒。有向图d 的亏格g 是指使得d 能 够有向嵌入到曲面墨中亏格最小的整数g 。 研究图的亏格分布有着非常重要的意义。研究图的嵌入亏格分布不仅对于图 的嵌入理论的发展具有一定的理论价值，而且还有很广泛的应用前景。图的嵌入 亏格分布在各个学科，比如电信，交通等领域都有很好的应用。 许多学者和专家教授为此作了大量的工作。1 9 8 7 年g r o s s 和f u r s t 1 2 最早 提出这方面的问题；1 9 8 7 年m c g e o c h 1 3 得到了圆梯和麦比乌斯梯( c i r c u l a r l a d d e r s ，m s b i u sl a d d e r s ) 在可定向曲面上嵌入的最大亏格；1 9 8 9 年f u r s t ，g r o s s 和s t a t m a n 1 4 讨论了闭尾梯和鹅卵石路( 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 e p a t h s ) 在可定向曲面上的嵌入亏格分布；1 9 8 9 年g r o s s ，r o b b i n s 和t u c k e r 1 5 得到了环束( b o u q u e t so fc i r c l e s ) 在可定向曲面上的嵌入亏格分布；1 9 9 3 年 k w a k 和l e e 1 6 给出了双极图( d i p o l e s ) 在可定向曲面上的嵌入亏格分布；2 0 0 0 年t e a r 1 7 得到了r i n g e l 梯( r i n g e ll a d d e r s ) 在可定向曲面上的嵌入亏格分布； l i 1 8 ，1 9 分别讨论了圆梯和麦比乌斯梯( 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 ) 在可定向曲面上的嵌入亏格分布；2 0 0 6 年万良霞在其博士论文 2 0 中着重研究了 几类三正则图的亏格分布；还有不少学者都研究过该问题，如： 2 1 ，2 2 ，2 3 除了图在可定向曲面上嵌入的亏格分布外，有些学者还致力于研究图的总亏 格分布。图的总亏格分布是指在可定向曲面和不可定向曲面上嵌入的分布情况。 通常也用多项式来表示图的总亏格分布： 厶( 石) = 蜀( g ) t + 磊( g ) x 卅 其中g ，( g ) ，磊( g ) 分别表示图g 茬亏格为f 的i 可定向、不可定向曲面上的嵌入。 1 9 9 4 年c h e n ，g r o s s 和r i e p e r 2 4 首先得到了项链图，闭尾梯和鹅卵石路 的总亏格的分布；2 0 0 2 年k w a k 和s h i m 2 5 得到环束的总亏格分布；2 0 0 4 年李 立峰和刘彦佩 2 6 得到了一类三正则图的总亏格分布；2 0 0 6 年c h e n 和l i u 2 7 给出了c a c t i 和( r ，s ) 型n e c k l a c e s 图的总亏格分布；2 0 0 7 年杨艳和刘彦佩 2 8 给出了两类四正则图的总亏格分布等等。 由于图的嵌入亏格问题已被证明是n p 一难的 2 9 ，所以目前关于图的亏格分布 的结果不多，具体到有向图的结果就很少。b o n n i n g t o ne t a 1 在文献 3 0 中给出 了有向图在可定向曲面上嵌入的基本概念和性质，并给出了某些特殊图类的最大 亏格。在文献 3 1 中对有向图在平面上嵌入的禁用结构进行了讨论。郝荣霞 3 2 ，3 3 得到了c r o s s l a d d e r s 有向图和a n t i l a d d e r s 有向图在可定向曲面上嵌入的亏格 4 多项式。 1 9 9 5 年刘彦佩 8 详细介绍了图的嵌入理论，提出了解决亏格分布的联树理论。 设g 是一个图，甜是g 的一个顶点，“处的一个旋吒是与u 关联的边的一个循 环置换。设d r 是g 的一个旋，则d r = ho v 。设丁为g 的一棵支撑树，把g 中的 v e 矿( g ) 非树边e 劈成两个半边，分别标上矿，矿，得到树丁。为方便，我们把e + 简记为e 。 对g 的任意给定的一个旋盯，可以确定树r 的一个旋，从而得到g 的一棵联 树，记乃为与盯对应的联树。由乙的所有半边按顺时针或逆时针产生的有向循环 序列可以认为是乃的嵌入曲面。下面的结论已经证明是成立的。 定理1 6 ( 8 】) 对g 的两个不同旋系q ，呸，它们对应的嵌入吒，g 电以及联树 和是不同的。 定理1 7 ( 8 】) 设丁和丁是图g 的两不同的支撑树，表示g 的旋系的集合。则存 在从( ，乃到( ，t ) 的一一映射。其中( ，d = 乃i 盯) ，( ，t ) = t ，i 盯) 。 定理1 8 ( 【8 ，1 0 ) 设a ，b , c ，d 和e 是线性序，且( 仰是一个曲面，则对于 口，b ( a b c d e ) ，有( a a b b c a d b - e ) ( a d c b e a b a - b - ) 。 定理1 9 ( 8 】) 设s 和s 是曲面，如果s ( gx y y c - y ) ，且五弘i ，夕正3 ，则 o ( s ) = o6 ) 卜。 利用联树方法，一些图类的亏格分布得到解决，本文第三章也是利用联树法 研究两类有向图在可定向曲面上的亏格分布。 第二章两类图的最大亏格的下界 自从1 9 7 1 年e n o r d h a u s 、b s t e w a r t 和a t w h i t e 在文献【1 】中引入了连通图g 的最大亏格r m ( g ) 的概念以来，图的最大亏格和上可嵌入性问题引起了广泛关注。 但是还有很多图类( 例如某些2 边连通图、3 一边连通图) 都不是上可嵌入的。因此， 最大亏格的下界的问题引起了人们的广泛关注。在本章中，将对连通4 一正则简单 图以及无环连通4 正则图的最大亏格的最优下界给出研究证明。 1 连通四正则简单图最大亏格的下界 定理2 1 1 设图g 是一个连通4 正则简单图，则它的最大亏格 们，乩半j 证明：设图g 是一。个连通4 正则简单图，v = l v ( c ) l 是图g 的顶点数，则有 ( g ) 爿e ( g ) i iy ( g ) l + 1 ：i 4 v - - v + 1 ：1 ，+ 1 ，考虑以下两种情况： 情况l ，当g 为上可嵌入时则有( g ) = l 里笋j ，又因为g 为连通4 一正则简 单图，则有淄，通过运算l - 竽h 鼍叫 o ( v 冽，因此靴5 时有 1 竽j 钆半j ，显然可得椰，l 2 f l ( g ) + 3 j 。 情况2 ，当g 为非上可嵌入时，由定理1 5 可得存在a e ( g ) 满足定理1 5 的 性质( 1 ) 一( 4 ) ，因此可得c ( g 爿) = 6 ( g 彳) 2 和善( g ) = 2 c ( g 爿) 一h 一1 。 令a 表示g a 的有i 个项点，b e t t i 数为的连通分支数。因为g 为简单图， c ( g 彳) = b ( g a ) 2 ，且g a 的任一连通分支f 有：f l ( f ) = l ( m o d 2 ) ，所以可知， 存在a 0 当且仅当i 3 和j = l ( m o d 2 ) 。 又由于g 为连通4 正则简单图显然可得： a ：- 口：= a ? = a i = a ；= a ；= a i = a ；= a i = = 0 于是，我们有 6 c ( g 彳) = a ：+ 口：+ 口；+ + z + + + + + 蠢+ 西+ v = 3 趟+ 4 a ：+ 5 珙+ + 4 玄+ 5 4 + 6 a 6 3 + + 5 4 - - i -。5 + 7 a 7 5 + 由定理1 5 的性质( 4 ) 可得，存在h = 互1 乙矧ki e ( f , ，g ) i ，因此 ( 1 ) ( 2 ) i 彳l5 三 6 砖+ 8 口：+ 1 0 口s 1 + + 4 + 6 + 8 口。3 + + 2 西+ 4 口a 5 + 6 西+ ( 3 ) = 3 a ：+ 4 a ：+ 5 a ：+ + 2 a ：+ 3 a ；+ 4 a ：+ + a ；+ 2 a ；+ 3 a ；+ 假设 v + 1 - 2 ( 半+ 尹3 = 詈_ 1 再由定理1 5 的性质( 4 ) 我们有善( g ) = 2 c ( g 么) 一i a i 一1 詈一1 ， n l l t ： 旨2 c ( g 彳) 一i a i 一詈 o 但是由上式( 1 ) ( 3 ) u - - j 徒j l 2 c ( g 、彳) 一i 爿i 一詈= 一詈口；一警口：一4 口：一一j 4a 。3 2 蠢一萼霞一一。霹一喜一詈苗一。 因此矛盾，可得( g ) l 2 p ( g ) + 3 j 5 。 由惜汾1 、2 帘弹21 1 得济 说明下面我们将给出例子证明连通4 正则简单图的最大亏格可达到定理中所求 下界，即= l 2 7 ( g ) + 3 j 5 ，由此得证定理2 1 1 中所求下界为最优下界。 令蠢如下图2 1 所示，由蜀增加一个项点且此顶点与蜀的其中3 个顶点相连 得到。 7 图2 1 令g l g 为k ( k 3 ) 个蠢的拷贝，将g f 与q + lo = l ，2 ，七一1 ) ；g l g k 与g 1 分别 用一条边相连，如下图2 2 所示，得到的图为g 。 图2 2 连通4 - 正则简单图 显然可知图g 为一个连通4 - 正则简单图，记a 为将g l q 相连的边集，即 a = e ( g ) 一u e ( g ) ，则g 彳有后个连通分支，每个连通分支均为蠢，有5 个顶点 且b e t t i 数为5 。由此可得图g 有5 k 个顶点，进一步检验可得( g ) = y + 1 ， 椰，乩半卜儿 由上例可知，我们可找到连通4 正则简单图的最大亏格为f 2 f l ( g ) + 3l 的图类， 5 l 因此可知定理2 1 1 中的下界为最优下界。 2 连通四正则无环图最大亏格的下界 注：以f 定理2 2 1 涉及的图为连通4 正则无环图。 定理2 2 1 设图g 是一个连通4 正则图，且图g 无环，则它的最大亏格 胛，l 钭 证明：与定理2 1 1 思路类似，设图g 是一个连通4 一正则图，v jv ( g ) i 是图g 的顶点数，则有( g ) 爿e ( g ) l _ iv ( g ) i + 1 ：4 v - v + 1 ： ，+ l ，考虑以下两种情况： 情况1 ，当g 为上可嵌入时则有= 【曼笋j ，又因为g 为连通4 一正则图，且 鄢删前 2 阄此l 盟2j l 熊3i 馒然可得胛) l 塑3i olill 。”、7 ll 情况2 ，当g 为非上可嵌入时，由定理1 5 可得存在么e ( g ) 满足定理2 1 3 的性质( 1 ) - ( 4 ) ，因此可得c ( g 彳) = 6 ( g 么) 2 和善( g ) = 2 c ( g 彳) 一h 一1 。 令口? 表示g a 的有i 个顶点，b e t t i 数为j 的连通分支数。因为g 为无环图， c ( g a ) = 6 ( g 么) 2 ，且g a 的任一连通分支f 有：f l ( f ) = l ( m o d 2 ) ，所以可知， 存在a 0 当且仅当i 2 和j = l ( m o d 2 ) 。 又由于g 为连通4 正则无环图，显然可得： a 卜a ? = a ；= a ；= a i = a ；= a ；= = 0 于是，我们有 c ( g 彳) = 之+ 砖+ 反+ + + 窖+ 芸+ 蠢+ 露+ + + + 巧+ ( 1 ) v = 2 a ；+ 3 4 + 4 d + 5 4 + + 3 司+ 4 西+ 5 露- - i - -。3 + + 5 a s 5 + 6 a 6 s + 7 a 7 5 + ( 2 ) 9 由定理1 5 的性质( 4 ) 可得，存在i 么i = j i 乙d kl e ( z ，g ) i ，因此 i 彳1 ：三1 4 口：i + 6 口：+ 8 口：+ 1 0 口，i + + 2 司+ 4 司+ 6 窍+ 8 0 6 3 + + 2 口，5 + 4 。5 + 6 口，5 + = 2 a ：+ 3 每+ 4 以+ 5 a ；+ + 露+ 2 a ；+ 3 蠢+ 4 a ：+ + + 2 + 3 西+ ( 3 ) 假设椰) 1 ，+ 1 _ 2 、v 2 + 1 斗i 2 ) ：詈一1 ，33 再由定理1 5 的性质( 4 ) 我们有手( g ) = 2 c ( g 彳) 一i a i 一1 罢一1 ， 因此有2 c ( g 彳) 一l 彳l 一罢 0 但是由上式( 1 ) ( 3 ) n n 2 c ( g 、妒l 彳i 一詈= 知等口号- - - 0 霹一詈西一詈霉一4 扣一；一2 1 3 0 a 5 ，o 因此矛盾，可得( g ) f l ( g ) + 2 j 。 由情泖1 、2 帝瑚221 得讦。 说明下面我们将给出例子证明连通4 正则无环图的最大亏格可达到定理中所求下 界，即悄) l 华j ，由此得证定理2 2 1 中所求下界为最优下界。 令巳3 如下图2 3 所示，由玛增加邻接同一个顶点的两条重边得到。 1 0 图2 3 令g 1 g 为k ( k 3 ) 个蠢的拷贝，将g f 与g + ，o = 1 ，2 ，k 一1 ) 中的两个三度点 相连，q 与g 1 中两个三度点相连如下图2 4 所示，得到的图为g 。 图2 4 连通4 正则无环图 显然可知图g 为一个连通4 一正则无环图，记么为g 1 g ： 2 f q 的边集，即 彳= e ( g ) - u e ( g , ) ，则g 彳有j j 个连通分支，每个连通分支均为蠢。南于g 有3 个顶点且b e t t i 数为3 ，由此可得图g 有3 后个顶点，进一步检验可得( g ) = v + l ， ( g ) = l f l ( g ) + 2 3 = 川。 由上例可知，我们可找到连通4 正则无环图的最大亏格为i 旦盟l 的图类， i 3 l 因此可知定理2 2 1 中的下界也为最优下界。 1 2 第三章两类有向图的可定向嵌入亏格分布 自从g r o s s 和f u r s t 2 提出图的可定向嵌入问题以来，很多学者围绕这一问题 进行了研究并得到了一些结论，但大部分图类的亏格多项式还是未知的，且大部 分关于亏格分布问题的结果是关于无向图的亏格分布的，对于有向图来说，其亏 格分布这方面的结果还非常少。本章把图的嵌入的联树模型推广到了有向图在可 定向曲面上的嵌入上来，研究了次三连环有向图和次四方环有向图在可定向 曲面上的有向嵌入，分别得到了它们的嵌入亏格分布，并由此得到相应的有向嵌 入的最大亏格。同时还由递推关系得到此两类图的亏格分布相同。 1 三连环有向图的可定向嵌入亏格分布 设有向图d o 如图3 1 ( a ) 所示。用如下方法从d o 得到三连环图见：在d o 的两条 弧上分别增加2 ，z 个顶点m ，v3 v 廖拍憋，? ，u 。，并增加2 ，z 个新顶点 屹，1 ，4 v 虚￥，3 - , 甜，。和6 n 条弧： a t = v 2 ，1 2 l - i 岛= u 2 _ l v 2 ，c ，= v e ，- l v e ，讲= “2 - l u 2 ，e t = v e ，屹，- l ，石= ，屹，_ l 其中( 1 ，胛) 。 d l ，0 2 如图3 1 c o ) ，( c ) 所示。称见为咒次三连环有向图。 u 2 u 4 u 2 ( a )( b )( c ) 图3 1 首先考虑d o ，取为非树边，t o 即为d o 对应的一棵联树，a o a o ：是z 其嵌入曲面。 所以，g o ( d o ) = 1 ，( d o ) = o ，f 1 ，故厶( x ) = 1 。 对d l ，设支撑树为r ，取a o ，a ，2 5 l ，c l ，而为其非树边，由于有向嵌入每 个顶点的入弧与出弧交错出现，故由丁可以得到日的下列1 6 中不同的联树： a o q c ( a i b l b f a ( d l d a oa oc l 岛口_ c i - 6 l a l 盔ia oc l 乙la l6 l 盔听耳 a o c l b l a l c ? d l a ( b ( d ( a o a o q b l a l c ( a o d ? b ( a d l a o a o d i d l a ( b ( c ( a l b l q a o b ? a - ( d , d