（运筹学与控制论专业论文）关于图的最大亏格的研究.pdf

北京交通大学博士学位论文中文摘要 中文摘要 与其他图论分支一样。图在曲面上的嵌入理论与著名的四色问题有着千丝万 缕的联系，这四色问题最早是由c a l y e y 在1 8 7 8 年提出的在1 8 9 0 年h e a w o o d 提出著名的地图着色定理后，h i l b e r t 等人又将它归结为引线问题，即在曲面品 表示品的亏格) 上给定n ( n 3 ) 个不同点，能否用简单曲线( 引线) 两两连接 这n 个点使得这些连线在曲面上互不相交? 用图论术语而言，引线问题与确定完 全图的亏格7 ( j 0 ) 等价自然确定一般图的亏格又是上述问题的推广尽管 h e a w o o d 地图着色问题早在1 9 8 6 年得以完全解决，然而它给图论开辟了一个至 今不衰的新课题一图在曲面上的嵌入 这里，曲面通常是指一个紧的，筘维流形( 可定向或不可定向) ，其亏格表示 为g ( s ) ，连通图g 在曲面s 上的一个嵌入是指存在个拓扑同胚映射f ：g s 使得s f ( g ) 的每个连通分支与圆盘拓扑等价，人们通常称之为2 一胞腔嵌入 图g 的亏格7 ( g ) 是指最小的整数g ( s ) 使得g 在曲面s 上有2 一胞腔嵌入而 图g 的最大亏格7 m ( g ) 是指最大的整数g ( s ) 使得g 在曲面s 上有2 - 胞腔嵌 入1 9 6 6 年d u k e 证明了图的亏格插值定理，即如果图g 在两个可定向( 或不可 定向) 曲面s 矗和& ( m n ) 上都有2 一胞腔嵌入，则g 在任意可定向( 或不可定 向) 曲面鼠sk 竹r 上也有2 - 胞腔嵌入因此在考虑g 的所有可嵌入的曲 面，只需确定它的亏格( 也称最小亏格) ，y ( g ) 和最大亏格7 ( g ) 由著名的欧拉公式，我们知道最大亏格有一个很显然的上界7 m ( g ) 【2 磐j ， 这里，z ( c ) = l e ( g ) i l y ( g ) i + 1 称为图g 的b e t t i 数，也称为圈秩一个图 被称为是上可嵌入的是指7 m ( g ) = 1 2 掣j 基于图在不可定向曲面下，早在7 0 年 代末，r i n g e l ，刘彦佩等独立地证明所有图都是上可嵌入的因此对图的最大亏格 的研究一般都指在可定向曲面情形下，自从7 0 年代初，由n o r d h a u s ，s t e w a r t 和 w h i t e 等人引进图的最大亏格以来，至今这一领域仍然足拓扑图论中的一个十分 活跃的方面 本文主要是研究图的最大亏格，共分五章 第一章概述图在曲面上的嵌入问题中关于最大亏格研究的历史和现状，然后 对本文的工作徽了简要介绍 第二章我们得出了一些上可嵌入的图类，它们具有一些特殊的邻域条件，或 特殊的边，或特殊的不相邻点的度和，或者根据条件构造出来的新图等等其中， i 北京交通大学博士学位论文中文摘要 推广了黄元秋等人的一些结果 第三章我f f 主要利用图的一些参数条件，例如直径边连通度、围长、点独 立数等等，给出了最大亏格的紧下界其中，推广了a r c h d e a c o n 等人。以及黄元 秋等人的一些结果 第四章给出了两类图r 和如的完全亏格多项式由于现有知道完全亏格 多项式的图类很少，基于这个目的，本章可视为在这方面的补充 第五章指出了应该继续考虑的问题 关键词t 图；嵌入；曲面；最大亏格；b c t t i 亏数；上可嵌入性；亏格分布 分类号：0 1 5 7 5 北京交通大学博士学位论文英文摘要 a b s t r a c t l i k em a n yo t h e rb r a n c h e so fg r a p ht h e o r y , t h es u b j e c to fg r a p he m b e d d i n g h a si t so r i g i nf r o mt h ek n o w n4 - c o l o rp r o b l e mw h i c hw a f tt op u b f i cb yc a y l e yi n 1 8 7 8 i t n a t u r a lt h a tg o m e o i l es h o u l dp o s et h ea n a l o g o u sq u e s t i o nf o rg e n e r a l s u r f a c e s a si n d e e dh e a w o o dd i di n1 8 9 0 f o ra na c c o u n to ft h ee x c i t i n gh i s t o r y o fc o l o r i n gp r o b l e m ，c u l m i n a t i n gi ni t sf i n a ls o l u t i o nb yr i n g e l ，y o u n g se t ，a 1 i n 1 9 6 8 i tw 硝e v e n t u a u yt r a n s f o r m e di n t ot h et h r e a dp r o b l e m i ti st os a y , g i v e nt w o i n t e g e r s 船a n d pw i t h 珏3a n d p20 ，嚣留cc h o o s e 讫p o i n t so nt h e3 u , r f a c e 。 a n dc o n n e c te a c hp a i ro jt h e s ep o i n t s _ b bs i m p l ec u r y e ( nt h r e a o nt h es u r f a c e w i t h o u ti n t e r s e c t i o npt h i sp r o b l e mc a nb ef o r m u l a t e da st h a to f d e t e r m i n g7 ( 玩) - t h em i n i m u mo fa ht h eg e n e r ao fs u r f a c e so nw h i c ht h ec o m p l e t eg r a p h 以c a n b ee m b e d d e d t h i s o fc o n r s o ，g e n e r a l i z i e st ot h ep r o b l e mo fe v a l u a t i n g7 ( g ) - t h e g e n u so ft h eg r a p hg m u c hw o r ko ng r a p he m b e d d i n gh a sb e e ni n s p i r e db yt h e t h r e a dp r o b l e mt h es o l u t i o no fw h i c hw a sn o tc o m p l e t e du n t i l1 9 6 8 t h ew o r ds u r f a c ew i l lm e n nac o m p a c to r i e n t a b l e2 - m a n i f o l d s u c hnm a n i f o l d m a yb et h o u g h to fa sas p h e r eo ras p h e r ew i t hh a n d l e s t h en u m b e ro fh a n d l e so n as u r f a c esi sc a l l e dt h eg e n u so ft h es u r f a c ea n di sd e n o t e db yg ( s 、b ye m b e d d i n g ag r a p ho nt h es i l l r f a c es ot h a te d g e s m a ym e e to n l ya tm u t u a l l yi n c i d e n tv e r t i c e s a 2 - e s t le m b e d d i n g , o ri no t h e rw o r d s c e l l u l a re m b e d d i n g , o fag r a p hgi so n ei nw h i c h e a c ho ft h ec o m p o n e n t so ft h ec o m p l e m e n to fgi nt h es u r f a c ei sh o m c o m o r p h i ct o a l lo p e nd i s k t h ec o m p o n e n t so ft h ec o m p l e m e n to fg a r ec a l l e d 如c e 8o rr e g i o n s t h eg e n u s7 ( a ) o fac o n n e c t e dg r a p hgi st h es m a l l e s to ft h en u m b e r s9 ( s ) ， w h e r esi sas u r f a c ei nw h i c hgh a sa2 - e e l le m b e d d i n g t h cn l o i m l n ng e n u s7 m ( g 、o fac o a n e e t e dg r a p hgi sd e f i n e dt ob et h em a x - i m u mi n t e g e r 七s u c ht h a tt h e r ee x i s t sac e l l u a re m b e d d i n go fgi n t ot h eo r i e n t a b l e s u r f a c eo fg e n u sk i th a sb e e ns h o w nb yd u k et h a ti r ac o n n e c t e dg r a p hgh a se m b e d d i n g so nt h e c o m p a c to r i e n t a b l e ( n o n - o r i e n t a b l e ) 2 - m a n i f o l d ，o ro l lt h es u r f a c e so fg e n e r ama n d n ( m n ) ，t h e nf o ra l l 七，m kst l ，gh a sa l le m b e d d i n go n 雠o r i e n t a b l e ( n o n - o r i e n t a b l e ) s u r f a c eo f g e n u sk h e n c e ，i f t h em i n i m u ma n dt h em a x i m u mo r i e n t a b l e g e n u s ( n o n - o r i e n t a b l e ) o fgr e s p e c t i v e l ya r ek n o w n ，t h e na nt h ep o s s i b l eo r i e n t a b l e ( n o n - o r i e n t a b l e ) s u r f a c e so nw h i c ht h eg r a p hg c a nb cc m b e d d e da r ci m m e d i a t e l y d e t e r m i n e d 。 f o rt h ee u l e rp o l y h e d r a lf o r m u l aw es e et h a tt h em a x i m u mg e n u so fag r a p h h a st h eo b v i o u su p p e rb o u n d7 m ( g ) 【竽j ，w h e r ep ( g ) = i e ( g ) i i v ( g ) j + 1 i sc a l l e dt h eb e t t i 雠抛ro fac o n n e c t e dg r a p hg a g r a p hg i ss a i dt ob eu p p e re m b e d d a b l ei f ，y 肼( g ) = 【鼍笋j ，e x a c t l y t h i sd i s s e r t a t i o ni sd e v o t e dt ot h em a 蟊m u l ng e n u so fg r a p 1 8 i tc o n s i s t so f f i v ec h a p t e r s i nc h a p t e r1 ，w eg i v ear e v i e wo fm a x i m u mg e n u so fg r a p h s ，a n dp o i n to u t t h eo r g a n i z a t i o no ft h i sd e s s e r t a t i o n i nc h a p t e r2 ，w ep r o v i d ean u m b e ro fc l a s s e so fu p p e rc m b e d d a b l eg r a p h s w h i c hh a v es p e c i f i cn e i g h b o u rc o n d i t i o n ，s p e c i f i ce d g e s ，a n ds p e c i f i cd e g r e e - s u mo f t w ov e r t i c e sw h i c hh a sd i s t a n c e3c t c w ch a v et h ef o l l o w i n gt h e o r e m s ： t h e o r e m2 1 1i fgi sal o o p l e s sc o n n e c t e dg r a p h t h e ne i t h e rgo ri t s c o m p l e m e n tg 。i su p p e re m b e d d a b l c t h e o r e m2 。2 1i fgi sas i m p l ec o n n e c t e dg r a p h t h e ng 3i su p p e re m b e d - d a b l e t h e o r e m2 3 1l e tgb eas i m p i ec o n n e c t e dg r a p h i ff o re v e r yt w ov e r t i c e s “a n d 口i ns u b g r a p hlw i t hd i s t a n c et w o ，i e d l ( 缸，口) = 2 ，s a t i s f yt h ec o n d i t i o n ln c ( n ) nn c ( v ) l 2 ，t h e ng i su p p e re m b c d d a b l e t h e o r e m2 4 1l e tg i sal o o p l c s sc o n n e c t e dg r a p hw i t hk ( g ) = 2 i fe a c h e d g ei ng i sc o n t a i n e di nac y c l eo ft h r e e ，t h e ngi su p p c re m b c d d a b l e t h e o r e m2 4 2l e tgi sal o o p l c s sc o n n e c t e dg r a p hw h i c hh a sa tm o s tt w o c u tv e r t e x i fe a c he d g ei ngi sc o n t a i n e di nac y c l eo ft h r e e ，t h e ngi su p p e r c m b e d d a b l e f o rt h et h e o r e m2 5 1 ，2 5 2 ，2 5 3 ，w eg i v e8p i c t u r ea sf o l l o w i n g ： e t 1 ( 命 l o o p l e s sg r a p hu p p e rc m b c d d a b l e ln ( g ) s 1y e s 2 a ( a ) 2 y e s 3 a ( g ) 5 y e s t h e o r e m2 6 1l e tgb e82 - e d g ec o n n e c t e d8 i l p l eg r a p h 1 ff o re v e r yt w o v e r t i c e sw i t hd i s t a n c et h r e e ，i e d g ( “，口) = 3 ，s a t i s f yt h ec o n d i t i o nd ( “) + d ( v ) 警一l ( n = i y ( g ) 1 ) ，t h e ng i su p p e re m b e d d a b l e ，f u r t h e r m o r e ，t h el o w e rb o u n di s t h eb e s t t h e o r e m2 6 2l e tgb ea3 - e d g ec o n n e c t e ds i m p l eg r a p h i ff o re v e r yt w o v e r t i c e sw i t hd i s t a n c et h r e e ，i e d g ( 缸， ) = 3 ，s a t i s f yt h ec o n d i t i o nd ( “) + d ( v ) 警= i y ( g ) i ) ，t h e ng i su p p e re m b e d d a b l e ，f u r t h e r m 6 r e ，t h el o w e rb o u n di st h e b e s t i nc h a p t e r3 ，w eo b t a i ns o m et i g h tl o w e rb o u n do fm a x i m u mg e n u si nt e r m s o ft h ep a r a m e t e rs u c ha 8d i a m t e r ，g i r t h ，v e r t e xi n d e p e n d e n tn u m b e re t c w eh a v e t h ef o u o w i n gt h e o r e m ： t h e o r e m3 1 1l e tgb eal o o p l e s sc o u n c c t e dg r a p hw i t hg i r t hg t h e nt h e l o w e rb o u n d so nt h en l a x i m l n ng e n u s 佃( g ) a r eg i v e ni nt h ef o l l o w i n gt a b l e t h e r o w sa r ec o r r e s p o n dt oe d g e - c o n n e c t i v i t yk = 1 ，2 ，3 ，o r 4 t h es a m eb o u n d sa l s o h o l d sf o rv e r t e x - e o n n e c t i v i t y f u r t h e r m o r e ，t h eb o u n d sa r eb e s tp o s s i b l e k i ( g )7 j ( g ) l m s 札 口( g ) 一精，【学j 2 n n ；( g ) 一掰，【竽- 3m z n ；p ( g ) 一督，【华j 4 【竽j t h e o r e m3 2 7l e tgb eas i m p l ee o n a e c t c dg r a p hw i t hd i a m e t e r4 1 fg d o e sn o tc o n t a i nc o m p l e t es u b g r a p hk 3 ，t h e nf ( g ) 2 ，i e ，7 m ( g ) p ( g ) 一1 t h e o r e m3 3 4l e tgb eas i m p l ec o n n e c t e dg r a p hw i t hd i a m e t e rd i ft h e g i r t ho fgs a t i s f y9 ( g ) d , t h e nf ( g ) s2 , i e ，7 m ( g ) j l p ( g ) 一1 i nc h a p t e r4 ，w eu $ ct h em e t h o do fo v e r l a pm a t r i xb ym o h a r ，o b t a i nt h et o t a l e m b e d d i n gd i s t r i b u t i o no ft w od a m e sg r a p h sn ra n dl 佳w eh a v et h ef o l l o w i n g t h e o r e m ： t h e o r e m 4 2 6t h e t o t a l e m b e d d i n g d i s t r i b u t i o n p o l y n o m i a l o f t h e n e c l d a c e m w i t hre a r s j s r j 以( 毛) = 7 4 。只，i ( f ) + ( 6 一a - ) ( x 一! ，2 ) v 北京交通大学博士学位论文英文摘要 t h e o r e m4 3 2t h et o t a le m b e d d i n gd i s t r i b u t i o np o l y n o m i a lo ft h eg r a p h l 2 k i s 屯2 - ( 。，y ) = 6 h + i 4 4 w 州5 + 缸撕+ 8 f 2 k + 1 札珏，如( ) 一g l 2 k ( 2 ) + g l 2 ( z ) i 1 + + l s = k i nc h a p t e r5 ，w eo n l yp r e s e n ts o m ep r o b l e m sf o rf u r t h e rs t u d y k e y w o r d s ：g r a p h ，s u r f a c e ，e m b e d d i n g ，m a x i m u mg e n u s ，b e t t id e f i c i e n c y m l m b e r ，u p p e re m b e d d a b i l i t y , g e n u sd i s t r i b u t i o n c l a s s n o ：0 1 5 7 ，5 符号说明 ( g ) ，图g 的最小亏格； 7 m ( g ) ，图g 的最大亏格； ( g ) ，图g 的b e t t i 数( 圈秩) ； ( g ，即，g e ( t ) 中边数为奇数的连通分支数 f ( g ) ， 图g 的b c t t i 亏数； g c ，图g 的补图 d ( “) ( 如g ( t ) ) ， 顶点u 的度； d ( u ， ) ，顶点t 和口之问的距离； d ( g ) ，图g 的直径； 9 ( g ) ， 图g 的围长； k ( g ) ， 图g 的点连通度； k l ( g ) ，图g 的边连通度； n o ( t ) ， 图g 中与顶点“关联的顶点集； 口( g ) ，图g 的点独立数； c ( c 、a ) ，g a 的所有连通分支数； b ( g a ) ，g a 中圈秩为奇数的连通分支数； r ( a ) ，矩阵a 的秩； g 】， 顶点集x 的点导出子图； j ，n 个顶点的完全图； c 二，n 个顶点的圈； 以n 曰，a 的口交； a u b ，a 的b 并； e c ( f l ，f 2 ，只) ，g 中两端点分别在不同的晟和乃中的边集( i j ，1 i ，j s l ) ； e ( 最，g ) ，g 中端点在只和不在最中的边集； 吲，不超过z 的最大整数； p 1 ，不小于z 的最小整数； g g ( x ) ，g 的环柄多项式( 亏格多项式) ； 北京交通大学博士学位论文符号说明 ，g ( ) ， g 的叉帽多项式； 如( z ，f ) ，g 的完全多项式； m i n ，求最小值； m a x ，求最大值； 口，表示证明结束 x 致谢 本论文的工作是在我的导师刘彦佩教授的悉心指导下完成的。刘彦佩教授严 谨的治学态度和深厚的数学功底以及高尚的人格给了我极大的帮助和影响另外。 刘老师在生活上也都给予我无微不至的关怀在此衷心感谢这几年来他对我的关 心和指导 修乃华教授、常彦勋教授，冯衍金教授、郝荣霞教授、江中豪教授、罗振东教 授、壬金亭副教授、王周宏副教授、和于永光副教授等对于我的科研工作和论文 都提出了许多的宝贵意见，在此表示衷心的感谢 在撰写论文期间，毛林繁，李赵祥、魏二玲、陈仪朝万良霞、许燕。刘文忠， 孔令臣等同学对我论文中的一些研究工作给予了热情帮助，在此向他们表达我的 感激之情 另外，感谢我的父母，我的妻子和儿子在生活中给予我的支持和鼓励他们 的理解和支持使我能够在学校专心完成我的学业 第一章绪论 本章首先概述图在曲面上的嵌入问题中关于最大亏格研究的历史和现状，然 后对本文韵工作做了简要介绍 1 1 研究问题的内容和意义 与其他图论分支一样，图在曲面上的嵌入理论与著名的四色问题有着千丝万缕 的联系，这四色问题最早是由c a l y e y 在1 8 7 8 年提出的在1 8 9 0 年f 2 h e a w o o d 提出著名的地图着色定理后，h i b e r t 等人又将它归结为引线问题，即在曲面s ( p 表示s 的亏格) 上给定n 3 ) 个不同点，能否用简单曲线( 引线) 两两连接 这 个点使得这些连线在曲面上互不相交? 用图论术语而言，引线问题与确定完 全图k 。的亏格7 ( 玩) 等价自然确定一般图的亏格又是上述问题的推广尽管 h e a w o o d 地图着色问题早在1 9 8 6 年得以完全解决，然而它给图论开辟了一个至 今不衰的新课题一图在曲面上的嵌入美于逮个问题的完全解决可以参考r i n g c l 的书f 3 】 本文中考虑的图g = i t , e ) 均指有限，无向连通图一个图称为简单图 ( s i m p l eg r a p h ) ，如果它不含重边和环一个图称为l r $ $ 1 ( l o o p l c g r a p h ) ( 或重 图( m u l t i g r s p h ) ) ，如果它不含环但允许有重边 希望读者对拓扑图论的知识多少有一些了解，一般的可参考文献支4 彦佩圈， g r 0 8 8 和t u c k e r 5 ，以及w h i t e 6 这里。曲面伽咖。砂通常是指一个紧的， 2 _ 维浇形( 可定向或不可定向) ， 其亏格表示为口( s ) ，连通图g 在曲面s 上的个嵌入( e m b e d d i n g ) 是指存在一 个拓扑同胚映射，：g s 使得s f ( o ) 的每个连通分支与圆盘拓扑等价，人们 通常称之为乒胞腔嵌入( e - c e l le m b e d d i n g ) 图g 的亏格( g e n u s ) 7 ( g ) 是指最小 的整数o ( s ) 使得g 在曲面s 上有2 - 胞腔嵌入丽图g 的最大亏格( m a z i m u m 9 e n 咖( g ) 是指最大的整数g ( s ) 使得g 在曲面s 上有2 胞腔嵌入 5 9 6 6 年 r d u k e 1 0 】证明了图的亏格插值定理，即如果图g 在两个可定向( 或不可定向) 曲面s k 和& ( m f 1 ) 上都有暑胞腔嵌入，则g 在任意定向( 或不可定向) 曲 面瓯( m sj 竹) 上也有参胞腔嵌入因此在考虑g 的所有可嵌入的曲面，只 磊确定它的亏接也称最小亏格) 7 ( g ) 和最大亏格协( 固 早在7 0 年代末，r i n g l e ，刘彦佩等人已经证明了图g 的不可定向最大亏格 1 箜二耋堑鲨 为口( g ) ( 树除外) 基于这个原因，一般考虑最大亏格都足指可定向情形下由著 名的欧拉公式，我们知道可定向最大亏格有一个很显然的上界 1 ( g ) 鲥掣j ， 这儿，z ( a ) = l e ( g ) 卜i 矿( g ) l + 1 称为图g 的b e t t i 数，也称为圈秩( c y c l e r a n k ) 个图被称为是上可嵌入( u p 册re m b e d d a b l e ) 的是指协( g ) = l 学j 1 2 最大亏格问题研究的历史和现状 自从n o r d h a u s ，s t e w a r t ，和w h i t c 1 1 1 等人引入最大亏格的研究，以及禁用子 图 1 2 】研究的快速发晨，关于最大亏格的研究一般围绕以下五个类型进行。 类型1 ：上可嵌人性从上可嵌入性的定义可知，一个图是上可嵌入的等 价于导出最大亏格的下界就是伽( g ) = i 譬j 大量的文献用不同的条件研究了 图的上可嵌入性，例如n o r d h a u s ，s t e w a r t ，和w h i t c 1 1 ，n e b e s k y ，3 0 ，3 1 ，3 2 ，3 3 ， 叫，r i n g e i s e n 1 3 ，1 4 】，z a k s 1 5 ，x u o n g 1 6 ，17 】，刘彦佩【1 8 1 9 ，2 0 】等等，特别地， 每个四边连通的图都是上可嵌入的( k u n d u 2 7 ) 因此，一般研究图的上可嵌入 性都把边连通度限制在小于等予3 然而，存在无限图类是3 边连通但不足上可 嵌入的( j u n g e r m a n 2 8 ) 黄元秋【5 7 ，5 8 ，5 9 ，6 0 ，6 1 ，6 2 ，6 3 ，6 4 ，6 5 ，6 6 ，6 7 】较系统 地研究了最大亏格的上嵌入性 类型2 ：最大亏格的表征x u o n g 1 6 ，刘彦佩f 2 0 j 用生成树的补的连通分 支来刻画图的最大亏格嵌入 个图g 与它的生成树t 的边的补集，即e ( g ) e ( 丁) ，称为图g 的余树 r 踟打傥j 显然，每个连通图g 的余树的边数等于( g ) 一棵余树不一定足连 通的余树的一个连通分支日称为边分支，是指f f 饵) f = 七如果是偶( 奇) ， 则称日是偶倚，分支记号f ( g ，t ) 表示所有g e ( t ) 中边数为奇数的连通分 支数称f ( g ) = 嘲n ( g ，t ) 为g 的b e t t i 亏数，其中r a i n 取遍g 的所有生成树 7 由定义，对g 的任意生成树丁，均有 f ( g ，t ) 兰f ( g ) 三口( g ) ( m d d 2 ) 一般我们把满足( g ，t ) = ( g ) 的那棵生成树称为最优树 定理1 2 1 设g 为连通图。则 2 垄壅 壅望查 兰竖主堂垡堡壅 r 砂g 是上可嵌入的当且仅当 ( g ) 1 ； 俐伽( g ) = 业铲 而后，n e b e s k y 【2 9 】给出了( g ) 另外一个完全组合化的表征，事实上，这两 者是对偶的 设a e ( g ) 为匿g 的任意边子集，记号c ( a a ) 表示g a 的所有连通 分支数；而记号b ( a a ) 表示所有具有圈秩为奇数的g a 的连通分支数 定理1 2 2 设g 为连通图，则 一，g 是上可嵌入的当且仅当对任意边集a e ( g ) ，c ( g a ) + 6 ( g a ) 一2 l a i i 例f ( g ) = l ! 嚣岛 c ( g a ) + 6 ( g a ) 一1 一i a i 黄元秋【5 9 】利用定理b 中边集a 的最小性，刻画了一个图不是上可嵌入的 充分必要条件，在实际应用中起到了非常重要的作用 设只，最，e 0 2 ) 为图g 的1 个子图，记号e c ( h ，f 2 ，只) 表示g 中 两端点分别在不同的只和乃中的边集( i 工1s i ，jsf ) 定理1 2 3 设g 为连通图，若g 不是上可嵌入的，即( g ) 2 ，则存在a e ( g ) 满足如下性质t “，c ( g a ) = b ( a a ) 2 ； r 缈对g a 的每个连通分支f ，f 是g 的一个点导出子图； 俐对g a 的任意口( 2 ) 个不同连通分支f l ，f 2 ，e ，则有f e a ( f , ，f 2 ，r ) l s2 a 一3 特别地，当n = 2 时，i j k ( f 1 ，f 2 ) i l ； 似，3 2 b ( a j 4 ) 一l a l 4 ； f 印f ( g ) = 2 b ( a a ) 一i a i 一1 类型3 ：最大亏格的算法f u r s t ，g r o s s ，和m c g e o c h 3 5 给出了计算最大 亏格的多项式算法，部分地依赖于拟阵中交换( m a t r o i d e ds w a p p i n g ) 技术 3 第一章 绪 论 类型4 ：最大亏格下界近几年以来。关于最大亏格研究的重点都致力 于导出不可上嵌入图的最大亏格的紧下界 g r o s s ，k l e i n ，和r i e p e r 4 6 ，c h c n 和 g r o s s f 4 7 】构造了一类图，它的b e t t i 数能任意地大但是最大亏格小于等于1 s k o v i c - r a 2 1 】证明了直径为2 的2 连通图的最大亏格下界为! 盟2 一2 c h e r t 和g r o s s 4 8 证明了2 连通简单图( 或3 连通) 的最大亏格的下界为! ( f o ( g ) ) 这一结 果又被c h c n ，g r o s s 和r i c p e r 4 9 1 改进，他们证明了2 连通最大亏格的下界为 2 譬a r c h d e a c o n ，c h e n 和t t u a n g 等人【7 4 】给出了用连通度为参数的最大亏格的紧 下界，将以前的结果推广到非简单图 类型5 ：亏格分布 为了系统研究图在陆面上的嵌入，g r o s s 和f 1 1 r s t s 4 1 提出了图的嵌入亏格分布闻题，一些图类如环束f 8 5 】，两极图 8 8 】，各种梯图【7 7 ， 8 7 ，9 2 】，项链图f 8 7 】等都已经求得方法主要有组合的方法【7 7 】，j a c k s o n 公式法 8 5 】，和m o h a r 的覆盖矩阵法 8 9 1 等，自从刘彦佩独创地提出了联树法【7 5 ，7 6 】，嵌 入亏格分布问题取得了突破的进展【9 4 ，9 5 】，万良霞的博士论文 9 6 】可以见证此方 法的用处 1 3 本文结构 本论文主要研究图的最大亏格，共分五章： 第一章主要介绍最大亏格研究的历史和现状，然后对本文的工作做了简要介 绍 第二章我们得出了一些上可嵌入的图类，它们具有一些特殊的邻域条件，或 特殊的边。或特殊的不相邻点的度和，或者根据条件构造出来的新图等等其中。 推广了黄元秋等人的些结果 第三章我们主要利用图的一些参数条件，例如直径、边连通度、围长、点独立 数等等，给出了最大亏格的紧下界其中，推广了a r c h d e a c o n 等人，以及黄元秋 等人的一些结果 第四章给出了两类图髓和2 的完全亏格多项式由于现有知道完全亏格 多项式的图类很少，基于这个目的，本章可视为在这方面的补充 第五章指出一些有待以后研究的问韪 4 第二章关于图的上可嵌人性 2 1 图g 和它的补图g c 的上可嵌人性 本文中考虑的图g = ( k 动均指有限，无向连通图个图称为简单图，如果 它不含重边和环个图称为无环图( 也称重图) ，如果它不含环但允许有重边图 g 的补图( c o m p l e m e n tg r a p h ) g 。是指y ( 6 t c ) = 矿( g ) ，e ( g 。) = u v l = v 簪e ( g ) ， 图g 中顶点的邻域m i 咖如一用i c ( u ) 表示是指n c ( u ) = v l u 口e ( g ) 一个图的直径( d i a m e t e # 是指所有两点问最短路长的最大者，用d ( g ) 表示，即 d ( c ) = m 们。v ( g ) m i * y f g ) d ( t ，u ) 设s 为一个可定向曲面( 曲面，这里指一 个紧的2 - 维闭流形) ，个图g 在s 上的个2 一胞腔嵌入是指g 能画在s 上 使得边与边之问除顶点外不再相交，且在s 上去掉g 的顶点与边之后的每个连 通分支与圆盘同胚图g 的最大亏格，记为，y ，( g ) ，是指最大的整数k 使得g 能 2 胞腔嵌入亏格为k 的定向曲面s 上因为图在任意定向曲面上的2 一胞腔嵌 入中至少有个面，由e u l e r 公式易得一个图的最大亏格上界1 m ( g ) l 壁掣i ， 其中妒( g ) = l 耳g ) 一 y ( g ) l + 1 称为图g 的圈秩任意实数毛驯表示不超 过z 的最大整数) 同时。称图g 是上可嵌入的若7 m ( g ) = 【旦磐j 图的最大亏格是刻划图在曲面上嵌入的一个拓扑参数，与最大亏格相关的上 可嵌入问题，即确定个图最大亏格的最好上界是拓扑图论中一直感兴趣的同题 给定一些限制条件，许多文献都证明了一些图类是上可嵌入的( 关于这方面的结 果，有兴趣的读者可参见 1 7 ，1 8 ，2 8 ，3 0 ，3 l ，3 2 ，3 3 ，3 4 ，5 7 ，5 8 ，7 0 ，7 3 1 ) 文献【2 l 】 和【2 2 】均用不同的方法证明了t 一个直径不超过2 的无环图是上可嵌入的显 然，。一个无环图的直径不超过2 。等价于。对于g 中任意不相邻的点社和玑 即删隹e ( g ) ，有l g ( t ) n g ( ) 1 2 1 。文献【5 8 】证明了，设g 是无环图。对 g 中任意相邻的点1 l 和弘若如下两条件之一满足( 1 ) in c ( u ) nn c ( v ) 22 ；( 2 ) g 是2 一点连通且i r g ( 珏) n j v g ( v ) l 1 ，则g 是上可嵌入的文献【6 8 1 考虑所有距 离为2 的不相邻的两个点的邻域的条件，即设g 是简单图。对g 中任意两个距 离为2 的点“和即如( “，口) = 2 ，都有ij i 、r g ( “) n 心( 口) 1 22 ，则g 是上可嵌 入的文献【5 9 】证明了。如果g 是简单图，那么图g 或者它的补图g c 是上可嵌 入的本节主要推广了文献【5 9 l 的结论，即证明了下述定理t 如果g 是一个无环 图，那么图g 或者它的补图伊是上可嵌入的 下面解释文中的有关概念和记号，其它未加说明的均同【4 】和【5 】对任意集 5 笙三 至 差王 堕 堕 土要垦丝 合x ，i x i 表示x 的基数设】，为图g 的任意边集合，g y 表示从g 中去 掉y 中的所有边所得到的图若t 为图g 的一棵生成树，记号( g ，t ) 表示所 有g e ( 卵中边数为奇数的连通分支数称f ( g ) = 蜒n ( g ，t ) 为g 的b e t t i 亏 数( b e t t id 币c i e n c yn u m b e r ) ，其中r a i n 取遍g 的所有生成树t ，由定义，对g 的 任意生成树丁，均有 f ( g ，t ) 三( g ) 兰p ( g ) ( m o d 2 ) 设4 e ( g ) 为图g 的任意边子集，记号c ( g a ) 表示g a 的所有连通 分支数；而记号b ( g a ) 表示所有具有圈秩为奇数的g a 的连通分支数设 置，易，月“2 ) 为图g 的f 个子图，记号e o ( r ，毋，最) 表示g 中两端点 分别在不同的只和髟中的边集( i j ，1s i ，j f ) 对图g 的任