（运筹学与控制论专业论文）关于图的可嵌入性的若干结果.pdf

摘要 本文主要研究拓扑图论的一个重要分支一图的嵌入性以及图的亏格的问题，给出了 三正则图的亏格的计算公式，证明7 两类可上可嵌入的图类，得到了边集亏数具有内插 值的性质，最后对图的s 丁p 数与图的嵌入的关系做了研究具体内容如下t 1 利用x u o n g 树的”t 于数”得到了三正则图的最大亏格的计算公式，根据图的 余数的插值定理给出了三正则图的一般曲面亏格的计算公式 2 利用“手术”运算以及反证法；得到了具有一因子的平面近三角剖分图是上可嵌 入的，最后得到了一般条件下的近三角剖分图是上可嵌入的 3 利用n e b e s k y 的不可上可嵌入性条件，得到了两类特殊二部图是上可嵌入的。 4 ，通过对边集亏数的研究得到1 其具有内插值的性质 5 给出了图的s t p 数j ( g ) 与图的b e t t i 亏数u ( g ) 之间的关系，即 存在图g 的边子集z 南满足 。( g ) s 蛳( 2 + b ( g _ - _ 一e o ) 一盯( g ) ) p o 其中c ( g e o ) 为g 一岛的奇分支数，b ( c 一晶) 为g e o 中具有奇b e t t i 数的分支 数；令p o = c ( g e o ) 一1 最后我们讨论了一类图的s t p 数与图的边连通度以及上 可嵌入的问题 关键词t上可嵌入，最大亏格，特殊二部图，近三角剖分，边集亏数，b e t t i 亏 数，s t p 数，边连通度 a b s t r a c t t h e e m b e d d i n ga n dg e n e r ao 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 l y i nt h i s p a p e r ，f i r s t l y , w eg i v et h ef o r m u l a eo ft h eg e n u so f3 - r e g u l a rg r a p h ； s e c o n d l y , w ep r o v et h a tt w oc l a s s e so fg r a p h sd x eu p e m b e d a b l e ；t h i r d l y w ei n v e s t i g a t e t h ep r o p e r t i e so fs u b - e d g e - s e t sd e f i c i e n c y ；l a s t l y , w eg i v et h er e l a t i o n sb e t w e e nt h e s t pn u m b e ro fag r a p ha n dt h ee m b e d a b i l i t yo fag r a p h s o m er e s u l t sw i l lb eg i v e ni n t h et h e s i sa sf o l l o w s ： 1 g i v i n gaf o r m u l a eo fc o m p u t i n gm a x i m u mg e n u so fa3 - r e g u l a rg r a p ha n de x t e n d i tt ot h eg e n e r a lc o n d i t i o n ； 2 g i v i n gt h eu p p e r - e m b e d d a b i l i t yo fs p e c i a lb i p a r t i t eg r a p h s ； 3 g i v i n gt h er e l a t i o n sb e t w e e nt h em a x i m u mg e n u so fag r a p ha n di t si n d e p e n d e n t e d g e sa n do b t a i n i n gt h eg r a p hi su p p e r e m b e d d a b i l i t yi fi ti sap l a n eg r a p ha n dw h o s e d u a lg r a p hh a s1 - f a c t o r s ； 4 g i v i n gt h ei n t e r p o l a t i o nt h e o r e mo nt h es u b - e d g e - s e t sd e f i c i e n c ya c c o r d i n gt o t h ef o r m u l a eo fb e t t id e f i c i e n c yg i v e nb yn e b e s k ， 5 g i 、r i n gt h er e l a t i o n sb e t w e e nt h es t pn u m b e ra n dt h ee m b e d d a b l i t yo fag r a p h k e yw o r d s ：m a x i m u mg e n u s ，n e a r - t r i a n g u l i t i o no fag r a p h ，u p p e r e m b e d d a b l i t y , b e t t i d e f i c i e n c y ，s u b - e d g e - s e t sd e f i c i e n c y ls t pn u m b e r 吕长青硕士学位论文答辩委员会名单 姓名职称单位备注 洪渊教授华东师范大学主席 董纯飞教授华东师范大学 束金龙副教授华东师范大学 戴浩晖讲师华东师范大学秘书 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成果据 我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研 究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢 意。 作者签名；翌l 墼盔日期：五盟互鎏玉目勰日 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留学位论 文并向国家主管部门或其指定机构送交论文的电子版和纸质版有权将学位论文用于非 赢利目的的少量复制并允许论文进入学校图书馆被查阅有权将学位论文的内容编入有 关数据库进行检索有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后 适用本规定。 学位论文作者签名： 日期 易乞畜 2 塑盔纽互国勰日 导师签名； e l 期 碣a 垃幽丝生壬唆 第一章概述 图论是组合数学的一个主要组成部分，近几十年里，它已经发展成数学的一个重要 分支。由于图论的本身魅力和其在信息社会中一些学科领域诸如计算机，运筹学，系统 工程以及物理学，电子学，生物学，化学等方面的广泛应用，因此，越来越受到科学界 尤其是数学界的重视和关注。由于像组合数学，代数学，拓扑学以及概率方法的结合， 现代图论除了传统的研究领域外已发展为包括代数图论，拓扑图论，以及随机图论等分 支在内的多个新的领域，促进了图论发展 图的嵌入性理论及图的亏格是拓扑图论的一个重要的问题。自从n o r d h a u s ( 文献 【2 6 ) 等引入图的最大亏格概念以来，图的最大亏格以及图的上可嵌入性引起了广泛关 注。 1 1基本概念 设图g = ( v e ) ，其中v 为顶点集，v = v ( c ) = 7 2 1 ，v 2 ，) ，i v i = u 称为 图g 的阶数，e 为边集，e = e ( c ) = e 1 ，e ”，e 。 ，i e | = e 为图g 的边数设 ( u ，v ) e ，则称顶点u 与u 相邻接，记为u u ，否则不相邻，记为“u 。若u 和 是边e 的两个端点( 记为e = ( ， ) = 口) ，则称“( ) 与e 关联与 关联的边数 称为 的度( 次) ，记作d e g ( v ) = d ( v ) 。图g 中最大、最小的度数分别记为a ( c ) 和 d ( g ) 。若( g ) = 6 ( g ) ，则称图g 为正则图记( g ) = e 一 + 1 称为图g 的b e t t i 数。如果一条边有相同的顶点，则称这条边为环，如果有两条边有相同的顶点则称这两 条边为重边，没有环和重边的图称为简单图如无特别说明，本文所研究均为有限无向 简单图 g 的一条途径是指一个有限非空序列w = o e 。u 。e 2 e ，它的项交替地为顶 点和边，使得对1 sk ，岛的端点是v h 和w 。；其中，和讯分别称为的 起点和终点，而v - ， 。，一，称为缈的内部顶点整数k 称为的长若途径w 的边e 。，e 。，e k 互不相同，则w 称为迹。称一条途径是闭的，如果它有正的长且起 点和终点相同若一条闭迹的起点和内部顶点互不相同。则它称为圈一个图的最小 的圈的长称为这个图的围长。若途径w 的边 o ，u 一，强互不相同，则w 称为路。 包含g 的每个顶点的路称为g 的h a m i l t o n 路 类似地，g 的h a m i l t o n 圈是指包含 g 的每个顶点的圈。 第一章概述 2 g 的两个顶点和u 称为连通的，如果在g 中存在从“到 的路。连通是顶 点集v ( v ) 上的一个等价关系。于是存在v ( c ) 的一个分类，把v ( a ) 分成非空子集 k ，k ，k ，使得两个顶点“和”是连通的当且仅当它们属于同一个子集k 。子图 g h 】，g ，g k 】称为g 的连通分支。若g 只有一个分支，则称g 是连通的； 否则，称g 是不连通的。 若v ( c ) 的子集y 使得v ( u ) 一v 不连通，则y 称为v ( c ) 顶点割。k 顶点割 是指有k 个元素的顶点割。若g 至少有一对相异的不相邻顶点，则g 所具有的k 顶点 割中最小的，称为g 的连通度，记为k ( g ) 。若k ( g ) k ，则称g 为k 连通的 对v ( c ) 的子集s 和s ，用暇 表示一个端点在s 中，另一个端点在s 中的所有 边的集合所谓g 的边割是指形为旧s 的e ( g ) 的子集，其中s 是v ( c ) 的非空真 子集。一个k 边割是指有k 个元素的边割。若g 是非平凡的，g 的所有k 边割中最小 的k ，称为g 的边连通度，记为k ( g ) 。若一( g ) k ，则称g 为k 边连通的 称图耳为图g 的子图，如果v ( h ) v ( g ) ，甄胃) e ( g ) ，并且 p h 是妒。上 的限制。g 的生成子图是指满足v ( h ) = v ( v ) 的子图日假如y 7 是y 的一个非空 子集以v 为顶点集，以两端点均在y 中的边的全体为边集所组成的子图，称为g 的由y 导出的子图，记为g 【y 。 连通的无圈图称为树。g 的生成树是指g 的生成子图，它同时又是树。 此外还有些未给出的术语与记号将在文中给出或参阅文献 3 ，2 1 。 1 2圉的可嵌入与图的亏格 曲面是一个紧的连通的2 一维闭流形。曲面可分为可定向曲面与不可定向曲面一 个可定向曲面瓯( 0 ) 是由一个球面添上 个环柄得到。不可定向曲面帆( 21 ) 是由一卟球面挖掉k 个圆盘而分别补上m s b i u s 带得到其中，岛称为球面，昌称为 环面，岛称为双环面；肌称为射影平面，飓称为克莱因瓶。 如果一个图画在曲面s 上使得它的边仅仅在端点处相交，则称这个图嵌入到曲面 s 上。图g 嵌入曲面s 上称为2 - 胞腔嵌入，如果s g 中每个分支同胚于一个开圆 盘。此时，每个分支称为g 在曲面s 上嵌入的一个面 由于不连通图无2 剖腔嵌入，所以如无特别说明以下提到的图均为连通图。 一个曲面s 的e u l e r 示性数x ( s ) ( 文献 2 1 ) 定义如下：当s = s 时，x ( s ) = 2 2 h ；当s = g k 时，x ( s ) = 2 一k 第一章概述3 e u l e r 公式( 文献 2 1 ) 设g 是个2 一胞腔嵌入在曲面s 上的图，如果g 有n 个 顶点，q 条边，在曲面s 上有，个面，则n q + f = x ( s ) 。 图的嵌入也可按组合的方式表示t 图g 一个嵌入是一个有序对1 i = ( ”，a ) ，这里 ”= ( 巩i y ( g ) ) 是一个旋转系统，即对v v v ( v ) ，“是指与v 相关联的边的长 为d ( v ) 的循环置换，a 是一个关于边的符号映射，即v e e ( g ) ，a ( e ) l ，一1 ) ； 给定图g 的一个嵌入，称g 是嵌入的 下面的定理保证了如果一个图可在一个可定向曲面上的2 胞腔嵌入那么这个2 一胞 腔嵌入可由其相应的一个旋转系统确定。 ( h e f f t e r e d m o n d s 定理) ( 文献 2 1 ) 一个图g 的每一个旋转系统都导出这个在 某个可定向曲面上的一个2 一胞腔嵌入。反之，一个图g 在某个可定向曲面上的一个2 胞腔嵌入都对应这个图的唯一的旋转系统。 在g 的一个2 一胞腔嵌入y i 中，如果一个圈上有奇数个边按 对应一l ，则这个豳 称为单侧的；否则称为双侧的。在g 的一个2 胞腔嵌入中，如果存在一个单侧圈， 则称是g 在一个不可定向曲面上的嵌入；否则，称n 是g 在一个可定向曲面上的 嵌入。 假设图g 是h 嵌入的，其顶点数为n ，边数为q ，有，个面圈，则称x ( n ) = n q + f 为嵌入的欧拉示性数，下面定义了嵌入的亏格 7 ( n ) ： 1 一弑1 ( ) 是可定向嵌入 l2 一x ( h )，h 是不可定向嵌入 称e g ( h ) = 2 一x ( n ) 为的欧拉亏格，如果一个可定向嵌入的亏格为g ，也称n 是g 在品的一个嵌入，这里晶是亏格为g 的可定向曲面。对于不可定向的情况类似 的给出。 在g 的卟2 一胞腔嵌入i i 上，设c = v 0 e l v l e 2 e 1 v l 是一个双侧圈。对于任意 的i = 1 ，2 ，1 ，如果e = 7 r 爨( e ，) ，则所有的边7 r 。( 岛) ，t ( 。2 ，( 岛) ，磕。( e ；) 称为圈c 的左侧边，所有含有圈g 的左侧边的a 的桥的并集称为g 的左图，记为 q ( c ) ；类似地，可以定义g 的右图，记为g ，( e ) 。在g 的一个2 一胞腔嵌入上， 如果g ，( g ) uc 与g ，( c ) ug 没有公共边则称g 是可分离的圈；如果g ，( g ) uc 与 g ，( g ) uc 中有一个限制在上的亏格为0 ，则称c 在n 上是可收缩的。 第一章概述 图g 的亏格1 ( g ) 是指使得g 能2 一胞腔嵌入到可定向曲面上的最小的整数 h 一个图g 的不可定向亏格彳( g ) 是指使得g 能2 一胞腔嵌a n 不可定向曲面k 上 的最小的整数k 。一个图g 的e u l e r 亏格j ( g ) ( 文献 2 l ”为它的亏格的2 倍与不可 定向亏格的最小值，即亏( g ) = m i n 2 7 ( a ) a 社，( g ) ) 一个图的亏格与不可定向亏格有 如下关系： 定理121 ( 文献 2 1 ) 如果一个连通图不是树，那末 一4 - 1 摹1g 的最大亏格恤( g ) 是指使得g 能2 - 胞腔嵌入到可定向曲面岛上最大 的整数g ；一个图g 的最大不可定向亏格嘶f ( g ) 是指使得g 能2 一胞腔嵌入到不可定 向曲面 上的最大的整数h 。特别地，一个图的亏格为0 当且仅当它是平面图。 1 9 6 6 年r d u k e ( 文献 7 】) 证明了图g 在可定向曲面2 - 胞腔嵌入的插值定理 d u k e 定理设g 是一个连通图，那么对任意整数g 7 ( g ) ，伽( g ) ，g 可嵌 入到黾上这里h ( g ) ，伽( g ) 称为亏格区间。 1 9 7 8 年，s t a h l ( 文献【3 2 ) 证明了图在不可定向曲面2 胞腔嵌入的插值定理。因 此考虑一个图g 的所有可2 胞腔嵌入，只需确定它的亏格( 不可定向亏格) 和最大亏 格( 最大不可定向亏格) 。 g 的圈空间的维数是口( g ) ( = ie ( g ) | 一iv ( a ) i + 1 ) ，它又称图g 的b e t t i 数 如果一个图g 的最大亏格7 m ( g ) 一i i g 掣l 。则称g 是上可嵌入的。设t 是g 的一个 支撑树，g e ( t ) 称为t 的余树，t 的余树中具有奇数条边的连通分支称为g 中r 确定的余树的奇连通分支；这样的奇连通分支数称为g 中r 确定的余树的奇连通分 支数，记为( g ，t ) 。记( g ) = m i n u ( g ，t ) lt 是g 的任意一个支撑树) 。x u o n g 在文【3 4 】和刘彦佩在文【2 0 】独立给出了计算7 m ( g ) 的定理： 定理1 2 2设g 是一个连通图，则 ( 1 ) 7 m ( g ) = l 她弩必j ( 2 ) g 是上可嵌入的当且仅当u ( g ) = 0 或1 n e b e s k ：p 给出了另外一个计算u ( g ) 的公式 第一章概述 5 定理12 3 ( 文献2 3 1 ) 设g 是一个连通图，则 ( 1 ) g 是上可嵌入的当且仅当c ( g a ) + b ( g a ) 一2 i a l ，这里a 是e ( a ) 的任 一个子集。 ( 2 ) w ( g ) 一i n a x a c e ( g ) c ( g a ) + b ( g a ) 一i a i 一1 ，。 这里a e ( v ) ，c ( a a ) 表示g a 的所有分支数，b ( c a ) 表示g a 中 b e t t i 数是奇数的所有分支数。 由定理1 22 知到，如果一个图有两个边不重的支撑树，那末它一定是上可嵌入的。 k u n d u 在文1 8 中证明了任何一个4 一边连通图都有两个边不重的支撑树，由此可知任 何一个4 一边连通图都是上可嵌入的。 虽然对于任意边连通度为4 的图都是上可嵌入的，但是对于较弱的条件下一对于 边连通度小于或等于3 的图并不能保证其上可嵌入性，甚至是最简单的三正则图也不能 保证其上可嵌入性( 如图1 1 ) ，因此对于边连通度3 的图，在研究其最大亏格与上可 嵌入性问题时，一方面研究特殊图类的上可嵌入性( 文献 1 5 ，3 0 ，3 1 ) ，另一方面研究 图的最大亏格的界，以求得到最大亏格的好的界( 文献【5 ，6 ，1 2 ，1 4 ，1 7 ) 。 由此可知，研究某一类连通度小于4 的图的上可嵌入或者它的最大亏格的下界很有 意义。 图11 1 3本文主要内容 本文归纳起来主要分两部分；第一部分为第二章，讨论了三正则图的最大亏格计算 公式，并确定了三正则图的一般亏格计算公式第二部分包括第三章和第四章，研究了 第一章概述 6 特殊图类的上可嵌入性。第三部分包括第五章和第六掌，研究嵌入图的有关参数的性 质。 本文定理的编号采用它们在各自章节中出现的编号，其中末交待的符号和概念请参 见对应章节。 1 3 一, - t n 图最大亏格计算公式 本文讨论了3 一正则图的叶子数l ( t ) 与最大亏格7 m ( g ) 之间的关系并给出了3 正 则图最大亏格的计算公式：伽( g ) = j ( f ( t ) + r 一昂) 这里，t 是g 的x u o n g 树， l ( t ) 是7 1 的叶数，只，昂分别是g t 中偶长路数与奇长圈数。作为应用我们计算了 若干图的最大亏格，最后将该公式推广到一般曲面上。 定理2 4 设g 为3 一正则上可嵌入图，则存在树t 满足 卢( g ) ；o ( m o d 2 ) 卢( g ) io ( m o d 2 ) ，g t 中无奇圈 9 ( a ) i1 ( r o o d ：) ，g t 中有一个奇圈 到亏格为1 的曲面上，则存在树t 满足 卢( g ) ；o ( m o d 2 ) 卢( g ) ；o ( m o a 2 ) ，g t 中无奇圈 卢( g ) il ( m o d 2 ) ，g t 中有一个奇圈 本章集中探讨特殊二部图的上可嵌入性，并证明了如下结果：( 1 ) 设g = ( x ，y ：e ) ， 定义g 3 = ( v ( g 3 ) ，e ( g 3 ) ) ，其中v ( c 3 ) = v ( g ) ，e ( g 3 ) = e ( g ) u e = x yjd g ( z ，y ) = 3 ，x ，y y ) ，则g 3 是上可嵌入的；( 2 ) 设g = ( x ，y ；e ) ，j x l = l y l = n ( n 3 ) ， 对任一对d c ( x ，y ) = 3 的z x ，y y ，均有a ( x ) + d ( y ) n + 1 ，则g 是上可嵌入 的 3 近三角剖分图的上可嵌人性 第一章概述 7 本章首先考察了平面近三角剖分图的最大亏格与独立边集之间的关系。运用手术运 算以及数学归纳法得到了下面近三角剖分图在一定条件下是上可嵌入的。设口是平面 近三角剖分图g 的一个平面嵌入的几何对偶，如果g + 有【 纠个独立边集，那么图g 的最大亏格7 m ( g ) k z ( c ) 一l ，这里妒和p ( g ) 分别表示图g 在平面上嵌入的面 数与g 的b e t t i 数。特别地，如果妒；0 ( m o d2 ) 即g 有1 一因子，则g 是上可嵌入 的。 以及 定理4 4 设g 十是近三角剖分图g 的对偶图，设g + 有睦纠个独立边集，如果图g 的最大亏格 t m ( g ) = ；卢( g ) 】一1 当且仅当g 不是上可嵌入的且对于图g 面边界不是 3 的面上的任意一边e ，存在g e 的一棵支撑树丁使得e 在g t 奇连通分支中， 这里妒和z ( o ) 分别表示图g 的面数与g 的b e t t i 数 k 定理4 9a 1 ，a 2 ，k 为g 的个三角，若【u 厶】是连通的且任意去掉g 中若 干条边都无g 0 子式，则g 是上可嵌入的特别的，( g ) = 1 ，当k i l ( m o d2 ) ； u ( g ) = 0 ，当k ；0 ( m o d2 ) k 定理4 1 0 设g 有k 个三角1 ，2 ，趣的近三角剖分图，若 u d 中有分支 i = l 口1 ，啦，其中至多有一个含有奇数个三角且对每一个分支0 - i ( i = 1 ，2 ，s ) 任 去若干条边都不包含g o ，则g 是上可嵌入的。 5 关于图的边集亏数的内插定理 本章通过n e b e s k p 在文 2 3 】给出的b e t t i 亏数的计算公式运用边变换和反证法给 出了图g 的边集亏数u ( g ，a ) 的内插定理 定理5 3 设g 是连通图，a 7 与a ”是g 的两个不同的边子集，且w ( a ) u ( a ”) ， 如果存在一个整数m ，满足m = u ( a 7 ) ( r o o d 2 ) 且u ( a ) sr n5w ( a ”) ，则存在图g 的 一个边子集4 ，使得w ( a ) = m 。 定理5 4 设g 是连通图，g m ，如上所定义；则存在g 的一个边子集a e ( c ) ，使得g = i 1 ( 卢( g ) 一u ( a ) ) 6 关于图的s t p 数与图的嵌人 第一章概述 8 本章讨论了图的s t p 数一( g ) 与图的b e t t i 亏数u ( g ) 之间的关系：即存在图g 的边子集岛满足 u ( g ) 劭( 2 + b ( g = - 一e o ) 一口( g ) ) j o 其中c ( a e o ) 为g e o 的奇分支数，b ( g e o ) 为g 一岛中具有奇b e t t i 数的分支 数；令p o = c ( g e o ) 一1 。最后我们讨论了一类图的s t p 数与图的边连通度以及上 可嵌入的问题。 第二章3 一, - f h i j 图最大亏格计算公式 2 1引言 由上一章可知，对于一个图边连通度小于或等于3 并不能保证其上可嵌入性，对于三 正则图也是如此。x u o n g 和刘彦佩分别给出了图的最大亏格的计算公式( 引理1 22 ) ， 根据这个计算公式人们在研究图的最大亏格时只要找到满足其余树上奇连通分支数最 小的支撑树即x u o n g 树即可；由此可计算图的最大亏格。这里考虑了这样一个问题t x u o n g 树的一度点数即叶子数与图的最大亏格之间的关系以及三正则图的最大亏格的 计算公式，最后将该公式推广到一般亏格。 2 2有关引理和结论 设丁是图g 的支撑树，图g 的b e t t i 亏数为u ( g ) = m i n w ( g ，t ) 若存在图 g 的某个支撑树t 满足w ( g ，t ) = u ( g ) ，则称支撑树t 为图g 的x u o n g 树j i n e r c h e n 等对于3 一正则图给出了下面的定理- 引理2 1 ( 文献【5 ) 若g 是3 ，正则图，则图g 的余树c 中只有路和圈 设g 是3 一正则图，t 为图g 的x u o n g 树，设丁中三度点的个数为f 个，二度点 的个数为m 个，t 中一度点称为“叶子”，其数记为t ( t ) 。令f 一( r ) = r h 辨l ( t ) ， 其中t 为x u o n g 树。 由引理2 1 可知3正则图的余树中只有圈和路，所以令余树中偶长路数为p 。， 奇长圈数为p 口，偶长圈数为“，奇长路数记为m 。令p p 。+ p 6 引理2 2 若g 为3 - 正则图，t 是它的支撑树，则t 中的叶子数等于t 中三度点数 加2 ，即l ( t ) = f + 2 证明：由于树r 为g 的支撑树，所以t 的顶点数l y ( t ) i = l v ( c ) l = l + m + i ( 7 1 ) ， t 的边数i e ( 丁) l = | e ( g ) i 一1 ，根据一个图的边数与顶点度的关系可得2 1 e ( t ) l = 2 ( i v ( g ) 一1 ) = 3 1 + 2 m + l ( t ) ，于是得至0z ( t ) = 2 + 2 引理2 3若g 为3 正则图，则它的支撑树t 的二度点数必为偶数。 9 第二章3 正则图最大亏格计算公式 证明：由于r n = l y ( g ) i f t ( t ) = i v ( g ) i 一2 1 ( t ) + 2 ，而3 一正则图的顶点数i v ( g ) 为偶数，引理显然成立。 引理2 4 若g 为3 一正则图，则它的支撑树t 的二度点等于其余树e 中路数的二倍， 即m = 2 p = 2 ( 十肌) 。 因为图g 为3 一正则图，余树a 中的每一条路的两个端点为1 度点，其必然对应 于树丁的两个二度点。引理24 显然成立。 定理2 1 设g 为3 - 正则图，一定存在一个支撑树t 使得l ( t ) 在所有的x u o n g 树中 最大。 因为图g 的x u o n g 树有有限个，所以必定存在一个叶子数最大的x u o n g 树，定理 成立。 定理2 2 图g 为3 正则图，则 m = ；( z ( t ) + 孤一p z ) 其中，r 是g 的x u o n g 树，t ( t ) 是t 的叶数，只，玮分别是g t 中偶长路数与 奇长圈数。 证明；因为 f l ( g ) 一u ( g ) 1 m 2 _ _ 。 所以存在一个支撑树r 满足 卢( g ) 一u ( r ) 7 m 2 一 而 口( g ) = i e ( g ) i i v ( g ) i + 1 = ；i v ( g ) i i v ( g ) i + l = i l v ( g ) i + 1 由引理22 ，23 及其证明可得 所以 得证 v ( g ) i = l + m + z ( t ) = 2 1 ( t ) 一2 + 2 ( p 。十p d ) = 2 l ( t ) + 2 p 一2 卢( g ) = l ( t ) + p l + 1 = l ( t ) + p 】1 7 m 2 i ( 。( t ) + p 一“( t ) ) 。i ( f ( 丁) + p n p 口) 1 0 第二章3 正则图最大亏格计算公式 由定理2 , 2 可得3 _ 正则图中x u o n g 树叶子的计算公式 推论2 1 l ( t ) = 2 m + u ( 丁) 一p 且l y ( g ) i = 2 1 ( t ) + 2 p 一2 由推论2 1 显然有 定理2 3 z 。( 丁) = 2 y m + u ( g ) 一吨n p ，其中t 为x u o n g 树 推论2 2设g 为3 - 正则图，丁为其x u o n g 树，若丁的余树g t 中无路，则l ( t ) 在所有的x u o n g 树中最大。 由定理2 2 可得该推论成立 定理2 4 设g 为3 - 正则上可嵌入图，则存在树丁满足 1 m ( g ) = ( t ) + p 。 ( t ) + p 。 ( r ) + 卢( g ) io ( m o d 2 ) 卢( g ) i0 ( m o d 2 ) ，g t 中无奇圈 卢( g ) il ( m o d 2 ) ，g t 中有一个奇圈 证明t 由于9 ( a ) 与u ( g ) 同奇偶性，引理12 1 以及定理2 2 可得定理成立。 推论2 3 设g 是3 正则二部图，则存在树t 满足 伽= 言( f ( t ) + p 。) 因为z - 部图中无奇圈，其任一余树中也无奇圈，由定理2 可得该推论成立。 一个图为h a l i n 图，如果一个图为三连通的平面图，且某一面，的边界a ，所有点 的度为3 ，把边界上所有的边删去得到一个除度为1 的点外其余的所有顶点的度都至 少为3 的树。 推论2 4若g 为3 一正则h a l i n 图，则存在g 的x u o n g 树t 满足； 椰，= | ：兹( g ) 刮- - - o ( 篡m o d 2 证明：因为g 为h a l i n 图，所以存在一个面，其边界a ，上的点的度为3 ，g e ( o f ) 为g 的支撑树，记为t 。那么o 就是g 的余树且是它的唯一的连通分支。若a ，有偶 鱼鎏笠型型达塑幽 ：1 2 数条边，则0 3 ( t ) = 0 ，显然t 为g 的x u o n g 树。若a ，有奇数条边，令t ，为g 的不 同于t 支撑树，显然i e ( t ) j = i e ( t 引，所以i e ( o ：) l = f e ( g 一丁引所以g t ，至少 有一个奇连通分支，即u ( ? 1 ) l ，所以u ( d s “( t 钆于是“( 丁) ：u f 一) ：m i n r 。 所以t 为g 的x u o n g 树。显然g 是上可嵌入的，由定理2 4 可得结论成立。 2 3定理的推广 文献 2 8 j 给出了下面的引理， 引理2 5 设g 是一个连通图，则g 必然满足下列条件之一， ( a ) 对任意的非负整数9 ，只要图g 嵌入到可定向曲面岛上，则存在支撑树 t ，使9 2 ( 卢( g ) 一u ( t ) ) 其中，卢( g ) ，u ( 丁 ) 分别是图g 的b e 撕数和由t 确定 的余树的奇连通分支数 f b ) 对图g 的任意一个支撑树t ，g 可以嵌入某个可定向曲面上使其恰好有 m ( t ) + 1 个面。由引理2 5 可知，仿照定理2 4 的证明可得 定理2 5 设g 为3 一正则图，可嵌入图亏格为1 的曲面上，则存在树t 满足 ，y ( g ) i ( t ) + i ( t ) + t ( t ) + p 。 卢( g ) 兰o ( m o d 2 ) p ( g ) io ( m o d 2 ) ，g t 中无奇圈 卢( g ) i1 ( r o o d 2 ) ，g t 中有一个奇圈 第三章特殊二部图的上可嵌人性 3 1引言 本章从另一个相反的角度出发，根据n e b e s k p 与黄元秋提供的一个关于不是上可 嵌入图的充要条件，我们主要证明下述结果：( 1 ) 设g = ( x ，y ；e ) ，定义g 3 = ( v ( a 3 ) ，e ( a 3 ) ) ，其中v ( g 3 ) = y ( g ) ，e ( g 3 ) 兰e ( a ) u e = x yid a ( x ，y ) = 3 ，z x ，yey ) ，则g 3 是上可嵌入的；( 2 ) 设g = ( x ，y ；e ) ，i x i = j y i = n ，对任一对 d a ( x ，y ) = 3 的z x ，y y ，均有d ( z ) + d ( y ) n + 1 ，则g 是上可嵌入的。 3 2相关的定义和引理 定义3 1 设g = ( x ，y ；e ) 为一个二部图，定义g 3 = ( v ( a 3 ) ，e ( g 3 ) ) ，其中v ( a 3 ) = v ( g ) ，e ( g 3 ) = e ( g ) u e = x yid a ( x ，y ) = 3 ，x x ，y y 。 定义3 2 对任意的a e ( g ) ，c ( g a ) 表示g a 的连通分支数，b ( c a ) = f i f 是g a 的一个连通分支，且z ( f ) ；l ( m o d 2 ) ，b ( a a ) = l _ 日( g a ) i 。 定义3 3 对g a 的两个不同的连通分支只日 1 g ( e h ) = e = u v l ue y ( f ) ，v 矿( 日) ， e ( 只g ) = e = u v i u y ( f ) ，v 隹v ( f ) 。 定义3 4 设g = ( x ，y ；e ) 为一个二部图，f 是g a 的个连通分支，i y p ) i 是指 f 中x 型节点数与y 型节点数之和。 定义3 5t 是简单连通图g 的一棵生成树，u ( g ，t ) 是指g e ( t ) 中含有奇分支的 数目；而u ( g ) = m i n t u ( g ，t ) 是g 的b e t t i 数，其中r a i n 取遍g 的所有生成树t 。 引理3 1 ( 文献 2 0 )若g 是一个简单连通图，g 是上可嵌入图当且仅当u ( g ) l 。 引理3 2 ( 文献 1 5 ) 若g 是一个连通简单图，如果g 是不髓上可嵌入的，那么存在 a z ( v ) ，满足下列性质： ( i ) c ( g a ) = 6 ( g a ) 2 ； 1 3 第三章特殊二部图的上可嵌入性 ( i i ) 3 2 b ( a a ) 一i aj 墨4 ； ( i i i ) 对g a 的每一个连通分支f ，f 是g 的一个导出子图； ( i v ) 对g a 的任意k 个不同的连通分支，i e ( 只】，只纠一，只k ) i 2 k 一3 ；特别地对于 a a 的两个不同的连通分支e h ，e ( f i h ) 1 注：由引理3 2 知，对g a 的每一个连通分支f 有以下结论： 事实1由性质( i ) 知卢( f ) ；l ( m o d 2 ) ； 事实2g 是一个二部图时，l y ( f ) i 4 ( f 中至少有2 个x 型节点和2 个y 型节 点) ； 事实32 i a i = i e ( f i ，a ) l ，i = 1 ，2 ，t 3 3主要结果 定理3 1设g = ( x ，y ；e ) 为一个二部图，若g 3 = ( v ( a 3 ) ，e ( g 3 ) ) ，其中v ( a 3 ) = y ( g ) ，e ( g 3 ) = e ( g ) u e = x yld g ( z ，y ) = 3 ，z x ，y y ) ，则g 3 是上可嵌入的。 证明；假设g 3 是不能上可嵌入的，由引理3 2 知t 存在a e ( g ) 满足引理3 3 的 ( i ) 一( i v ) 性质令r = 日，f 2 ，只) 0 = b ( a 3 a ) ) 是g 3 a 的所有连通分支因为 g 是一个二部图，由g 3 的定义知t伊是一个二部图且g 3 a 的每一个连通分支也是 一个二部图。记只= ( 置，m ；目) ，i = 1 ，2 ，t 结论3 1对每一个e e 口( 只，毋) ，则e e ( g ) 。 假设e = ( x ，y ) e 点b s ( f i ，f j ) e ( g ) ，其中x 五，y 巧。由g 3 的定义知t 存在一条距离为3 的路连接x ，y ，令p = x y l k x l 。y ，其中y l k k ，x l 。x k 由 于只是一个= 部图，故至少存在一点y 1 ；m ，使得x y u e ( g ) ，同理至少存在一 点n ，ex j ，使得z l j ee ( g ) 。于是得到d g ( y l i ，z 1 。) = 3 ，d c , ( y l k x l j ) = 3 。 由g 3 的定义知：z l m 1 。e ( g 3 ) ，x l j y l k e ( c 3 ) 。显然 z g ，x y lj ：，x l 。y l k ，x l m y ， z 1 。1 。，x l j y l k ) a ( r ，玛，r ，f m ) ，因此l e a a ( 只，乃、r ，) l 6 ；而由引理3 2 的 性质( i v ) 知t | f 扫( 只，f j ，f k ，f m ) f 2x4 3 5 ，这就导致矛盾。 结论3 2g 3 是2 ，边连通，即对每一个只r ，i e ( 只，g 3 ) i 2 ，i = 1 ，2 ，一，t 。 反证，假设存在一个连通分支只r ，使得i f ( 只，g 3 ) i = 1 ，令e = ( x ，y ) 既。( 只，毋) ，其中x 五，y 巧。由于只是一个二部图，故至少存在一点y 1 。， 1 4 第三章特殊二部图的上可嵌 性 使得x y l 。e ( c ) ，同理至少存在一点1 ，玛，使得茁“e ( g ) 。由结论3l 知： e e ( g ) 。于是得到d g ( z 1 j ，y 1 。) = 3 ，由g 3 定义知：x l j y l l e ( c 3 ) 这导致矛盾。 结论3 3 对每一个只r ，i e ( 只，g 3 ) l 3 ，i 一1 ，2 ，t 。 反证，由结论32 可假设存在一个连通分支只r 使得j e ( 只，g 3 ) j = 2 。 ( 1 ) 不妨设存在两个不同的连通分支毋，咒，使得e ( 只，毋) = x l l y l j ，e ( e ，r ) = z 2 。目1 k ，其中x x 2 ；玉( 可能。l 。= x 2 i ) ，1 ，b ，y l k k 。由结论3 1 知一 x l i y l j e ( a ) 由于只是一个二部图，故至少存在一个点y u m ，使得x u y l e ( c ) ， 同理至少存在一点z 1 玛，使得z 1 j 口1 j e ( g ) 。于是得到d g ( x l j ，1 ) = 3 ，由g 3 的定义知；x j y l i e f g 3 ) ，这导致矛盾。 ( 2 ) 不妨设存在两个不同的连通分支玛，最，使得e ( 只，乃) = x x i m ，e ( 只，r ) = z l k 掣1 。) ，其中z l i 五y 1 。，x l k 凰，掣l j 巧。由结论3 1 知：x l l y l j e ( a ) 由于只是一个二部图，故至少存在一个点x l j 玛，使得x l j y l j e ( c ) 。如果 x l l y l ；e ( a ) ，于是就得刘如( z l j ，y l 。) = 3 ，由g 3 的定义知tx l j y l i e ( a 3 ) ，这导 致矛盾如果巩y l lge ( a ) ，由事实2 知：l v ( f ) f 4 ，故至少存在一点y 2 1 k ， 使得。，驰。e ( a ) ，否则与( 只) ；1 ( r o o d 2 ) 矛盾这样得到d c ( z l ，抛 ) = 3 ，由g 3 的定义知；z 1 ，讹；e ( c 3 ) ，这导致矛盾。 结论3 4对每一个e r ，l e ( 只，g 3 ) f 4 ，i = 1 ，2 ，t 。 反证，由结论3 3 可假设存在一个连通分支只r ，使得i 届限，g 3 ) i = 3 。 ( 1 ) 不妨设存在三个不同的连通分支乃，以，j l m ，使得e 假，巧) = z l i y l j ， e ( 只，r ) = z 2 i l k ， e ( 只，1 m ) = 茁瓢y 1 m ) ，其中茁z 2 ；，z 瓢k ( 可能茁1 ，= ：9 2 i = x 3 i ) ，可l ，匕，y l k k ， y 1 。y 鲁由结论3 1 知x u y l j e ( c ) 。由于只是一个二部