（应用数学专业论文）树图和大次和条件图的上可嵌入性研究.pdf

学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究 成果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经 发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在 文中作了明确说明并表示谢意。 作者签名：i 轴日期：碰! 厶如 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有 权将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 学位睁文作者签石卸导师签名： 像稀 日期：碰! ! ! ：! 摘要 自从e n o r d h a u s ，b s t e w a r t 和a w h i t e 等人引进图的最大亏格的概念 以来，最大亏格及其相关概念图的上可嵌入性嵌入引起人们的广泛关注由 r d u c k 图的亏格插值定理知：考虑图g 的所有可定向嵌入的曲面，只需确定它 的亏格r ( g ) 与最大亏格( g ) g 的最大亏格k ( g ) 是指存在最大的整数膏使得 g 在亏格为七的可定向曲面s 上有2 一胞腔嵌入由于图在任意曲面上2 一胞腔嵌入 至少有一个面，由e u l e r 公式知：( g ) ；芦婴】，这里卢( g ) i e ( 6 ) i i v ( 6 ) l + 1 称为圈g 的b e t t i 数如果r ( g ) 芦掣】，称图g 是上可嵌入的 关于图的上可嵌入性，刘彦佩 5 和n e b s k e y 7 分别给出了不同形式的充要 条件；黄元秋和刘彦佩 1 9 】从另一相反角度出发，提供了一个关于不是上可嵌入 图的充要条件由此充要条件，本文主要对一些满足特殊条件的图的上可嵌入性 和树图的上可嵌入性进行专门研究，共分为四章 在第一章中：集中探讨了双圈图的树图的上可嵌入性双圈图以( f 。，z ：) 的树 图是f 。+ z ：一2 正则图，且是上可嵌入的，其最大亏格为： r 施) i 【掣】i 【丝等 坚】 l 孵) 卢( 岛) 型d 婪地“ 二 在第二章中：集中探讨了连通图的( 邻接) 树图的上可嵌入性若图g 可2 胞腔嵌入到可定向曲面s 上，j t c 嵌入s 后至多只有2 个面，称gk s 上是上可 嵌入的。本文证明了如下结果：若图g 是连通图，则g 的邻接树图g f 、树图g ， 都是上可嵌入的 在第三章中：集中探讨大次和条件图的上可嵌入性设g 是k 点连通图，若 对任一 禹，恐，凰+ 。 一独立集均有d ( 蜀) + d ( 盈) + 十d ( 玉+ 。) 一n - - k ( n = i 以g ) ) 则称g 是满足大次和条件的图；我们证明了如下结果：若大次和条件图g 是简 单图，则g 是上可嵌入的本章还指出了，若大次和条件图g 不是简单图，不一 定是上可嵌入的，并分别给出几个不能上可嵌入的大次和条件图 在第四章中：本章给出一个三角等式的初等证明，同时给出了这三角等式 的两种高数证法及一个图论证明，体现了高等数学在解决一些初等问题上的简捷 性和优越性 关键词： 树图，最大亏格，b e t t i 亏数，上可嵌入 2 s t u d i e so ns o m es p e c i f i cu p p e r - e m b e d d a b l eg r a p h s s i n c et h ei n t r o d u c t o r yi n v e s t i g a t i o no fm a x i m u mg e n u sb yen o r c h a u s , s t e w a r t a n d - w h i t e ，m x i m mg e r m sa n dt h e 删i l i t yo f 目讪h a sb e e np a i dg r e a t a t t e n t i o ns of a r i ft h em i n i m u ma n dt h em a x i n u no r i e n t a b l e ( n o n - o r i e n t a b l e ) g e n u so f gr e s p e c t i v e l ya r ek m t h e na l lt h e p o s s i b l e 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 e s o nw h i c ht h e 舯p hgc a nh em 埘d e di m m e d i a t e l y n yh ed e t e r m i n e db yt h et h e o r e mo f rd u c kt h em a x i m u mg e n u s ( g ) o fac o n n e c t e dg r a p hgi st h em a x i m ni n t e g e rk w i t ht h ep r o p e r t yt h a te x i s t sa2 - c e l l u a re m b e d d i n go fgo nt h ea r i e n t a b l es u r f a c e so fg e n u sks i n c ea n y2 - c e l l u a rm b e d d i n gm u s th a v ea tl e a s to n ef a c e ，t h ee l u e r p o l y h e d r a le q u a t i o ni j l p l i e sa nu p p e rb o u n do nt h el 旧x i i i l 眦g e 叫s ( g ) s 乎孕】，w h e r e 卢( g ) 一i 占( g ) i ly ( g ) l + 1 ，a n d 芦( g ) i sk n o w na st h eb e t t in t 皿b e ro ft h ec o n n e c t e d g r a p hg a g r a p h i ss a i d t o b e u p p e r c m b e d d a b l e i f ( g ) ，掣】 o n t h e u p p e r 御b e d d a b i l i t y o f ，l i u 5 a n d n e b e s k y 7 h a d i r i d e s c e n t l y p r o v i d e dd i f f e r e n tn e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n s ；o nt h eo t h e rb a n 7 n - k ( i ；i l h 盯e 俨i v ( g ) 1 ) w ep r o v et h ef o l l o w i n g r e s u l t s ：i ft h es p e c i f i cd e g r e e - s i g ng r a p h gh es i m p l e 蹴t h e ngi su p - e e b e 6 拙l e , o t h e r w i s e , t h et h e o r yi sn 0t r u e , a n dt h el d o t 3 e r p r o v i d es e v e r a lo a n c e “攫a l p l e s i nc h a p t e r4 ：t h i sp a p e rp r o v i d e sa ne l e m e n t a r yp r o o fo ft r i a n g u l a re q u a l i t y m e a n w h i l e 1 cp r o v i d e st w ok i n d sa d v a n c e dm a t h e m a t i c sp r o o fa n dg r a p ht h e o r ym e t h o d st op r o v et h i s t r i a n g u l a re q u l i t y , t h eo n e st h a th a v ee m b o d i e dt h es i m p l ea n dd i r e c tq n m i t ya n ds u p e r i o r i t yo i l s o l v i n gs o m ee l e m e n t a r yp r o b l e m so fa d v a n c e dm a t h e m a t i c s k e yw o r d s ： t r e eg r a p h ，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 ，u p p e re m b e d d a b l e 4 前言 一背景 图论是- - e q 应用极其广泛的数学分支，它是处理离散数学问题的强有力的 工具五十多年来，随着计算机科学、运筹学、信息科学和系统科学的发展，越 来越多的研究者被吸引到这一领域拓扑图论是它的一个重要的领域，更是一个 非常活跃的研究方向它不仅丰富了图论和组合数学本身，而且在物理、化学、 神经网络等学科中有非常广泛的应用象图论其他分支一样，图在曲面上的嵌入 性也有其深厚的根基一著名的四色问题，自从c a y l e y 1 1 8 7 8 年正式公布了著名 的四色问题后，图在一般曲面上的嵌入引起人们的广泛关注在1 8 9 0 年h e a w o o d 2 提出了著名的地图着色问题后，h i l b e r t 等人又将其归纳为引线问题：即在曲 面s ( p 为s 的亏格) 给定( 3 ) 个不同点，能否用简单曲线( 引线) 两两 连接这个点使得这些连线在曲面上互不相交? 就图论的知识而言，引线问题与 确定完全图丘的亏格r ( 咒) 等价，而确定一般图的亏格又是上述问题的推广 从而，为解决引线问题，大量关于图在盐面上的嵌入的研究工作产生了虽然地 图着色问题得以完全解决，然而它却给图论开辟了一个至今不衰的新课题图 在曲面上的嵌入，它为圈的理论研究与应用开辟广阔的前景 曲面通常是指一个紧的，2 一维流形s ( 定向或不定向) 其亏格表示为占岱) 一个连通图g 在曲面s 上的一个2 一胞腔嵌入是指存在一个拓扑同胚映射h ：g s 使得乱h ( g ) 的每一个连通分支与圆盘拓扑等价图g 的亏格r ( g ) 是指最小的整 数g 岱) 使得g 在曲面s 上有2 - 胞腔嵌k ，而图g 的最大亏格( g ) 是指最大的 整数g ) 使得g 在曲面占上有2 一胞腔嵌入1 9 6 6 年r d u c k 3 证明了图的亏格 插值定理：即如果图g 在两个可定向盐面晶和( ms ”) 上都有2 一胞腔嵌入， 那么g 在任意可定向曲面s ( 1 7 1 k ，1 ) 上也有2 一胞腔嵌入因此由图的亏格插 值定理知：考虑图g 的所有可定向嵌入的曲面，只需确定它的亏格r ( g ) 与最大 亏格( g ) 5 图的最大亏格是刻划图在曲面上胞腔嵌入的一个重要的拓扑参数，由 e n o r d h a u s ，b s t e w a r t 和a w h i t e 6 等人在7 0 年代初引进这个概念，至今这 领域仍是拓扑图论中的一个最活跃的领域由于图在任意曲面上的胞腔嵌入至少 有一个面，故由e u l e r 公式知：( g ) 【型掣】，其中芦( g ) t i e ( a ) l i v ( a ) i + 1 二 称为图g 的b e t t i 数同时如果称图g 是上可嵌入的，如果( g ) 。【堂掣】基于 二 在不可定向曲面下，早在7 0 年代末r i n g l e 4 、刘彦佩 5 等独立地证明上述等 号成立，因此对图的最大亏格的研究一般都指在可定向曲面情形下而与最大亏 格相关的是图的上可嵌入性一确定个图最大亏格的最好上界是拓扑图论中 一直感兴趣的问题，因此对图的上可嵌入性的研究是一项很有意义的课题 二图的上可嵌入性的相关研究 图的最大亏格是刻划图在曲面上嵌入的一个重要的拓扑参数，而与最大亏 格息息相关的就是图的上可嵌入性，确定一个图最大亏格( 或其最好上界) 是拓 扑图论中一直感兴趣的问题，对这两者的研究吸引了研究者的广泛关注，大量的 研究成果涌现出来关于图的上可嵌入性，刘彦佩 5 和n e b s k e y 7 分别给出了不 同形式的充要条件；在文 8 中，x u o n g 证明了一个连通图是上可嵌入的当且仅当 亭( g ) 1 ；且r m ( g ) 丛尘三互( 旦许多文献对给定一些限制条件的一些图类的上可 嵌入性进行了大量的研究n e b s k e y 在文 9 中证明了每一个局部连通图是上可 嵌入的在文e 1 0 中证明了每一个局部半连通无环图g 是上可嵌入的若图g 是 这样得来：连接两个具有偶b e t t i 数的上可嵌入图的相交顶点所得到的图，在文 1 1 中，j a e g e r ，p a y a na n dx u o n g 证明了每一个这样的图g 是上可嵌入的在文 1 2 中，s k o v i e r a 证明了每一个直径为2 的无环图是上可嵌入的在文 1 3 中， 证明了下述结论：对于简单图g ，或者g 或者它的补图g 。是上可嵌入的；每一个 2 k - 正则的二部图是上可嵌入的；每一个( 4 k + 2 ) - 正则图是上可嵌入的在文 1 4 中，黄元秋和刘元佩证明了下述结论：无环连通图g 能嵌入某个曲面s 上，使得 每个面的大小不超过5 ( 即短面嵌入) ，则g 是上可嵌入的；每一个( 4 k + 2 ) 一正 则图是上可嵌入的在文 1 5 中，k u n d u 证明了每一个4 一边连通图包含2 个边不 相交的生成树，由此可见每一个4 一边连通图是上可嵌入的由于4 一点连通图必是 4 - 边连通图，故每一个4 一点连通图是上可嵌入的然而存在3 一点连通图是不能上 可嵌入的 1 6 ( 如图所示) 图的上可嵌入性的研究成果不胜枚举，由于篇幅有限这里不再一一阐述 2 0 0 1 2 0 0 4 年本人在华东师大数学系应用数学专业以研究生毕业同等学力申请 硕士学位的研究生课程班学习，在此期间参与了任韩老师的课题研究，在任韩老 师的悉心指导下取得一定的成绩，共完成了几篇文章：其中双圈图的树图已 发表在泉州师范学院学报2 0 0 3 年第4 期 连通图的( 邻接) 树图的上可嵌入性 已发表在泉州师范学院学报2 0 0 5 年第4 期：一个三角等式的图论证明已发表 在西北工业大学高等数学研究2 0 0 5 年第4 期 三基本定义与引理 本文中考虑的图g - ，e ) 均指有限，无向的连通图一个图g 称为简单图， 如果它不含重边和环若连通图g 的生成予图是树，则称日是g 的生成树其 他未涉及的术语与记号均可参见文 1 7 与 1 8 定义1 ：图g 的最大亏格( g ) 是指存在最大的整数量使得g 在亏格为k 的可定 向曲面s 上有2 一胞腔嵌入 定义2 ：如果( g ) 曩【曼! 婴】，其中卢( g ) 。i ( g ) i - i v ( c ；) l + 1 ，则称图g 是上可 嵌入的 定义3 ：设，为连通图g 的一棵生成树，g 五( 丁) 的一个连通分支称为奇分支， 如果有奇数条边；否则，称为偶分支。记号；( g ，t ) 表示g j e 仃) 中奇分支的 个数称亭( g ) 一m i n ( g ，r ) 为g 的b e t t i 亏数，这里m i n 取遍g 的所有生成树z 定义4 ：对g 的任意边子集a e ( g ) ，c ( g 爿) 表示g a 的连通分支数， 7 6 ( g 一) 表示g 爿中具有b e t t i 数为奇数的连通分支数 定义5 - g 是连通图，矿仃) - 佤，正，瓦) 是g 的生成树集，以矿口) 为点集， 霉与0 邻接的充分必要条件是五与l 有p 一2 条公共边( 即霉与i 中只有一条边 不同) ，其中p 是g 的点数，称得到的新图为g 的树图，记为g ， 定义6 ：若定义5 中的i 与l 中不同的两边在原来的图g 是相邻的这条件加到 上述定义，所得到的图称为g 的邻接树图，记为q 在g ，中，若正与t 是相邻 点，称l 与l 是( g 的) 相邻树 引理ae t ：一个连通图g 是上可嵌入的当且仅当c ( g 爿) + 6 ( g 爿) 一2 s i a i ，对 任意4 e ( g ) ；且亭( g ) 2 。m 觚a x g ) ( c ( g 爿) + 6 ( g 爿) 一卜h ) 引理b 8 ：一个连通图g 是上可嵌入的一亭( g ) s 1 。够) 一旦学 第一章双圈图的树图的最大亏格 1 1引言 图的最大亏格是刻划连通图在曲面上嵌入的一个重要的拓扑参数，而与最 大亏格息息相关的就是图的上可嵌入性确定一个图的最大亏格( 或找出这个图 的最好上界) 是拓扑图论中一直感兴趣的问题关于图的上可嵌入性，人们进行 了大量的研究，比如文 5 和文 7 分别给出了不同形式的充要条件；文 1 9 从另 一相反角度出发，提供了一个关于不是上可嵌入图的充要条件树图是图论中的 一个重要概念。在计算机科学、电网络设计等学科中有着广泛的应用，人们对树 图也做了大量的研究工作，c u m m i n s 2 0 讨论了树图的h a m i l t o n 一圈；l i u 2 t 讨 论了无环拟阵的基因是p 连通的，其中p 是劈的余秩；l i u 2 2 讨论了简单连 通图的邻接树图的连通性质；还有很多关于树图比如进行谱方面的研究，这里就 不一一列举因此对双圈图的树图的上可嵌入性的研究及找出双圈图的树图的最 大亏格是一个很有意义的话题本章证明了下述结果：( 1 ) 双圈图4 ( f 。，i ：) 的树 图是f 。+ z ：一2 正则图 ( 2 ) 双圈图z 。( f 。，i ：) 的树图是四边连通的，故是上可嵌 入的 ( 3 ) 双圈图4 ( f l ，f ：) 的最大亏格为： r 。辑) | 掣】i 【丝竽 坚】 l ( g ，) b ( a ，) 。丝盥些二尘“ 1 2定义及引理 定义1 1 ：记具有月个点的圈为q ，将圈c f l 的某一点与圈c ，：的某一点粘合或 分别和某一条路的两个1 度顶点粘合后，所得到的图记为a ，然后以a 为导出子 图，用其若干个顶点为根长出树图后，得到的，l 阶连通图称为双圈图，记为 以( f 。，：) 定义1 2 ：g 是连通图，y 仃) ；佤，l ，t ) 是g 的生成树集，以y 仃) 为点集， 9 i 与t 邻接的充分必要条件是互与0 有p 一2 # a f f i x ( u p t , 与l 中只有一条边 不同) ，其中p 是g 的点数，称得到的新图为g 的树图，记为g ，同时，在g 中， 若互与l 有p 一2 条公共边，称正与弓是相邻树 引理1 1 1 2 3 ：( m e n g e r 定理) 图g 是七边连通的当且仅当g 中任意两个相异顶 点被至少七条边不重的路所连 引理1 2 1 2 4 ：连通图的树图是连通的 引理重3 【2 5 】：每个4 边连通图都是上可嵌入的 引理1 4 1 2 5 1 ：连通图g 是上可嵌入的，则y 。( g ) 。【旦婴】 引理1 5 】：设图g 有p 个点g 条边，若g 不是树，则歹。( g ) 一q p + 1 引理1 - 6 ：围长为1 的单圈图g ( 只含一个圈的连通图) 的树图g ，同构于完全 图墨。 证明：单圈图g 仅含一个圈，不妨设这个圈为c f = v 1 e 1 v 2 e 2 v 3 v l e i v l ，则删 去c ，中任意一条边q 都得到g 的一生成树，记为五0 i s ) 所以， g ，的点集为：v ( a ，) 一亿，五，正 又显然有：五中仅有一边和正( ，一i ) 中的一边不同，其余的边相同， 即 l 与l 相邻a _ j , i 、，一1 ，2 ，f ) 所以， 互的相邻顶点为正( ，- ，一l 2 ，f ) ，即互( 1 墨isz ) 的度为l 一1 所以， g r 是一个具有z 个点的完全k t - l ，即q k i 。 证明完毕# 1 3 主要结果 为了叙述方便，下面设f 1 、1 2 苫3 定理1 1 ：双圈图一。( f ，f ：) 的树图是连通的z 。+ f 。一2 正则图 证明：由双圈图的定义及引理2 2 知，其树图是连通图 记双圈图g = 以( f 。，1 2 ) 的树图为q ，圈c 为：c j ia v l e l v z e 2 v ，v l l e l t v - 圈c b 为：c f ：；“1 “2 ，2 3 l l i ，1 , 2 u l 其中： v j 和e j 分别是c 的点和边( 1 暑s1 1 ) ； “j 和，分别是c h 的点和边( 1 s ，主z z ) 方便起见，用毛表示g 中删去边q 和边所得的生成树( 1 妄i j f t ，1 量j sz ：) 则g 的生成树集为y ( 丁) - 互，五：，k ，e ，毛， ，共f 1 z ：个 所以，g r 的点共有l ，- 1 2 个 由于，一弓：+ f s ：一，j 1 ( 1 s is 1 1j - - ，：，且1 s ，t ，：量z z ) ， 即与：有，l 一2 条公共边，则气与气( 1 s f s ，t ，- ，：，且1 5j 1 , ，：sz ：) 相 邻 同理：矗与毛( 1 f 1 ，i 2 量f 1 ，i l - f 2 ，且1 s ，f 2 ) 相邻 敌，、五 与毛b 相邻的充分必要条件是一f 2 莉t j ：( 1 s i ii ：s f l 1 sj + 1 , ，2 墨1 2 ) 所以，在g r 中毛的度为l ，+ 如一2 ， ( 1 s i5 1 1 ，1 sjs f ：) 所以，以( f 。，f 2 ) 的树图g r 是连通的l ，+ z 2 2 正则图 结论得证# 定理1 2 ；双圈图g 一以( f 。，l ：) 的树圈g ，是4 边连通的 证明：g r 的任意两个相异顶点毛 和气b 必有4 条边不重的路相连，事实上， ( 1 ) 若，i 2 ，。，2 两两不等，取 只一毛 毛 i ：，：己一毛 z 2 j l z 2 j ： b - 毛 i ：a 只一毛 i ：气止 则 置、最、只、只为这种情况下连t 。 和互：j ：的4 条边不重的路 ( 2 ) 若，i ：，j ，：中有且仅有两个相等，又可分以下三种情况 ( 2 1 ) 若i 1t i 2 ，则取 1 1 只毛 毛&只2 毛 k 毛矗 弓毛 乃 毛 毛，： 只= z l l ： 乃，n 五： ( 2 2 ) 若i ，- ，则取 b 。z l j ：毛， b ；气 王凶霉：l 与。b 王：l 只。五：t ：z 2 b ( 2 3 ) 若i 1 一j 2 ，则取 墨。毛 只zz l z 2 l 与。气 瓦 只4 正：t 则 置、只、只、只分别为上面几种情况下连 和瓦j ：的4 条边不重的路( 若 i ：一，。或f ：- j ：骑。一j ：，只要重新标号，则和上面三种情况完全一样) ( 3 ) 若- 如一j ，- j ：，则取整数j ，满足l s ，3 且矗，j 。且j ：- j ，取 置z i l 昱。毛矗 与乃“厶毛l 只。瓦乃 巧， ，： 则 置、只、只、只为这种情况下连毛 和l ，n 的4 条边不重的路( 若出现另三个 相等的情况，同理可证) 综上各种情况，再由引理1 3 知结论成立证明完毕# 定理1 3 ：双圈图g - 4 ( f 1 ，f ：) 的树图g 的最大亏格为： r 施) _ 掣一阻盟 业】 、兀鸭) ( g ，) 。型d 幽+ 1 证明：由定理1 1 知，。q 是连通的z + f ，一2 正则图，则 岛的边数为 生：生：垡! ! ! = 型 2 所以 p ( g ，) 。生：生掣一l 。 1 2 + 1 ，生：! 掣+ 1 又q 是4 边连通图，即g ，上可嵌入， 所以 麒g r ) i 【掣】| 【丝学1 再由g ，是连通的非树图( 五。，互：，死两两相连构成g ，的一个3 圈) ， 所以 歹水r ) ip ( a r ) - 姓半+ 1 证明完毕# 由定理1 2 可迅速得到： 推论：双圈图g 一4 ( f 1 ，f ：) n 树n g ，是上可嵌入的 前面的讨论是建立在、z ：3 的前提下，下面给出这个条件外的双圈图 g 一4 ( f 1 ，z ：) 的树图q 其他情况： ( 1 ) 当l 。一z ：- 1 时，则圈c f i 和圈c ，是环，把两个环删去可得到 g - a ( f l ，l ：) 的唯一一棵生成树，所以g ，是一个点的平凡图 ( 2 ) 当f 。一l ：一2 时，则圈c l 和圈c 都是c ：，两个圈中各删去一条边即 得g 的一棵生成树，所以g ，是一个4 个点的圈c 4 显然q 是上可嵌入的，且 y 。( g ，) - 0 ，。帏) 一1 ( 3 ) 当、z ：一个是2 另一个是3 时，n _ k 分析，q 是连通的3 正则图， 易验证q 是上可嵌入的且g ，是非树图，所以，y 。( g ，) 一2 ，歹。( g ，) 一4 ( 4 ) 当? ，、z 2 一个是1 ，而另一个不是1 时，不妨设一l z ：芑2 ，则圈c f l 是 环，删去环q 的图记为4 ( f ：) ，是一个单圈图，易看出g 一4 ( f 1 ，f ：) 的生成树集 和以( f ：) 的生成树集完全相同，由引理1 6 知单圈图砖( f ：) 的树图是个完全图 吒一所以，当l 。、f ：一个是1 ，而另一个不是1 时，双圈图g 的树图与删去环之 后的单圈图的树图同构，即双圈图g 一以( f 。，：) 的树图坼m k l 1 ，其中z * z ，z ： 显然g t 也是上可嵌入的，且当l ，l ：= 2 时，g ，是一条边所组成的图， 忡加。：1 1 1 2 乏3 时帏) | 【坐竽】i - 施卜学+ 1 ( 1 = 1 2 ) # 1 4 第二章连通图的( 邻接) 树图的上可嵌入性 2 1引言 树图是图论中的一个重要概念，在计算机科学、电网络设计等学科中有着广 泛的应用，c u m m i n s 2 0 讨论了树图的h m n i l t o n 一圈；l i u 2 2 讨论了简单连通 图的邻接树图的连通性质；徐睿 2 6 在此基础上研究了邻接树图的连通度，本章 将在这基础上进一步讨论连通图的树图的拓扑性一一上可嵌入性自从 n o r d h a u s 等引入图的最大亏格的概念以来，图的最大亏格以及图的上可嵌入引 起了入们的广泛关注，是拓扑图论的一个点之一关于图的上可嵌入性，文 5 和 文 7 分别给出了不同形式的充要条件；文 1 9 从另一相反角度出发，提供了一个 关于不是上可嵌入图的充要条件本章证明了：连通图的树图和邻接树图都是上 可嵌入的 2 2定义及引理 定义2 1 ：g 是连通图，y - 识，t ，) 是g 的生成树集，以y p ) 为点集， 王与l 邻接的充分必要条件是i 与l 有p 一2 条公共边( 即正与中只有一条边 不同) 其中p 是g 的点数，称得到的新图为g 的树图，记为g ， 定义2 2 ：若定义l _ i 中的z 与r 中不同的两边相邻这条件加到上述定义，所 得到的图称为g 的邻接树图，记为e 在q 中若正与i 是相邻点，称z 与l 是 ( g 的) 相邻树 引理2 1 2 5 b 每个4 边连通图都是上可嵌入的 引理2 2 1 2 5 ：连通图g 是上可嵌入的充要条件是亭( g ) g1 ，其中 亭( g ) 一m i n 偕( c ) l ( c 一g 的余树c 的奇分支的数卧 引理2 3 1 2 6 ：若图g 的点的最小度记为d ( g ) ，则连通图g 的邻接树图g 。满 足：( g | ) 6 ( q ) 由邻接树图和树图的定义可得： 由邻接树图和树图的定义可得： 引理2 。4 ：连通图g 的邻接树图g l 是树图g t 的生成予图，且( g ，) 主七( g ，) ， 由引理1 、引理3 和引理4 可得： 引理2 5 ：若连通图g 的邻接树图g ，满足6 ( q ) z4 ，则g 的邻接树图与树图都 是上可嵌入的 2 3 主要结果 记栉点坍边连通图为c ( n ，m ) ，则州n 一1 若m n 一1 ，则g o ，棚) 是一棵树， 它的( 邻接) 树图为平凡图简称g 0 ，n ) 为单圈图( 这个图中只含一个圈) ；简 称c ( n ，月十1 ) 为双圈图( 这个图中只含两个或三个圈) 若连通图g 中含有环和割 边，由邻接树图和树图的定义知，删去图g 中的环和收缩所有割边得到的新图的 邻接树图和树图分别与图g 的邻接树图和树图同构，所以，以下除非特别说明， 出现的图都是无环无割边的连通图 定理2 1 ：有一个割点z 。的双圈图g g i u g ：，其中g 。、g ：都是圈且 g 1n g ：一忸。 ，则g 的邻接树图和树图都是上可嵌入的 证明；( 1 ) 若g l 、g ：都是2 圈，则g 的邻接树图和树图都与4 圈同构，显然 圈是上可嵌入的( 对于珂圈有亭( c 。) 一1 ) ( 2 ) 若g 1 、g ：一个是2 圈另一个是p - 3 ) 圈 当r 一3 时，g 的邻接树图和树图都与图( 1 ) 同构，图( 1 ) 中画浓线的部分为这 个图的生成树，删去树上的边后得到的余树是一个连通图，它的奇分支的数目为 0 ，由引理2 知，g 的邻接树图和树图图( 1 ) 是上可嵌入的； 当，la4 时，g 的邻接树图与图( 2 ) 同构，图中画浓线的部分为这个图的生成 树，删去树上的边后得到的余树也是一个连通图，它的奇分支的数目至多为1 ， 即g 的邻接树图是上可嵌入的为了得到g 的树图，对图( 2 ) 进行加边，在图 1 6 ( 2 ) 中2 n 个3 度顶点排成两行，上面这一行的任意非相邻顶点连边，同时， 对下面这一行的任意两个非相邻顶点连边这样可得到一个新的图就是g 的树 图，此时，取g ，的生成树仍为图( 2 ) 中画得比较浓的部分，删去这生成树的所 有边后，所得的余树显然仍是只有一个分支的连通图，所以，这余树的奇分支数 至多是1 ，所以，g ，是上可嵌入的 ( 3 ) 若两个圈g ，、g 2 的长都不小于3 ，任取g 的一棵生成树t ，则r 是分 别删去图g ，、g ：中的一条边得到的，设t 是删去g i 中的边e ，获得，则丁+ e i 含 有g l 这个圈，设圈g f 中与巳相邻的边为q ，、岛：，从而，r + e ；一e d ( j - 1 , 2 ) 是r 的相邻树，f 一1 , 2 所以，r 的相邻树共4 棵，所以，在g ，中r 的废等于4 ， 即，6 ( g f ) - 4 ，所以，g 的邻接树图和树图都是上可嵌入的。 综上所述，命题得证# 定理2 2 ：叶子图( 分别把三条路的一个一度顶点粘合在一起，再把另外三个 一度顶点粘合在一起所得到的图简称叶子图) 的邻接树图和树图都是上可嵌入 的。 证明：设三条路分别为昂只、只，其中l , m ，阼为各路的顶点数，简记这叶 子图为g = a ( f ，m ，n ) ( 1 ) 显然a ( 2 ，2 , 2 ) 的邻接树图和树图都是三圈，是上可嵌入的 ( 2 ) a ( 2 ，2 ，3 ) 的邻接树图和树图都是轮图- 墨+ c 4 ，从峨中删去它的 棵生成树k 。( 有一公共顶点的4 条边) 得到的余树是c 。并上一个孤立点，即 亭o 吃) 一0 ，所以，a ( 2 ，2 ，3 ) 的邻接树图和树图是轮图暇；k + c 4 是上可嵌入的 ( 3 ) g = 彳( 2 ，2 ，n ) ( 玎4 ) 的邻接树图如 图( 3 ) ，且图( 3 ) 中3 度点的数目为2 - o 一1 ) 个图中画得比较浓的部分为图( 3 ) 的生成树， 删去这生成树的所有边后，所得的余树的奇分 1 7 ( 3 ) 支数至多是1 ，即，亭( g f ) 1 ，所以爿( 2 ，2 ，1 ) ( ，lz 4 ) 的邻接树图是上可嵌入的 为了得到g 的树图，把图( 3 ) 的顶点分为3 类：在图( 3 ) 中2 仍一1 ) 个3 度点 排成两行，在上面这一行的称为第一类，下面这一行的称为第二类，唯一一个4 度点单独一类称为4 度点现在对图( 3 ) 加边，首先，把4 度点分别与第一类和 第二类中的每个点连边( 但图( 3 ) 中原来与4 度点相邻的顶点不再与4 度点连 边) ；其次，第一类里的任意两个非相邻顶点连边，同时，对第二类里的任意两 个非相邻顶点也连边这样可得到一个新的图就是g 的树图，此时，取g ，的生成 树仍为图( 3 ) 中画得比较浓的部分，删去这生成树的所有边后，所得的余树显 然也是只有一个连通分支的连通图，所以，这余树的奇分支数至多是1 ，故，研 也是上可嵌入的 ( 4 ) g = 4 ( f ，小，丹) ，若j 2 , m 苫3 , n 3 ，任意取g 的一棵生成树t ，则r 是 分别从g 的两条不同的路上各删去一条边得到的，不妨设被删去的边为e 。、e ：， 则r + e i 是一个含有边e ，且圈长不小于3 的圈，设圈上与e i 相邻的边为e j l 、e i ：， 则r f t + e j 一( ，1 ，2 ) 是丁的相邻树，o - l 2 ) 所以，t 的度至少是4 即 6 ( q ) 之4 ，所以，q 、g ，都是上可嵌入的 综上所述，命题得证# 定理2 3 ：单圈图g ( n ，行) 的邻接树图和树图都是上可嵌入的 证明：无环无割边的单l 翻m g ( n ，l 1 ) 其实就是一个豇圈c 。 ( 1 ) 若玎一2 ，则c ：的邻接树图和树图都是一条边，显然是上可嵌入的 ( 2 ) 若n 3 ，任意删去圈上一条边得到它的一棵生成树，共h 棵。任取两 棵生成树r 、z ，是分别删去g o ，1 ) 的边e 、e 得到的，若边e 、e 相邻，则这 两棵生成树相邻，又e 中的每一条边只有两条相邻边，所以e 的邻接树图是有 n 个点的2 正则图，即圈q ，显然是上可嵌入的由于g 0 ， ) 是圈，所以它的任 两棵生成树作为树图的顶点总是相邻的，所以，g o ，厅) 的树图是完全图k ，取蚝 1 8 的生成树墨。，从髟中删去树上的边，所得到的余树是一个连通图并上一个孤 立点，所以，余树的奇分支数至多为1 ，其中k 1 。是共一个顶点的n - 1 条边， 故，g ( n ，n ) 的树图k 。也是上可嵌入的结论成立# 引理2 6 ：双圈图g 0 ，n + 1 ) 的邻接树图和树图都是上可嵌入的 证明：无环无割边的连通图c ( n ，n + 1 ) 只能有两种图： ( 1 ) 有一个割点的双圈图，即gt g lu g ：，g 。、g ：都是圈且 g 1 n g 2 一缸o ( 2 ) 6 ( n ， + 1 ) 是叶子图 由引理5 和定理1 知，结论成立# 引理2 7 ：连通图g 0 ，撑+ 2 ) 的邻接树图和树图都是上可嵌入的 证明：关于无环无割边的连通图g o ，月+ 2 ) 的周长分下面两种情况进行讨论， ( 1 ) 若g ( n ，万+ 2 ) 的周长为2 ，则连通图c ( n ，n + 2 ) 只有下面4 图，图( 4 ) 一： 而( 4 ) 一( 7 ) 这4 个图的邻接树图和树图分别如下：图( 4 ) 的邻接树图和树图都与k 。 同构，显然是上可嵌入的：图( 5 ) 的邻接树图和树图都与图( 8 ) 同构，图中画浓 线的部分为这个图的生成树，删去树上的边后得到的余树的奇分支的数目为o ， 即图( 5 ) 的邻接树图和树图图( 8 ) 是上可嵌入的；图( 6 ) 和图( j 7 ) 的邻接树图和树图 都为图( 9 ) ，且图中线画得比较浓的部分组成该图的一棵生成树，删去这生成树 边所得到的余树的奇分支就1 个，所以，这个图是上可嵌入的 ( 2 ) 若g ，l + 2 ) 的周长至少为3 ，任取g o ，n + 2 ) 的棵生成树t ，由于r 的边数是露一1 ，所以f 是由g ( n ，n + 2 ) 删去3 条边得到的设被删去的边为e ，、e ：、 e ，则r + e i 含有一个圈且这个圈含有边g ；( f 1 1 , 2 、3 ) ，且r + e f ( i ；1 , 2 、3 ) 中 有一个所含的圈圈长不小于3 ( 否则，同时把e 。、e ：、e 3 加到r 上是一个周长为 2 的图，与a ( n ，n + 2 ) 的周长至少为3 矛盾) ，不妨设r + e 。中所含的圈圈长不小 于3 ，且设圈中与e ，相邻的两条边为厂1 、，2 ，令lt z + e 。一九，一1 , 2 ，贝, j r j 为 丁的相邻树，1 1 , 2 同理，r + 岛含有一个圈且这个圈含有边e 。，设这个圈中与 e i 相邻的一条边为，令正一t b e ，一一，则i 为t 的相邻树，i t2 3 所以，r 的 度至少是4 ，所以，6 ( g ，) 4 ，所以，q 、g ，都是上可嵌入的 综上所述，命题得证# 引理2 8 ：连通圈g 伽，m ) l jm 童刀+ 3 的邻接树图和树图都是上可嵌入的 证明：任取g ( n ，m ) 的一棵生成树r ，由于r 的边数是，l 一1 ，所以f 是由 a ( n ，t n ) 删去m 一竹+ 1 条边得到的设被删去的边为e 1 、e 2 、e ， ( s - m n + 1 乏4 ) ，则r + e 。含有一个圈且这个圈肯定含有边乞，设这个圈中与 q 相邻的一条边为，令正一t + e 。一e 0 则五为t 的相邻树，it 1 , 2 、s 又 s z4 ，所以，z 的度至少是4 ，即，6 ( g ，) 之4 ，故，g 、g 都是上可嵌入的 结论成立# 下面给出本文的主要结果： 定理2 4 ：连通图( 可以有环或割边) 的邻接树圈和树图都是上可嵌入的 证明：若连通图g 含有环或割边，删去g 所有的环和同时收缩g 的所有割 边得到的新图的邻接树图和树图分别与g 的邻接树图和树图同构删去g 中的 环后得到的图记为g ，设g 的点数和边数分别为疗、m ，收缩g 的所有割边 得到的新图虿= g o ，州) 的点数和边数分别为n 、m ，则有h 一拼= 歼一坍，所以 2 0 对于连通图g ，必可转化为唯一的无环无割边的连通图g 0 ，m ) 的情况来考虑， 而无环无割边的连通图g 0 ，) 若不是树可根据h 一珊的值分成上面四种情况， 即定理2 3 、引理2 6 、引理2 7 、引理2 8 所以，这定理的结论成立# 第三章大次和条件图的上可嵌入性 3 1引言 自从n o r d h a u s 等引入图的最大亏格概念以来，图的最大亏格以及图的上可 嵌入性引起了人们的广泛关注设s 为一个可定向曲面( 曲面，这里是指一个紧 的2 一维闭流形) ，一个图g 在s 上的一个2 一胞腔嵌入是指g 能画在s 上使得边与 边之间除顶点外不再相交，且在s 去掉g 的顶点与边之后的每个连通分支与圆盘 同胚；而图的最大亏格( g ) 是指最大的整数七使得图g 的一个2 一胞腔嵌入到可 定向的曲面& 上由e u l e r 公式，有( g ) 引旦婴】，这里卢( g ) 。l e ( 6 ) l i v - n - k ( n = i 以国1 ) ，则称g 是满足大次和条件的图 定义3 3 - 对于任意的一e ( g ) ，c ( g o ) 表示g 4 的连通分支数，丑( g 御： ( 州尸是g 、爿的一个连通分支，r d ( f ) z 1 ( m o d 2 ) ) ，6 ( g 爿) - i b ( g a ) 定义3 4 ：对于g 4 的两个不同连通分支r 最 e ( f ，h ) 一 p h v l u e v ( f ) ，v e v ( h ) ， e ( f ，g ) 一 e 一“v i 球y ( f ) ，v e v ( f ) 引理3 1 7 ：若g 是一个连通图，那么 ( 1 ) g 是上可嵌入的当且仅当c ( g 彳) + 6 ( g 月) 一2 川，对任意的彳e e ( g ) ； ( 2 ) 亭( g ) 一m a x j 缸( g 】 c ( 6 a ) + b ( g a ) - a i - i 引理3 2 1 9 ：g 是一个连通图，如果g 是不能上可嵌入的，那么存在 a e ( g ) ，满足下列性质； ( i ) c ( g a ) - b ( g a ) 乏2