（基础数学专业论文）拓扑图论中的有关问题.pdf

拓扑图论中的有关问题 摘要 拓扑图论是目前国际上一个非常活跃的图论分支，其中对图的拓扑 参数一图的嵌入亏格的研究又是十分重要的课题之一，它是刻划图在某 个定向曲面上是否有二包腔嵌入的一个特征参数而由亏格分布的插值 定理可知，我们只要确定图的最小亏格( 简称亏格) 和最大亏格本文主 要研究了这两个参数，具体内容如下： ( 1 ) 设g 为图，用u ( g ) 和g ( v ) 分别表示图g 的边覆盖数和围长结 合图g 的边覆盖数和围长等条件，本文得到了b e t t i 亏数( g ) 的一个上 界，进而也就得到了最大亏格协( g ) 的一个下界 ( 2 ) 结合垂边形2 - 因子条件，确定了一类上可嵌入图类，推广了相 关文献结果，从而综合已有结果较完整的刻画了这类图的上可嵌入性情 况 ( 3 ) 讨论图的上可嵌入性与直径的关系，得到一些新的上可嵌入图类 进而补充了这方面的结果 ( 4 ) 利用电压图及其覆盖图的嵌入理论，得到了一类剪刀积图的亏格， 这一结果可视为目前在研究这类图的亏格上的个补充，且较大程度上 推广了相关文献的主要结果 关键词：上可嵌入性；最大亏格；b e t t i 亏数；边覆盖数；亏格；剪刀 积图；电压图 拓扑图论中的有关问题 a b s t r a c t a tp r e s e n t ，t o p o l o g i c a lg r a p ht h e o r yi sav e r ya c t i v ec o m p o n e n to fg r a p ht h e o r y i nt h ew o r l d ，a n di n v e s t i g a t i n gt h et o p o l o g i c a lp a r a m e t e ro fg r a p h ( t h eg e n u so f g r a p h ) i sav e r yi m p o r t a n ts u b j o c t i ti sac h a r a c t e r i s t i cp a r a m e t e rt h a td e t e r m i n e s w h e t h e rag r a p hh a sa2 - c e ue m b e d d i n gi nac e r t a i no r i e n t a b l es u r f a c e i ti sk n o w n f r o mt h ei n t e r p o l a t i o nt h e o r e mo ft h eg e n u so fg r a p h ，w eo n l yc o n s i d e rt h em i n i m u m a n dt h em a x i m u mg e n u so fg r a p h i nt h i sp a p e r ，w em a i n l yi n v e s t i g a t et h et w o p a r a m e t e r sa n do b t a i n sf o l l o wr e s u l t s ： ( 1 ) l e tg b eag r a p h ，a n dl e tu ( g ) b et h ee d g ec o v e r i n gn u m b e ro fg ，a n dg ( c ) b et h eg i r t ho fg c o m b i n i n gw i t ht h ec o n d i t i o n so ft h ee d g ec o v e r i n gn u m b e ra n d g i r t h ，w eo b t a i nau p p e rb o u n do fb e t t id e f i c i e n c y 专( g ) ，a n dw eg i v eal o w e rb o u n d o nt h em a x i m u mg e n u s ( 2 ) c o m b i n i n gw i t ht h ec o n d i t i o no f4 - q u a d r a n g l e2 - f a c t o r ，w eg i v ed a s s e so f u p p e re m b e d d a b l eg r a p h s b a s e do nt h ek n o w nr e s u l t s ，w ec h a r a c t e r i z ee n t i r e l yt h e u p p e re m b e d d a b i l i t yo fs u c hc l a s s e so f 日a p h 8c o n t a i n i n ga4 - q u a d r a n g l e2 - f a c t o r ( 3 ) b yi n v e s t i g a t i n gt h er e l a t i o n s h i pb e t w e e n t h eu p p e re m b e d d a b i l i t yo fg r a p h s a n dt h ed i a m e t e ro fg ，w eo b t a i ns o m en e wu p p e re m b e d d a b l eg r a p h s ，a n dt h e n w ec a nc o m p l e m e n ts o m er e c e n tr e s u l t so ft h eu p p e re m b e d d a b l eg r a p h sa b o u tt h e d i a m e t e ro fg ( 4 ) w i t ht h eh e l po ft h et h e o r yo fe m b e d d i n g so fav o l t a g eg r a p ha n d i t sc o v e r g r a p h ，w eo b t a i nt h eg e n u so fac l a s so ft e n s o rp r o d u c tg r a p h m e a n w h i l e ，w ef u r t h e r g e n e r a l i z es o m er e s u l t si nr e c e n tp a p e r s k e y w o r d s ：u p p e re m b e d d a b i l i t y ；m a x i m u mg e n u s ；b e t t id e f i c i e n c yn u m b e r ； e d g ec o v e t i n gn u m b e r ；g e n u s ；t e n s o rp r o d u c tg r a p h ；v o l t a g eg r a p h i l l 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究所取得的研究成果除了文中特别加以标注引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写的成果作品对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完 全意识到本声明的法律后果由本人承担 学位论文作者签名：年 月日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，研 究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分 内容编人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密口 ( 请在以上相应方框内打奠、井) 作者签名： 导师签名： ( 躯乏 凄己彳乙 日期：叼年t 1 月y 日 日期：0 7 年7 月7 日 拓扑图论中的有关问题 第一章引言 图论是组合数学的一个主要组成部分，近几十年里，它已经发展成 数学的一个重要分支由于图论本身的魅力和其在信息社会中一些学科 领域诸如计算机，运筹学，系统工程以及物理学，电子学，生物学，化学 等方面的广泛应用，因此，越来越受到科学界尤其是数学界的重视和关 注随着组合数学，代数学，拓扑学以及概率方法与图论的结合，现代图 论除了传统的研究领域外已发展为包括代数图论，拓扑图论，以及随机 图论等分支在内的多个新的领域，极大地促进了图论的发展 拓扑图论是目前国际上一个非常活跃的图论分支其中对图的拓扑 参数一图的嵌入亏格的研究又是一个十分重要的课题之一曾有很多图 论学者都投身子这方面的研究，但随着其研究的深入，它越来越多地与 其它数学分支相互交叉，相互影响，使之成为目前这方面研究的重要发 展趋势确定图的亏格早期工作归功于r i n g 著作一般地，确定图的亏 格从计算难度上是n p - 完全问题目前知道亏格的图类非常少，如确定 完全孓部图虬 t r 的亏格也是一个公开问题图的最大亏格的研究主要 表现在如下几个方面： ( 1 ) 特征结构： 七十年代末，n h x u o n g 借助于图的支撑树上的补图，通过引进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 h x u o n g ，j c h e n 和j l g r o s s 高校教师在职攻读硕士学位论文 等人的工作表明对图的最大亏格的研究往往可以转化为一个特殊的3 正 则图的情形黄元秋教授和刘彦佩教授证明了一个3 - 正则图的最大亏格 等于其最大不可分离独立数，在结构上给出3 - 正则图上可嵌入的充要条 件另外，黄元秋教授和刘彦佩教授通过引进图的扩张运算，研究了扩 张运算与图的b e t t i 亏数之间的内在联系，揭示了图的最大亏格与图的2 - 因子的某些联系然而，在探求图的最大亏格的结构特征上，仍有广阔 的前景 ( 2 ) 上可嵌入性： 一个图是上可嵌入的表明其最大亏格可取到最好的上界虽然l i u i ， x u o n g 2 和n e b e s k y a 分别提供了不同的确定图的上可嵌入性充要条件，黄 元秋教授和刘彦佩教授【4 】研究了图不是上可嵌入的充要条件，但对于什 么类型的图是上可嵌入的尚知不多，现综合已知为上可嵌入的图如下： 所有垂连通图( k u n d a s 1 ) ；所有循环垂边连通图( j a e g e r ，p a y a n 和x u o n g 6 ) ；局部连通的连通图( n e b e s k y 7 1 ) ；局部拟连通的连通图( n e b e s k yi s ) ；4 k + 2 - 正则的连通图( k o v e r i a 【9 】) ；在某曲面上可三角化的图( k l u k o v i t 0 ) ；直径为 2 的简单图( 誊k o v i e r a1 1 1 1 ) ；在曲面上有一个嵌入使得每面边界长均不超过 5 的图( 茑k 丽e r a 【1 2 】) ；n 2 局部连通的连通图( n e b e s k y1 1 3 4 ) ( 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 考虑了孓边连通( 非简单) 图的情形黄元秋教授推广了上 述工作，对任意k - 边连通( 非简单) 图，给出了由图的最小度所表达的图 的最大亏格的下界表达式，证明了最小度趋向无穷大时，最大亏格趋近 最好的上界最近，黄元秋教授研究了图的最大亏格与图的余色数及团 的关系，利用h e a d w o o d 着色定理揭示了图的最大亏格与图的亏格之间的 联系 ( 4 ) 利用拟阵研究图的嵌入及有关算法： - 2 拓扑图论中的有关问题 利用拟阵考虑图的嵌入是人们所熟知的工作t u t t e 和国内刘彦佩教 授等人的工作表明图的平面嵌入的判断可转化为判断拟阵的图性和上图 性m l f u r s t 和j l g r o s s 运用拟阵研究了图的最大亏格嵌入，给出了图 的最大亏格嵌入多项式算法是否存在多项式时间算法来判断图的同构 一直是一个公开性的问题限定图的平均亏格，j c h e n 和j l g r o s s 证明 了存在多项式时间算法来判断图的同构问题 本文受文献f l 】一例的启发，运用和发展了其中某些方法，结合图的其 它参数一边覆盖数，连通度，直径，二因子，点度等条件，得到了一些上 可嵌入图类，以及一些图类的最大亏格下界另外，利用电压图及其覆 盖图的嵌入理论，得到一类剪刀积图的亏格，推广了目前已有的相关结 果 3 - 拓扑图论中的有关问题 第二章基本概念和性质 2 1 基本概念 本文考虑的图，若无指明均指有限无向的连通图，其他未加说明的术 语和记号均同文献 1 4 】一个图g 是指一个有序三元组( y ( g ) ，e ( g ) ，妒g ) ， 其中v ( c ) 是非空的顶点集，e ( g ) 是不与v ( c ) 相交的边集，而惦是 关联函数，它使g 的每条边对应于g 的无序顶点对1 v i = n 称为图g 的阶 称图日为图g 的子图，如果v ( h ) sy ( g ) ，e ( h ) ：ce ( g ) ，并且妇是 惦上的限制g 的生成子图是指满足v ( h ) = v ( v ) 的子图日假如 是y 的一个非空子集以为顶点集，以两端点均在y 中的边的全体 为边集所组成的子图，称为g 的由y 导出的子图，记为g 【叫g 的两个 顶点u ，钞称为连通的，如果在g 中存在从u 到u 的路连通是顶点集 v ( v ) 上的一个等价关系于是存在y ( c ) 的一个分类，把v ( c ) 分成非空 子集，k ，k ，使得两个顶点u ，t ，是连通的当且仅当它们属于同一个 子集k 子图g 陬】，g 【】，g 【吲称为g 的连通分支若g 只有一个分 支，则称g 是连通的；否则，称g 是不连通的若v ( c ) 的子集y 7 使 得v ( g ) 一v 不连通，则y 7 称为v ( v ) 的顶点割k 顶点割是指有k 个元 素的顶点割若g 至少有一对相异的不相邻顶点，则g 所具有的k 顶点 割中最少的k ，称为g 的连通度，记为k ( g ) 若k ( g ) k ，则称g 为k 连 通的对v ( v ) 的子集s 和，用慨s 1 表示一个端点在s 中，另一个端 点在中的所有边的集合所谓g 的边割是指形为峨s 1 的e ( g ) 的子 集，其中s 是v ( v ) 的非空真子集一个k 边割是指有k 个元素的边割 若g 是非平凡的，g 的所有k 边割中最少的k ，称为g 的边连通度，记为 ( g ) 若( g ) k ，则称g 为k 边连通的 5 - 高校教师在职攻读硕士学位论文 曲面是指一个紧的二维闭流形，分为可定向和不可定向两类本文 考虑图在定向曲面上的嵌入，图g 到曲面s 的一个嵌入7 r ：g s 是g 到s 的一个1 - 1 映射其中，s 丌( g ) 的每个连通分支f 称为嵌入7 r 的 一个面；面f 的边界记为o f ，为g 的一条或多条闭迹组成；面f 的大小 是指a f 包含的边的条数( 重复的边按两条计算) ，一个大小为k 的面简称 为k 一面若嵌入丌中的每个面都是缸面，则称丌为g 到s 上的一个肛 面嵌人一个图g 的最小亏格，简称为亏格，记为，y ( g ) ，y ( g ) 全r a i n r i g 能 嵌入亏格为r 的定向曲面耳) 若嵌入丌是：g _ s ( 圆，则称丌是g 的最 小亏格嵌入7 m ( g ) 全m a x r g 能嵌入亏格为r 的定向曲面母) 若嵌入 丌是：g _ s ( g ) ，则称丌是g 的最大亏格嵌入因为图在任意定向曲面 的2 胞腔嵌入中至少有一个面，由e u l e r 公式易得一个图g 的最大亏格 上界7 m ( g ) 【华j ，其中z ( a ) = i e ( g ) l _ i y ( g ) l + 1 称为图g 的b e t t i 数， 对任意实数z ，h 表示不大于z 的最大整数，司表示不小于z 的最小整 数同时，若7 m ( g ) = 【掣j ，称图g 是上可嵌人的 对任意集合x ，i x i 表示x 的基数设y 为图g 的任意边集，g y 表 示从g 中去掉y 中的所有边所得到图若t 为图g 的一棵生成树，记号 ( g ，t ) 表示所有g e ( t ) 中边数为奇数的连通分支数称( g ) = 叫nf ( g ，t ) 为g 的b e t t i 亏数，其中m i n 取遍g 的所有生成树t 设a e ( g ) 为图g 的边子集，记号c ( g a ) 及b ( g a ) 分别表示g a 所有连通分支数及其 g a 的具有b e t t i 数为奇数的所有连通分支数 一个图g 的围长，记为9 ( g ) ，是指g 中最短圈的长度，若g 没有圈， 则规定g ( a ) = + o o 用9 ( e ) 表示一个图g 中包含边e 的最短圈的长，若没 有圈包含e ，则定义夕( e ) = + o o 设仳和7 3 为图g 的任意两点，乱和口之间的 距离，记为d a ( u ，影) ，是指g 中连结u 和口之间最短路的长一个图g 的直 径记为d ( g ) ，是g 中所有两点之间距离的最大者g 的一个边覆盖是指 e ( g ) 的一个子集己，使得g 的每个顶点都是己中某条边的端点，记g 的最 小边覆盖的边数为u ( g ) 设m 是e 的一个子集，它的元素是g 中连杆，并 一6 拓扑图论中的有关问题 且这些连杆中的任意两个在g 中均不相邻，则称m 为g 的匹配，记g 的 最大匹配的边数为m ( g ) 一个图g 的独立集是指图g 的边集y 的子集 s ，若s 中任意两个顶点在g 中均不相邻，g 的最大独立集的顶点数称为 g 的独立数，记为口( g ) 设日和g 为连通图，日和g 的剪刀积图h g 定 义为：v ( hc 西g ) = v ( h ) xy ( g ) ，e ( h c ) = 心，s ) ( t ，t ) l t v 曰( 日) ，s t e ( g ) ) 图g 的一个2 因子是指g 的一个二正则生成子图显然，2 - 因子中的 每个连通分支是一个圈若f 为图g 的一个2 一因子且f 中每个圈的长 度均为忌，则称f 为g 的一个缸边形2 因子 2 。2 最大亏格的两个基本定理 文献【1 】和【2 】给出了一个图g 是上可嵌入的充分必要条件及其最大 亏格由p ( g ) 和善( g ) 所表达的一个公式 定理a i - 】( 2 l 设g 为图，则 ( 1 ) 伽( g ) ：堂乓塑； ( 2 ) g 是上可嵌入的，当且仅当( g ) i 由定理a 知图的最大亏格由b e t t i 亏数亭( g ) 确定对一个图g 的最 大亏格的研究可转化为对参数f ( g ) 的研究，关于( g ) 文献 3 】给出了如 下组合表达式： 定理b 嗍设g 为图，则f ( g ) 2 a m c e a ( x g ) c ( g a ) + 6 ( g a ) 一i a i 一1 ) 2 3 不是上可嵌人图的一个特征结构 设r ，玛，日( s 2 ) 为图g 的s 个不相交的连通子图，记号e ( f 1 ，r ， ，e ) 表示g 中2 个端点分别在2 个不同的乃和咒( 1 j ，亡s ，歹t ) 中 的边集；另外，对g 的任意子图f ，记号e ( eg ) 表示g 中一个端点属于 f ，而另一个端点不属于f 的边组成的集合 - 7 高校教师在职攻读硕士学位论文 定理c 4 1 1 1 5 1 设g 为图，如果g 不是上可嵌入的，即f ( g ) 2 ，则存在g 的边子集a 满足下列性质： ( 1 ) c ( v a ) = b ( v a ) 2 ，且对g a 的任意连通分支f ，有声( f ) = l ( m o d2 ) ； ( 2 ) 对于g a 的任意连通分支f ，f 是g 的点到导出子图； ( 3 ) 对g a 的任意s 0 2 ) 个连通分支e 。，月。，有i e ( f , 。，只。， ，只。) l 2 s 一3 ，特别地，当s = 2 时，l e ( 毋。，忍。) i 1 ； ( 4 ) ( g ) = 2 c ( g 4 ) 一i a i 一1 定理d 【1 6 】在定理c 的条件和结论下，有 ( 1 ) 若g 是b 边连通的( k 1 ) ，则对g a 的任意连通分支f ， l e ( 只g ) i 七； ( 2 ) i a l = i e ( e e ) l ，这里是取遍g a 的所有连通分支f 求和 8 拓扑图论中的有关问题 第三章图的最大亏格与边覆盖数 自n o r d h a u s ，s t e w a r d 和w h i t e 引进最大亏格以来，图的上可嵌入性至 今仍受到人们的注意其中，一个最感兴趣的问题就是给出一个与图的 其它参数有关的最大亏格较好的下界而由定理a 可知，要得到最大亏 格的下界等价于得到b e t i i 亏数的上界最近文献【l7 】利用独立数和围长 等条件给出了如下结果：设g 是简单连通图，则( g ) 2 q ( g ) ( 9 ( g ) 一1 ) 本文结合边覆盖数和围长等条件得到了一些比较好的b e t t i 亏数上界，根 据定理a ，同时也就得到了最大亏格的下界对于某些图类，这里的界比 文献【17 】的更好 引理3 1 1 1 4 1 设g 是图，则m ( a ) + u ( g ) = l y ( g ) l 引理3 2 设g 是图，且不是树，则 l e ( g ) i u ( g ) t g 字- - - a j 证设c 是g 的一个最短圈，即i y ( c ) i = 9 ( g ) 设d z 是圈c 的一 个最小边覆盖则i d 。i = f 甲1 = 华1 设d = d 1ud 。，其中d 2 是能 覆盖所有y ( g ) 一v ( c ) 顶点的最小边子集显然f 岛l i e ( g ) l f e ( c ) i ， d - n d 2 = 西，且d 是g 的一个边覆盖根据边覆盖数的定义，u ( g ) i d i = i d l l - i - i d 2 1 f 华1 + i e ( g ) i 一夕( g ) 注意到夕( g ) 一f 华1 = 【皇笋j 于是 l e ( g ) i u ( g ) 【墨笋j 口 引理3 3 设g 为k 边连通图，在定理c 的条件和结论下，设r ，兄， 月为g a 所有连通分支，则有 1 ，i a i 1 主三主 f 瞥， b 1 ， 2 ) f 臀，b 2 ， 【黼，扣3 证1 ) 我们按如下方式构造一个新图，记为口，g 中的点g = 1 ，2 ，t ) l 一1 对应于只，g 中任意两点与仇连一条边，当且仅当，根据 9 高校教师在职攻读硕士学位论文 定理c ( 3 ) 和魄分别对应的e 和f t 有i e ( f o ，f o l = l ( s t ，s ，亡= 1 ，2 ，1 ) 若k = 1 ，即g 是连通图，显然g + 也连通，故有 i a l = i e ( c ) i l v ( c ) i 一1 = f 一1 若七= 2 ，3 ，则对于任意江1 ，2 ，j ，由定理c ( 3 ) 有l e ( 忍，c ) i 七，所 以 川= 坝g 钏= 丢毫似只，g ) i 争 2 ) 设d 是r 的一个最小边覆盖，即。( e ) = i d , i ，则d = ud t 是g 的一个边覆盖，所以u ( g ) i d i = l d i i = u ( r ) ，因只是g 的导出子 图，由围长的定义，夕( 只) g ( g ) ，又i e ( g ) l = l e ( 最) i + l a i ，从而由引理 3 2 可得： i e ( c ) i u ( g ) j e ( g ) i 一u ( 最) l = ( i e ( 置) l - u ( r ) ) + 川 壹【掣j + l a i 华j + i a i 1 1 掣j + 川 隔| ! j = 1 ， 知= 2 。 七= 3 因g 没有环，故【华j o ，从而f 紫， = 2 ， 口 f 常， 拈1 ， 【氍臀， 胜3 拓扑图论中的有关问题 3 1 定理3 1 和定理3 2 的证明 定理3 1 设g 为b 边连通图，则 | ，带， 皓1 ) m a x 1 ，筲1 ) ，b 2 ， i - m a x 1 ，夏i e 【( c 嘲) i - 。+ ( c i ) 一1 ) ， 詹以 证情形1 当专( g ) = 0 时，显然成立 情形2 当f ( g ) = 1 时，则g 不是树，由引理3 2 ，不等式显然成立 情形3 当( g ) 2 时，即g 不是上可嵌入的，则由定理c 知，一定 存在g 的边子集a e ( g ) 满足定理c 的性质( 1 ) ( 4 ) 而由引理3 3 ( 1 ) 有 f f 一1 ， 七= 1 ， l a i f ， k = 2 ， l ；? ， 后= 3 从而结合定理c ( 4 ) 和引理3 3 ( 2 ) ( g ) = 2 1 一i a l l 3 容易计算 ( g 毛。七) = k ，9 ( g 毛，七) = 2 m ，i e ( g 麓，南) i = 2 i n k + k 一1 ，u ( g 量，知) = k m - 1 3 高校教师在职攻读硕士学位论文 另外， 等( g 象，七) = k 一1 ，夕( g i ：l ，南) = 2 m ，i e ( e 2 m , k ) i = 2 i n k + 尼，u ( g 象，知) = 意m 于是 i e ( g ，知) i 一( g 毛，知) + 1 2 i n k + 南一1 一m 七+ 1 【簧g , 1 掣j + 1 m + 1 。1 。_ _ _ _ _ - _ _ _ _ _ _ - - _ _ - _ - _ 一= _ _ _ - _ _ _ _ - _ _ _ - _ _ i _ _ - _ _ _ _ _ _ _ l _ _ _ 一 = ( g 仇1 知) 雩券一l ：百2 m k + k - m k l 【掣j + l 一m + 1 工 = k 一1 = ( 雠2 鬼) 由以上计算可以知道，定理3 1 的界是可达的，从而由定理a 知定理 3 2 的界也是可达的 但是对于i = 1 ，2 ，q ( g 七) = m k ，文献【17 】给的界 茬i 等= 笔瑚- 4 - 2 m1 忐2 m1 蹦( 瓯o ( 1 ) 一= 一= 咒一) 髭7 一l i t 。lt-i 9 ( ( 七) 一1 一 “ 一7 “。、。m 冉7 、叫 这表明对于这两种图类，本文所给的界优于文献f 17 】的界，同时从不等 式( 1 ) 中看出，当m 固定，后增大时， l i m 。y 器, 一i 群- 叫) = k h mf 上1 - t - i - 1 ) - + o o ( 2 ) 从( 2 ) 中我们不难看出，确实存在一些图类使得由文献【17 】得到的b e t t i 亏数的上界会比b e t t i 亏数的真实值相差很大 下面再给出另外一个很有趣的事实设是一个星图，且l y ( ) i = m + 1 ，即是用一个点t ，连接中其他所有点t ，z ，v 2 ，的树现在 构造一个新图，将中的点忱a = 1 ，2 ，m ) 用一个奇圈c k ( k 3 ，尼三 拓扑图论中的有关问题 1 ( r o o d2 ) 代替( 如图3 3 ) 通过这样得到的图记为g ；：1 这样我们将很容易 得到下面的事实 ，m = 4 图3 3 g 翟，m = 4 ，k = 3 事实对于任意小的 0 ，存在无数个图g 满足 卿m 鼍铲 通过简单计算可得： i 昱( g ；：i ) i = k m + m ，f ( ( 帮) = m ，g ( e r ) = k ，u ( ( 翟) = m ( k + 1 ) 2 。 因此 鼍铲南叫黜南 因为l i m + 。2 ( k + 1 ) = 0 ，这样我们就证明了这个事实 口 - 1 5 拓扑图论中的有关问题 第四章图的2 一因子与图的上可嵌人性 确定一类图的上可嵌入性问题本身就是确定图的最大亏格问题结合 图的连通性条件，一个早期的结果( 见文献【2 1 ) 表明每个4 边连通图是上 可嵌入的然而，文献【1 8 】给出了许多3 连通的，但不是上可嵌入的图类 结合图的一个或多个参数，许多文献给出了若干上可嵌入图类例如，文 献【9 】证明了每个4 k + 2 - 正则连通图是上可嵌入的又文献【1 9 】推广【9 】9 中上 述结果，证明了：设g 为连通图，若对任意 y ( g ) ，d a ( t ，) 兰2 ( r o o d 4 ) ，则g 是上可嵌入的，利用3 _ 边形二因子研究图的最大亏格起源于文献【2 0 】，而 且【2 0 】中确定了含有3 边形易因子的3 正则图的最大亏格接着文献 2 1 】 用扩张运算研究了含垂边形二因子的图的最大亏格，证明了下述结果：若 g 为一个含垂边形2 因子的连通图，且对任意口y ( g ) ，d a ( u ) 兰3 ( r o o d4 ) ， 则g 是上可嵌入的最近文献【2 2 】结合冬边形2 - 因子等条件，又研究了点 度在m o d u l 0 4 下取值是o ，1 时，图的上可嵌入性，l l p ( 1 ) 设g 是一个2 连 通无环图若g 含有垂边形2 因子，且对任意t ，y ( g ) ，, t o ( u ) 三o ( m o c l 4 ) ， 则g 是上可嵌入的( 2 ) 设g 为3 连通图若g 含有4 - 边形2 - 因子， 且对任意t ，y ( g ) ，a c ( v ) 三1 ( r o o d4 ) ，则g 是上可嵌入的本文在此基础 上进一步推广了这个结果，得到如下结果： 定理4 1 设g 是一个参连通无环图若g 含有乒边形2 因子，且 对任意让， y ( g ) ，d o ( u ) 兰d g ( u ) 三0 ( r o o d2 ) ，d o ( 缸) + d a ( t ，) 三o ( m o c i4 ) ，则g 是上可嵌入的 定理4 2 设g 为3 连通图若g 含有垂边形参因子，且对任意 t ，y ( g ) ，d g ( u ) 兰1 ( r o o d2 ) ，则g 是上可嵌入的 1 7 - 高校教师在职攻读硕士学位论文 4 1 定理4 1 的证明 定理4 1 的证明假设g 不是上可嵌入的，即毒( g ) 2 ，则由定理c 知存在g 的边子集a 使得c a 满足定理c 的性质( 1 ) ( 4 ) ，设f 1 ，易，冠 为g a 的所有连通分支，这里f c ( c a ) 2 ，对任意只( 1 i z ) ，由定 理c ( 1 ) 知只有圈，又由g ( 从而e ) 无环，则有i y ( r ) l 2 设日为g 的 所含的一个4 - 边形禾因子对任意1 i z ，我们将证明i 曰( r ，g ) l 4 首先，因g 是2 连通的，由定理d ( 1 ) 有i e ( 只，g ) l 2 ，又因g 为e u l a r 型，则g 无奇数边割集，所以i e ( 尼，g ) i 3 ，我们只要证明i e ( 只，g ) l 2 若不然，设l e ( r ，g ) i = 【e - ，e 2 ) ，且设e 。和e ：在r 中的端点分别为z 和y 因g 为2 连通的，且i y 限) i 2 ，则显然z y 因g 含有垂边形2 - 因子日， 则或者e 。和e 2 同属于日中的某个4 圈或者均不属于日中的任何垂圈 若e l 和e 2 同属于日中的某个乒圈，则鼠的点数可写成4 k + 2 ( k 0 ) 的形 式；若e 。和e 2 不属于日中的任何乒圈，则只的点数可写成4 a ( a 1 ) 的形 式总之，只有偶数个点因对任意t ，u y ( g ) ，d a ( u ) 三d a ( u ) 兰o ( m o d2 ) ， d g ( u ) + d a ( v ) 兰o ( m o d 4 ) ，以及因l e ( 蜀) i = ；( d a ( v ) 一2 ) ，所以i e ( 只) i 必 , 口e v ( f d 为奇数因此，p ( 尻) = i e ( 只) l _ i y 僻) i + 1 为偶数，即( 最) 兰o ( m o d2 ) ，这 与定理c ( 1 ) 矛盾 由上可知，对任意1 i z ，j e ( 只，g ) i 4 再由定理d ( 2 ) 有i a i = l e ( 只，g ) i 2 1 ，最后由定理c ( 4 ) 有( g ) = 2 1 一i a | - 1 一1 ，矛盾! 因此 定理获证 口 推论4 1 z z 设g 是一个2 连通无环图若g 含有垂边形2 - 因子， 且对任意t ，y ( g ) ，d a ( v ) 兰o ( m o d4 ) ，则g 是上可嵌入的 注记在这种意义下，定理4 1 中的条件q 无环一以及誓2 一连通”均 是不可缺少的，否则，存在反例图( 见文献1 2 2 1 ) 1 8 - 拓扑图论中的有关问题 4 2 定理4 2 的证明 定理4 2 的证明假设g 不是上可嵌入的，即亭( g ) 2 ，则由定理c 知存在g 的边子集a 使得g a 满足定理c 的所有性质设只，尼，用 为g a 的所有连通分支，这里f - c ( a a ) 2 类似于上述定理4 1 的证 明，只要证得对任意尻( 1 z z ) ，有l e ( 冠，g ) i 4 首先，因为g 是孓连通的，由定理d ( 1 ) 有i e ( f i ，g ) i 3 下面只要 证明i e ( 最，g ) l 3 若不然，设l e ( f i ，g ) l = e l ，e 2 ，e 3 ) 且设e l ，e 2 和e 3 在 忍中的3 个端点分别是z ，y 和名由g 的争连通性，则有z ，y 和z 互不 相同又因g 含有一个垂边形二因子日，则必有如下两情形之一发生： a ) e ，e 2 和e 3 有2 条边同属于日中的某个4 - 圈，而第3 条边不属于日中 的任何垂圈；b ) e 。，e 2 和e 3 均不属于日中的任何垂圈注意到z ，y 和z 互不相同，因此我们得到：若a ) 发生，则冠的点数可表示成4 k + 2 ( k 0 ) 的形式；若b ) 发生，则只的点数可表示成4 k ( k 1 ) 的形式不管哪种情 形，我们知l y ( 只) i 为偶数又易看出在图只中，有且只有这3 个点z ，y 和名的度为偶数，因此e 有奇数个奇度点这是一个显然的矛盾以下 类似于定理4 1 的证明，同样可得到一个与荨( g ) 2 相矛盾的结论，从而 完成定理的证明 口 推论4 2 嗍设g 为3 连通图若g 含有垂边形2 因子，且对任意 t ，y ( g ) ，d a ( t ，) 三l ( m o d4 ) ，则g 是上可嵌入的 注记在这种意义下，定理4 2 中的条件誓孓连通”是必要的，不能 换成。参连通嚣或誓3 - 边连通”，否则存在反例图( 见文献 2 2 】) 1 9 高校教师在职攻读硕士学位论文 4 3 结论 综合文献【1 9 ，2 1 】，以及本文的结果，我们用表列形式给出对于任意点 u ，口v ( a ) 的度在r o o d2 或r o o d4 下等值的上可嵌入图类 表4 1 点度条件垂边形2 因子条乍眭通性条件文献 2 0 拓扑图论中的有关问题 第五章与直径有关的上可嵌人图类 关于图的直径与最大亏格的关系，近年来引起了图论学者的重视 首先，文献【1 1 】和文献【2 0 】均用不同的方法考虑了直径为2 的情形，证明 了 定理e 设g 是直径为2 的无环图，则f ( g ) 1 ，即g 是上可嵌入 的 最近文献 2 3 】和【2 4 】进一步考虑了直径为3 的情形，证明了 定理f 设g 是直径为3 的无环图，则有( g ) 2 ，即7 m ( g ) ；( g ) 一1 对于直径为4 的图，文献【2 5 】证明了如下结果 定理g 设g 为直径为4 的简单图，若g 不含3 阶完全子图拖，则 亭( g ) 4 ，即7 m ( g ) ( g ) 一2 由定理f 和定理g 我们知道，直径为3 和直径为4 的图并一定都是 上可嵌入的，事实上，存在无穷的直径为3 和直径为4 的非上可嵌入图 类( 见文献【2 4 】) 人们自然会问，那么满足什么样条件的直径为3 或4 的 图才是上可嵌入的呢? 基于回答这一问题，本文对定理g 的边进行了一 定限制后，得到了如下定理5 1 和定理5 2 定理5 1 设图g 是直径为3 的连通图，若对任意e e ( g ) 都有 9 ( e ) 4 ，则( g ) 1 ，即图g 是上可嵌入的 定理5 2 设图g 是直径为4 的连通图，若对任意e e ( g ) 都有 g ( e ) = 4 或9 ( e ) = + o o ，则( g ) 1 ，即图g 是上可嵌入的 我们将在本章的第一、二节给出定理5 1 和定理5 2 的证明，这里， 我们先证明如下引理 设日是g 的子图，对任意钞y ( g ) ，记鼠( t ，h ) = u i d g ( 口，乱) = i ，牡 y ( 日) ， = 0 ，1 ，2 ，d ( g ) ) 为到点”的距离为t 的点集在定理c 的条件 和结论下，用x 表示g a 的所有连通分支组成的集合，此时为了方便 2 1 高校教师在职攻读硕士学位论文 我们把x 的元素与g a 的连通分支无区别地对待，由定理c ( 3 ) ，对任意 eh x ，都有i e ( 只日) i 1 若e ( 只h ) = e ) ，则称f 和日是1 相邻的且 e 是连结f 和目的边我们把x 中的元素具有定理c ( 3 ) 称为x 具有1 一 相邻性 引理5 1在定理c 的条件和结论下，设风，飓，竭为g a 所有 连通分支，同时还满足d ( v ) 4 且y e e ( g ) 都有夕( e ) 4 ，则有： ( 1 ) 必存在某个h x 使得1 l e ( h ，g ) i 3 ； ( 2 ) 对于任意的h x ，l v c h ) 4 ； ( 3 ) 对于任意的h x 以及任意点t | y ( 日) ，必存在点口s 2 ( t i ，日) ； ( 4 ) 若存在g a 的s 个连通分支，不妨设为日，飓，也使得 l e ( h 1 ，1 - 1 2 ，凰) l = 2 s 一3 则对任意j = 8 + 1 ，s + 2 ，l x l 都有 l e ( 马，皿u 飓u u 风) i 2 ( 5 ) 对于任意的e e ( h ，g ) ( 日x ) ，都有9 ( e ) + ，即e ( eg ) 1 证( 1 ) 由定理c ( 1 ) 知i x i 2 若对任意h x ，均有i e ( h ，g ) i 4 ， 则i a i = i e c h ，g ) l 2 1 x 1 再由定理c ( 4 ) 得：( g ) = 2 i x i - 一1 1 ， 这与f ( g ) 2 假设矛盾因此存在h x 使得i e ( h ，g ) l 3 又因g 连通 的，必有i e ( h ，g ) i 1 证毕 ( 2 ) 若l y ( 日) i 3 ，则由定理c ( 1 ) h 中必含圈，从而导致存在e e ( 日) ， 使得9 ( e ) 3 ，与已知条件矛盾 ( 3 ) 假设y ( 日) 中的所有点t ，都有t ，& ( 牡) ，因g ( 从而日) 是简单图， 由定理c ( 1 ) 知，p ( 日) 三l ( m o d2 ) ，所以日中必含有3 阶圈，这与已知条 件9 ( e ) 4 矛盾 ( 4 ) 如若不然，即i e ( 马，夙u 岛u u 风) i 3 ，则有i e ( h 1 ，1 - 1 2 ，玩，马