（应用数学专业论文）图的上可嵌入性与3正则图的最大亏格.pdf

摘要 本篇论文主要研究了拓扑图论中的一个十分活跃的方面图的上可嵌入性和最大亏 格，它是图的曲面可嵌入性理论的一个重要研究课题。图的曲面可嵌入性起源于著名的四色 问题。自从c a y l e y l 8 7 8 年正式公布了四色问题后，图的平面可嵌入性问题便开始引起了人 们的关注。1 8 9 0 年h e a w o o d 对一般的曲面提出了类似的地图着色问题后，图的曲面可嵌入 性问题便进一步提出来了，特别是h i l b e r t 和c o h n v o s s e n 将四色问题化为确定k 。的引线问 题( k 。的引线问题等价于求其亏格) 。虽然，地图着色问题于1 9 6 8 年得到解决，它的解法 却导致了一个新的数学分支拓扑图论的产生，图的曲面可嵌入性就成了这一数学分支的 一个主要研究内容。这里的图是指连通图，曲面是指一个连通紧致的2 维闭流形( 可定向或 不可定向均可) 。图的一个嵌入是指存在一个从图到曲面的拓扑映射使从曲面上去掉图的顶 点和边后的每个连通分支都拓扑同胚于一个开圆盘，这样的嵌入也称为2 - 胞腔嵌入。图的 ( 最小) 亏格r ( g ) 是指最小的整数g 使之在曲面s g 有2 - 胞腔嵌入，而图的最大亏格 y m ( g ) 是指最大的整数g 使之在曲面s 。有2 - 胞腔嵌入。图的亏格具有介值性质，即对于 最小亏格和最大亏格之间的任一整数g 存在图g 在s 。上的2 - 胞腔嵌入。达到最大亏格上界 的嵌入称为上可嵌入。由于已经证明了任一连通图在不可定向曲面上的最大亏格等于其圈 秩，因此这里关于曲面上可嵌入性的讨论均指是在可定向曲面上。 拓扑图论不仅丰富了拓扑学的内容，也使图论的面目一新，使人们对图和曲面有了更为 深刻的认识。考虑到图在曲面上的上可嵌入性及图的一些性质如边连通度、独立集和独立数、 3 - 正则等以及n x u o n 9 1 9 7 9 年、l n e b e s k y l 9 8 1 年分别给出的图的上可嵌入性的两个充要条 件，本文主要利用了黄元秋1 9 9 9 年给出的非上可嵌入图的结构特征，给出了一些新的上可 嵌入图类，使图论中的一些上可嵌入性问题得到了解决。本篇论文作了以下主要工作： i 、结合边连通度，探讨了独立集中具有最小特定度和的上可嵌入图类。 2 、刻画了边连通简单图中具有特定最小度的上可嵌入图类。 3 、讨论了边连通简单图的独立数与上可嵌入性的关系。 4 、探讨了v 6 的连通3 一正则图的最大亏格和上可嵌入性。 5 、得到了连通3 一正则简单图当，m ( g ) 2 詈+ 1 ( v = l 矿( g ) l 1 8 ) 时的结构特征。 关键词：图、上可嵌入、最大亏格、b e t t i 亏数。 j a b s t r a c t t h i sd i s s e r t a t i o ni sd e v o t e dt ot h eu p p e re m b e d d a b i l i t ya n dm a x i m u mg e n u so f g r 印h s w h i c hi sa na c t i v ea n di 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 ht h e o r y i n r e c e n ty e a r s ，g r a p he m b e d d i n gp r o b l e m sh a v ea t t r a c t e dm o r ea n dm o r er e s e a r c h e r s a n dm u c hw o r ko nt h eu p p e re m b e d d a b i l i t ya n dm a x i m u mg e n u sh a sb e e ni n s p i r e d s o m er e s u l t sw i l lb eg i v e ni nt h i st h e s i s ： 1 、c o m b i n e dw i t ht h ee d g e c o n n e c t i v i t y , w ei n v e s t i g a t et h eu p p e re m b e d d a b l e g r a p h sw i t hs p e c i f i cm i n i m u md e g r e e s k l n ao f v e r t i c e si ni t si n d e p e n d e n t s e t 2 、w eg i v ean e wc l a s so f u p p e re m b e d d a b l ee d g e - c o n n e c t e ds i m p l eg r a p h sw i t h s p e c i f i cm i n i m u md e g r e eo f v e r t i c e s 3 、w es h o wt h er e l a t i o n s h i pb e t w e e nt h ei n d e p e n d e n c e n u m b e ra n du p p e r e m b e d d a b i l i t yo f3 一e d g e c o n n e c t e ds i m p l eg r a p hw i t h 口( g ) s 5 4 、w ed i s c u s st h em a x i m u mg e n u sa n du p p e re m b e d d a b i l i t yo ft h ec o n n e c t e d 3 - r e g u l a rg r a p h sw i t hv 6 5 、w ep r e s e n tan e ws t r u c t u r a lc h a r a c t e r i z a t i o no f t h ec o n n e c t e d3 - r e g u l a rg r p h s w i t h y m ( g ) = 詈+ 1 ( v = i v ( g ) i _ 1 8 ) k e yw o r d s ：g r a p h 、u p p e re m b e d d a b l e 、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 学位论文独创性声明 本入掰至交瓣学位论文是我在簿赉器静捂导下滋行靛研究工俸及取褥懿辑究 成果。摄淡掰知，涂文中心经注明弓l 媚豹起套辨，本论文不包含其他个人已经 发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在 文中作了明确说明并表示谢意。 学位论文使用授权声明 本大完全了簿华东帮藏大学宥关保蘩、使爱学位论文豹蔑宠，学较裔较傈 馨学位论文并囱黧家主管郎门或其指定规擒送交论文豹魄子版和纸质舨。有权 将学位论文用于非赢利目的的少擞复制并允许论义进入学校图书馆被查阅。有 枚将学位论文的内容编入有关数据库进行检索。有权将学位论文酌标题和摘要 澎编窭敝。保密瓣学位论文在解爨螽逶矮零燕定。 学位谂文作者整襄：毛哥潞导帮签名；像嚆每 e t 期：塑! 皇。! !蠢期： 第一章概述 图论戆- - f 发展迅速而又应用极其广泛的数学分支，它是组合数学与离散数 学的一个主要成员。图谂已广泛地艨用予物理、化学、运筹学、计算掇科学、电 子学、话惠论、控铡论、网络理论、管理科学、社会科学等几乎所有学科领域。 拓扑图论，结合了图论和低维拓扑学，现已成为近年来一个十分活跃的研究方向。 图的曲藤可荻天性理谂作为拓扑图涂的一个重要薅究课题，更怒吸弓l 了越来越多 的研究者的注意。关予图豹上可嵌入性( 或者说使得所在益面的亏格为最大) 的 论文 1 ，4 ，7 ，3 3 ，3 5 ，3 9 ，4 3 ，4 4 ，4 6 ，4 7 ，5 0 ，5 2 尤其照近年来频频出现 在名翻上，专著 3 6 ，3 7 】等也不叛班现，为图的壤论磷究和应弼舞辟了广阔敬藏 景。 l 。图的最大亏揍与上霹嵌入懿由来 图的曲面可嵌入饿起源于著名的四色问题( f o u r - c o l o rp r o b l e m ) 即造通简 单平面图的色数不超过4 。1 8 5 2 年，g u t h r i e 向数学家d em o r g a n 提出了这个问 逶，当懿寒褥至解决。1 8 7 8 年，c a y l e y 把它正式箍鬟荚藿皇家数学会上，嚣色 问题由此成为众所周知的难题。1 8 9 0 年，p j h e a w o o d 对一般的曲面提出了类似 的地图着色猜想( m a pc o l o rc o n j e c t u r e ) 。一肖多年来，这一灌名的数学滩题 啜g l 了鑫溺爨数学家扶事霆惫獍戆懿涯筏，疆举载涯赘了薅建黧着色鬟5 耱颜色 就足够了，但不能证明用4 种颜色就足够了。1 9 7 6 年，美国i l l i n o i s 大学的数 学家k a p p e l 和w h a k e n 把四色问题归结为2 0 0 0 个不同的组含结构图形，刹用 三台毫逮i b m 3 6 0 诗算瓤黪这些銎形送雩亍分舞，髑了1 2 0 0 令稳瓣、近吾经次逻辑 判断，宣布了一个借助予计算机的诞明。但是，邀个证明引起了广泛争论，原因 是在他们的证明中使用了1 2 0 0 小时的机时，它怒不是真正的诞明? 对鞠魏翊题酶繇究囊遂了霾戆霹着琶毪静搽讨，酝褥了缀黧要鹣残暴，淹嚣 来的研究隳定了良好的基础，而且也导致了对图论其它一些领域的探讨，促进了 图论的理论和应用的发展。1 9 3 2 年，d h i l b e r t 和8 c o h n v o s s e n 将四色问题的 解决癌终凳霉| 缓| 、蠢戆( 冤 镪) 。1 9 6 8 每，g 。r i n g e l 挺鲞t 雩| 绫阉蘧( 其竞螯缝 的证明可参见 4 5 ) ，即给定两个整数n ( n 3 ) 和p ( p o ) ，我们能否在曲面n 。上 选择聆个点并在曲面上每两点间用一条简单曲线( 即引线) 连接使得这些曲线不 相交? 这个问题可归结为完全图k 。能够嵌入到的r i e m a n n 曲面的最小亏格 r ( k 。) 的计算问题，或更一般地，如何决定一般图g 的亏格r ( g ) 的计算问题。 由此，曲面的亏格问题引起了许多研究者的注意。 1 9 7 0 年，r r i n g e i s e n 在美国m i c h i g a n 州立大学的博士论文 4 1 中提到了 图的最大亏格一词。1 9 7 1 年，e a n o r d h a u s 、b m s t e w a r t 和a t w h i t e 首先在 文献 4 0 中引入了连通图g 的最大亏格，。( g ) 的概念，他们定义这个参数为一个 图可有2 一胞腔嵌入的曲面的最大亏格，他们同时也t i o 了它的上界i 壁粤f 。 r r i n g e i s e n 在广泛地研究了最大亏格 4 卜4 3 后于1 9 7 2 年在文献 4 2 中首次给 出了上可嵌入图这一名词。此后，图的最大亏格和上可嵌入性问题引起了广泛的 关注。由于在7 0 年代末g r i n g e l 和刘彦佩等人独立地解决了图在不可定向曲面 的最大亏格和上可嵌入性问题 4 5 ，3 4 ，3 6 ，3 7 ，因此，对图的最大亏格和上可 嵌入性的研究此后一般都指是在可定向曲面上。联想到1 9 6 6 年r a d u k e 在文献 5 中证明的后被人们称为图的亏格插值定理，即如果图g 在亏格为肌和珂的可 定向2 一流形上有2 一胞腔嵌入，则对任意整数k ( n 坍) ，图g 在亏格为后的可 定向2 一流形上也有2 一胞腔嵌入( i ft h e r ee x i s t2 - c e l le m b e d d i n g so ft h eg r a p h gi no r i e n t a b l e2 - m a n i f o l d so fg e n e r a 州a n d 玎t h e nf o ra n yi n t e g e r k ( n 后聊) ，t h e r ee x i s t sa 2 - c e l le m b e d d i n go fgi nt h eo r i e n t a b l e 2 - m a n i f o l do fg e n u sk ) 。因此，考虑图g 的所有可嵌入的可定向曲面，只需 确定它的亏格r ( g ) 和最大亏格( g ) 。至今，对图的最大亏格和上可嵌入性的 研究仍然是拓扑图论中的一个十分活跃的方向。 1 2 基本概念 一个图( g r a p h ) g 通常用g = ( v ，e ) 表示，其中v = v ( e ) 是非空的顶点 ( v e r t e x ) 集，e = e ( g ) 是不与v ( g ) 相交的边( e d g e ) 集。若矿和e 为有限集，则 这时的g 称为有限图( f i n i t eg r a p h ) ，否则g 称为无限图( i n f i n i t eg r a p h ) ，本 文中只讨论有限图。图g 的顶点数y = l 矿( g ) i 称为图g 的阶( o r d e r ) ，图g 的边 数s = | e ( g ) i 有时也称为图g 的度( s i z e ) 。如果口= w e ( g ) ，则说p 关联 ( i n c i d e n t ) 甜和v ，称“和v 为边e 的端点( e n d ) ，并且称这两个顶点是邻接的 ( a d j a c e n t ) ，与同一个顶点关联的两条边也称为是邻接的。端点重合为一点的边 称为环( 1 0 0 p ) ，端点相同的边称为平行边( p a r a l l e le d g e ) 或重边( m u l t i p l e e d g e ) ，不与任何边相关联的顶点称为孤立点( i s o l a t e dv e r t e x ) ，仅有一些孤立 点的图称为零图( n u l lg r a p h ) 或空图( e m p t yg r a p h ) ，只有一个顶点的图称为平 凡图( t r i v i a lg r a p h ) ，其它所有的图都称为非平凡图( n o n t r i v i a lg r a p h ) ，本 文中主要考虑非平凡图。无环并且无平行边的图称为简单图( s i m p l eg r a p h ) ，任 意不同两顶点之间都有边相连的简单无向图称为完全图( c o m p l e t eg r a p h ) 并记 作k ，完全图k 有= 妄n 印一1 ) 条边。由完全图可引出一个图的补图的概念， 二 设有一图g = ( v ，e ) ，若对图百= ( v ，e ) 有g = ( v ，e u e ) 是完全图且 e n e = ，则虿称为g 的补图( c o m p l e m e n tg r a p h ) 。容易看到，若g 是一个n 阶简单图，则有g u 舀= e 且陋( g ) l + i e ( 百) i = q = 寺以。一1 ) 。 在研究和描述图的性质以及图的局部结构中，子图的概念占有重要的地位。 图h 是图g 的子图( s u b g r a p h ) 记作h g ，如果v ( h ) 矿( g ) ，e ( h ) e ( o ) 且 h 中边的重数不能超过g 中对应边的重数。若h 互g 且h g ，则称日是g 的 真子图( p r o p e rs u b g r a p h ) 。若h g 且v ( h ) = v ( o ) ，则称日是g 的生成子图 ( s p a n n i n gs u b g r a p h ) 。设v c v 且v 一，以v 为顶点集以两端点均在y 中的 全体边为边集的g 的子图称为y 的导出子图( i n d u c e ds u b g r a p h ) ，记作o v 】。 导出子图o v v 】记为g v 或g v ，它是从g 中删除矿中的顶点以及与这些顶 点相关联的边所得到的子图。若矿= v ，则把y 一 v ) 简记为g v 。设e c e 且 e 西，以e 为边集以与中的边关联的全部顶点为顶点集的g 的子图记为 g 陋】，我们称g 陋】是g 的边导出子图( e d g ei n d u c e ds u b g r a p h ) 。由于图g 的 1 每条边都有两种选择，邵包含于或不苞禽予菜个子图中，如果每条边都包含就是 图g ，如果每条边都不包含就是空图，因此我们有：图g 的所有不网的予图的 个数为2 1 e ( a ) 1 个( 惫括胬g 和空图) 。 g j 和g 2 憝两个图，若g 。和g 2 没有公共 顶点，则拣它们是不相交的( d i s j o i n t ) ，糟g 1 帮g ，没有公共边，努称它铜是逡 不莛的( e d g e d i s j o i n t ) 。设g t 和g 2 是两个图，则g l 积g 2 的势图( u n i o no f g r a p h s ) 定义为g lu g 2 = ( 巧u k ，e iu e 2 ) ；类似地可定义g 。和g 2 的交图 ( i n t e r s e c t i o no fg r a p h s ) g in g 2 = ( kn k ，en e 2 ) a 图g 中与顶点v 关联的边数( 一条环要计算鼷次) 髂必v ( 在g 中) 鼢发或 次( d e g r e e ) ，记为如( d 或d ( v ) 。我们把奇数度的顶点称为奇点，偶数度的顶点 称势鹈点。谗占( g ) = m i n d ( v ) 1 v 芒矿( g ) 茅西a ( g ) = m a x d ( v ) v 矿( g ) ；，刚它们分 别称为图g 的最小度( m i n i m a ld e g r e e ) 昶蠼大度( m a x i m u md e g r e e ) 。妇渠一个 图的每个璎点都其有褶鬻静度，剩称这个强燕正赁| j 的( r e g u l a r ) ，每个顶点的度 均为k 的正则图称为k 一正则图( t r e g u l a rg r a p h ) 。图g 的k 一正则生成子圈称 为g 的k - 因予( k - f a c t o r ) ，势星螺累躅g 存在迭不重的辩一潮予h i ，丑2 ，抒。使 得g = b u h 2 u u 以，则弥圈g 是, - i k 一因子分鹪的( k - f a c t o r a b l e ) 。 关于顶点的度，我们有下面的握手定理( h a n d s h a k i n gt h e o r e m ) 2 ，3 定理1 1 ：d ( v ) = 2 i e ( g ) l ，即图中魇有顶点的废积等于边数的嚣蹙。 v y 推论1 1 2 ，3 ：在任何圈中，奇点的个数必为偶数。 路积违邋是图论中秀个燕要麴基本獠念。若爨g 的一个有限稚空序列 w = y o e l v l 口2 v 2 吒，它的项交替为顶点和边且q ( 1 i 蔓七) 的端点是u l 和v ；， 剡称矿是一条 ( g 1 ，则v 是g 的一个割点( c u tv e r t e x ) 。没有割点的非平凡连通 图称为块( b l o c k ) ，图g 中不含割点的极大连通子图称为图g 的块。 如果图g 的顶点集的一个真子集v 使得g 一矿不连通或是平凡图，则称v 是g 的一个点割( v e r t e xc u t ) 。设图g 是连通图，则称 r ( g ) = m i n i v | l 矿是g 的点割 为图g 的点连通度( v e r t e xc o n n e c t i v i t y ) 或连 通度( c o n n e c t i v i t y ) 。于是，当图g 是平凡的或不连通时，j r ( g ) = 0 。若芷( g ) ， 则称图g 是七一连通的( 七- c o n n e c t e d ) 。所有非平凡连通图都是卜连通的。 6 如果图g 的边集的一个真子集s 使得g s 不连通或是平凡图，则称s 是g 的一个边割( e d g ec u t ) 。设图g 是连通图，则称盯( g ) = m i n i s ls 是g 的边割 为 图g 的边连通度( e d g ec o n n e c t i v i t y ) 。于是，当图g 是平凡的或不连通时， 暂( g ) = 0 。若r ( g ) 七，则称图g 是七一边连通的( t e d g e c o n n e c t e d ) 。所有 非平凡连通图都是卜边连通的。 一个图g 的连通度、边连通度和最小度之间有如下的关系。 定理1 ，7 3 ：i c ( g ) 茁( g ) 兰a ( g ) 。 设g = ( v ，e ) 是简单无向图，s v ，s 庐，若s 中任意两个顶点在g 中均不 相邻，则称s 是图g 的一个独立集( i n d e p e n d e n ts e t ) 。图g 的一个独立集s 称 为g 的最大独立集( 眦x i 眦mi n d e p e n d e n ts e t ) ，如果g 不包含使炒i 1 s i 的独立 集s7 。图g 的最大独立集的顶点数称为g 的独立数( i n d e p e n d e n c en u m b e r ) ，记 为a ( g ) 。 给定两个图g 。和g ：，如果它们同构或者通过反复插入或去掉2 度顶点后同 构，则称g 1 和g 2 是同胚的( h o m e o m o r p h i c ) 。 曲面( s u r f a c e ) 通常记为s ，这里是指一个连通紧致2 维闭流形，这样的 流形可想象为一个添加了若干环柄的球面。曲面s 上环柄的数目称为曲面s 的亏 格( g e n u so ft h es u r f a c es ) 并记为g ( s ) 。一个图在曲面上的嵌a , ( e m b e d d i n g ) 是指将图的顶点和边放在曲面上使得边只在相互关联的顶点处相交。一个图g 在 曲面s 上的一个2 一胞腔嵌入( 2 - c e l le m b e d d i n g ) 或胞腔嵌入( c e l l u l a r e m b e d d i n g ) 是指g 能画在s 上使得边与边之间除顶点外不再相交，且在s 上去 掉g 的顶点与边后的每个连通分支都拓扑同胚于一个开圆盘，g 的每个连通分 支称为面( f a c e s ) 或区域( r e g i o n s ) 。注意一个非连通图在任何曲面上都没有2 胞腔嵌入。 连通图g 的亏格( g e n u s ) ，( g ) 是指最小的整数g ( s ) 使得g 在曲面s 上有 2 一胞腔嵌入，而连通图g 的最大亏格( m a x i m u mg e n u s ) y m ( g ) 是指最大的整数 g ( s ) 使得g 在s 上有2 一胞腔嵌入。前面提到的定义的更精确描述可参见s s t a h l 7 的概述文章 4 8 。 因为一个图g 在任意可定向曲面的2 - 胞腔嵌入中至少有一个面，由e u l e r 公 却( g 阳”i ( g 籽 篇茹霖硎晒桶帅 的最大亏格上界( g ) | 曼笋i ，这里( g ) = i e ( c i i y ( g ) 卜l 称为图g 的 b e t t i 数( b e t t in u m b e r ) ( 或称为圈秩( c y c l er a n k ) ) ，k j 表示不超过口的最 大整数。如果( g ) = l 笪笋j ，则称图g 是上可嵌入的( u p p e r e b e d d a b l e ) 。 由e u l e r 公式易知，图g 是上可嵌入的当且仅当它根据z ( g ) 是偶或奇而在最大 亏格曲面上有一或两个面的嵌入。 设r 是连通图g 的一棵生成树，图g 中生成树t 的亏数( d e f i c i e n c y ) 4 ( g ，t ) 定义为g e ( t ) 的有奇数条边的连通分支数。图g 的亏数 f ( g ) = m i n 善( g ，r ) ，其中m i n 取遍g 的所有生成树r ，注意善( g ) = f l ( g ) ( m o d 2 ) 。 1 3 图的最大亏格与上可嵌入性的已有结果 关于图的上可嵌入性，1 9 7 9 年n h x u o n g 在文献【5 0 中给出了一个充要条 件。 定理a ( x u o n g ) ：设g 是一个连通图，则 ( i ) 图g 是上可嵌入的当且仅当分别根据p ( g ) = 0 ( m o d 2 ) 或卢( g ) = 1 ( m o d 2 ) ，有掌( g ) = o 或善( g ) = 1 。 ( 2 ) ( g ) ：丛! 尝盟。 对于图g = ( v ，e ) ，取边子集a e ( g ) ，c ( 6 a ) 表示6 a 的所有连通分支 数，6 ( g 爿) 表示有奇b e t t i 数的g 4 的连通分支数。 1 9 8 1 年，l n e b e s k y 在文献【3 9 中又给出了上可嵌入性的另一个充要条件。 定理b ( n e b e s k y ) ：设g 是一个连通图，则 ( 1 ) g 是上可嵌入的当且仅当对任意爿e ( g ) 车f f c ( g a ) + b ( 6 a ) - 2 - i a l ( 2 ) f ( g ) = 艨，叠( g 一) + b ( g a ) 一i a i 一1 设e ，鼻( ，2 ) 为图g 的，个不同的连通子图，记号( e ，e ，鼻) 表 示g 中两个端点分别在两个不同的只和f ( f j ，1 f ，j ，) 中的边所组成的集 合。另外，对g 的任意子图f ，记号e ( g ，f ) 表示中一个端点属于而另一个端点 不属于的边所组成的集合。 1 9 9 9 年和2 0 0 0 年，黄元秋和刘彦佩在文献【1 3 ，1 5 ，2 4 平1 j 用定理a ( 1 ) 和定 理b ( 1 ) 提供了一个非上可嵌入图的结构特征。 定理c ( h u a n g ) ：设g 是一个连通图，如果g 不是上可嵌入的，即f ( g ) 2 ， 则存在g 的边子集一满足下列性质： ( 1 ) c ( g a ) 2 ，且对g 一的任意连通分支，有f l ( f ) = l ( m o d 2 ) 。 ( 2 ) 3 2 c ( g a ) - i a l 4 ( 3 ) 对g a 的任意连通分支f ，f 是g 的一个点导出子图。 ( 4 ) 对g 彳的任意z ( t 2 ) 个连通分支e ，疋，e ，有 l e 。( e ，最，e ) i 2 ，一3 ， 特别地，当，= 2 时，i e g ( f j ，e ) i 1 a ( 5 ) f ( g ) = 2 c ( g a ) - i a i - 1 。 1 9 9 4 年和1 9 9 5 年，刘彦佩在文献 3 6 ，3 7 】中也给出了上可嵌入图的一个充 要条件。 定理d ( 刘) ：对连通图g = ( v ，e ) ，下列说法是等价的： ( 1 ) g 在可定向曲面上是上可嵌入的。 ( 2 ) g 有一棵生成树r 使得g 可简化为t 或丁+ e ，这里e 是e 中余树的一条 边。 ( 3 ) g 有一棵生成树丁使得其余树至多有一个奇数条边的连通分支。 1 4 本文的主要结果 本节定理熬缎号采用它识在务鑫章节中出现鹣缡号，其中未交蟹豹餐号积摄 念请对应它们相麻的章节。 定瑾2 1 ：设强g 是一令2 边连逶蕊攀霾，虽淹是条拳：对t n g 戆程漾一个 3 w 独立集，若帆，x ，( j ，= 1 ，2 ，3 ) ，d ( x 。，x j ) 3 ( 1 蔓i 簪，s3 ) d ( x ，) v + l ( v = 矿( g ) ) ，则g 是上可嵌入的。 定理2 2 ：设图g 是一个3 边连通简单图，且满足下列条件：对图g 的任意 一个6 - 猿立纂f ，若v x f ，专z ( ，= 1 , 2 ，3 ，4 ，5 ，6 ) ，d ( x ，并，) 3 0 i 歹6 ) 等 d ( x ，) v + l ( v = y ( g 秘，羯g 楚虿嵌入戆。 定理2 + 3 ：设溷g 为一个2 一逡连i 爨筵攀图，爨渍足搬，岁y i ) ，则g 是上可嵌入的。 证明：假设g 不是上可嵌入的，由定理c 可知存在a e ( o ) 使得g a 的所 有连通分支e ，f 2 ，f , q = c ( g 一) ) 满足定理c 的性质( 1 ) ( 5 ) a 因为g 是3 - 边连 通的，所以对所有f = 1 ，2 ，有陋( 只，g ) 1 23 。又由事实2 我们知道，= c ( o 爿) 4 。 v a x 为满足l e ( f ，g ) i = 3 的f ( f _ 1 ，2 ，) 的分支数，则我们有 1 4 i 丢 3 x + 4 ( 1 一x ) 】= 2 ，一言 又由定理c 的性质( 2 ) ：3 s2 c ( g 彳) 一h 有3 2 1 - ( 2 1 一言) 即x 6 。不失一般性， 设e ，r ，e ，e ，瓦为满足旧( f ，g ) 1 = 3 ( 1 i 6 ) 的六个连通分支。 因为g 是一个简单图，且每一个连通分支均满足( e ) = l ( m o d 2 ) ( 1 i 6 ) ， 因此我们有l 矿( e ) 1 3 ( 1 i 6 ) ，而且存在x ，v ( f 3 ( 1 i 茎6 ) 使得 x 1 ，x ：，x ，x 。，x ，和x 。互不相辱b 且d ( x ，) i y ( 只) l ( 1 i s6 ) 。 对选定的两个连通分支e 和( 1 - i ，6 且下标为模6 同余) ，因为由定理 c 的性质( 4 ) 可知陋g ( e ，f j ) l 1 ( 1 - i 6 ) 并且陋( e ，g ) i = 3 ( 1 f 6 ) ，所以对 于上述的i 存在x 。矿( f ) 和x 。矿( 只+ 1 ) 使得边x i x 。萑e ( g ) ，并且有 d ( x 。) l v ( f 3 1 和d ( x 。) 矿( e + ，) i 。根据定理的条件，我们知道有d ( x 。，z ，) 3 ( 1 f 6 ) ，并且对于这个f 有m i n p ( 一) ，d ( x j + 1 ) ) ! 芸。 0 于是对于1 f 6 ，我们得到2 壹p ( e ) l 6 ； 也就是有壹旷( f ) i v + 1 。 ，= 。 ；一-ii1 6 然而，i 矿( e ) j p ( g ) l - v 。这样就有v + 1 v 。矛盾 扭1 因此，图g 是上可嵌入的。证毕。 1 9 第三章边连通简单图的独立数与上可嵌入性 本章中将讨论边连通简单图的独立数与上可嵌入性的关系，我们得到了下列 缭莱：( 1 ) 设g 怒一个霖- 逮连通简单圈( 露= l ，2 ) ，着g ( g ) k ，潮g 是一t 可嵌 入静。( 2 ) 设g 怒一个3 - 逸连通麓单图，若瑾( g ) s5 ，则g 是上可嵌入的。 3 1引言 本章我餐瑟考虑豹圈缘务连_ i