（应用数学专业论文）特殊图类xa与基本极大m1k2free图.pdf

河南大学硕士学位论文 摘要 摘要：八十年代以来，图的匹配理论在组合数学，运筹学与控制论 中的作用日益突出，近年来更成为图论及组合最优化中最为活跃的研究课题 之一。而图的导出匹配是近年来兴起的新研究方向。g 的匹配m 是导 出匹配，如果f 5 1e ( y ( m ) ) = m 。图g 的导出匹配数i m ( g ) 表示图g 的一个最大导出匹配的边数。是否存在一个非完伞连通简单图g ，对于图 g 的任意两个非相邻顶点z 和可，都有i m ( g + x y ) = i m ( g ) + 1 7 这 是一个有趣而且基本的问题。谢炎涛已经解决了这个问题，找到了顶点数 位1 2 ，1 3 ，1 4 个点的导出匹配数为1 的满足上述条件的图。本文研究了 一个特殊图类托，定义此= h ：h = ( ve ) 是一个简单连通图，任给 v vi m ( h ) = i m ( h 一( 秽) ) ，任给a b e ，n ( a ) 一n ( b ) d 将研究 托中图的结构性质，对特殊图类的研究内容与基本极大( m + 1 ) 鲍一f r e e 图的结构研究有直接联系。另外，本文还研究基本极大2 k 2 一丘e e 图的一些 特征，并构造了一些顶点数为1 4 ，1 5 ，1 6 基本极大2 k 2 - f r e e 图。 关键词：导出匹配；导出匹配数；特殊图类x a ；极大2 k 2 一f r e e 图；基 本极大( m + 1 ) k 2 - f r e e 图。 河南大学硕士学位论文 a b s t r a c t s i n c e1 9 8 0 s ，g r a p em a t c h i n gt h e r yh a sp l a y d ea ni n c r e a s i n gp r o m i n e n t r o l e i nt h ec o m b i n a t i o no f m a t h e m a t i c s ，o p e r a t i o n sa n dc o n t o r yt h e o r y ， e s p e c i a l l yi nt h er e c e n ty e a r s ，i th a sb e c o m eo n eo ft h em o s ta c t i v ec o r ei s s u e s d e a l i n gw i t ht h eo p t i m i z a t i o no fg r a p hm a t c h i n gt h e o r ya n dc o m b i n a t i o n m e a n w h i l ee x p o r tm a t c h i n gh a sb e e nan e wr e s e a r c hd i r e c t i o n sd e v e l o p e d i nt h ep a s ty e a r s am a t c h i n gm o fgi s i n d u c e di fe ( y ( m ) ) = m t h e i n d u c e d m a t c h i n gn u m b e ro fg ，d e n o t e db yi m ( g ) ，i st h en u m b e ro f e d g e so f am a x i m u mi n d u c e dm a t c h i n go fg i st h e r eac o n n e c t e db u t n o tc o m p l e t es i m p l eg r a p hg ，s u c ht h a tf o re a c h p a i r o fn o n a d j a c e n t v e r t i c e sxa n dy ，i m ( g + x y ) = i m ( g ) - 4 - 17 t h i sp r o b l e mi sf u n d a m e n t a l a n dv e r yi n t e r e s t i n g x i ey a n - t a os e n i o rs c h o o l m a t eh a sa l r e a d ys o v e l dt h e p r o b l e m ，f i n d i n g1 2 ，1 3 ，1 4v e t i c e sp o i n t st om a t c ht h ee x p o r to fan u m b e r o fp l a n st om e e tt h ec o n d i t i o n s a b o v e ，i nt h i sp a p e r ，as p e c i a ld i a g r a mt y p e x aa n dt h ed e f i n i t i o no fxah a v eb e e ns t u d i e da n dt h eg r a p en a t u r ew i l lb e s t u d i d e ，w h i c hh a sa d i r e c tl i n kw i t ht h es t u d yo ft h es p e c i a lt y p eo fx am a p a n dt h eb a s i cs t r u c t u r eo fag r e a t ( m + 1 ) 鲍一f r e er e s e a r c h ，i na d d i t i o n ， t h i sa r t i c l ew i l la l s oc o n t i n u et os t u d yt h eb a s i cg r e a tp l a n2 2 f r e ea n d c o n s t r u c ts o m e2 k 2 一f r e eg r a p eo fo r d e r1 4 ，1 5 ，1 6 k e y w o r d s ：i n d u c e dm a t c h i n g ；i n d u c e dm a t c h i n gn u m b e r ；b a s i c m a x i m a l2 k 2 一f r e eg r a p h ；b a s i cm a x i m a l ( m + 1 ) 鲍一f r e eg r a p h i i 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学住或证书而 使用过的材料。与我一同工作的同事对奉研究所做的任何贡献均已在论文中作 了明确的说明并袁示了谢意。穹：= ；，。一， ， 。；。| j 、tj i ! j j 。j 。 学位串请人，：学住论走作者，) 签名：翅坠醢丛： ；。 、，、 | ，_ 。 - 、 。；o ”。二 月fd 日 、1 ：p o0z j 。| j。 j 一 ? ? f f ， i 。jj ? 、麓瓤一。善j；：。j 一，一 ；j 蘑誊曩：鬈：j，! 譬i ：- ：- 关于学位论文著作权使用授权书，； ：j 7 7 ： ：。、。：二：、j ；：。鼻、? i i ；! ，j j ! ：i 二：j ，j 、| i 本人经河南大学审核批准授予硕士学位。作为学住论文的作者，本人完全 了解并同意河南大学有关保留、使用学位论文，钓要求即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电子史本) 蹦供公焱检索、奎阅。本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目v 衲，可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解窑后适用本授权书) 学位获得者( 学位论文作者) 釜名：羹盔照徵 2 0 q 年 月f o 日 学位论文指导教师签名：宝塞壶 2 0d 呷年卜月f o 目 第一章引言 早在上世纪初，图的理论匹配就以不同的表现方式受到学者的普遍关注， h a l l 1 1 定理和t u t t e 2 】定理为图的匹配理论的研究奠定了坚实的基础。近 百年来，图的匹配理论的研究迅速发展，( l o v a s z 和尸? 钆m m e r ) 1 3 】的专著匹 配理论极大地促进了图的匹配理论的研究。八十年代以来，图的匹配理论 研究在组合数学，运筹学与控制论中的作用日益突出，近年来更成为图论及 组合最优化中最为活跃的核心课题之一。而图的导出匹配是近年来兴起的 新的研究方向。 图的导出匹配，导出匹配数和极大导出匹配可扩图是重要的研究课题 之一。图的导出匹配的扩张是原晋江【4 】新近提出的最新概念，旨在研究图的 导出匹配与完美匹配的结构性质，在研究技巧上与一般匹配理论的研究有很 大差别。我们说g 是一个基本极大( m + 1 ) k 2 一f r e e 图，如果g 是一个基本 极大( m + 1 ) 一f r e e 图，而且图g 的任何一个正则导出子图都不是一个基 本极大( n + 1 ) k 2 一f r e e 图，其中礼为任意自然数。宋晓新【5 】研究了基本极大 ( m + 1 ) k s f r e e 图的部分性质，找出了五的一些禁用子图，并在郑州大学 组织的图论研究会上作了报告，目前己知的极大导出匹配可扩图只有n 和鲍n 。我们想知道是否存在其它极大导出匹配可扩图。在极大导出匹配 可扩图的刻画方面，宋晓新已经有了满意的结果，谢炎涛也在从事这方面的 研究工作。 宋晓新研究了是否存在一个简单，连通，非完全图g ，对于图g 中的 任意两个非相邻的顶点z 和可，g + z 的导出匹配数等于图g 的导出匹 配数2 u 1 7 答案是肯定的! 谢炎涛已经找到了顶点数为1 2 ，1 3 ，$ 1 j 1 4 的简单，非 完全，基本极大2 k 2 - f r e e 图。( 宋晓新已经证明，一个简单，非完全，基本 极大( m + 1 ) k s f r e e 图的顶点数一定不小于1 2 ) 我们简称这样的图为基本极 大( m + 1 ) 娲一f r e e 图。宋晓新在郑州大学原晋江组织的有博士与博士后参 加的学术讨论班上，宋晓新为此作了专题报告。在武汉图论会议上，宋晓新 又与田丰，赖鸿建，陈冠涛等多位知名学者讨论过这个问题，得到了广泛的 关注，三正则基本极大( m + 1 ) k s f r e e 图的存在性问题仍然是o p e n 的。本 文研究了特殊图类x a ，定义托= fh ：h = ( ve ) 是一个简单连通图。 任给口vi m ( h ) = i m ( h 一( u ) ) 。任给n 6 e ，n ( a ) 一n ( b ) 1 河南大学硕士学位论文 d ) 。将研究比中图的结构性质，对特殊图类x a 的研究内容与基本极大 ( m + 1 ) 一f r e e 图的结构的研究有着直接的联系。另外，本文还将继续研究 了基本极大2 k 2 一f r e e 图的一些特征，并构造了一些项点数为1 4 ，1 5 ，1 6 基本 极大2 k 2 一f r e e 图。 2 第二章记号 在本文中，所考虑的图均为有限的非平凡简单图。 给定一个图g ，v = v ( c ) 和e = e ( g ) 表示它的点集和边集。 对于x y ( g ) ，q y ( g ) ，x 在q 中的邻集。 n q ( x ) = q x ：存在一个点z x 满足x y e ( g ) ) 。记 n v ( x ) = ( x ) 。 对任意的x y ( g ) ，q ( x ) ) 简单记作q ( z ) 。 如果q = v ，简单记作n ( x ) 。 x 在q 中的闭邻集记作q ( x ) = xt j q ( x ) 。 如果q ：v ，简单记作丙( x ) 。 对任意的口vv 在q 中的度记作d q ( u ) ，q v 。 对图g 来说，在图g 中的最小度记作6 ( g ) ，最大度记作a ( g ) 。 图g 中的以q 为顶点集的导出子图记作g q 1 。 对于x y ( g ) ，x 中的边集记作e ( x ) = u v e ：u ，v x 。 对于x ，y y ( g ) ，从x 发向y 中的边集记作e ( x ，】厂) ， 从x 发向y 中的边数记作一e ( x ，y ) 一。 对于m e ，记 v ( m ) = f u v ：存在一点x v 满足v x m ) 。 对于任一个简单图g ，g 的导出匹配数记作 i m ( g ) = m a x i m i ：m 是g 的一个导出匹配】， g 的匹配数记作 m ( g ) = m a x l m i ：m 是g 的一个匹配， 记m i m ( c ) = m ：m 是g 的一个导出匹配满足l m i = j m ( g ) ) 。 x a = h ：h = ( ve ) 是一个简单连通图任给v vi m ( h ) = i m ( h 一( 秒) ) 。任给a b e ，( n ) 一( 6 ) d ) 。 给定一个简单连通图日，我们称q 是日的一个导出仇圈。如果q 是 日的一个导出子图。而且q 同构与。记玩( 日) = _ e e ：存在日 的一个导出m 圈包含e ，m 4 。 我们称g 是一个基本极大( m + 1 ) 鲍t e e 图，如果g 是一个连 通非完全简单图，使得任意给定一对非相邻的顶点z 和y ，i m ( g + x y ) = 3 河南大学硕士学位论文 i m ( g ) + 1 = m + 1 。日是图g 的一个真导出子图，如果日是g 的一个导 出子图。而且h g 。我们说g 是一个基本极大( m + 1 ) 鲍- - f r e e 图，如 果g 是一个极大( m + 1 ) k 2 一f r e e 图，而- 月图g 的任何一个真导出子图都 不是一个极大+ 1 ) 恐一f r e e 图，其中死为任意自然数。 4 第三章相关的已知结果 下面是有关图的导出匹配的一些己知结果。 定理3 1 ： 8 设g = ( ve ) 是一个顶点数为凡，导出匹配数为m 的基本极 大( m + 1 ) ( 2 一f r e e 图。那么我们有如下结论： ( a ) 设z ，y ，z vx y e ，y z 隹e 。那么n ( x ) 一丙( 可，z ) 。 ( b ) 设让，口vu u e 。那么i m ( g 一- z ( u ，秒) ) = i m ( g ) 。 ( c ) 设a = a ( a ) 。那么n 一2 i m ( g ) 一4 。 ( d ) k ( g ) 2 ，其中k ( g ) 表示g 的连通度；如果t = u 1 ，? 2 2 ) 是g 的 点害0 集，勇厣么让1 让2 e 。 ( e ) 6 ( g ) 3 并且n 2 i m ( g ) + 7 。 定理3 2 ：【8 设g = ( ve ) 是一个顶点数为死，导出匹配数为m 的基 本极大( m + 1 ) k 2 一f r e e 图。t 是g 的一个点割集，且是g 一丁的一个分 支，那么我们有以下结论： ( a ) 设x 和y 是图g 中不相邻的两个顶点，满足丙( z ，可) ) 2t ， 那么，m ( 且) = ，m ( 凰一( z ，) ) ) 。 ( b ) 设x 和y 是图g 中不相邻的两个顶点，满足e ( g 1 一丙( z ，) ) ) e ( t ) ，其中g 1 = g v ( h 1 ) ut 】。令t 1 = t 一丙( z ，y ) ) 。那么j m ( 凰一 2 v ( t , 1 = 0 。 ( c ) 设t = u l ，乱2 ) 和n l = l v ( h 1 ) i ，那么n 1 1 0 ，3 ( h i ) 礼1 4 ，6 ( h 1 ) 2 。 定理3 3 ： 9 设i vj = n ，设g = ( ve ) 是一个顶点数为死，导出匹 配数为m 的基本极大( 仇+ 1 ) 鲍一f r e e 图。令= z x ( g ) = d ( v 1 ) ，研是 g 一( 移1 ) 的一个分支，满足铭1 = i y ( h i ) i 2 ，那么我们有以下结论： ( a ) 对每一个v y ( h 1 ) ，我们有m ( h i ) = ，m ( 皿一( 秒) ) 。 ( b ) 凡1 5 ，6 ( h 1 ) 2 ；如果n 1 = 5 ，研一个5 一圈；如果礼1 = 6 ，那 么h 1 = 7 1 或者乃。如图1 和图2 所示。 ( c ) 设g = ( ve ) ，那么佗= j vj 1 2 。 定理3 4 ：【9 设g = ( ve ) 是一个顶点数为n ，导出匹配数为m 的 基本极大( m + 1 ) ( 2 - - f r e e 图。那么对每一对不相邻的顶点z 1 和z 2 ，都有 g ( z 1 ) n a ( z 2 ) 。 5 河南大学硕士学位论文 定理3 5 ： 9 】对每一个i = 1 ，2 设h i = ( k ，e ) 是一个5 一圈，其中k = 吼，b i ，q ，比，q ，邑= n i b i ，兢臼，q 也，d i e t ，e i a i ，定义图g 1 ，顶点集 为y ( g 1 ) = u u 1 ，h 2 ，边集为e ( g 1 ) = u ；邑，其中e 3 = h l h 2 u h l z l ，忽2 2 2 ：x l m 且x 2 k ，蜀= a l a 2 ，a l c 2 ，a l d 2 ) u b i b 2 ，b l d 2 ，b l e 2 u 0 1 c 2 ，c l e 2 ，c a a 2 u d l d 2 ，d , a 2 ，d a b 2 u e l e 2 ，e l b 2 ，e l c 2 。则g 1 是一个基本 极大2 一f r e e 图。如图所示这里a i ( n ，c k ，d m ) 表示a j ，c k ，如n ( a i ) 。 b i d ) 定理3 6 ：【9 设h 1 = ( ，日) 是一个5 一圈，其中= _ ( 乱1 ，乱2 ，“3 ，u 4 ， u 5 ) ，e 1 = u l u 2 ，u 2 u 3 ，u 3 u 4 ，7 2 4 u 5 ，u 5 u 1 ) ，1 - 1 2 = ( k ，易) ，其中k = u 1 ，v 2 ，v 3 ，v 4 ，口5 ) ，易= v l v 4 ，v l v 5 ，v 1 1 6 ，v 2 v 4 ，v 2 v 5 ，v 2 u 3 ，v 3 v 6 。我 们定义图g 2 ，顶点集为v ( g 2 ) = uku h i ，九2 ) ，e ( g 2 ) = u 叁1 e ， 边集为e 3 = l h 2 ) u 1 2 1 ，h 2 x 2 ：x l k 且x 2 ) ，和e 4 = 也l u l ，i v 2 ，u l v 6 l j u 2 v l ， u 2 v 3 ， l 2 v 4 ，u 2 v 5 l j u 3 v 2 ，u 3 v 4 ，u 3 v 5 ，u 3 y 6 u 乱4 u 1 ，u 4 v 2 ，u 4 v 3 】u u 5 y 3 ，乱5 v 4 ，u 5 5 ，u 5 v 6 。那么g 2 是一个基本极大 2 尬一行e e 图。如图所示。 6 河南大学硕士学位论文 定理3 7 ：【9 设h 1 = ( ，e 1 ) ，其中= u l ，u 2 ，u 3 ，u 4 ，u 5 ，乱6 ) ， e 1 = 7 , l u 2 ，u l u 5 ，u l u 4 uu 2 u 5 ，u 2 钆3 ) uu 3 u 6 ，u 3 u 4 u u 4 u 6 uu 5 u 6 。 凰= ( ，e 2 ) ，定义k = v l ，v 2 ，v 3 ，v 4 ，v 5 ) ，e 2 = v l v 4 ，v l v 5 ，v l 钌6 ) u v 2 v 3 ，v 2 v 4 ，v 2 v s uv 3 v 5 ，v 3 v 6 ，v 4 v 6 ) 。设g 3 是这样一个图，顶点集 为v ( g 3 ) = u u 1 ，h 2 ) ，边集e ( g 3 ) = u 基1 晟，其中e 3 = 1 九2 ) u h l z l ，h 2 x 2 ：x l 且x 2 ) ，并且e 4 = u 1 v 2 ，u 1 v 4 ，u l v 5 ，? a l v 6 ) u u 2 u 1 ，u 2 v 2 ，u 2 v 3 ，u 2 v 6 ) u u 3 v 3 ，u 3 v 4 ，u 3 v 5 ，u 3 v 6 u u 4 v l ，u 4 v 2 ，u 4 v 3 ，u 4 v 4 ) u u 5 v l ，u 5 v 3 ，u 5 v 4 ，u 5 u 5 ) uu 6 u 1 ，u 6 v 2 ，u 6 v 5 ，u 6 v 6 ) 那么g 3 是一个基本极 大2 k 2 一行e e 图。如图所示。 这里，u ( v j 仇u m ) 表示，讥，v m ，v n n ( u i ) 。 7 河南大学硕士学位论文 8 ：、) ；) 第四章主要结果与证明 4 1特殊图类 定义托= h ：h = ( ve ) 是一个简单连通图。任给v vi m ( h ) = i m ( h 一丙( u ) ) 。任给a b e ，n ( a ) 一一n ( b ) 囝) 。在本节中，我们将要 研究扎中图的结构性质，本节的研究内容与基本极大( m + 1 ) 一f r e e 图 的结构的研究有着直接的联系。 命题4 1 ：设h = ( ve ) x ，n = i v l 2 ，则我们有如下结论： ( a ) n 5 ，6 ( 日) 2 。 ( b ) 如果礼= 5 ，则日是一个5 一圈。 ( c ) 如果n = 6 ，则日同构于乃，正。其中t a = ( y ( 7 1 ) ，e ( 正) ) = ( u i ：i 厶) ， u l u 2 ，q 比1 u 3 ，u 2 u 4 ，u 2 u 5 ，铂魄，u 3 u 6 ，u 5 d ) 。t 2 = ( y ( 乃) ，e ( t 2 ) ) = ( u i ：i j i b ) ， 1 u 2 ，乱2 u 3 ，“3 u 1 ，让4 乱5 ，u 5 u 6 ，u 4 u 6 ，u l u 4 ， u 2 u 5 ，u 3 u 6 ) 。见图1 和图2 。 佥u 二公 图1 ：t 1 图2 ：t 2 ( d ) 如果a ( h ) = 2 ，则日是一个圈，而且n 三2 ( m o d 3 ) 。 证明：( a ) 假设a b e ( 日) ，而且a 是日中一悬挂点，则有n ( a ) 一 n ( b ) ，矛盾因此，我们有5 ( h ) 2 。由托定义可知，i m ( h ) = i m ( h 一( o ) ) 1 ，则有礼5 。( a ) 证毕。 ( b ) 假设6 ( h ) 3 ，设n 为h 中最大度点，则有i m ( h 一丙( n ) ) = 0 矛 盾。因此，日中每个点都是2 度点，日是一个5 一圈。( b ) 证毕。 ( c ) 如果忍= 6 ，根据i m ( h ) = 1 m ( h 一( 秽) ) ，我们有( 日) 3 ，且 日不是一个6 一圈。当( 日) = 3 时，假设v ( h ) n - ( a ) = n ，b ，c ，d ) ，v ( 日) 一 一n ( a ) = _ e ，厂) ，注意到m ( 日) = ，m ( 日一丙( o ) ) = 1 ，我们有e f e ( h ) 且b ，c ，d n ( e ) u ( 厂) ，不妨设6 e ，d e ，盯e ( 日) ，见图3 。假设h 噩，死，那么d f e ( 日) ，( 否则j m ( 日丙( d ) ) = 1 ，b c e ( 日) ，日= 疋) 。 9 河南大学硕士学位论文 同理b c ，b y ，c d 岳e ( 日) ，那么n ( b ) 一- n ( d ) = ，显然b d 聋e ( 日) ，( 否则， 我们有h 隹x a 矛盾) ，因此我们得到h = 乃，与假设矛盾。( c ) 证毕。 cf 图3 ( d ) 已知日的每一个点都是2 度点，而且日是一个简单连通图，显然日 是一个圈设v 是日中任意一点，假设( d ) 结论不成立，下面我们研究两种 情形： 情形1 ：当礼三0 ( m o d 3 ) 时，i m ( h ) = 罟，i m ( h 一( 口) ) = 号一1 ， 与i m ( h ) = i m ( h 一( u ) ) 矛盾。 情形2 ：当n 三1 ( m o d 3 ) 时，i m ( h ) = 孚，i m ( h - n ( v ) ) = 孚一1 ， 与i m ( h ) = i m ( h 一( u ) ) 矛盾。命题4 1 得证。 命题4 2 ：设h = ( ve ) x a ，n = i v i = 7 ，a ( h ) = 3 ，则t 同构于 死。其中t 3 = ( y ( t 3 ) ，e ( 死) ) = ( u i ：i 乃) ， u l u 2 ，u l u 4 ，u l u 5 ，u 2 u 3 ， u 2 u 6 ，u 3 u 4 ，钍3 让5 ，让4 u 6 ，u 5 u 7 ，u 6 u t ) 。如图4 所示： u 图4 ：t 3 证明：由于日中有奇数个顶点，不可能是3 正则图，则有6 ( 日) = 2 。 设v = o ，b ，c ，d ，e ，厂，夕) 和n ( a ) = 6 ，c ，d ) ，注意到i m ( h ) = i m ( h 一丙( o ) ) = 1 ，不妨设e s e 。如果b 譬n ( e ) u ( ，) ，则 a b ，e 厂) 是日上的一个导出匹配，矛盾。因此b g ( e ) u ( 厂) ，同理可证 c ，den ( e ) ug ( f ) 。考虑到b ，c ，d 的对称性和e ，厂的对称性，不妨设 b y ，c e ，d e e ，这样一来我们就得到了日的一个支撑子图h o = ( ve o ) ， 1 0 会 河南大学硕士学位论文 其中e o = a b ，a c ，a d ，e 厂，b f ，d e 。见图5 。考虑到凰中b ，的对 称性和c ，d 的对称性，我们讨论以下几种情形： f b g c 图5 e 情形1 ：b ，( 夕) ，此时我们有d ( 9 ) 。否则 g f ，a d ) 是日 的一个导出匹配，矛盾。同理可知c ( 9 ) 与a ( h ) = 3 矛盾。 情形2 ：n ( g ) = d ，c ，田，此时e ( h ) = e ou 咖，g c ，g d 。h 同构 于磊。 情形3 ：n ( g ) = c ，d ) ，此时 ，= 厂，9 ) ， m ，k 】= z 可e ：z ，y v 2 ) = f b ，y c ，g d ，夕e ) 。 贝0 日同构 于乃，毛，磊，乃。其中t 4 = ( y ( t 4 ) ，e ( 丑) ) = ( u i ：i 1 7 ， u l u 2 ，u 1 7 2 3 ， u l u 4 ，u l u 5 ，u 2 u 6 ，u 3 u 6 ，u 4 u 7 ，u 5 t 正7 ，u 6 u 7 ) t 5 = ( y ( t 5 ) ，e ( 死) ) = ( u i ：i 厶) ， u l u 2 ，乱1 乱3 ，u l u 4 ，u l u 7 ，札2 u 3 ，u 2 u 5 ，u 2 u 7 ，u 3 u 4 ，u 3 7 2 5 ， u 4 u 6 ，u 5 u 6 ，u 6 u 7 ) ) 。t 6 = ( y ( 死) ，e ( t 6 ) ) = ( u i ：i 厶， u l u 2 ，乱1 乱3 ，u l u 4 ， u l u 7 ，u 2 u 3 ，u 2 u 5 ，u 2 u 7 ，u 3 u 4 ，u 3 u 5 ，u 4 u 5 ，u 4 u 6 ，u 5 u 6 ，u 6 u 7 ) 。t 7 = ( y ( 乃) ，e ( 乃) ) = ( u t ：i 乃) ， u l u 2 ，u l u 3 ，u l u 4 ，u l u 5 ，2 也6 ，u 3 u 4 ，u 3 钆6 ， u 4 缸7 ，u 5 铭7 ，铭6 铭7 ) ) 。见图7 1 0 u u u 二 图7 ：t 4 u 图9 ：t 5 1 2 u u ： u 图8 ：t 5 u ! u ； 图l0 ：t 7 河南大学硕士学位论文 证明：由i m ( h 一丙( d ) ) = i m ( h ) = 1 ，可知f g e a 记e o = a b ，a c ，a d ，a e ，i g ，f b ，f c ，g d ，9 e ) ，记t o = ( k 凰) 则死为日的一个 支撑子图。显然我们有e = e oue ( p ，c ，d ，e ) ) 。我们下面分三种情形讨 论。 情形1e ( d ，c ，d ，e ) ) = 国，则有e a ( h ) = e ，日= t o = 五x a 。 见图1 1 。其中，蜀同构与t 4 。- 我t 1 简单记为t o = t 4 。在下文中我们采取 类似的表达方式。 b a e 图l1 f g 情形2b c e 在这种情况下，我们必有d n ( b ) u ( c ) ，否则， b c ，d g 是日的一个导出匹配，矛盾。同理可知，e n ( b ) u ( c ) 。考虑到b ，c 的 对称性和d ，e 的对称性，以及b 至多有4 个邻点，不妨设b d ，c e e 。 情形2 1e ( 6 ，c ，d ，e ) ) = b e ，b d ，c e ，时，玩( 日) = e ，h = t 5 托。 见图1 2 。 情形2 2e ( d ，c ，d ，e ) ) = b c ，b d ，c e ，d e ) 时，点( 日) = e ，h = t 6 x a 。见图1 3 。 b 图1 2 情形3b c ，d e 隹e ，而且e ( 6 ，c ，d ，e ) ) i m ( h ) = i m ( h 一丙( c ) ) = 1 ，n v ；c e e 。 同理可知，b d 譬e 。此时共有两种情形。 1 3 图】3 0 ，不妨设c d e 。注意到 否则，我们有g b e ，矛盾。 河南大学硕士学位论文 情形3 1e ( 6 ，c ，d ，e ) ) = c d ) 时，研( 日) = e ，h = 乃x a 。见 图1 4 。 a b e 图l4 f g 情形3 2e ( 6 ，c ，d ，e ) ) = c d ，6 e ) 时， 础，6 e ) 是日的一个导出匹配，矛 盾。命题4 。4 证毕。 命题4 5 ：设h = ( ke ) x a ，v = o ，6 ，c ，d ，e ，9 ) ，( 露) = 4 ，n ( a ) = 6 ，c ，d ，e ) 。设= o ，b ，c ，d ，e ) ，k = 厂，9 ) ， ，k = x y e ：x ，y ) = y b ，c ，g d ，9 e ) 。则日同构于珏。其中b = ( y ( 死) ，e ( 乃) ) = ( u i ：i b ) ， t l u 2 ，u l u 3 ，u l u 4 ，札1 乱5 ，u 2 7 2 6 ，u 3 钆6 ，u 4 u 6 ， 钍5 u 7 ，u 6 u 7 ) ) 。见图1 5 。 u u5 图15 ：t 8 证明：由i m ( h 一丙( o ) ) = i m ( h ) = 1 ，, - 1 矢ny g e 。记e o = a b ，a c ，a d ，a e ，f b ， 豇，d ，如，夕e ) ，记t o = ( ke o ) 。则蜀为目的一个支撑子图。显然我们 有e = 岛ue ( 6 ，c ，d ，e ) 。我们下面分三种情形进行研究。 情形1e ( 6 ，c ，d ，e ) ) = 0 ，则有玩( 日) = e ，h = t o = t s 比。 河南大学硕士学位论文 a b e 图16 g 情形2b c e 。在这种情况下，我们必有( 6 ) 一- zc ) d ，和( c ) 一- r ( b ) 0 。考虑到b ，c 的对称性，以及b 和c 一定不是g 的邻点，不妨设扰，b e e 。 但此时，i m ( h ) = i m ( h 一- n ( b ) ) = 0 ，矛盾。 情形3h t s 。在这种情况下，考虑到扫，c ，d 的对称性，我们必 有e ( 6 ，c ，d ) ) = 0 和e ( 6 ，c ，d ，e ) ) d 。不妨设d e e 此时， i m ( h ) = i m ( h 一一n ( d ) ) = 0 ，矛盾。命题4 5 证毕。 命题4 6 ：设h = ( ve ) x a ，v = 【口，b ，c ，d ，e ，夕 ，a ( h ) = 4 ，( o ) = b ，c ，d ，e 。设= 口，b ，c ，d ，e ) ，= ，夕) ， ，】= z 可e ：z ，y = y b ，y c ，g c ，9 d ，9 e 。则日同构 于死，马，乃o 。其中t 9 = ( y ( t 9 ) ，e ( t g ) ) = ( ：i 厶) ， u l u 2 ， u l u 7 ，i , l u 4 ， u l u 5 ，u 2 u 6 ，u 2 u 3 ，u 3 u 4 ，u 3 u 6 ，? - $ 3 u 7 ，u 4 u 5 ，u 5 札6 ) ) 。t l o = ( y ( 正o ) ，e ( t l o ) ) = ( 札i ：i 厶) ， u l u 2 ，u l u 3 ，? - $ 1 u 6 ，乱1 乱5 ，u 2 u 6 ，u 2 0 , 5 ， a 2 u 4 ，u 3 “4 ，u 3 u 7 u 4 u 7 ，u 5 u 7 ，u 6 u 7 ) ) 。见图1 7 - 1 s 。 甜。 图17 ：t 9图18 ：t10 证明：由，m ( 日一丙( 8 ) ) = z m ( h ) = 1 ，可知，夕e 。记e o = a b ，a c ，a d ，a e ，f b ，c ，g c ，g d ，g e ，夕) ，记t o = ( ve o ) 。则蜀为日 的一个支撑子图。显然我们有e = e oue ( p ，c ，d ，e ) ) 。见图1 9 。由于 i m ( h ) = i m ( h 一丙( c ) ) = 1 ，则宵e ( p ，d ，e ) ) 0 。下面我们分三种情 形讨论。 1 5 衫 河南大学硕士学位论文 情形1d e e ，在这种情况下，我们必有n ( d ) 一丙( e ) d 和n ( e ) 一 - n ( d ) 0 。考虑到d ，e 的对称性，不妨设c n ( d ) 一丙( e ) 和b n ( e ) 一 丙( d ) ，我们有e ( 6 ，c ，d ，e ) ) = d e ， 托。见图2 0 。 b e 图l9 ：t o f g b e ，谢) ，则有e a ( h ) = e ，h = t 9 图20 情形26 e e 且d e e 。如果b c e ，则有i m ( h ) = i m ( h - n ( c ) ) = l ， 则d e e ，矛盾。因此b c 譬e 如果c d e ，则有i m ( h ) = i m ( h 一 丙( d ) ) = 1 ，则必有b d 譬e ，n ( d ) 一( e ) = 毋，矛盾。因此，c d 隹e 。如 果c e ，则有i m ( h ) = i m ( h 一丙( e ) ) = 0 ，矛盾。因此，c e 譬e 。 情形2 1e ( 1 6 ，c ，d ，e ) ) = 6 e ) 时，则有既( 日) = e ，h = t l o x a 。 见图2 1 。 情形2 2 e a ( 日) = e ， 图22 1 6 河南大学硕士学位论文 情形3b e 岳e ，且d e 隹e 。此时，由e ( 6 ，d ，e ) ) o 可得b d e 。由 蜀中d ，e 两点的对称性可知，t 同构于丑o 。命题4 6 证毕。 命题4 7 ：设h = ( ve ) x a ，v = n ，b ，c ，d ，e ，9 ) ，a ( h ) = 4 ，n ( a ) = 6 ，c ，d ，e 。设= ( 口，b ，c ，d ，e ) ，k = ，9 ) ，【，】= z e ：z ，y k ) = u b ，c ，f d ，g c ，g d ，夕e - 。则g 同构 于正o ，互1 。其中五1 = ( v ( t n ) ，e ( 互1 ) ) = ( 地：i b ，( u l u 2 ，札l u 3 ，u l u 4 ， u l ，u 2 u 3 ，u 2 u 8 ，u 2 u 7 ，乱3 地，乱3 ，u 4 u 5 ， u 4 u 7 ，u 5 u 6 ，u 5 u 7 ，嘶 ) a 见 图2 3 。 纠， 图23 ：r i l 儿 “5 甜， 证明：由i m ( h 一丙( n ) ) = i m ( h ) = 1 ，可知，夕e 。记e o = a b ，a c ，a d ，a e ，f b ，c ，f d ，g c ，g d ，g e ，y g ，记t o = ( ve o ) 。则蜀为 日的一个支撑子图。显然我们有e = e oue ( 6 ，c ，d ，e ) ) ，i m ( h o ) = 1 ， 而且蜀不是一个平面图。见图2 4 。由于i m ( h ) = i m ( h 一( c ) ) = 1 ，则 有e ( ( 6 ，d ，e ) d 。下面我们分三种情形讨论。 情形1d e e ，在这种情况下，我们必有i m ( h 一( d ) ) = ，m ( 日) = 1 ， 则有b c e 。又由( e ) 一一n ( d ) d ，和a ( h ) = 4 可知6 e e ，此时， e ( 伯，c ，d ，e ) ) = b e ，b e ，e 田，h 是一个4 正则图，则有既( 日) = e ，h = 互2 x 。见图2 5 。 a bc 图2 4 ：t 0 1 7 图25 g 河南大学硕士学位论文 情形26 e e ，且d e 隹e 。如果6 c e ，则有i m ( h 一( c ) ) = i m ( h ) = 1 ，则d e e ，矛盾。因此，b c 譬e 。如果以e ，由a ( h ) = 4 可知y ( c ) = - n ( d ) ，矛盾。因此，c d 萑e 。 情形2 1b d e 。在这种情况下，i m ( h 一丙( c ) ) = i m ( h ) = l ，则 c e 圣e ，此时，e ( 6 ，c ，d ，e ) ) = 沈) ，则有f - , a ( h ) = e ，h = 五3 x a 。 见图2 6 。 图26 命题4 8 ：设h = ( ve ) x a 是一个7 个顶点的简单连通图。则对某 一个3si 1 1 ，h 同构于乃。 u u t 图1 ：t1 u u 图7 ：t 4 图2 ：1 2 u u 3 u 2 图4 ：t3 ， 图8 ：t5 河南大学硕士学位论文 u u 图9 ：t 6 u 2 图l0 ：t 7 图15 ：t 8 图17 ：t 9 ：? 一： 证明：如果( 日) 5 ，不妨设a 为日中的最大度点，则有1 m ( h ) = i m ( h 一丙( 8 ) ) = 0 ，矛盾。因此a ( h ) s4 。显然a ( h ) 2 。如果 ( 日) = 2 ，则有命题4 i ( d ) 可知，日是一个圈。而且仃三2 ( m o d 3 ) ，矛 盾。 如果a ( h ) = 3 ，由命题4 2 可知，t 同构于死。在下文中，我们设 a ( h ) = 4 ，设v = a ，b ，c ，d ，e ，f ，9 ) ，n ( a ) = 6 ，c ，d ，e ) 。由 i m ( h 一丙( 口) ) = i m ( h ) = 1 ，可知f g e ，而且b ，c ，d ，e n ( f ) u ( 夕) 。 记i 1 = l n ( f ) nn ( a ) l ，1 2 = n ( g ) nn ( a ) l ，则有：1