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

北京交通大学博士学位论文中文摘要 中文摘要 摘要：拓扑图论最初是研究怎样把图画在曲面上使得任何两条边互不相交，这个 直观的几何问题随着其它数学分支，特别是代数拓扑、群论、组合计数理论以及 算法分析等的介入而变得丰富多彩目前拓扑图论的研究领域可分为两个主流： 一是研究图在曲面上嵌入的性质；另一个研究地图计数问题本文研究属第一个 方面，即研究图的嵌入的最大亏格问题 连通图g 在紧的闭曲面s 上的嵌入指存在一个同胚映射痧：g _ s 使得 s o ( c ) 的每个连通分支都同胚于一个开圆盘，这样的嵌入称为胞腔嵌入根据 s 是可定向曲面或者是不可定向曲面，这样的嵌入又分别称为可定向嵌入或不可 定向嵌入图g 的最大亏格指图g 所能嵌入曲面的亏格中最大的那一个因为 图的任何嵌入必至少含有一个面，由欧拉公式易得图的最大亏格的一个上界： 7 f ( g ) l 盟盟半剑兰| ， 么 其中符号【q j 指不超过o l 的最大整数，i e ( g ) j i y ( g ) l + 1 被称为图g = ( y ( g ) ：e ( g ) ) 的b e t t i 数并用符号p ( g ) 表示如果7 m ( q = 【壁盟2j i ，则图g 被 称为上可嵌入的最大亏格问题起源于n o r d h a u s 、s t e w a r t 和w h i t e l 9 7 1 年的 文章【3 1 1 ，刘彦佩【2 1 】和x u o n g 3 8 j 于1 9 7 9 年分别独立地得到了关于图的嵌入 的最大亏格的经典定理，随后，由于诸多学者对这一问题的关注与研究使得这一 问题取得重大进展其研究分为两个方面：一是图的上可嵌入性的研究；二是对 非上可嵌入图的最大亏格的界的研究因为任意图在不可定向曲面上总是上可嵌 入的，因此最大亏格问题只讨论图在可定向陆面上的嵌入 在本论文中，一方面，借助已有的研究成果对图的最大亏格问题进行了深入 地研究，得出了一些新结果，改进了一些已知结果；另一方面，借助刘彦佩提出 的联树法，对最大亏格问题从另一个方面进行了一些尝试性的研究，并取得一些 初步进展本文可分为以下几个部分： 第一章介绍图的最大亏格问题的背景知识以及一些基本概念和术语 第二章研究了直径3 图中的加边运算与最大亏格 第三章结合图的围长以及相邻顶点或非邻顶点的度和研究图的上可嵌入性 第四章研究非上可嵌入图的最大亏格的下界问题 第五章借助联树模型研究图的最大亏格 第六章介绍了一些需要进一步研究的问题 北京交通大学博士学位论文中文摘要 关键词：最大亏格；图的嵌入；联树；关联曲面；图的亏数 分类号：0 1 5 7 5 北京交通大学博士学位论文 英文摘要 a b s t r a c t a b s t r a c t ：t os t u d yt h ed r a w i n go fag r a p ho nas u r f a c es u c ht h a tn ot w o e d g e sc r o s s ，w h i c hi sa ni n t u i t i v eg e o m e t r i cp r o b l e m ，i st h ep r i m i t i v eo b j e c t i v eo f t o p o l o g i c a lg r a p ht h e o r y a r m e dw i t ho t h e rm a t h e m a t i c a lb r a n c h e ss u c ha u sa l g e - b r a i ct o p o l o g y a n dg r o u pt h e o r y , a n de n u m e r a t i v ec o m b i n a t o r i c s ，a n dt h ea n a l y s i s o fa l g o r i t h m s ，t o p o l o g i c a lg r a p ht h e o r yh a sb e e nb e c o m i n gm o r ea n d m o r em e a n i n g f u l t h e r ea r et w of i e l d si nt o p o l o g i c a lg r a p ht h e o r y ：o n ei st h es t u d 3 , o ft h e p r o p e r t i e so fg r a p he m b e d d i n g ，a n dt h eo t h e ri st h ee n u m e r a t i v et h e o h o fm a p s t h i sp a p e rc o n c e r n st h em a x i m u mg e n u so fg r a p h sw h i c hb e l o n g st ot h ef i r s tf i e l d t h ee m b e d d i n go fa g r a p hg o nas u r f a c esi ss u c hah o m e o m o r p h i s m0 ：g s t h a te a c hc o n n e c t e dc o m p o n e n to fs 一咖( g ) i sh o m e o m o r p h i ct oao p e nd i s k a c c o r d i n gt osi so r i e n t a b l eo rn o n o r i e n t a b l es u r f a c e ，t h ee m b e d d i n g 矽o fgo n si sc a l l e do r i e n t a b l ee m b e d d i n go rn o n o r i e n t a b l ee m b e d d i n gr e s p e c t i v e l y t h e m a x i m u mg e n u s7 m ( c ) o fac o n n e c t e dg r a p hgi st h em a x i m u mi n t e g e rks u c h t h a tt h e r ee x i s t sa l le m b e d d i n go fgi n t ot h eo r i e n t a b l es u r f a c eo fg e n u sk s i n c e a n 3 e m b e d d i n gm u s th a v ea t1 e a s to n ef a c e ，t h ee u l e rc h a r a c t e r i s t i cf o ro n ef a c e l e a d st oa nu p p e rb o u n do nt h em a x i m u mg e n u s ，y m ( g ) 【盟业半倒生j ， w h e r et h en u m b e ri e ( g ) i l y ( g ) i + 1i sk n o w na st h eb e t t in u m b e r ( o rc y c l e r a n k ) o ft h ec o n n e c t e dg r a p hga n di sd e n o t e db yp ( g ) ag r a p hg i ss a i dt ob e u p - e m b e d d a b l ei f7 m ( g ) = 【警j t h ei d e ao ft h em a x i m u mg e n u s7 ，( g ) o fa c o n n e c t e dg r a p hgw a si n t r o d u c e db vn o r d h a u s ，s t e w a r ta n dw h i t e 【3 1 】i n1 9 7 1 i n1 9 7 9 ，l i u 2 1 】a n dx u o n g 3 8 】o b t a i n e dt h ec l a s s i c a lt h e o r e mo nt h em a x i m u m g e n u si n d e p e n d e n t l y f r o mt h e no n ，m a n yr e s e a r c h e r sh a v es t u d i e dt h ep r o b l e m a n do b t a i n e dm a n yi n t e r e s t i n gr e s u l t s t h er e s e a r c ho nm a x i m u mg e n u si sm a i n l y f o c u s e do nt w oa s p e c t s ：o n ei st h es t u d yo ft h eu p - e m b e d d a b i l i t yo fg r a p h s ，a n d t h eo t h e ri st h el o w e rb o u n do nt h em a x i m u m g e n u so fn o n u p - e m b e d d a b l eg r a p h s b e c a u s ee v e n ，g r a p hi su p - e m b e d d a b l eo nn o n - o r i e n t a b l es u r f a c e s ，t h em a x i m u m g e n u sp r o b l e mo n l ys t u d yo r i e n t a b l ee m b e d d i n g s t h i st h e s i sc o n s i s t so ft w op a r t s ：o n ei st h ed e e p e rs t u d yo ft h em a x i m u m g e n u sv i at h er e s u l t so b t a i n e di nt h ef o r e t i m e ；t h eo t h e ri sa na t t e m p to nt h e n l 北京交通大学博士学位论文英文摘要 s t u d y i n go ft h em a x i m u mg e n u st h r o u g hj o i n tt r e e ，w h i c hi se s t a b l i s h e db yl i u y a n p e i t h et h e s i sa r ec o m p o s e do ft h ef o l l o w i n gs i xc h a p t e r s ： i nc h a p t e r1 ，t h eb a c k g r o u n do ft h em a x i m u m g e n u sa n d s o m ed e f i n i t i o n sa n d t e r m i n o l o g i e sa r ep r o v i d e d i nc h a p t e r2 ，t h er e l a t i o nb e t w e e nt h em a x i m u mg e n u sa n dt h ee d g e - a d d i n g o p e r a t i o no ng r a p h so fd i a m e t e r3a r ed i s c u s s e d c h a p t e r3i sf o c u s e do nt h es t u d yo fu p - e m b e d d a b i l i t yo fg r a p h sv i ag i r t ha n d t h ed e g r e e - s u mo fa d j a c e n tv e r t i c e so rn o n a d j a c e n tv e r t i c e s i nc h a p t e r4t h el o w e rb o u n do ft h em a x i m u mg e n u so fg r a p h sn o n u p _ e m b e d d a b l ei sd i s c u s s e d c h a p t e r5f o c u s e so nt h es t u d yo ft h em a x i m u mg e n u so fg r a p h sv i aj o i n tt r e e m o d e l c h a p t e r6c o n s i s t so fs o m ep r o b l e m sw o r t hs t u d y i n gf u r t h e r k e y w o r d s ：m a x i m u mg e n u s ；g r a p he m b e d d i n g ；j o i n tt r e e ；t h ea s s o c i a t e d s u r f a c e ；d e f f i c i e n c y c l a s s n 0 ：0 1 5 7 5 l v 符号说明 亏格为p 的可定向曲面 亏格为q 的不可定向曲面 图g 的最大亏格 图g 的b e t t i 数 图g 的亏数 图g 的围长 图g 的独立数 图g 的最小度 k 功 习 习 郇 炯 峒 北 京交通大学博 士 学位论文索引 b 胞腔嵌入 半边 半双图 c 触点 重图 d 单瓣图 导出子图 独立数 g 关联曲面 j 简单图 1 4 1 3 2 1 1 3 1 1 4 k 亏数 2 可定向曲面 3 扩展螺旋图 4 8 l 连杆 联树 临界顶点 螺旋图 p 劈分顶点 剖分 q 曲面 强围田图 1 4 3 9 4 8 3 4 5 索引 s 算法 3 9 w 围长 围田图 伪图 z 直径 最大亏格 1 4 5 1 1 2 北京交通大学博士学位论文独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位论文作者签名；签字日期：年月日 6 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：导师签名： 签字只期：年月日签字同期：年月目 致谢 本文是在刘彦佩教授的精心指导下完成的正是得益于刘彦佩教授的指引才 使我得以进入拓扑图论这研究领域，刘老师严谨的学术作风、渊博的专业知识、 诚勤宽厚的师者风范永远是我学习的楷模刘老师给予的不仅是学术上的指引， 在思想上以及生活中也给予了很多帮助，传授给我不少做学问以及为人处事的道 理在此对刘老师的帮助与鼓励表示衷心的感谢 感谢常彦勋教授、修乃华教授、冯衍全教授、郝荣霞教授以及何卫力副教授， 他们在学习和科研工作中的给予的帮助和鼓励，使我受益匪浅 感谢万良霞、陈仪朝、刘文忠、许燕、杨艳、邵泽玲、曾建初、潘立彦、吕胜 祥、张永利等同学，在论文完成过程中的帮助 感谢父母，正是他们给予我的鼓励与帮助才使我得以顺利完成学业，深深的 感谢他们 第一章预备知识 这一章主要介绍图的嵌入的最大亏格问题的研究背景及一些概念和术语 1 1 研究背景 图论起源于哥尼斯堡七桥问题，包括拓扑图论、代数图论、化学图论、算法图 论等研究领域l e u l e r 于1 7 5 3 年发现了e u l e r 公式而成为拓扑图论的奠基人 1 9 3 0 年，波兰数学家c k u r a t o w s k i 和美国数学家o f r i n kp a s m i t h 发现了 平面图判定准则后，这方面的研究开始活跃起来，图在高亏格曲面上嵌入的研究 也随之不断取得进展在图所有可嵌入的曲面中必有亏格最小的曲面，但如何确 定个图的最小亏格是n p h a r d 的1 9 7 1 年，n o r d h a u s 、s t e w a r t 和w h i t e 【3 1 】首次引进了连通图的最大亏格这一问题，r i n g e i s e n 【3 3 3 4 3 5 】深入地研究 了最大亏格问题，并给出了图的上可嵌入性的定义，此后许多学者研究了这一问 题，并得出许多有意义的结果，从而极大地推进了这一问题的研究目前关于图 的最大亏格问题的研究主要集中于两个方面：一是关于图的上可嵌入性的研究， 另一个是关于非上可嵌入图的最大亏格下界的研究 1 2 相关的定义与性质 个图常记作g = ( y ( g ) ，e ( g ) ) ，其中v ( c ) ，e ( c ) 和f ( g ) 分别指图g 的顶点集，边集和面集本文所考虑的图都是有限，无向的连通图端点重合为一 点的边称为环，端点不同的边称为连杆，两个不同端点被多于一条的边连接时， 这些边被称为重边既无环也无重边的图称为简单图；有重边但无环的图称为重 图；重边和环都允许出现的图称为伪图剖分图g 中个环指通过在该环上添加 个新顶点而把该环变为重边的过程若s v ( c ) ，则符号c s 】表示图g 的由 顶点集v ( a ) 的非空真子集s 导出的子图，即以s 为顶点集并以g 中两端点都 在s 中的边为边集的g 的子图符号a ( c ) 表示图g 的独立数g ( c ) 或不易引 起混淆时用g 表示图g 的围长符号d ( g ) 表示图g 的直径，d g ( 乱， ) 表示图 g 中两个顶点t 和t 7 之间的距离，即图g 中t 和秒之间的最短路的长度设口 是图g 的一个度至少为4 的顶点，劈分顶点秒指对图g 做如下变换：用两个新 顶点t ，1 和t j 2 替换 并用边连接v l 和吨，图g 中每条连接秒和另一个顶点牡 第一章预备知识 的边被连接“和 1 或钆和忱的边代替其它未解释的概念同文献 2 】，读者应 熟悉拓扑图论，有关拓扑图论的详细内容可参看文献 2 3 】，g r o s sa n dt u c k e r 【8 】8 以及w h i t e 【3 7 】 图g 的最大亏格7 m ( g ) 指最大的整数七使得g 可嵌入到亏格为k 的可定 向曲面上因为图的任何嵌入必至少含有一个面，由欧拉公式易得图的最大亏格 的一个上界： ，y m ( g ) 纠避韭半倒旦j 其中符号【q j 指不超过q 的最大整数，i e ( g ) i l v ( g ) i + 1 被称为图c = ( y ( g ) ，e ( g ) ) 的b e t t i 数并用符号z ( c ) 表示如果7 m ( a ) = 【幽2j l ，则图g 被称为上可嵌入的如果一个图的所有圈是独立的，即任何两个圈都没有公共顶 点，则这个图称为c a s c a d e 显然，如果图g 是一个c a s c a d e ，则7 m ( c ) = 0 设a 为图g 的边集e ( c ) 的一个子集，c ( 吼a ) 表示g a 的所有连通分 支的个数，b ( g a ) 表示g a 的b e t t i 数为奇数的连通分支的个数，其中g a 表示从图g 中删除a 中的所有边后得到的图g 的子图设丁是图g 的一个 生成树，图g 中树t 的亏数d c ，t ) 为c e ( t ) 中边数为奇数的连通分支的个 数；图g 的亏数f ( g ) 为t 取遍g 所有的生成树后d c ，t ) 的最小值不难发 现( 6 3 三p ( 6 3 ( m o d2 ) 设只，r ，r 为图g 的k ( k 2 ) 个不同的子图， 符号e g ( 乃，局，凡) 表示边集e ( c ) 中一个顶点在y ( r ) 中而另一个顶点在 y ( 乃) ( 1 i ，j k ，i j ) 中的边的集合，e ( r g ) 表示边集e ( c ) 中一个顶点 在y ( 只) 中而另一个顶点不在y ( e ) 中的边的集合( 1 i k ) 设u y ( 尻) ( 1 isk ) ，如果 不与e ( e ，g ) 中任何边关联，则”称为v ( 尻) 的非触点；如 果u 与e ( r ，g ) 中至少一条边关联，则u 称为y ( e ) 的触点；如果 与e ( r ，g ) 中m 条边关联，则 称为y ( e ) 的m 一触点( m 2 1 ) 下面介绍两个分别由l i u 【2 1 】，x u o n g 3 8 】和n e b e s k - 3 0 1 独立得到的关于 图的最大亏格的组合表示以及本文中要用到的其它几个定理： 定理1 2 1 ( l i u 2 1 ，x u o n g ( 3 8 ) 设图g 是一个连通图，则 1 ) 图g 是上可嵌入的当且仅当f ( g ) 1 ； 2 ) ，y ，( g ) = 堂学盟 定理1 2 2 ( n e b e s k t 【3 0 1 ) 设图g 是一个连通图，则 1 ) 图g 是上可嵌入的当且仅当c ( a a ) + b ( g a ) 一2si a i ，其中a 为 e ( g ) 的任意子集； 2 北京交通大学博 士 学位论文 2 ) f ( g ) 2 鼢 c ( g a ) ( g a ) 一i a 一1 ) 定理1 2 3 ( h u a n g 1 6 )对于图g ，如果( g ) 2 ，即g 不是上可嵌入 的，则必存在边集e ( g ) 的子集a 满足下列性质： ( i ) c ( c a ) = b ( g k a ) 2 ； ( i i ) a a 任一连通分支f 是图g 的一个顶点导出子图； ( i i i ) 对于a a 任意k 个不同的连通分支n j 疋，：凡有i e g ( f 1 f 2 ? r ) i 2 k 一3 ，特别的，对于g a 任意两个不同的连通分支f 和h 有l e c ( f , h ) l a ； ( i v ) ( g ) = 2 c ( g a ) 一l a i 一1 不难发现，在上面的引理中，对于g a 任一连通分支f 有以下事实： 事实1 2 1 性质( i ) 表明p ( 乃兰1 ( r o o d2 ) ，并且f 中至少含有一个圈 另外，如果g 是简单图，则i y ( f ) i 3 ；如果g 是重图，则i y ( f ) l 2 ；如果 g 是伪图，贝0i y ( f ) i 1 事实1 2 2 如果g 是2 边连通图，则对任意f g a 有l e ( fg ) l 2 ， 并且c ( c a ) = b ( c a ) 3 ； 如果g 是孓边连通图，则对任意f e a 有i e ( eg ) i 3 ，并且c ( g k a ) = b ( g a ) 4 事实1 2 3 i a i = ；i 以fq l ，其中f 取遍g a 所有的连通分支 1 3 曲面与联树模型 曲面指没有边界的2 维紧流形事实上可以把它看作平面上的一个偶多边形， 每边分配一个方向且两两成对，将同一对边依同方向合二为一而得到因此本文 用偶多边形或者代表其边的字母序来表示曲面，如球面、射影平面、环面和k l e i n 瓶可分别表示为a a 、a a 、a b a 1 b - 1 和a b a b 一般的，o p = i ia i b i a y z1 酊1 和 i = 1 q g q = na i a i 分别表示亏格为p 的可定向曲面和亏格为q 的不可定向曲面，并称它 = 1 们为曲面的标准形式，其中字母n f l 表示它所代表的边与字母n 所代表的边在偶 多边形的边界上方向相反本文中英文大写字母a ，b 等通常用来表示字母的线 性序，括号表示字母的循环序如果字母x ，y ，x y - 1 具有a x b y c x _ 1 d y - 1 e 的 形式，其中ab c d e 允许为空，则称它们为交错型的设s 是一个曲面，符号 g ( s ) 表示曲面s 的亏格如果a = a l a 2 a i ( i21 ) ，则a - 1 = a i1 口i 1 口f 1 由l i u 2 4 1 一 2 7 】可知下面3 种运算不改变曲面的类型： 3 第一章预备知识 运算1 ：( a a a - 1 ) 乍令( a ) 运算2 ：( a a b b a b ) 甘( a c b c ) ；( a a b b b 。a 。) 管( a c b c 。1 ) 运算3 ：( a b ) 仁今( a a ) ( a _ b ) 事实上，上面三种运算确定的是一类拓扑等价，记做一除在运算2 中a 和 b 允许为空外，其余都限制为非空以下等价关系可参看l i u 【2 4 一 2 r 】 关系1 ：( a x b y c x 1 d y - 1 e ) 一( ( a d c b e ) ( x y x - 1 y - 1 ) ) 关系2 ：( a x b x c ) 一( ( a b _ 1 c ) ( z z ) ) 关系3 ：( a x x y z y 一1 z 一1 ) 一( ( a ) ( z z ) ( 可炒) ( z z ) ) 这里a ，b ，c ，d 和e 都允许为空，在无特别需要区分时，曲面表示中 的括号常被忽略 给定图g = ( ke ) ，设丁是图g 的一棵生成树，则图g 的边集e 被划分 为树边研和上树边研两部分，记脐= 邑瞳= 1 ，2 p ) ，其中p = p ( g ) ， 将每条上树边而研从中间切断使其成为两条半边，并分别标以符号- - 8 和 ( s ，t 1 ，- 1 ) ，在不易引起混淆时c - i 1 常常简记做西，显然，这样所得的图是 一个由树边和2 p 条上树半边构成的树，我们称之为t 在图g 上的扩充树，记 为您，或简记为丁令6 = ( 6 1 ，如如) ，其中文= o ，1 ) ( 1 i p ) ，符 号p 表示在丁上，半边爵和c - i t 的指数s ，t 由玩所决定，6 i = 0 表示两个标数 不同，也= 1 表示两个标数相同对于任何 v ，令表示 处一个旋，用 o g = o 可l v v y ) ，或不易引起混淆时用盯，表示图g 的一个旋我们称霉为 图g 的一个联树显然霹确定了丁在平面上的一个嵌入在一个联树砭上， 按照一定的方向( 如顺时针方向) 绕着它的平面嵌入乃的无限面边界走一圈，并 依次记下所遇到的带标号的上树半边，这样所得到的字母序就表示一个曲面，称 之为这棵联树的关联曲面图1 给出了图g 的一棵联树已及其关联曲面，其中 图g 每个顶点处的旋取顺时针方向从文献【2 4 】- 2 7 】可知：( i ) 联树是可定向 的当且仅当6 = 0 ，( i i ) 图g 的嵌入与图g 的联树间存在着1 1 对应关系 e 3 g e 1 e 3 乃 图1 4 百1 芎1 莳1 s o 第二章直径一3 图的加边运算与最大亏格 结合图的直径研究图的最大亏格是最大亏格问题中一个重要的研究方面 s k o v i e r a 于1 9 9 1 年在文【3 6 】证明了下面两个定理： 定理2 0 1 每个直径为2 的无环图都是上可嵌入的 定理2 0 2 设图g 是一个直径为2 的2 连通图( 允许有环) ，则有f ( g ) 4 ，即f 墨笋1 2 7 ，( g ) l 垡笋j 何卫力与刘彦佩在文 9 】证得： 定理2 0 3若图g 是一个直径为3 的简单图，则简单图g 3 是上可嵌入的 本章把定理2 o 3 中用到的图g 由简单图推广到了重图并得到了一类新的上 可嵌入图类，定理2 0 1 也可很容易地由本文得到的结论而证得，并且还得到了一 类直径为2 的2 连通伪图的最大亏格的紧下界，另外，通过剖分一类直径为2 的 允许有环的图g 中的环，得到了一类直径为4 的重图以及这些图的最大亏格的紧 下界本章结论推广了s k o v i e r a 的结果 2 1 相关概念及引理 设图g 是一个直径为3 的简单图，则图g 3 是通过用一条连杆连接图g 中 任何两个距离为3 的顶点而得到的图，即g 3 = ( v ( c 3 ) ，e ( c 3 ) ) ，其中v ( e 3 ) = v ( a ) ，e ( e 3 ) = e ( e ) u e = l wju ，u y ( g ) ，d e ( 锃， ) = 3 ) 设图g 是 个直径为3 的重图( 无环图；伪图) ，图g 3 4 ( g 3 3 ；g ) 是通过用一条连杆连接 图g 中任何两个距离为3 的顶点而得到的图，即g 3 + = ( v ( c 3 1 ) ，e ( e 缸) ) ，其中 v ( c 3 。) = v ( c ) ，e ( e 3 ) = e ( g ) u e = “ul “，t ，y ( g ) ，d a ( u ，u ) = 3 ) ( g 3 3 = ( v ( c 3 3 ) ，e ( c 3 3 ) ) ，其中v ( e 3 3 ) = v ( c ) ，e ( c 3 3 ) = e ( e ) u e = t l uiu ，u y ( g ) ，d g ( 让，u ) = 3 ) ；g = ( v ( a ) ，e ( a ) ) ，其中v ( a ) = v ( e ) ，e ( e ) = e ( c ) u e = “ l 乱， y ( g ) ，d a ( “，秒) = 3 ) ) 不难发现，图g 3 是简单图，图 g 3 ( g 3 3 ；g a ) 是重图( 无环图；伪图) ，并有以下事实： 事实2 1 1 设t l ，口是图g 3 中任何两个不同的顶点，则有如s ( u ， ) 3 事实2 1 2 设u ，”是图g 3 3 中任何两个不同的顶点，则有d g ( 钉，u ) _ 掣， d g ( 小r i g ( v 3 ) 掣， 联合式子( 3 1 0 ) 一( 3 1 2 ) 有 如( 口1 ) + d g ( 忱) + 如( u 3 ) n 一2 1 6 ( 3 1 1 ) ( 3 1 2 ) ( 3 1 3 ) 9 + g 6一九 一 u g d 6 越 北 京交 通大学博士学位论 文 显然当定理3 1 1 中图g 的围长g = 3 时可得结论成立。因此当g 是2 边连通图 时，推论3 1 1 可看作是定理3 1 1 中图g 的围长9 = 3 时的特殊情况 情况2 当g 是3 边连通图时，证明过程与情况1 所用方法相似，用6 个彼 此不相邻的顶点的两两度和代替情况l 中3 个彼此不相邻的顶点的两两度和，通 过运算化简可得；当g 是3 边连通图时，推论3 1 1 可看作是定理3 1 2 中图g 的围长g = 3 时的特殊情况 结合情况1 与情况2 ，该推论得证 口 推论3 1 2 设g 是一个阶为n 的简单图，如果满足以下条件( i ) 或( i i ) ， 则g 是上可嵌入的；( i ) 当g 是2 边连通图时，满足q ( g ) 2 或者q ( g ) 3 且对任何彼此不相邻的顶点耽( i = l ，2 73 ) 都有：1 如( 让) 佗一2 ； ( i i ) 当 g 是3 边连通图时，满足q ( g ) 5 或者n ( g ) 6 且对任何彼此不相邻的顶点 协( i = 1 ，2 6 ) 都有薹1d g ( 蜴) n + 1 证明显然，当g 是2 边连通图和3 边连通图时，该推论分别是定理3 1 1 和定理3 1 2 中图g 的围长g = 3 时的特殊情况，因此该推论得证 口 注释3 1 1 图3 和图4 分别是一个2 边连通图和个3 边连通图，其上可嵌入 性可分别由本文定理3 1 1 和定理3 1 2 判定，但却不能被文章 1 2 】和【3 2 】中所得结 论，即本文推论3 1 1 和3 1 2 判定( 图3 和图4 都是3 正则图对于图3 中任意3 个 彼此不相邻的顶点u 1 ，吨：魄都有：l 如( 眈) = 9 n 一3 9 + 7 = 1 2 - 3 x 4 + 7 = 7 ， 所以由定理2 1 可判定它是上可嵌入的；对于图4 中任意6 个彼此不相邻的顶点 眈( i = 1 ，2 6 ) ，都有：1 如( 地) = 1 8 死一6 9 + 1 9 = 1 8 6 5 + 1 9 = 7 ，所 以由定理3 1 2 可判定它是上可嵌入的) 一 西 图3 1 7 图4 第 三章图的上可嵌入性与图的围长及相邻顶点或非邻顶点度和的关系 3 2 非简单图的上可嵌人性与非邻顶点度和的关系 非简单图上可嵌入性的确定比简单图复杂，本节借助半双图和单瓣图讨论非 简单图的上可嵌入性 去偶运算指对图g 进行满足以下条件的去边运算：( i ) 去掉的边可以是连杆、 重边或自环；( i i ) 去边后所剩部分是连通的；( i i i ) 从g 中去掉的边数是偶数，并 且所去边的边导出子图是连通的一个非简单图的偶先代指由g 经过一系列的去 偶运算得到的图，它可以是简单图、半双图或者单瓣图为便于理解这些概念，图 7 给出了一些例子，其中g 1 1 和g 1 2 是g 3 的偶先代显然，一个非简单图的偶 先代可能不止一个并且根据定理3 2 1 ( 其证明将在后面给出) 可知，我们可以 通过研究简单图、半双图或单瓣图的上可嵌入性来研究非简单图的上可嵌入性 定理3 2 1 一个非简单图g 是上可嵌入的当且仅当g 的偶先代中至少有一 个g 是上可嵌入的 为便于理解概念，图1 给出了一些例图，其中g 1 是个半双图，g 2 是一个 重图但不是半双图，g 3 是一个单瓣图，g 4 是一个位图但不是单瓣图 ( ) o ( ) 卜( ) ( ( ) ( 7 i g 2 图1 g 3 g 4 关于半双图与单瓣图的上可嵌入性，有以下结果 定理3 2 2 设g 是一个阶为n 的1 - 边连通半双图，对于g 中任意不相邻 两顶点“、t ，如果d g ( “) + 如( 口) 2 n 一3 则g 是上可嵌入的 证明假设图g 不是上可嵌入的，由定理1 2 3 可知存在a e ( c ) 使得定理 1 2 3 中性质( i ) 一( i v ) 成立设冗= ：1 ，忍，日) ( z = c ( g a ) = b ( a a ) 2 ) 是 g a 所有的连通分支，x 、y 和z 分别是r 冗中满足i e ( e g ) l = 1 、2 和3 的连 j 通分支数根据事实1 2 3 可得i a i = 互1 l e ( e g ) i2 考+ 可+ ；z + 2 ( z z 一可一z ) i = 1 由定理1 2 3 ( i v ) 可得 2 ( g ) = 2 1 一1 月l 一1 墨2 z 一( 互x + ! ，+ 耋z + 2 ( 1 - z - v - z ) ) 一1 1 8 北 京交 通大学博士学位论文 容易推知 z + v + z 2 根据事实1 2 1 可得对任意f 冗有l y ( f ) l 2 对任意f 冗，如果 是 v ( f ) 的非触点则d a ( v ) 2 i v ( f ) i 一2 ；如果u 是v ( f ) 的1 一触点则d g ( t ，) 2 i v ( f ) i 一1 ；如果u 是v ( f ) 的2 一触点则d g ( 耖) s2 i v ( f ) l ；如果u 是y ( f ) 的孓触点则d c ( u ) s2 i v ( f ) i + 1 我们将考虑以下几种情况 情况1 ：f = 2 设r 、尼是g a 的两个连通分支根据定理1 2 3 ( i i i ) 可得i ( 只，如) i = 1 ，并且e ( 待1 ，2 ) 中的顶点除了一个1 一触点外都是非触点由事实1 2 1 可 得i 矿( e ) i 2 ( i = 1 ：2 ) 显然必然有非触点y l e v ( r ) 、v 2 v ( f 2 ) ，并且1 1 1 、 0 2 是两个非邻顶点因此d o ( u 1 ) + 如( v 2 ) 2j v ( 日) j - 2 + 2 i v ( 足) j - 2 = 2 ( 1 v ( r ) i + i y ( 恳) d - 4 = 2 n - 4 ；另一方面，根据定理3 2 2 的条件有d a ( 秒1 ) + d g ( 也) 2 佗- 3 ， 因此2 n 一3 d c ( v 1 ) + d a ( v 2 ) 2 n 一4 ，矛盾 情况2 ：f 3 因为z + j | ，+ z 2 ，不失一般性，不妨设r 和足是g a 中任意两个满足 l i e ( f ，g ) l 3 ( i = 1 ，2 ) 的连通分支有以下断言 断言3 2 2 1 必存在两个非邻顶点 l j l y ( r ) 、忱y ( f 2 ) 使得如0 1 ) + 如( 忱) 2 ( i v ( r ) l + i y ( r ) 1 ) 一1 成立 显然：( q ) e 中任意顶点必是y ( e ) ( i = l ，2 ) 的一个非触点，或者1 一触 点，或者2 一触点，或者3 - 触点；( p ) 如果e 中有一个非触点，则此非触点不与 乃( i ，歹= 1 ，2 ，i 歹) 中任何顶点关联；( 7 ) 如果尻中有一个3 - 触点，则必同时还 有个非触点在e ( = 1 ，2 ) 中因为l y ( r ) l 2 ( i = 1 ，2 ) ，y ( r ) ( i = 1 ，2 ) 中