（基础数学专业论文）最大亏格下界与上可嵌入图类.pdf

最大亏格下界与上可嵌入图类 中文摘要 本文主要研究了拓扑图论的一个重要分支一图的最大亏格问题 得到 了两类上可嵌入图类 以及一类图的最大亏格下界 具体如下 1 用 g u 表示一个图g 中任意点u 的邻域集 目前利用图的邻域 性质来研究图的上可嵌入的结果甚少 结合图g 的邻域条件 本文给出 了两类上可嵌入图 丰富了文献 1 4 关于图上可嵌入性的结果 并推广 了文献 5 5 的一个结果 2 图g 的顶点r 划分是指 图g 的一个顶点划分 k 满足每个导出子图g 吲 1 i 8 为多重完全n 部图 本文结合图的顶 点r 划分 3 点度等条件 确定了一类上可嵌入图类 从而丰富 了已有这方面的结果 见文献 6 1 0 3 图g 的顶点肌划分是指 图g 的一个顶点划分 k k k 满足每个导出子图g m 1 i s 都包含轮为生成子图 结合 厶划分 给出了一个最大亏格比较好的下界 对于某些图类 该界比文献 1 1 的 界更好 在文章最后部分 提出了几个善待解决的问题 即作者在今后将致力 前进的方向 关键词 图 上可嵌入性 b e t t i 亏数 最大亏格 p 划分 肌划分 邻域集 最大亏格 下界与上可嵌入图类 a b s t r a c t t h em a x i m u mg e n u so fag r a p hi sa ni m p o r t a n ts u b j e c ti nt o p o l o g i c a lg r a p h t h e o r y i nt h i sp a p e r w eg i v et w od a s s e so fu p p e re m b e d d a l e 酎a p h 8 a n do b t a i na b e t t e rl o w e rb o u n do nt h em a x i m u mg e n u sf o rs o m eg r a p h s s o m er e s u l t sw i l lb e g i v ei nt h et h e s i sa sf o l l o w s l e tn a u d e n o t et h en e i g h b o rs e to fv e r t e xui ng a tp r e s e n t t h e r ea r e o n l yaf e wr e s u l t sa b o u tt h en e i g h b o rc o n d i t i o no nt h eu p p e re m b e d d a b i l i t yo f g r a p h s c o m b i n e dw i t ht h en e i g h b o rc o n d i t i o no fg w eg i v et w od a s s e so fu p p e r e n b e d d a l eg r a p h s a n dg e n e r a l i z e dt h er e s u l t so nt h eu p p e re m b e d d a h i l i t yo fg r a p h s i n 1 4 5 l e tgb eag r a p h s a n dt h e r ee x i s t sap a r t i t i o n k k o fv a s a t i s f y i n ga i r am u l t i b i p a r t i t eg r a p hf o ra n y1 i s t h e ng h a sar p a r t i t i o n c o m b i n e dw i t ht h ec o n d i t i o n so fr p a r t i t i o n d e g r e eo fv e r t e x t h ep a p e rg i v e sc l a s s e s o fu p p e re m b e d d a b l eg r a p h s g e n e r a l i z e dt h er e s u l to nt h eu p p e re m b e d d a b i l i t yo f g r a p h si n 睁1 0 1 l e tgb eag r a p h s a n dt h e r ee x i s t sap a r t i t i o n k o fv c s a r i s 研n gg k c o n t a i n i n gaw h e e la st h es p a n n i n gs u b g r a p hf o ra n y1 i s t h e ng h a saw p a r t i t i o n c o m b i n e dw i t ht h ec o n d i t i o n so fw p a r t i t i o n i tp r e s e n tab e t t e r t h a nt h er e s u l ti n 11 f o rs o m eg r a p h s i nt h el a s ts e c t i o n w ep u tf o r w a r ds o m eq u e s t i o n st or e s o l v e n a m e l yt h ed i r e c t i o n1w i l lg oa h e a di nt h ef u t u r e k e y w o r d s g r a p h u p p e re m b e d d a b i l i t y b e t t id e f i c i e n c y r p a r t i t i o n w p a r t i t i o n n e i g h b o rs e t i i i 湖南师范大学学位论文原创性声明 本人郑重声明 所呈交的学位论文 是本人在导师的指导下 独立 进行研究所取得的研究成果 除了文中特别加以标注引用的内容外 本 论文不包含任何其他个人或集体已经发表或撰写的成果作品 对本文的 研究做出重要贡献的个人和集体 均已在文中以明确方式标明 本人完 全意识到本声明的法律后果由本人承担 学位论文作者签名 年月 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版 允许 论文被查阅和借阅 本人授权湖南师范大学可以将学位论文的全部或部 分内容编入有关数据库进行检索 可以采用影印 缩印或扫描等复制手 段保存和汇编本学位论文 本学位论文属于 1 保密口 在 年解密后适用本授权书 2 不保密口 请在以上相应方框内打 日期 o 年 月沁日 啉刁刚其1 马 夸 咎扣 0 1i面 懿告 最大亏格下界与上可嵌入图类 第一章引言 图论是一门应用广泛的数学分支 它在物理学 化学 通讯科学 计 算机技术 生物遗传学 社会学等学科都有应用 它与数学本身的许多 分支密切相关 这些分支包括 群论 矩阵论 拓扑学 概率论 组合学 等 拓扑图论作为它的一个重要领域 更是一个非常活跃的研究方向 它极大地丰富了图论和拓扑学本身的研究 其中对图的拓扑参数一最大 亏格的研究又是一个十分重要的课题之一 一个图的最大亏格f 1 2 记为 似 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 提出图的最大亏格以来 很多图论学者都投身于这方面的研究 但随着其研究的深入 它越来越多地与其它数学分支相互交叉 相互影 响 使之成为目前这方面研究的重要发展趋势 目前 图的最大亏格的 研究主要表现在如下几个方面 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 正则图上可嵌入的充要 1 高校教师在职攻读硕士学位论文 条件 另外 黄元秋教授和刘彦佩教授通过引进图的扩张运算 研究了 扩张运算与图的b e t t i 亏数之间的内在联系 揭示了图的最大亏格与图的 2 因子的某些联系 然而 在探求图的最大亏格的结构特征上 仍有广 阔的前景 2 上可嵌入性 一个图是上可嵌入的表明其最大亏格可取到最好的上界 虽然l i u 1 3 和n e b e s k y m 分别提供了不同的确定图的上可嵌入性的充要条件 但对 于什么类型的图是上可嵌入的尚知不多 早期k u n d a p 5 证明了所有垂边 连通图是上可嵌入的 所以我们只需研究k k 3 边连通图就够了 然 而 已知确有3 边连通而非上可嵌入的图 j u n g e r m a n 1 6 1 这就导致什么 样的k k 3 边连通图是上可嵌入的 目前 已有很多文献研究了图的 上可嵌入性与图的其它参数之间的关系 h x u o n g 证明了局部连通图 是上可嵌入的 l n e b e s k y 证明了半局部连通图及 2 局部连通图均是上 可嵌入的 m s k o v i e r h u a n g l i n f u 和m i n c h e nt s c a i 分别考虑直径 为2 和3 的图的上可嵌入性 黄元秋教授和刘彦佩教授研究了一些正则 图的上可嵌入性 j z a k s 研究了一些笛卡尔图的上可嵌入性 m s k o v i e r 证明了一个图嵌入曲面上使得每个面度的大小不超过4 则该图是上可嵌 入的 黄元秋教授和刘彦佩教授证明了l n e b e s k y 和m s k o v i e r 关于上可 嵌入性与面度大小的猜想 近期 国内已有很多学者结合图的点和边连 通性 直径 半径 围长 顶点度 最小度 2 因子 独立数 匹配数 顶点划分等条件 得到一些新的上可嵌入图类 见文献 7 1 0 1 7 2 1 3 最大亏格的下界 有时我们很难判断出一个图的最大亏格是否能取到最好的上界 竽j 即是否是上可嵌入的 这时 一个比较感兴趣的问题是确定这个图的最 大亏格与其它参数有关的比较好的下界 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 给出了与连通性 2 最大亏格下界与上可嵌入图类 有关的简单图的最大亏格的下界估计式 d a r c h d e a c o n 考虑了3 边连通 非简单 图的情形 黄元秋教授推广了上述工作 对任意肛边连通 非简 单 图 给出了由图的最小度所表达的图的最大亏格的下界表达式 证明 了最小度趋向无穷大时 最大亏格趋近最好的上界 最近 黄元秋教授 研究了图的最大亏格与图的余色数及团的关系 利用h e a d w o o d 着色定理 揭示了图的最大亏格与图的亏格之间的关系 4 利用拟阵研究图的嵌入及有关算法 利用拟阵考虑图的嵌入是人们所熟知的工作 t u t t e 和国内刘彦佩教 授等人的工作表明图的平面嵌入的判断可转化为判断拟阵的图性和上图 性 m l b u r s t 和j l g r o s s 运用拟阵研究了图的最大亏格嵌入 给出了图 的最大亏格嵌入多项式算法 是否存在多项式时间算法来判断图的同构 一直是一个公开性的问题 限定图的平均亏格 j c h e n 和j l g r o s s 证嘎 了存在多项式时间算法来判断图的同构问题 本文受文献 4 7 1 0 1 1 的启发 运用和发展了其中某些方法 结合图 g 的邻域条件 顶点划分等得到了一些新的上可嵌入图类和一些图类的 最大亏格较好的下界 推广和深化了目前有关这方面的结果 3 最大亏格下界与上可嵌入图类 第二章基本概念和基本定理 2 1 基本概念 本节给出以后各章节涉及到的基本概念和术语 凡未说明的概念均 同文献 2 1 1 且无特别说明所涉及的图均为有限无向连通图 一个图g 是 指一个有序三元组 y g e g c a 其中y g 是非空的顶点集 e g 是不与v c 相交的边集 而忆是关联函数 它使图g 的每条边对应于 图g 的无序顶点对 不必相异 m n 称为图g 的阶 设n v y g 且 钍 e g 则称顶点u u 为图g 的相邻顶点 否则 称钍 u 为图g 的非邻 顶点 假如y 7 是y 的一个非空子集 以y 为顶点集 以两端点均在 中的 边的全体为边集所组成的子图 称为图g 的由y 7 导出的子图 记为c v 图g 的两个顶点u 和口称为连通的 如果在图g 中存在从u 到t 的路 连通是顶点集y v 上的一个等价关系 于是就存在v a 的一个分类 把v a 分成非空子集 k k 使得两个顶点u 和 是连通的当且仅 当它们属于同一个子集磁 i l 2 c 子图g m g f g k 称为 图g 的分支 若图g 只有一个分支 则称图g 是连通的 否则称图g 是不连通的 图g 的分支数记为u g 图g 的割边是指使得 g e u g 的边e 对v a 的子集s 和 用 s s 表示一个端点在s 中 另一个端点在s 7 中所有边的集合 所 谓图g 的边割是指形为慨s 的e g 的子集 其中s 是v c 的非空真 子集 且s v s 图g 的极小边割称为键 极小边割是指其任何真子集 均不是边割的边割 若图g 是连通的 则图g 的键b 是使g 日不连通 的e g 的极小子集 若v c 的子集y 7 使得y y 7 不连通 则子集y 7 5 高校教师在职攻读硕士学位论文 称为图g 的顶点割 k 顶点割是指有k 个元素的顶点割 若图g 至少有 一对相异的不相邻顶点 则图g 所具有的k 顶点割中最小的k 称为图g 的连通度 记为k g 若k g k 则称图g 为舡连通的 一个k 边割是 指有k 个元素的边割 若图g 是非平凡的 图g 的所有k 边割中最小的 k 称为图g 的边连通度 记为尤7 g 若k 7 g k 则称图g 为肛边连通 的 称图h 为图g 的子图 如果v h cy g e h c 刀 g 并且妇是 惦在e h 上的限制 图g 的生成子图是指满足v h v a 的子图日 不含圈的图称为无圈图 连通的无圈图称为树 图g 的生成树是指图 g 的生成子图 它同时又是树 设d 是图g 的一个点子集 即d y g 若图g 中每一点或者在d 中 或者与d 中某一点邻接 则称d 是图g 的一个支配集 图g 中点数最少的支配集称为最小支配集 最小支配集 中点的数目称为支配数 记为m g 曲面这里指一个连通紧致2 维闭流形 曲面分定向与不可定向两 类 如定向蓝面有球面 胎面等 而不定向曲面有摄影平面 克莱茵瓶曲 面等 一个图g 在曲面s 上的一开2 胞腔嵌入是指图g 能画在曲面s 上 使得边与边之间除顶点外不再相交 且在曲面s 上去掉图g 的顶点与边 之后的每个连通分支与开圆盘同胚 此时 每个开圆盘称为图g 在曲面 s 上的一个面 注意到 不连通的图在任意曲面上不存在2 胞腔嵌入 图g 的最大定向亏格 简称为最大亏格 用7 m g 表示 是指最大的 整数k 使得图g 能2 胞腔嵌入亏格为k 的定向曲面s 上 图的定向亏格 用 y g 表示 或不可定向亏格用彳 g 表示 是指最小整数k 使得图g 在 亏格为k 的定向 或不定向 曲面s 有2 胞腔嵌入 设图g 是一个具有z 个点 e 条边的图 若图g 在一个亏格为g 的 定向或不定向 曲面有参 胞腔嵌入 且具有7 个面 则由e u l e r 公式 i 一e 丁 2 2 9 s 定向 或 z 一e 丁 2 一g s 不定向 因为任何一个图在任意曲面上的2 一胞腔嵌入 6 最大亏格下界与上可嵌入图类 中至少有一个面 由最大亏格的定义及e u l e r 公式 即有m g 掣j 其中卢 g 一 1 称为图g 的圈秩数 对任意实数z h 表示不超过z 的最大整数 同时 若伽 g 星譬j 称图g 是上可嵌人的 有关图的 最大亏格以及上可嵌入性 读者可参阅引导性文献1 1 2 1 3 对于任意集合x 用l x l 表示x 的基数 设y 为图g 的任意边子 集 c z 表示从g 中去掉 中的所有边所得到的图 设图g 是连通 图 且丁为图g 的一棵生成树 记f g t 表示g e t 中边数为奇数 的连通分支个数 我们称毒 g 卿 g t 为图g 的b e t t i 亏数 这里 r a i n 取遍图g 的所有生成树t 由定义 对图g 的任意生成树丁 均有 g t 三 g 兰f l g m o d2 设a e c c 为图g 的边子集 记号c g a 及b g a 分别表示g a 所有连通分支数及其c a 的具有b e t t i 数为奇数 的所有连通分支数 设风 飓 风 七 2 为图g 的k 个不相交的连通 子图 记号e 皿 凰 凰 表示图g 中2 个端点分别在2 个不同的凰和 h j i j 1 t j k 中的边集 另外 对图g 的任意子图日 记号e o h 表示图g 中一个端点属于日 而另一个端点不属于曰的边集 将图称为多重完全t t 部图 若它有一个基础图为完全札部图 图g 的顶点砰划分是指 图g 的一个顶点划分 k 满足每个导 出子图g k 1 1 i k 为多重完全n 部图 轮图 记为 可表示如下 v c w u 1 也 一1 e r o y i ll i 礼一1 u v d v i 1 l lsi 体一1 r o o dn 1 同时 称为轮的中心 图g 的顶点w 划分是指 图g 的一个顶点划分 h 坎 满足每个导出子图g 都包含轮嘶 i 1 i k 为生成子 图 g r a p h 图2 1 是指 设风 吼是简单连通图 且对任意i 1 2 凰 兰 7 高校教师在职攻读硕士学位论文 l m o d2 存在讹 y 鼠 使得对于任意轨 y 凰 戤 讹 都有戤 e h i 通过连接x y x v h 1 y y 也 就得到a g r a p h 简单的说就是 y v h t uy 日j e a e h 1 ue 月 u z 可 图2 1 g r a p h 2 2 最大亏格的基本定理 在最大亏格的研究中 一个很显著的事实就是最大亏格这个拓扑不 变量能用纯组合学的形式刻画出来 在这节我们将介绍3 个方面的结果 这些也将是本文主要定理的证明基础 首先 文献 1 3 2 2 给出了图g 是 上可嵌入的充要条件及其最大亏格由z a 和 g 所表达的一个公式 定理a 1 3 m 设g 为图 则 1 似 g 华 2 图g 是上可嵌入的当且仅当 g 1 由定理a 知 对一个图g 的最大亏格的研究可转化为对参数 g 的 研究 关于f g 文献 1 4 给出了如下组合表达式 8 最大亏格下界与上可嵌入图类 定理b 1 1 4 1 设g 为图 a e g g a c g a b g a 一l a l 1 则毒 g m a x z g a i a e g 文献 2 3 从反面给出了非上可嵌入图所具有的结构特征 定理c 2 3 设g 为图 若图g 不是上可嵌入的 即f g 2 则存在 图g 的边子集a 满足下列性质 1 c g a b c a 2 且对g a 的任意连通分支日 都有 z h l m o d2 2 对于g a 的任意连通分支日 日是图g 的点导出子图 3 对于g a 的任意k k 2 个不同连通分支玩 飓 风 有 f e h 1 恐 玩 l 2 k 一3 特别的 当南 2 时 l e h 1 1 1 2 l 1 4 f g 2 c a a 一i a l 一1 设c g a 表示g a 的所有连通分支组成的集合 定理d 设图g 为肛边连通图 在定理c 的条件和结论下有 1 对g a 的任意连通分支日 若图g 是肛边连通的 k 1 则 i e h g l 后 2 吉 i e c h g i 这里 是取遍g a 的所有连通分支h 求 和 3 必存在某个h c g a 使得1 i e h g i 3 4 图g 为简单图 对g a 的任意连通分支日 有l y 日 i 3 5 哪 掣1 甚3 证 1 假设结论不成立 则图g 中必有边数小于k 的边割集 这与 图g 是七 边连通图矛盾 2 我们构造一个图9 如下 图g 的所有点对应于g a 的所有连 通分支 图g 中任意两点z 和z 连一条边当且仅当 根据定理c 的性质 高校教师在职攻读硕士学位论文 3 x l 和x 2 所分别对应的g a 的两个连通分支研和仍有l e c h 岛 f 1 显见 对图g 中任意点z 有d g z i e g h j 这里点z 对应于g a 的 连通分支日 而且由图g 的构造及定理c 的性质 2 易知i e g i i a i 因此 2 1 a 2 e g l d c z i e g h i ev g h 其中日取遍c a 的所有连通分支 即结论成立 3 由定理c 的性质 1 知c g a 2 假若对任意的h c g a 均 有i e h g i 4 则 吉 i e h c l 2 c g a h e c g a 再由定理c 的性质 4 得 专 g 2 c g a 一l a l 一1 1 这与 g 2 假设矛盾 因此必存在h c v 4 使得i e h g i 3 又 因图g 是连通的 必有i e h g l 1 从而结论成立 4 由定理c 的性质1 知f l h l m o d2 即日含圈 又图g 为简单 图 从而日也为简单图 结论显然成立 5 我们按如下方式构造一个新图g 图g 的每条边1 1 对应于a 中的每条边 且对任意e a 若e 的两个端点分别属于g a 的两个连通 分支凰和 则图g 中对应于e 的边e 的两个端点是图g 中与凰和 马对应的两个点 首先 因图g 是连通的 显然图9 也是连通的 故有 i a i l e g l l v v l 一1 c g a 一1 从而 由定理c 的性质4 有 f g 2 c g a 一i a i 一1 c g a 1 0 最大亏格下界与上可嵌入图类 其次 当图g 是2 边连通的 设日为c a 的任意连通分支 则图 g 中与日对应的点的度为如 日 i e h g l 2 所以有 i a i i e g l 去e ie h v lc a a c g a 由定理c 的性质4 有 证 g 2 c g a 一f a i 一1 c g a 一1 最后 当图g 是3 边连通的 可类似证明 于是定理d 的性质5 得 最大亏格下界与上可嵌入图类 第三章新邻域条件与图的上可嵌人性 联系着一个图g 的邻域条件 许多文献证明了一些图类是上可嵌入 的 特别是 文献 1 2 用不同的方法证明了 一个直径不超过2 的无环图是上可 嵌入的 显然 一个无环图的直径不超过2 等价于 对于图g 中任 意不相邻的点也和u 即让u 隹e g 都有i 珏 ng d v l2 1 文献 3 证明了 设图g 是无环图 对图g 中任意相邻的点u 和钉 若如下两条件之一满足 1 l g c u n g a v i 2 2 图g 是2 一点连通且 l g u n g 钉 l 1 则图g 是上可嵌入的 文献f 4 考虑特殊的距离为2 的两个点的邻域的条件 证明了 设图 g 是简单图 对图l 中任意两个距离为2 的点u 和u 即如 珏 口 2 都有 l g n g 口 i 2 则图g 是上可嵌入的 这里l k 1 3 k 1 3 e 其中 硒 3 k 3 e 是图g 的点导出子图 文献 5 结合相邻顶点邻域并的条件得到了 设图g 是简单连通图 若存在非割边e 让秒 e g 使得l g 钍 u g i l v c i 则图g 是上可 嵌入的 本章考虑相邻两点的邻域的连边条件 并利用定理c 中关于非上可 嵌入图的一个结构特征 得到下面的定理3 1 还进一步推广了文献 5 的 结果 得到下面的定理3 2 目前 关于利用图的邻域性质来研究图的上 可嵌入性结果甚少 基于这个目的 本文可视为在这方面的补充 定理3 1 设图g 是2 一连通图 若对图g 中任意相邻的点u 和 即 u 口 e g 一定存在a i 让 b i g c v 且a i 秽 b i 钍 a l a 2 b l 5 2 使得a l b i e g a 1 2 则图g 是上可嵌入的 定理3 2 设图g 是非 g r a p h 简单连通图 且存在不相邻的点钍和 u 使得i g d u u g u j i y g 2 则图g 是上可嵌入的 1 3 高校教师在职攻读硕士学位论文 定理3 3 设图g 是 一g r a p h 则r m g p g 一1 3 1 定理3 1 的证明 为了完成定理3 1 的证明 我们先证明以下引理 引理3 1 设图g 是2 一连通图 且对图g 中任意相邻的点u 和口 即 伽 e g 一定存在a l n o u b i g 口 且a i 玩 缸 使得o t 玩 e g 江1 2 则图g 是3 边连通图 证假设图g 不是3 边连通图 不妨设 s 习 e l e 2 是图g 的一个 键 且e 产既玑 戤 s y i 富 i 1 2 由题意有 一定存在a i g c x 1 b l n c y 且a t y 1 玩 z 1 使得o 玩 e g g 1 2 显然a 1 a 2 不能同时属 于君 否则与假设矛盾 无论a 1 0 2 s 或a 1 s a 2 一s 都必存在2 条形 式为y l b i a 舰 i 1 2 的路 这样就有3 条从y l 到x l 的边不交的路 所以 i 限习l 3 与假设矛盾 从而图g 必为3 一边连通图 口 定理3 1 的证明用反证法 假设图g 不是上可嵌入的 则由定理c 存在a e g 使得性质 1 一 4 成立 设r 如 兄是g a 的连通分 支 其中k c a a 首先由引理3 1 知图g 是3 边连通图 再结合定 理c 可知 对于任意i 1 2 k 都有 e f i g l 3 下面证明 对任意 i 1 2 七 i e f i g i 4 假设存在某个t 1 2 k 使得i e f t g l 3 设 e r g e l e 2 e 3 e i 鼢玑 鼢 y 尻 y l y e y 2 y 用 珈 y r 其中江1 2 3 8 f n t 8 f n 1 2 k 下面分情况讨论 情形1 若z x 2 强这显然与图g 是2 连通图矛盾1 1 4 最大亏格下界与上可嵌入图类 情形2 若x z 2 z 3 中有两点相同 不妨设z z 记为z 则设 a i g z 1 饥 n g y 1 且a i y t 6 i x l i 1 2 显然有 2 1 a 2 y 尻 b l 5 2 簪y f t 子情形2 1 若 铂0 1 2 则a a a 且锄瑰 勺o 1 2 j l 2 3 这样i e f t g i i e 1 e 2 e 3 a l b l a 2 5 2 l 5 与假设矛盾 子情形2 2 若z o i 0 1 或2 不妨设x 0 2 则a l b l a 且 a t b l 勺 歹 1 2 3 这样i e f t g i l e l e 2 e 3 a l b l l 4 与假设矛盾 情形3 若z 1 z 2 z 3 彼此不同 即z 1 z 2 z 3 设a g z 1 玩 g 矽1 且a y 1 瓯 z 1 0 1 2 显然也有a 1 a 2 v f o b t b 2 隹y r 则必有 8 l a 2 t 3 否则 同情形2 分析可得a l b l a 且a l b 勺 歹 1 2 3 这导致i e f t g i i e l e 2 e 3 a l b l l 4 与假设矛盾 此时 b t 6 2 y 2 蜘 所以可1 抛 e g y l y 3 e g 又设a g z 2 6 n o y 2 且n y 2 6 x 2 i 1 2 则同前面分析可知 必有 西 n 2 7 1 z 3 此 时 醴 船 所以y 2 y a e g 这样 i e r e 局 r i i 1 与定理c 的性质3 矛盾 情形2 若昭u 盼gy h j 则必存在u 7 曙u 盼且 7 圣y 马 不妨 2 1 高校教师在职攻读硕士学位论文 设 y 玩 s 五1 8 忌 同样 因为a i r 为多重完全3 部图 所以 1 7 也 e g 这将导致 i e 吼 1 6 f f 姐口 v 2 v 7 l 2 1 与定理c 的性质3 矛盾 断言1 得证 口 断言2v 1 i k i y 玩 nk i 1 证若不然 那么一定存在某个凰 使得i y 甄 e l y 2 不妨设 l y 凰 nk i 2 设v l v 2 k 且钉l u 2 y 凰 1 t 忌 由断言l 可知 v 属于k 的不同部集 情形1 若 6k 1 v 26 昭 或盼 则因i w l 2 且由断言1 知 一定 存在地6 盼 或昭 且v 3 聋y 凰 不妨设u 36y h j 歹 i 1 j 七 从而 由g 吲为多重完全3 部图有1 1 1 6e g t 2 2 v 36e g 所以 e 凰 s j i i v 1 t 1 3 忱均 i 2 与定理c 的性质3 矛盾 情形2 若 16 吁 v 26 昭 则因i w i 2 i 2 3 且由断言i 知 一定 存在v 3 吁且v 3 甓v c s 不妨设 y 矾 s i i 8 七 又设7 2 4 k 1 以下分两种子情形讨论 子情形2 1 若啦6v c h 则v 3 v 26e g 地 6e c g 这样 l e 凰 矾 i i v 3 v 2 啦地 i 2 与定理c 的性质3 矛盾 子情形2 2 若坝6y 凰 f z 1 l 七 则有v v 4 e g v 2 v 46e g 这样 i e 鼠 凰 i l 啦魄 屹舰 l 2 与定理c 的性质3 矛盾 从而断言2 获证 口 2 2 最大亏格下界与上可嵌入图类 断言3 设三元函数 f x l 2 7 2 x 3 z l z 2 x 2 x 3 x 1 2 3 2 x l 2 2 x 3 3 x l x 2 2 3 r 当x l 1 2 2 2 x 3 2 时 有 z 1 2 z 3 0 证因为 显然 关于 差 现 x a 2 差 x 1 x 3 2 瓦o f z 勋以 当z 1 1 x 2 2 x 3 2 时 瑟 o 1 2 3 所以f x l z 2 z 3 z l z 2 z 3是严格单调递增函数 从而 i x l x 2 x 3 f 1 2 2 1 0 分别 断言3 证毕 由断言2 可知 k 的i k l 个顶点分别属于g a 的i k l 个连通分支 不妨设为 皿 飓 局k i 同时 记戤 i w l 1 2 3 因为 e g v t e h 1 h 2 竭k i 又因为g m 为完全3 部图 所以 于是有 e g k i x l x 2 x 2 x 3 x l x 3 x l x 2 x 2 x 3 x l x 3 又根据定理c 的性质3 有 i e h 1 h 2 h ij 1 4 1 e h 1 t 1 2 h l k l l 2 i k i 一3 2 t x 2 2 3 一3 联合 1 2 有 即 x l x 2 十x 2 x 3 x l x 3 2 x l x 2 x 3 一3 l x 2 x 2 x 3 x l x 3 2 1 x 2 x 3 3 0 此时z 1 1 现 2 z 3 2 综上所述 命题成立 与断言3 矛盾 2 高校教师在职攻读硕士学位论文 4 1 定理4 1 的证明 定理4 1 设图g 为连通图 图g 的顶点集存在一个尼 划分f k k k v l i 8 满足以下条件 1 k k 1u 叩uw 为多重完全3 部图g 的3 部点集 m l 2 t 2 3 2 d g 秽 三o m o d4 i k i 三o m o d2 v 6 k 则图g 是上可嵌入的 证假设图g 不是上可嵌入的 即亭 g 2 则由定理c 知存在图g 的边子集a 使得g a 满足其所有的性质 设矾 飓 仉为g a 的 所有连通分支 这里k c g a 2 因为图g 的顶点集存在一个昆 划 分 k 圪 且满足引理4 1 的条件 从而 v 1 i k 凰中的顶点 集是 k k k 中若干元素之并 记 a i v ji 巧 y 鼠 1 j s 而i k l o m o d2 所以 v h d l 吲兰o m o d2 码 a 下面证明i e 鼠 g f 4 因图g 为连通图 所以i e 凰 g l 0 下面分情 况讨论 情形1 若i e 凰 g i 1 因 d g v 三o m o d4 记 e v j d g t 4 n 扎 z t 所以 d e u d e z t y 五k v j6 a e 1 5 最大亏格下界与上可嵌入图类 则 电 t d a v 一1 4 n 一1 三1 m d2 v e v h dv e v h d 即在图趣中有奇数个奇度点 显然矛盾 情形2 若i e h i g l 2 由情形1 知 始 u 4 n 所以 电 u ed g 口 一2 4 n 一2 e v h d e v g d 从而 i e h i 互1 电 口 互1 撕 一2 2 4 n 2 2 一1 t y 丑 v e v h i 因此 p 飓 i e 风 l i y 甄 l 1 2 一1 一l y 见 1 1 2 n 7 一i y 甄 i 三o m o d2 这与定理c 的性质1 矛盾 情形3 若l e 盟 g i 3 同情形1 可得出 d 日t t d e 一3 4 一3 兰1 m d 2 v e v h dv e v 日d 即在图鼠中有奇数个奇度点 显然矛盾 综上所述 v 1 i k 都有i e h i g 4 这与定理d 的性质3 矛 盾 故定理4 1 得证 口 4 2 定理4 2 及定理4 3 的证明 定理4 2 设图g 为连通图 图g 的顶点集存在一个尸3 划分 m k k v 1 i 8 满足以下条件 2 5 高校教师在职攻读硕士学位论文 1 k k 1u 曙u 叩为多重完全3 部图g m 的3 部点集 m l 2 1 2 3 2 d c t 三2 r o o d4 m 兰l m o d2 面 则图g 是上可嵌入的 证假设图g 不是上可嵌入 即 g 2 则由定理c 知存在图g 的 边子集4 使得g a 满足其所有性质 设风 飓 风为g a 的所有 连通分支 这里k c g a 2 因为图g 的顶点集存在一个尼 划分 k 且满足引理4 1 的条件 从而 v l i 尼 凰中的顶点集 是 又 注意到这里每个v j v 1 0 i l i 2 如 这是因为 否则 若v v o 则 有y v f 且i v i 1 这与f c 矛盾 然后再由定理d 的性质4 f 在 a c v 1 中的度d g c f 3 因此由f c 1 的任意性 i e 2 l 3 1 c 1 i 因为 a c v 1 为偶图且c 1 c 我们有易 毋 所以 3 1 c 1 i i e 2 i i e l i 3 w 1 i 即 c l i v i i 这样 c a a i c i i c o i i c l l i v o l i i i y i 礼 由定理d 的性质5 定理证毕 定理5 2 设g 为肛边连通图 若存在图g 的 个顶点划分 k 使得每个a i r 都含有轮w j k j 1 i n 为生成子图 则 椰 g k 尚叫 k 2 l 3 证由定理a 和定理5 1 直接可得 口 最大亏格下界与上可嵌入图类 5 2 定理5 1 及定理5 2 中的界 下面我们通过图例来说明定理5 1 中的界是可达的 由定理a 从而 定理5 2 的界也是可达的 且对于某些图类比文献 1 1 中给的界更好 1 设g 毛 是由k k 2 个轮w 2 m m 2 的拷贝按图5 1 轮中心串 起来所得到的图 则g 毛 七是1 一边连通的 且去掉k 一1 条非吆0 1 2 k 的边 得到k 个连通分支 每个连通分支都为轮吆 显然 p 吆 三l m o d2 所以由定理b g 七 2 k 一 k 一1 一1 k 而由定理5 1 专 g m 1 南 k 所以 g 毛 七 k 隰蠓 m 2 吆礁 m 3 图5 1 1 边连通串轮图 2 设g 象 七是由k k 2 个轮 m 2 的拷贝按图5 2 轮中心串 起来得到的图 会囟 高校教师在职攻读硕士学位论文 m 2 磋 吆j 图5 2 2 边连通串轮图 m 3 略 嗾 显然嚷 七是2 边连通的 且去掉k 条非略 t 1 2 尼 的边 得 到k 个连通分支 每个连通分支都为轮嗉 显然卢 嗉 三l m o d2 所 以由定理b 毒 g 荔 知 2 k k 一1 k 一1 而由定理5 1 g 象 詹 k 一1 所以毒 g 象 k 一1 以上两个事实说明定理5 1 的界是可达的 由定理a 知 定理5 2 的 界也是可达的 3 对于上述两类图g 乞 七和g 象 因p 嘛 兰1 r o o d 2 0 1 2 七 所以 鸭 1 这样壹 略 k 这时对于歹 1 2 文献 1 1 给的界 k 嚷 南 嘛 忌一1 2 k 一1 i 1 这表明对于这两种图类 本文所给的界要优于文献 1 1 所给的界 最大亏格下界与上可嵌入图类 第六章后记 对图的拓扑参数 最大亏格的研究 前人已经作了很大的工作 得 到了很多重大结论 这一领域的研究已经日趋完善 但在最近几年内未 能取得突破性进展 其中主要是方法上很难突破 就目前而言 国内外 一些学者所作有关这方面的结果 主要是利用黄元秋教授在1 9 9 8 年得到 的非上可嵌入图的结构特征来作的 即定理c 估计最大亏格的研究要取 得实质性进展 必须要有新的理论出现 具体来讲 应该从另一个角度 来研究最大亏格 即从生成树入手 找到一个类似如定理c 的结论 这 需要我们今后继续努力 当然 就眼下我们还是有很多急需要解决的问 题 比如 1 目前还未曾有人研究过半径与最大亏格之间的内在关系 它们之间存在一个怎样的联系呢 2 若图g 是上可嵌入的 是否存在 点u y g 使得图g 口 仍是上可嵌入的 若不存在 是否能找到反例 呢 3 图g 和它的对偶图之间是否必有一个是上可嵌入的呢 当然 随着研究的深入还有很多的问题等待我们去研究 去挖掘 也许在现有 的理论方法下我们无法解决这些问题 我们应该偿试去寻找新的方法 这将是我们今后所面临的极具挑战性的工作 3 5 最大亏格下界与上可嵌入图类 参考文献 1 1 s k o v i e r am t h em a x i m u mo fg r a p h so fd i a m e t e rt w o j d i s c r e t em a t h 1 9 9 1 8 7 1 7 5 1 8 0 2 誊跏i e r am t h ed e c a yn u m b e ra n dt h em a x i m u mg e n u so fag r a p h j m a t hs l o v a c a 1 9 9 2 4 2 4 3 9 1 4 0 6 3 黄元秋 刘彦佩 图的上可嵌入性的邻域条件 j 应用数学学报 1 9 9 9 2 2 4 5 8 9 5 9 2 4 1 何卫力 刘彦佩 关于图的上可嵌入性的一个新的邻域条件 j 运筹学学报 7 3 2 0 0 3 9 2 9 6 5 h u a n gy u a n q i u l i uy a n p e i s o m ec h a r a c t e r i z a t i o n so fu p e m b e d d a b i l i t yo f g r a p h s j j n o r t h e r nj i a o t o n gu n i v e r s i t y 1 9 9 6 2 0 1 4 2 4 9 6 黄元秋 刘彦佩 s o m ec l a s s e so fu p p e re m b e d d a b l eg r a p h s j 数学物理学报 1 9 9 7 1 7 1 5 4 1 6 1 7 刘端风 黄元秋 新的上可嵌入图类 j 湖南师范大学学报f 自然科学版 2 0 0 2 2 5 3 1 4 8 盛秀艳 与顶点c 划分有关的上可嵌入图类 j 河北师范大学学报 自然科学 版 2 0 0 3 2 7 5 4 3 8 4 4 0 9 盛秀艳 新的上可嵌入图类 j 1 重庆师范大学学报f 自然科学版j 2 0 0 4 2 1 3 1 孓1 4 1 0 欧阳章东 黄元秋 张启明 与顶点a 划分有关的上可嵌入图类 已投稿 1 1 黄元秋 刘彦佩 图的最大亏格与图的顶点划分 j 数学学报 2 0 0 0 4 3 3 6 4 5 6 5 2 1 2 n o r d h a u s e a s t e w a r t b m w h i t e a t o nt h em a x i m u mg e n u so fag r a p h j j c o m b i n t h e o r y 1 9 7 1 1 1 2 5 8 2 6 7 1 3 刘彦佩 图的可嵌入性理论胁御 北京 科学出版社 1 9 9 4 f 1 4 n e b e s k y l an e wc h a r a c t e r i z a t i o no ft h em a x i m u mg e n u so f g r a p h s j 3 c z e c h o s l v a km a t h 1 9 8 1 3 1 1 0 6 6 0 4 6 1 3 1 5 1k u n d a s b o u n d so nn u m b eo fd i s j o i n ts p a n n i n gt r e e s j j o m b i n a t o r i a lt h e o r y s e r b 1 9 7 4 1 7 1 9 9 2 0 3 3 7 高校教师在职攻读硕士学位论文 1 6 j u n g e r m a n m ac h a r a c t e r i z a t i o no fu p p