（基础数学专业论文）图的上可嵌入性.pdf

摘要 x 6 6 3 6 0 5 图的最大亏格是刻鲻圈在篥个定向曲萄土是喾有2 一臌整嵌入的一个 特征参数对这一参数的研究是拓扑圈论的主要问题之一而确定一类圈 的上可嵌入往问题本身就是确定图的最大亏格闻麓结合图的个或多 个参数，许多文献都给出了若干上可嵌入图类 7 - 1 4 】，即给出了最大亏格达 t ，一、， 到最好上界i 垦掣l 的图类；或给出一然图类的最大亏格的较好下界“ 【 z j 本文的第一个主要结果，根据图的顶点划分和点的度的条件，研究 图魄上可嵌入性。图g 的c 一划分是指：g 的一个顶点划分慨，以，圪 使得每个g 阮 为多重完全图( 1 f k ) ，证明了如下结果：设g 为连通国， 且对任意v 矿 ) ，蟊；l ( m o d 4 ) 装g 的顶点集存在一个c 一划分 e ，吒，- ，圪 ，使得对每个1 s f s 膏，吲缸4 且吲- o ( m o d 4 ) ，则g 是上 可嵌入的 本文的第二个主要结果，利用图在曲面上的嵌入特征，特别是面的 度懿大小，礤究灏的最大亏接下赛或上霹嵌入性。黄元致教授彝吏g 彦撮教 授在文献 1 8 中证明了n n e d e a 和m s k o v i e r a 在文献 1 7 中所提的一 令猜想；蓑一个( 篱单) 图g 存在某个( 定鹅或不定囊) 戆瑟嵌入使得g 的缚个面的度不超过7 ，则g 是上可嵌入的，即专移) s1 同时，文献e 1 8 说溺条 孛“嚣的度不超过7 ”是毖要淤皇然遗，若一个图g 在莱令錾嚣 嵌入中存在度超过7 的面，个值得回答的问题是：毫( g ) 的上界情况怎样， 或者等价玩，g 的最大亏格下界怎释? 本文的第二个主要结果圈答这个 问题 关键宇：图；最大亏格；上可嵌入；b e t t i 亏数；丽度 a b s t r a c t m a x i m u mg e n u so f g r a p h s i sac h a r a c t e r i s t i cp a r a m e t e r w h i c hd e t e r m i n e sag r a p hw h e t h e rh a sa2 一c e l le m b e d d i n gi na c e r t a i no r i e n t a b l es u r f a c e t h es t u d yo ft h i sp a r a m e t e ri so n eo f t h e m a j o rp r o b l e m s o f t o p o l o g i c a lg r a p ht h e o r y w h i l e ，t h e d e t e r m i n a t i o no fag r a p h su p p e re m b e d d a b l i t yi st od e t e r m i n ea g r a p h sm a x i m u mg e n u s c o m b i n i n go n e o rm o r ep a r a m e t e r so fa g r a p h ，m a n yp a p e r s e i t h e r p r e s e n t s o m e u p p e re m b e d d a b l e g r a p h sp 一1 “，t h a t i st o s a y ，t h e yp r e s e n t t h e g r a p h s ，w h o s e m a x i m u mg e n u sr e a c h e st h eb e s tu p p e rb o u n d l 挈| ，o r ，t h e y l - j g i v e ab e t t e rl o wb o u n do nt h em a x i m u mg e n u so fs o m e g r a p h s d - 3 , t h ef i r s tm a j o rr e s u l to ft h i sp a p e ri st h a t ：c o m b i n i n gv e r t e x p a r t i t i o na n dd e g r e eo fv e r t i c e so fg r a p h s ，t os t u d yt h eu p p e r e m b e d d a b l i t y o fg r a p h s l e tgb eag r a p h ，t h e r ee x i s t sap a r t i t i o n 怯，圪) o fv ( g ) s a t i s f y i n gg 阢 i s am u l t i p l ec o m p l e t eg r a p h f o ra n yie m ，t h e ngh a sac p a r t i t i o n t h i sp a p e rs t a t es u c ha r e s u l t ：l e tgb eac o n n e c t e dg r a p h ，a n d 如o ) 一l ( m o d 4 ) f o ra n y v e v ( g ) ，i f t h ev e r t e x s e to fgh a sa c p a r t i t i o n 以，哆，k ) s a t i s f y i n g 1 一l 4 a n d a l s o 防 o ( m o d 4 ) f o rf d ，k ，t h e n gi s u p p e r - e m b e d d a b l e t h es e c o n dm a j o rr e s u l to ft h i sp a p e ri st h a t ：u s i n gt h ee m b e d d e dc h a r a c t e ro fag r a p hi nas u r f a c e ，e s p e c i a l l yt h es i z eo f f a c e s ，t os t u d yt h el o wb o u n do nt h em a x i m u mg e n u so fag r a p h i n t h ep a p e r 18 ，p r o f e s s o rh u a n gy u a n q i ua n dl i uy a n p e is t a t ea g u e s sg i v e nb yr n e d e a la n dm s k o v i e r ai nt h ep a p e r 17 】t h i s g u e s si s t h a t ：l e tgb eas i m p l eg r a p h ，i ft h e r ee x i s t ss o m e s u r f a c e e m b e d d i n gm a k i n gt h es i z eo fe v e r yf a c eo f gn om o r e t h a n7 ，t h e ngi su p p e r e m b e d d a b l e ，i e 鼍( g ) s1 a tt h es a m et i m e ， t h ep a p e r 1 8 s t a t e st h a tt h ec o n d i t i o no f “t h es i z eo fe v e r y f a c eo f gn om o r et h a n7 ”i sn e c e s s a r y n a t u r a l l y i ft h e r ee x i s t saf a c e s i z em o r et h a n7 ，t h e naw o r t h yq u e s t i o na r i s e s ：w h a ta b o u tt h e u p p e rb o u n do f 专( g ) ? o rt os a y ，w h a ta b o u tt h el o wb o u n do nt h e m a x i m u m g e n u s o fg ? t h es e c o n dm a j o rr e s u l to ft h i sp a p e rw i l l b ea n s w e rt h i sq u e s t i o n k e yw o r d s ：g r a p h ；m a x i m u mg e n u s ；u p p e re m b e d d a b i l i t y ；b e t t i d e f i c i e n c y ；f a c es i z e 前言 拓扑图论怒目前网际上一个非常活跃的图论分支，菇中对阕的拓扑 参数一最大亏格的研究又是一个十分重要的课题之一。一个图黥最大亏 格 2 】，记为y 。，( g ) ，是指那些g 可嵌入的可定向曲面亏格之最大者曲面， 这里指一个连逯聚致2 一维阏流形塞从七十年 弋扔，出 e n o r l d a u s b s t a i v a n t 和a w h i t e 提出圈的最大亏格这一概念以来，很 多銎论学者都投身子这方瑟的研究，但隧麓其研究的深入，它越来越多 地与其它数学分支相曩交叉，相互影响，使之成为目前这方面研究的遵 要发震趋势。嚣蓠，鹭的最大亏格的研究圭漤表瑗在懿下a 个方褥： ( 1 ) 特征结构： 七卡年代泰，n 1 x u o n g 籀动手溺酶支撑薅上豹替鬻，透过弓l 进b e t t i 亏数，给出了图的最大亏格的表示定理国内刘彦佩教授通过应用确向树 臻论方法， 歪鞠了一个鹜是主胃嵌入静当基仅当存在2 一重鹜上的标准 e u l e r 圈，给出了一些闼的嵌入的可约化模型，也构造性地解决了图的不 可定商最大亏格静存在悭闻愆。，十年代襁，l n e b e s k y 掰图的去逮子黼 给出了图的另一个b e t t i 亏数的组会表达式由此，黄元秋教授和刘彦佩 教授研究了图不是上霹嵌入的充分必要条件n 1 x u o n g ，j c h e n 稻 j l g r o s s 等人的工作表明对图的最大亏格的研究往往w 转化为一个特 殊的3 一疆剜囤的情澎，黄元欲教授和刘彦佩教授诞臻一个3 一正剜图的澄 大亏格等于其最大不可分离独立数，在结构上给出3 一正则图上可嵌入的 充分必要条件。另外黄冗秋教授和刘彦佩教授通过写l 进图的扩张运算，研 究了扩张运算与图的b e t t i 亏数之间的内在联系，揭示了图的最大亏格 与图的2 因子的某些联系然而，在探求图的最大亏格的结构特征上，仍 奄广阔的研究前景。 ( 2 ) 上可嵌入性； 一令图是上可嵌入的表明其最大亏格可取到羧好的上界，躐薅判定 什么样的图类是上可嵌入的是很有意义的工作n h x u o n g 证明了局部连 逶受是上露嵌入鲢+ l 。n e b e s k y 涯骧了半届帮连通隧及甄趱罄连遵图均楚 上可嵌入的m s k o v i e r ，h u a n g - l i u f u 和m i n c h e nt s a i 分别考虑直径 为2 纛3 既銎的土可嵌入性。黄元秋教授露文| l 彦摩曩教授研究了一些正列鞠 v 髓上霹嵌入性。j + z a k s 研究了一些积图鲢上可嵌性。基s k o v i e r 歪翻了一 个图嵌在曲面上使得每个面的度的大小不超过4 ，则该图是上可嵌入的 荑元秋教授秘文l 彦骶教授诞爱了l n e b e s k y 翻m s k o v i e r 关予上虿嵌入 性与面的度的大小的猜想 ( 3 ) 最大亏格斡下赛与圈的蔟它参数的联系： n h x u o n g 和l n e b e s k y 考虑了最大亏格与图的连通性的关 系j 。c h e n 霸j l 。g r o s s 绘疆了与涟逶缝有关的简单嚣兹最大亏格的下界 估计式d a r c h d e a c o n 考虑了3 一边连通( 非简单) 图的情形黄元秋教授 搀广上述王作，对任意露一边连邋( j 简单) 黼，给磁了由窝的最小度s 所表达的图的最大亏格的下界表达式，证明了最小度趋向无穷大时，最 大亏格趋近袋好的上赛。最近，黄元欷教授研究了图的最大亏格与圈的余 色数及团的关系，利用h e a d w o o d 薷色定理揭示了图的最大亏格与图的亏 格闻的联系 本文受到文献p 枷】的启发，运用和发展了其中某些方法，根据图的顶 点的某种划分、图的点的魔、图夜曲面止的嵌入特征，特别是面的度的大 小、以及其它条件，褥到了一些毅的上霹嵌入麴类和些图的最大亏格 的较好下界，推广和深化了目前有关这方面的结果 v i 第一章引言 本文考虑的图，若无指明均指有限无向的连通图，但可有重边或环 其他未加说明的术语和记号均同文献 1 一个图g 称为多重完全图，若 它有一个基础图为完全图设g 为图，用y ( g ) 和e ( g ) 分别表示其顶点集和 边集，图g 的c 一划分是指：g 的一个顶点划分以，圪 使得每个g 吵 为 多重完全图( 1s j j k ) 一个图g 的一个2 一因子是指g 的一个2 一正则支撑 子图显然，2 一因子中的每一个连通分支是个圈：若f 为图g 的一个2 一 因子且f 中每个圈的长度均为k ，则称f 为g 的一个k 一边形2 一因子曲 面，这里指一个连通紧致2 一维闭流形曲面分定向与不定向两类如定向 曲面有球面，胎面等，而不可定向曲面有射影平面，克莱茵瓶益面等一 个图g 在曲面s 上的一个开2 一胞腔嵌入是指存在一个1 - 1 连续映射 玎：g s 使得s 、兀( g ) 的每个连通分支与开圆盘拓扑同胚此时，s 玎( g ) 的 每个连通分支称为g 在s 上的一个面( 关于嵌入兀) 一个面，的度，用| 厂l 表示，是指这个面的边界占用的边的条数( 重复的边记数两次) 一个图 的最大亏格【2 】，记为y 。，( g ) ，是指那些g 可嵌入的可定向曲面亏格之最大者 设图g 能2 一胞腔嵌入亏格为g $ ) 的定向曲面s 上，f ( o ) 表示g 的面集，则 有e u l e r 公式：l 矿( g ) 卜e ( g ) l + 1 f ( g ) l _ 2 2 9 ( s ) ，因为一个图g 在任意定向曲 面的2 一胞腔嵌入中至少有一个面，易得到g 的最大亏格满足： y 。( g ) sl 掣l ， l 二 j 其中p ( g ) 一 以g ) h 矿( g ) i + l 称为图g 的圈秩数( 或b e t t i 数) ( 对任意实数 x ，h 表示不超过x 的最大整数) 同时，若y 。( g ) i 墨导l ，则称图g 是上 一一 l 二 j 可嵌入的关于图的最大亏格及其上可嵌入性，有兴趣的读者可参阅文献 2 或 3 图的最大亏格是刻划图在某个定向曲面上是否有2 一胞腔嵌入的一个 特征参数对这一参数的研究是拓扑图论的主要问题之一，而确定一类图 的上可嵌入性问题本身就是确定图的最大亏格问题结合图的一个或多 个参数，许多文献p 刊都给出了若干上可嵌入图类，或给出了一些图类的 最大亏格的较好下界1 1 5 - 2 9 本文联系着图的顶点划分和度的条件，研究图 的上可嵌入性，得到了若干新的上可嵌入图类，推广和深化了目前有关 这方面的的若干结果同时，根据图在曲面上的嵌入特征，特别是面的度 的大小，研究图的最大亏格下界或上可嵌入性，也得到一些新的结果， 推广了文献1 1 8 中的主要结果 第二章基本定理 2 1 最大亏格的两个基本定理 设g 为图，工为g 的一个边子集，g z 表示从g 中去掉x 中的所有 边所得到的图设丁为图g 的一棵生成树，g e 仃) 的一个连通分支k 称为 g 的关于丁的奇边分支，如果k 的边数为奇数：否则k 称为偶边分支记号 毫( g ，丁) 表示g e 仃) 的所有奇边分支数称毫( g ) 一吨n 毫( g ，r ) 为g 的b e t t i 亏 数，这里m i n 取遍g 的所有生成树丁易知，b ( g ) 与专( g ) 同奇同偶文献 2 ( 也可参考文献 3 第1 2 章) 给出了一个图g 是上可嵌入的充分必要 条件及其最大亏格由( g ) 和毫( g ) 所表达的一个公式 定理 【2 】设g 为图， t ) y 。( g ) - 去( 9 ( g ) 一号( g ) ) ， 二 2 ) g 是上可嵌入的当且仅当毒( g ) s 1 由定理a 知图的最大亏格由b e t t i 亏数芎( g ) 确定又，设a 量e ( g ) 为 图g 的一个边子集，记号c ( g 4 ) 表示g a 的所有连通分支数；而记号 b ( g 4 ) 表示具有圈秩数为奇数的g a 的所有连通分支数另外，对g 的任 意子图f ，记号e ( g ，f ) 表示g 中一个端点属于f ，而另一端点不属于f 的 边组成的集合关于芎( g ) ，文献 4 给出了如下组合表达式： 定理b 叫设g 为图则专( g ) - 。m 叫a x 。) ( c ( g 4 ) + 6 ( g 彳) 一h 1 ) 2 2 不是上可嵌入图的一个特征结构 设e ，e 为图g 的k 个不同子图仁= 2 ) ，用记号佤，五，e ) 表示g 中两端点分别在某两个只和e 0 一t , 1 s s ，t5 】 ) 中的所有边对于不是 上可嵌入的图，有这样的一个特征结构，用一个定理表示就是： 定理c j 设g 为图，藩专( g ) 融2 ，即g 不是上可嵌入的，鲻存在g 韵逾子 集a ，满足下列性质： 1 ) 口( g a ) 2 ，鼠对g a 的任意连通分支f ，有p p ) s l ( m o d 2 ) ： 2 ) 对g 4 的任意连通分支f ，f 是g 的点导蹬子圈： 3 ) 对g a 的任意后g2 ) 个不同连通分支一，岛，耳，刘有 阮皈，五，一，疋l9 2 k 一3 ； 特别地，当j i 一2 时，积，如) s 1 ： 4 ) 毫留) - 2 c ( a 、4 ) 一溶l l ： 在定理c 的条件署既结论下，则商 定理d 【6 】 i ) 对g 、鼻的任意连透分支f ，藩g 努k - 连遵的砻麓1 ) ，裂| 嚣g f 】, - k ： 2 ) 洲一三忑i e ( g ，f 】t 这里求和取遍g a 的所有连通矜支f 第三章图的上可嵌入性 3 。1 主要结果( 1 ) 联系饕一个圈g 的顶点划分的点导出子圈，文献 7 给出了一个与这 些点导出予图有关的图的毫( g ) 的一个上界证明了如下结果：设g 为图， 若猖在g 蛇顶点划分毂，砭 ，使褥对每一个g e 】囊墨j s | | ) 连通， 则有：毫( g ) t 妻芎( g 畋卫+ k 1 联系着图的点的度和其他条件，文献 7 - t 4 给 趸 出了一些图的最大亏格及上可嵌入性本节的第一个主要结果是衡权图 豹溪点划分及点的度懿条件，绘密一类上可嵌入霾，露舞下定理。 定理3 。l ，l 设g 为连通豳，且对任意v e v ( g ) ，磊( v ) - 1 ( m o d 4 ) 若g 的顶点 集存在一个c - 划分识，吒，- ，以 。使得对每一个1 j f 蠕k ，吲4 且 别0 ( r o o d 4 ) ，则g 是上霹嵌入的。 证明假设g 不是上可嵌入的，即毫( g ) ；2 则由理定c ，存在a e ( g ) ， 使褥g a 满足定理c 积定理b 设互，五，。，e 为g a 憋历鸯连逶分支，这 里p - c ( g 4 ) 苫2 对任意1 墨- ，s p ，我们将证明：陋( g t 】：4 阁g 为连通图， 所激因裕，e j - 0 。下嚣分烧况讨论： 情况l 若陋( g ，v , l = 1 设e 虹巧= 嵇，且e 属子蜀中的端点记为x 因 为g 存在一个c 一划分戗，吒，以 ，所以易得到e 不属于某个 g 彰j 囊s ig 露) 因魏，曩中的顶点集是c 一划分中若干元素之并，进而宥 i 矿眈】- 0 ( m o d 4 ) ，因此的顶点个数为偶数叉因如g ) 为奇数，故办0 ) 为 偶数所班，f 1 率有奇数个奇度点，这怒一个驻然的矛盾 情况2 若陋 g ，f , i = e 设豆杠，弓产；，e ： ，且岛弱散属予弓孛鲶端点分 别记为弓和x ：( 可越有x ，= x 2 ) ，宅们的另一端点分别势必秘芦：。设y ；移y ：所 属的g a 的分支分别为以和e 由定理c 中的3 ) ，只* e 下面将说明的 顶点集是塞e 一划分孛的若予个元素之势构成+ 否则，则存褒某个 k g c 一划分( 1s f 兰| ) ，点：咕矿i f , ) 以及：匹矿i f , ) 使得叠，= ) k 因为0 g 以 为g 的多重完全子图，那么哭可能k = 能，y ； ，或者= 如，y ： 这与阳a 4 相 矛盾所以，有矿仁j ) - 0 ( r o o d 4 ) 眭l 定理条件，对任意v 矿( g ) ，可设 d av ) 4 n 。+ 1 之形式，其中巩为整数，进而得到 吲珊州叫2 韶+ 争e h 以及 b e ) - p 纯1 一i v 眈】+ ，_ ：j 漆一l i v 眈1 2 0 ( r o o d 2 ) 这与定理c 中1 ) 矛盾 情况3 若 巅z 】= 3 。设露 g ，弓) 一毛岛，岛 ，岛一_ 兄，一屯此h e , - x 3 y 。 且蕞y 眈j 垂一l ，2 ，3 ) ，又没y i ，魏窝y 3 所震g a 的分支分别为只，鬈和霉，显 然巧簪以，只，e ，又由定理c 中3 ) ，e 只* f 同样地，将证明的顶点 集是密e 一翔分中静若予个元素之著季奄成为就，考虑如下子情况； 子情况3 1 墨一- b ，、攮意到g e 为g 的多熏完全予图，此时，只可 镜有以一技，咒，y ：，y ， 因诧，易翔阪惦，五，髯，0 】6 这与定理c 审3 ) 矛蒋。 子情况3 2 在五，x ：和毪中仅有两个相同，不妨设鼍= x ：反设要证明 的结论不成立：翼| j 存在某个v , e c 一划分q f s 壤点z 圣矿眈) 以及= 矿阮) ， 使得e ，。 k ，注意剡g e 】为g 的多重宠全子图，此时，只可能有 k = 备，y 。 ，或者巧= 能，y ： ，或者k = k ，y ， ，或者k = 扛。，y ，y ： 这些均与 列4 矛詹 子情况3 3 在为，x ：和码中，两两互不相同同样，反设要证明的结论 不成立：则存在某个k c 一粼分( 1 s s 砖，患z 蒜矿e j 戳及；y 眈) ，馊 导 矗，z ) _ 因为g 以 为g 的多蓬完全予图，此时，只可能有k = 扛，y ， ，或 者= k ，孔 ，或者鬈= 岛，魏 。这与醐z 毒矛瓣。 由以上情况，得到对任意e ( 1 ，p ) ，有陋( g ，】4 又由定 理d 中2 ) 有1 a 卜音f e ( g ，e 】兰2 p 最后由定理c 中4 ) ，有 芎妇) 一2 p 一溷一1 一1 ，矛盾l 鬻瑟定毽获证 文献8 】涯明了懿下绩鬃：设g 为一个3 一连遴图若g 含骞矮边形2 一 因子，且对任意v 矿 ) ，比0 ) z l ( m o d 4 ) ，则g 是上可嵌入的本节的第二 个结果是：上述最后一个条件“且对任意v v ( g ) ，d o ( v ) ；l ( m o d 4 ) ”用更 松的条件“且对任意v 矿( g ) ，d o ( v ) = l ( m o d 2 ) ”取代，可以得到如下结果： 定理3 1 2 设g 为一个3 - 连通图若g 含有4 - 边形2 一因子，且对任意 v 矿( g ) ，有如( v ) - l ( m o d 2 ) ，则g 是上可嵌入的 证明假设g 不是上可嵌入的，即毫( g ) z 2 则由定理c 知，存在 爿e ( g ) ，使得g a 满足定理c 和定理d 中的每条性质设e ，e ，”，为 g 4 的所有连通分支，这里p - c ( g 4 ) 2 要证明，对任意f ，( 1s ，s p ) ， 有陋( g ，巧】a 4 首先，因为g 是3 一连通的，由定理d 中1 ) 有陋( g ，乃】= 3 ， 下面只要证明i e ( g ，巧l 一3 ，若不然，设e 【g ，) = 色，岛 ，且设e 1 ，e ：，巳 在f 中的3 个端点分别是x , y ，z 由g 的3 一连通性，则有x - y t = 又因g 含 有4 一边形2 一因子h ，则必有如下两种情形之一发生：q ，e ，和e ，有2 条边同属于h 中某个4 一圈，而第3 条边不属予h 中的任何4 一圈：印e ， 和巳均不属于h 中的任何4 一圈；注意到x , y ，= 互不相同因此得到：若情形 发生，则f ，的点数可表示成4 k + z ( k = 1 ) 的形式；若情形发生，则f ，的 点数可表示成4 k ( k 1 ) 的形式不管是情形或发生，知i v ( a 1 为偶数 又易看出图f ，中，有且只有这3 个点x , y , z 的度为偶数，因此f ，中有奇数 个奇度点，显然矛盾! 所以1 e ( g ，f ，】4 ，又由定理d 中2 ) ，有 j a i 一去陋( g ，f 】2 p 最后由定理c 中4 ) ，易得到：专( g ) 一2 p h 一1 s 一1 ， 面 矛盾! 因此定理获证 在证明另一个主要结果之前，先证一个引理 引理3 1 1 设g 为偶图，且对任意v e v ( g ) ，若如( v ) s 2 k ( m o d 4 k ) ，忙苫2 ) ， 存在两条边q ，e ：e e ( g ) ，使得g p ，g ： 不连通，则对g k ，p ：) 的任何连 通分支f ，有p ) - 0 ( r o o d 2 ) 证明因g 是e u l e r 型图，故g 中无割边若g ， 不连通，则有两 个连通分支，记其中一个为f ，另一个为日不失一般性，设巳，而m ， e ：一x 2 y ：，且_ ，屯矿p ) 以及儿，y ：矿) 因g 是一个偶图，那么f 也是一 个偶图v ( e ) 的两个偶划分以，) 将证明如下断言：在和x ：中，必有 一个属于k ，另一个属于k 若不然，不失一般性，假设毛，x 2 k 因f 是 偶图，易有 薹如g ) 一2 。荟如( y ) 因对任意v e v ( u ) ，如( v ) - 2 k ( r o o d 4 k 炽z2 ) 上式变为一2 ；0 ( r o o d 4 k ) ，因为 kz2 ，这是一个矛盾式，因此要证的断言成立 因f 是偶图，由上面断言有陋】2 互比o ) 一1 2 荟叱( y ) 一l 而对任意 v e v ( g ) ，如( v ) 一2 k ( m o d 4 k z 2 ) ，易得吲- l 匕l ( m o d 2 ) ，又因为 l e 护】2 磊如o ) - i , i m 0 8 2 ) 因此，p p ) - 陋( f i 一帜l + i v ，1 ) + 1 - o ( m 。8 2 ) 由f 选择的任意性，从而引理得证 文献 8 证明了如下结果：设g 为图，若对任意v e v ( g ) ，有 d o ( v ) 2 ( m o d 4 ) ，则g 是上可嵌入的增加“g 为偶图”条件，可得到如下 更一般的结果 定理3 1 3 设g 是偶图若对任意v y ( g ) ，有叱( v ) - 2 k ( m o d 4 k 1 ) ，则g 是上可嵌入的 证明当k 1 时，本定理是文献 8 的结果以下考虑_ i 2 的情况假 设g 不是上可嵌入的，即毫( g ) z 2 贝0 由定理c 知，存在a c _ e ( g ) ，使得g a 满足定理c 和定理d 中的性质设e ，e ，一，e 为g 4 的所有连通分支， 这里p c ( g a ) - 2 ，因g 为e u l e r 型图，对每一个，i e ( g ，】为偶数，因g 是连通图，显然陋( g ，】- 0 ，我们断言对每个，p ( g ，f 】- 2 否则，若存 在某个0 式，p ) ，l e ( g ，】一2 ，由引理3 1 1 知p 眈) ；o ( m o d 2 ) 这与定 理c 中1 ) 矛盾因而对每个，l e ( g ，c 】z 4 又由定理d 中2 ) 知有 川- 吉艺p ( g ，乃】z2 p ，最后由定理c 中4 ) ，有号( g ) 2 p h 一1 s 一1 ， 矛盾! 因此定理获证 3 2 主要结果( 2 ) 本部分考虑的图均为简单连通图，根据图在曲面上的嵌入特征，特 别是面的度的大小，研究图的最大亏格下界或上可嵌入性黄元秋教授和 刘彦佩教授在文献 1 5 中讨论了若一个图g 在某个曲面嵌入中每个面的 度不超过5 时的上可嵌入性h u a n gl i n f u 在文献 1 6 中研究了若一个图 g 在某个曲面嵌入中每个面的度不超过7 时，g 的最大亏格问 题r n e d e a l 和m s k o v i e r a 在文献 1 7 证明了：若一个( 简单) 图g 存 在某个( 定向或不定向) 曲面嵌入使得g 的每个面的度不超过4 ，则g 是 上可嵌入的同时，提出了一个猜想：若一个( 简单) 图g 存在某个( 定 向或不定向) 曲面嵌入使得g 的每个面的度不超过7 ，则g 是上可嵌入的 同时，文献 1 8 说明条件“面的度不超过7 ”是必要的自然地，若一个 图g 在某个曲面嵌入中存在度超过7 的面，一个值得回答的问题是：专( g ) 的上界情况怎样，或者等价地，g 的最大亏格下界怎样? 本部分的第一 个定理将回答这个问题 因为一个图的圈秩数是极易计算的量，由定理a 知，确定图的最大 亏格主要是确定图的b e t t i 亏数：同时，给出一个图的b e t t i 亏数的上 界等价于给出了这个图的最大亏格的下界在给出和证明我们的有关结 果之前，先给出有关引理 由b e t t i 亏数可直接得到下面引理3 2 1 和引理3 2 2 ，或参看文献 r 3 1 。 引理3 2 1 设g 为图，e 为g 中一条非环边，则毫( g e ) 墨专( g ) ，这里毫( g e ) 表 示g 的收缩边e 所得到的图 引理3 2 2 设g 为图，若g 是由g 增加一条新边( 但不增加新点) 所得 到的图，则芎( g ) s 毫( g ) + 1 设p 为一条路，g 为一个图，任取g 中两个点工和y ( 不排除x = y ) ， 用路p 连接g 中的点，和y ，记所得到的图为g t ，则称g 一是由g 通过增加 路p 所得到的图 下面引理是引理3 2 2 的一般形式 引理3 2 3 设g 为图，且g 是由g 通过增加一条路p 所得到的图，则 专( g ) s 芎( g ) + 1 证明设增加的路p 连接g 中的点x 和y ，且设g 是由g 通过增加一 条连接g 中的点x 和y 的边所得到的图则由引理3 2 2 知， 毫( g ) s ( g ”) + 1 ，由各自定义，图的最大亏格以及图的圈秩数均是图的一个 拓扑不变量因此由定理a ，图的b e t t i 亏数也是一个拓扑不变量又注意 到g ”拓扑同胚于g 因此，鼍p ”) = 专( g ) ，进而我们有芎( g ) s 专( g ”) 十1 = 专( g ) + 1 引理3 2 4 设g 为图，e 为g 的一条割边，则：鼍( g ) 一芎( g 。) + 专( g ：) 这里g 。和 g ：为g 。的两个连通分支 引理3 2 5 设g ，和g ：为两个图，v f 为g l 中的点( f 一1 , 2 ) ，记号g 1 n ，v ：k 表 示把u 和v ：粘合成一个点所得到的图则有如下结论： 芎( g ， v 。，v ：) g ：) s 专( ( z ) + 鼍( 岛) 证明设g 表示增加一条边连接g 中点v l 和g ：中点v ：所得到的图， 显然e t 是g 的一条割边，且g 、和g ，是g 、e 的两个连通分支由引理3 2 4 知鼍( g ) 一专( g 1 ) + 专( g 2 ) 另外图g 1 “，v ：b 可由图g 收缩而得到由引理 3 2 1 知毫( g l v 1 ，v ：k ) s 毫( g ) 一专( g 1 ) + 毫( g 2 ) ，因此引理得证 个图中长度为k 的圈，我们称之为k 一圈 引理3 2 6 设g 为图且g 每一条边属于一个3 一圈若g 中最多含有两个 割点，则专( g ) s1 ，即g 是上可嵌入的 证明反证法即假设号( g ) 2 则由定理c 知，存在a e ( g ) 使得g a 满足定理c 和定理d 中的性质设e ，e ，一，f ，为g a 的所有连通分支， 这里p 。c ( g a ) z 2 因为图中g 每一条边属于一个3 一圈，g 中无割边，因 此i e ( g ，】七2 ，( 1s ，墨p ) 定理c 中1 ) 以及g 的简单性，对任意1 s js p ， 我们有眇仁，】z3 下面我们将证明：对任意1s ，s p ，若矿亿) 中不含g 的割 点，贝 m l e ( g ，巧】4 若不然，假设i e ( g ，只l = 2 或3 首先，设e 【g ，) = p ：) ， 且q 和e ：属于e 中的端点分别记为x 1 和x ：，它们的另一个端点分别为咒和 y ：注意n y ，y ：不可能属于矿e ) 设h 和y 。所属的g a 的分支分别为只 和只由定理c 中的3 ) ，只一只一，且s ，f ，- ， 1 ，2 一p ) ，因为由假设有 1 e ( g ，f ，) ：2 ，若x 。- 岛，则边一m 不可能在一个3 一圈上，这与引理条件矛盾； 若五= x ：，则一是g 的割点，这与假设矿 e ) 中不含g 的割点矛盾若 旧( g ，f ，l _ 3 ，类似于上述分析可得到同样的矛盾：或者矿，) 含g 的割点， 或者存在边e e ( g ，e ) 不可能在一个3 一圈上这就证得要证的结论另外 由定理d 的2 ) 知h - 告蔓陋( g f 】因为g 中最多含有两个割点，所以最多 蜀。 1 0 存在某两个瓦和e 使得陋( g ，e 】和i e ( g ，】的值为2 或3 因此，我们得到 h z 2 p 一2 最后由定理c 中4 ) ，有鼍( g ) - 2 p h 一1 s 1 ，矛盾! 因此定理获 证 果： 在引理3 2 6 的条件下，若g 的割点个数大于或等于2 ，则有如下结 引理3 2 7 设g 为图且g 每一条边属于一个3 一圈若( g ) z 2 ，则 芎( g ) = 七( g ) 一1 这里i ( g ) 表示g 中割点个数 证明 对七( g ) 用归纳法若i ( g ) = 2 ，这是引理3 2 6 的结果现假定 i ( g ) z3 ，任取g 中一个割点v 设g 和g ”是g 的如下两个子图：g 是g 中所 有含点v 的块组成的并，而g ”是g 中所有不含点v 的块组成的并不难看出 有如下简单性质：g 中最多含有一个割点v ，且g ”中割点个数 ( g ”) s 七( g ) 一1 设v - 仁弦矿( g ) n z ( g ”l x 矿( g ) j ，设i v | 一m ( m 为整数且 m z 1 ) ，那么，矿可以表示成这样的集合：矿一k ，x ：，一，) ，这时候，g ” 就是由分别包含g 中的点- ，x ：，一，的块g j ，g ；，g 二组成的并g 和g ”均满足引理条件，即每一条边属于一个3 一圈因为g t 中最多含有一 个割点v ，由引理3 2 6 知毫( g ) s 1 ，又因为| | ( g ”) s | 】 ( g ) 一1c i ( g ) ，由归纳假 设有毫( g ”) s k ( g ”) 一1 ，g 可看成是由g 中的_ ，x ：，和g ”中的 ，x ：，“，对应粘合成肌个点之后形成的图，g 的具体构成如下：假设g 先与g ：经过点一粘合，形成g j ，然后再将研与旺经过x ：粘合，形成g ：，如 此继续下去，得到g 二即g ，此时g 可表示成g 传，也， ，】g 因此由引理 3 2 5 ，我们有 鼍坎) s 鼍簖) + 芎虹) | 枝) + | 杖) 一1 ： 毫( g ；) s 毫( g ：) + 毫惦) s | 】 ( g ：) + | 】 ( g ；) + 】 虹) 一2 ： 毫( g ) - 芎蛾) s 专( g ：。) + 毫( g ：) s _ | 虹) + | j 帜) + + j 】 ( g ：) 一 一1 ) 则得 毫( g ) s i ( g ) 一( ，栉一1 ) j | ( g ) 一1 由归纳假设，引理得证 下面的引理是直接的 薯| 瑾3 2 8 设x 和y ；| 任意实数，剐有h + m s p + y 1 1 ( 对任意实数x ， p 1 表示大于或等于x 的最小整数) 瘢理3 2 1 设g 嵌入在某个( 定向或不定向) 曲面s 上，则 渤十别字1 这里f 表示g 凌就嵌入下的嚣集 若恕上述定理孛的毒留) 的上赛代入定遴矗1 ) 孛，即霹褥到g 懿最大亏 格的一个相应下界表达式另外，待后我们将说明定理3 ，2 1 中的号( g ) 的 上爨是可以达到兹。 设p 为图g 在某个曲面上的一个嵌入，g 中的一个度大于7 的面称为 大面，记号m 黼示如下弑啦p ) - 莩f 牢1 ，这显，为g 的 大面 定理3 。2 1 的试弱设嚣为g 在s 上的嵌入，我键只要试明 鼍( g ) s 1 + m ( g ，“) 下面对胁( g ，“) 用归纳法若m ( g ，) = o ，易知g 中无大面， 这是文漱 1 s 】酶结鬃。对予菜令鬻g 戳及它的菜令藏蟊嵌入嚣t ，若 卅( g ，兀) tm ( g ，托) ，假设结论对g 成立，现假定m ( g ，耵) ，0 ，且设为g 的最 大嚣。若g 孛有边e 属于盈只满予，赡逸赛，选定一个方商，沿着，鲶边 界行走，则经过边两次；若两次经过e 的方向相同，则称e 关于，是一致 静。否巅，剃称e 关予，是不一致的，因此，我翻凳考虑如下情况 情况1 存在关予，的一致边e 此时，的边界可表示成：矽- a e b e 。 由文献 3 的基本知识可知：在s 上，面厂与速。的并形成一个m 6 b i u s 带， 在区域厂u e 的内部“掇入”一个“交叉帽”，使 ! 晕e 穿过这个交叉幄，则 褥图g 在一个新的曲丽s 上的嵌入托- ，且具有如下性质：原来的面，变成 鼹个新藤f 和8 ，它们的边界可表示成矽。一a e ，a f 一b e ：除夕 ，g 中 原来的面保持不变( 关于这方面图的嵌入邀算，可参阅文献 3 和 1 9 ) 因为l ，l + 矿”| 一l 爿由弓l 理3 。2 。8 ， f 耻1 + 比1 蠕f 业1 + 1 苫f 比1 一l | 3ll3 | | 3 | 3 | 因此不论厂i 或，4 是否为g 在s 上的大面，总有m ( g , n ) 皇俄( g ，兀) 一1 由归纳假 设毫( g ) s 】+ 肌( g ，兀) s 脚( g ，玎) ，即结论成立 情况2 存在关于厂的不一致边e 此时，的边界可表示成： o f ，a e b e ，同样易知，在s 上面厂与边p 的并形成一个圆桶选取s 上的一 条简单闭曲线c 使得c 绕过此圆桶，即c 位于面厂内且与e 相交现考虑 s c 连通与不连通两种情况 子情况2 1s 、c 不连通，且设它的两个分支为s 和s ：此时不难看 出g 为g 的割边，且设g ，和g ，为g e 两个分支不妨设q 位于有界面s ，中 o 1 ，2 ) ，分别用一个2 一胞腔补上最的“洞”，得n g , 在新曲面s ：的一个嵌 入兀，使得g ，在爿上的每个面或者是原来g 的一个面，或者是一个新面z ， 其边界为谚一一( 或为占) 因为+ 阮j - j 州一2 ，由引理3 2 ，8 ， 业1 + 盥1 f 绁1 + 1 ：f 址1 2 i 3 li 3 ll 3 li 3 i 不论z 是否为g f 在上的大面，总有m ( g l ，兀，) + m ( 6 2 ，兀：) s m ( g ，兀) 一2 又因为 埘虹，兀，) 不大于或等于所( g ，玎) ，所以肼( g ，) t 朋( g ，玎) ( j 一1 ，2 。) 由归纳假设 鼍( g 1 ) s 1 + m ( g ，兀，) ( i - 1 ，2 ) 因为p 为g 的割边，由引理3 2 4 ， 毫( g ) 一毫( g 1 ) + 鼍( g ：) s 脚( g 1 ，兀，) + m ( g ：，兀：) + 2 9 肌( g ，兀) ，即结论成立 子情况2 2 若s c =