（基础数学专业论文）超欧拉图的判定及catlin猜想的研究.pdf

超欧拉图的判定及c a t l i n 猜想的研究 学科专业基础数学 指导教师李登信 研究方向群与图 研究生 王斌( 2 0 0 0 2 0 7 l 内容摘要 超欧拉图问题是图论研究中非常重要的一个问题，这一问题主要有两方面： 一判定问题，二边数问题。本文使用收缩法对这两方面进行了若干探讨，提出了 一个新的概念次可折子图，并对它进行了一些研究本文主要结果有： 定理7 g 是一个简单图。则g s l g 中有边不交路p l ，p 2 ，：。p ，其端点互不相同。 满足( 1 ) o ( g ) = 只的端点f f = 1 , 2 s ， ( 2 ) g u e ( 只) 连通。 f = i 命题3 2 设轧n 为自然数，m 2 n 2 ，不同时为3 ，则m n 型矩形网格图是超欧拉图。 定理8h 是连通图g 的一个子图。如果h 是g 的次可折子图，则g h 脱g s l 。 定理9 g = e ) 是超欧拉图，n ( g ) l = n ，艿( g ) 是g 的最小度。若占( g ) m “ 4 ，竺善) ， ) 见qg 中有欧拉生成子图h ，满足 ( 日) i 怍( g m 。 定理1 0 g ；( 、e ) 是不含x 3 子图的趣欧拉图，n ( g ) l - - n 。若占( g ) 熹，则g 中有欧拉 生成子图h ，满足f e ( ) f 詈l e ( g ) f ，或者g e ( h ) 有平凡分支。 命题6 1 h 是一个图。如果存在v ( i ) 的一个偶子集x ，使得每一个以x 为奇顶点集的h 的子图日，都不是h 的生成子图，则存在h 的一个超图g ，使得g h 脱臼g s l 不 成立。、 0 关键词：超欧拉图；可折叠图；c a t l i n - 猜想、 t h ed e t e r m i n a f i o no f s u p e r e u l e r i a ng r a p h s a n dr e s e r c ho f c a t l i n - c o n j e c t u r e m a j o r b a s i c m a t h e m a t i c s s u p e r v i s o r ：p r o f l id e n g x i n a b s t r a c t s p e c i a l i t y ：g r o u p & g r a p h a u t h o r ： w a n gb i n ( 2 0 0 0 2 0 7 ) t h es u p e r c u l e r i e ng r a p hp r o b l e mi sa ni m p o r t a n ts t u d yi nt h ec i r c l eo f g r a p ht h e o r y , w h i c h m a i n l yi n c l u d e st w oa s p e c t s ：o n ei st h ed e t e r m i n a t i o no fs u p e r e o l e r i s ng r a p h sa n dt h eo t h e ri st h e e d g e - p r o b l e m 1 1 l cd i s s e r t a t i u ni n v e s t i g a t e dt h ep r o b l e m sm e n t i o n e da b o v eu n d e rt h ec o n 打a c t i o n m e t h o di nt h ep a p e r , t h e r ei san c v vc o n c e p t i o n - - s u b - c o l l a p s i b l es u b g r a p l r 一p r e s e n t e d ， a r o u n dw h i c ht l i a s o m ed i s e n s s i o a sm a d e n ”m a i nr e s u l t so f t h ep a p e r 帆f o i l o w i n g ： t h e o r e m7gi sa s i m p l eg r a p h t h e nges lc ，t h e r ea r e e d g e d i s j o i n tp a t h s p i ，p 2 ，p 。w h o s ec n d p o i n t s a r ed i f f e r e n t i np a i rs u c h t h a t o ( g 卜 e n d p o i o t s o f 只f f = 1 , 2 ，s j a n dg u e ) i sc o n n e o t e d i = l 。 p p “沁n3 2 i f 甄na 砖n a t u r a ln u m b e r s ，1 1 0l e s st h a n2 ，t h e n 卅”- 舒dg r a p h sa r e s u p e r c u l e r i a nw h e nm ，na r en o t3s i m u l t a n e o m l y t h e o r e m8 s u p p o s ehi s as u b g r a p ho fac o n n e c t e dg r a p hgi fhi sa s u b - c o l l a p s i b l e s u b g r a p ho f g t h e ng i - i s l g s l t h e o r e m9a s s u m e ( 每( v e ) i ss u p e r e u l e r i a n ，i v ( g ) i - - n ，艿( g ) d e n o t e st h em i n i m a ld e g r e e o fg i f 占( g ) m 双 4 ，n - - 4 ) ，t h e nt h 盯ei s a s p 蛐j l i n ge u i e r i 孤s u b 鲫p hhs u c ht h a t | e ( t ) l 妄l 以g h t h e o r e m1 0a s s u m eg = e ) i ss u p e n m l e r i e na n dk 3 一沁e ，i v ( g ) i = n ，艿( g ) d e n o t e st h e m i i i i m a ld e g r e eo f g i f j ( g ) 2 而g ，t h e n t h e r ee x i s t sas p a n n i n ge u l e r i a ns u b g r a p hh ，s u c ht h a t 陋饵1 2 导l 耳g m ，甜岫眦订晌i b r a n c h e s i n g e p r o p o s i t i o n6 1 hi sas i m p l eg r a p h i ft h e r ei s 缸e v e l ls e txo fv ( h ) s u c ht h a te v e r y s u b g r a p hh ro f hw h o s eo d d - v m 忆 xs o ti sx i sn o ts p a n n i n go n e , t h e nt h e r ei sas u p o r g r a p hg o f h s u c h t h a t g ，h es l g s l f a i l s k e y w o r d s ：s u p e r e u l e r i a ng r a p h s ；c o l l a p s i b l e ；c o n t r a c t i o n ；s u b - c o l l a p s i b l e s u b g r a p h s ；c a t l i n c o n j e c t u r e 2 一术语和记号( n o t a t i o n a n d t e r m i n o l o g y ) 在本文中，g ，h 表示无向图( u n d i r e c t e dg r a p h ) 。e ( g ) 表示图g 的边集- v ( g ) 表示幽g 的顶点集。o g ) 表示豳g 的奇顶点集，即o ( g 户 g 的奇顶点 。 冈表示集合x 的基数即集合x 所含元素的个数。 p ，q 表示路( p a t h ) ，t 表示森林( 觚s t ) 或树( t r e e ) 一个图称为欧拉i 萄( e u l e r i a ng r a p h ) ，如果它是连j i l l ( c o n n e c t e d ) ( i c j 并且不含奇顶点。一 个圈称为超欧拉图( s u p e r e u l e r i a n ) ，如果它含有欧拉生成子图( s p a n n i n g e u l e r i a ns u b g r a p h ) 。超 欧拉图全体通常记为观，即乩= f 超欧拉幽 。 图g 称为可折叠图( c o l l a p s i b l e ) ，如果对v ( g ) 的任意偶子集s 都有子图h 满足i ) o ( h 户s ； 2 ) g e ( h ) 连通。可折叠图全体通常记为c l 。即c = 可折叠图 。 图h 是图g 的子图，g 称为g 关于h 的收缩( c o n t r a c t i o n ) 。如果v ( g 产v ( g - h ) + ”， e ( g + 产e ( g - h ) u l n ，hi 材e v ( g 一日) ，3 v v ( h ) s ，1 n ，e ( g ) 芒v ( g ) 。应当指山 的是，在收缩图中可能出现重边。通常把g 关于h 的收缩记为g h 。 如无特别说明，以下引用的术语和记号都来源于文献【l 】。 二引言( i n t r o d u c t i o n ) 1 7 3 6 年，莱昂纳多欧拉o o n h a r de n t e r ) 发表了划时代的论文，题目叫做“一个与位 置几何相关的问题之解答”( t h e s o l u t i o no f a p r o b l e mr e l a t i n gt ot h eg e o m e t r yo f p o s i t i o n ) 在 这篇论文里，他解决了著名的“歌尼斯堡七桥问题”( k i n i g s b e r g b r i d g e w o b l e m ) 。此后，以 他的名字命名的欧拉图，以及与之相关的问题的研究成为图论研究里非常重要的一个方面。 比如欧拉迹( e u l e r i a n t r a i l ) 问题，途径覆盖( w a l k v 甜雌) 问题中国邮递员问r e ( t h ec h i n e s o p o s t m a np r o b l e m s ) ，以及与之相关的计数问题，等等，详情请参阅文献【2 】。 1 9 7 7 年，b o e s c h ，s u f f i e l 和t i n d e l l 等人问道：在什么条件下，图g 有一个超图 ( s u p e r g r a p h ) h ，使得( 1 ) h 是欧拉图；( 2 ) v ( g 产v ( h ) ? 如果这样的h 存在，就称g 为次欧拉图 ( s u b e u l e r i a n ) 。【3 】 b o e s c h ，s u f f i e l 和t i n d e l l ，以及j a e g e r 分别独立地证明了： 定理1 口1 【4 】图g 是次欧拉图g 没有生成：子 ( s p a n n i n g s u b g r a p h ) h 满足h 望k ，其 中s ，t 都是奇数。 另一方面，b o e s c h 等人问道：在什么条件下图g 有一个欧拉生成子图即g 趄超欧拉 图? 【3 】 超欧拉图的研究主要集中在两个方面：一判定问题：二边数问题。所谓边数问题指的 是；当g 是超欧拉图时，至少要去掉几条边才能得到一个欧拉生成子图。 1 9 7 9 年，p u l l e yb l a n k 发现：确定一个图是否是超欧拉的，是一个n p _ 完备问题。【5 1 1 6 可见这一问题的难度。至于边数问题，目前也只是刚刚起步。 现今国际上研究超欧拉图问题的主要方法，是著名学者p m dac a n i i i 于1 9 8 8 年首先提 出和使用的收缩法( c o n t r a c t i o n m e t h o d ) 。c a t s n 发现，当h ec 时，有如下结果： 定理2 【7 】图h 是图g 的子图，h ，则g h e 皿g s l 。 事实上，这一结果是用收缩法寻求欧拉生成子图的理论根据。c a f l i n 和他的合作者用收 缩法得到了很多重要的结果。 定理3 【8 1 若g 是一个4 一边连通图，则g 是超欧拉图。 定理4 1 8 设k 是自然数，则g 是2 k _ 边连通图，当且仅当g 中去掉任意k 条边后还含 有k 棵边不交生成树。 定理5 忉至多添一条边，就能使图g 含有2 棵边不交生成树则 ( 1 ) g s l 或( 2 ) g 有割边。 定理6 1 1 0 设n ，m 和p 都是自然数，m , p 2 。g 是2 - 边连通图，i 矿( g m = i i p + 6 且不含 k 。“一子图。如果 i e ( g ) i ( p y ) 坳叫坳一一御量4 钭， 则 ( 1 ) g s l ；或 ( 2 ) g 可以收缩成不超过p 个顶点的非超欧拉图；或 ( 3 ) ( + ) 式等号成立，且g 中有一个n - p + l 阶子图h 同构于完全n 卜- 部图l ，一。1 ，使得 g h 同构于如，2 ，其中p 是奇数。 详细情形请参看文献【l l 】【1 2 】。 易知c 2 是可折叠图，由定理2 可得，图g s l4 ：r ，g c 2 s l 。因此超欧拉图的讨 论可以集中在简单图方面。下面从两方面讨论简单图的超欧拉图问题。 5 三超欧拉图的判定 , ( d e t e r m i n a t i o no f s u p e r e u l e r i a ng r a p h s ) 反复利用定理2 图g 的非平凡可折叠子图可以收缩成一个个点，从而超欧拉图的判定 问题可以集中在不含有非平凡可折叠子图的图上进行。不含有非平凡可折叠子图的图称为简 化图( 吲u c 甜g f a p ”。诚然，使用收缩法可以将一个大的、比较复杂的图转化为较小的、较 简单的图但它没有解决：怎样的简化图才是超欧拉图? 另外，阶数较大的可折叠子图也不 容易判断。 下面证明了： 定理7g 是一个简单图，则g 乩g 中有边不交路a ，p 2 ，以其端点互不相同 满足( 1 ) o ( g ) = a 的端点i ，= 1 , 2 引 ( 2 ) g u e ( a ) 连通。 i = i m ( o ) 引理7 1 川设g 是简单图，g 。g j ，g i 是连通分支a 是v ( g ) 的偶子集。若a c 、v ( g ，) i = 1 都是偶集，则g 有子图h ，使得o ( h ) = a 。 定理7 的证明：设g 仨s l ，则有子图h g 是g 的欧拉生成子图，则o ( g ) = o ( g - - e ( h ) ) 。 设g e ( h ) = g 。，t = 脚i ：g - e ( h ) ) 0 ( g ) = 0 ( g - 一e ( h ) ) = 0 ( g t ) 。设t 是g - e ( h ) 的生成林。 f 1l = i t t = t i ，则0 ( g ) n v ( t 1 ) = o ( g t ) ，i = i 2 t 。由引理知t 中有子图h 满足0 ( h + ) ，= i = 0 ( g ) 。h + 无圈，容易从中分离出边不交路p l ，p l ，使得o ( g ) = p i 的端点i i = 1 2 s 。 fj 又g ue ( p i ) h ，所以g ue ( f i ) 连通。 1 2 lf o l j 反之事实上，g c ，e ( 乳) 就是g 的一个欧拉生成子图，从而g s l 。证毕。 下面利用定理7 给出定理2 的另一个证明。 命题3 1 ：g c l ，a 是v ( g ) 的偶子集。则6 中有边不交路p l ，如，p i 满足a = p i 的端点 f 2 1 2 5 ) ，且g 些e p t ) 连通 证明：由c l 的定义，g 有子图h ，满足o ( d = a ，且g - - e ( d 连通。取h 的生成林t ，则 t 的每一分支含a 中偶数个点。由引理7 1 及定理7 的证明知。t 有边不交的路p l ，p i ，满 足a = p - 的端点i i = l ，2 s 。g u e ( a ) 三g - - e ( h ) 所以连通。证毕。 i 一 6 定理2 的证明：设g h s l ，由定理7 知g h 有边不交路q 一q 满足o ( g h ) = ( q i 的端 点 i = 1 2 。t 且g h u e ( m ) 连通。q ，。m 在g 中的导出子图为边不交的路 r 2 l 记为q 。q ，。又h 连通所以g 一毋e ( q 。) 连通。令a = fq ；的端点i i = l 、2 s t 2 i a = a + n v ( h ) b = o ( g ) n v ( h ) 。则a a b v ( h ) 是偶集。又h e c l ，由命题7 1 知h 有边不交路p l p 满足a a b = p 。的端点i = 1 、2 m 且h ue ( p - ) 连通。 f 2 t 将q ，q ，p 。p _ 中首尾相接的路合并重新编号得边不交路p p n 。并且 p i 的端点j i = 1 ，2 n = a ( a b ) = ( a n ( v ( h ) u v ( g ) v ( h ) ) ) ( a b ) i = ( o ( g ) 、v ( h ) ) u ( 0 ( g ) n v ( h ) ) = 0 ( g ) 。叉g ue ( p i ) 连通，由定理7 知g e s l 。 l = l 反之。容易看出超欧拉图关于收缩是封闭的故然。证毕。 另外，利用定理7 可以较方便地判定某些图的超欧拉性，比如矩形网格图 ( r e c t a n g l e g r i dg r a p h ) 设g 是一个筒筚固如聚v ( g ) 2 。 i = 1 , 2 ，埘，= 1 , 2 ，) e ( g ) = 甜j ，p 1 i f = 1 , 2 埘，= 1 , 2 ，j i 一1 u l ，u 打，+ 1 ji i = 1 , 2 ，埘一l ，= 1 , 2 ，f m 。n 为不小于2 的自然数。则称g 为xn 矩形网格图。埘= 3 ，疗= 4 时，网格图如图一所示。 ( 图一) 命题3 2 设m 1 1 为自然数m 2 ，n 2 ，不同时为3 则m n 型矩形网格图是超欧拉图。 证明；设g 是xn 型矩形网格图，m ，1 1 不同时为3 ，则易见o ( g ) = u 。i i = 2 m 一1 j = 1 n ju fu j i = 1 ，m j = 2 n i 。由定理7 知只需在g 中找出边不交路p 1 ，r 其端 点互不相同，使得0 ( g ) = p 的端点1 i - - - - 1 ，2 ) 且g u e ( p i ) 连通。下面分情况 i = i 讨论。 由m 、n 的对称性，不妨设口n 。m = 2 对令p ，= m ；u t n ，i = l 。n 一2 满足要 求。故下设3 m 4 n 。 1 ) m = 2 k 。n = 2 1 ，k 1 为自然数。令p 1 2 u 1 2 m 1 i = l ，2 i - i ：p 2 i = u “2 i + i i ：1 卜l ： r ，。也j i u ”l ，p i j - j 。u 1 ，j ：1 ，z ，k - 1 。易见p i ，j 满足要求。 2 ) m = 2 k + l ，n = 2 r a 令a j = i l , 2 + | u i 2 f + 2 ，i = 1 。2 ，r 一2 p 2 = 2 ，”_ 2 i + l i 2 1 卜1 p 3 ，= h 2 ，+ i 1 h 2 i + 2 1 ，4 。，= 2 p l 。 2 ，+ 2 j = z ，2 - k - i p j o = ”2 。l 2 2 1 2 肌1 = z ，2 h 。 易见p u 满是要求。 3 ) m = 2 k ，n = 2 r + l ，由r a n 的对称性，类似于2 ) 可得。 4 ) m = 2 k + l ，n _ 2 件l ，令p l = i 2 j u i 2 i “，i = 1 2 r 一1 ：p 1 o2 i , n _ l i l 2 , n 1 1 1 2 ，n ：p 2 i 2 甜2 i + i h 打2r + 2 、n ，i = l ，- - k - 1 ：p o ，l = ，巾l ，i ”_ 一i ，2 1 1 m2 ：p 3 j = 2 l l u 2 p l l l j 2 1 2 ，k - l ；p 4 j = 打m 2 ，+ l “m 2 j + 2 ，j 2 l ，2 ，一卜1 。易见p 满足要求 综上所述，l a x n 型矩形网格图，当m n 不同时取3 的时候为超欧拉图。证毕。 当m 2 n 2 3 时，网格图g 如图二所示：0 ( g ) = ”2 fj i = l 4 。若g e s l ，由定理7 存在边不交路p l ，p 2 ，其端点集为0 ( g ) ，且g - - e ( p 1 ) 一e ( p 2 ) 连通。但易见只不经 过”l ，蚝，甜7 ，则蚝i p l 与p 2 的公共点但d ( u ，) = 4 ，则6 - - e ( p 1 ) 一e ( p 2 ) 不连通 矛盾。所以，g 匹s l 。 t l 正 曲 讲请 确 ( 图二) t ( 图三) 四次可折子图( s u b - c o ii a p s i b i es u b g r s p h ) 在具体判定一个图是否超欧拉图时，我们发现。定理2 对于子图h 的要求过分强了。实 际上。对于一个给定的图g 和g 的子图h ，要使得g ，何| s 三 专g 乩成立，不必要求 h 对于v ( h ) 的任意偶子集s 都有连通生成子图风，满足o ( 日s ) = s ；只要对于v ( h ) 中和g - - v ( h ) 邻接的点满足上述要求即可。故而我们提出如下定义： 定义4 1 ：设h 是简单图g 的一个子图。v ( h ) 的一个子集b 称为h 关于g 的边界 ( b o u n d a r y ) ，如果b = v 矿( ) 1 3 u v ( g ) 、y ( h ) ，s t j l v e ( g ) 。 定义4 2 ：设h 是简单图g 的一个子图。v ( h ) c v ( g ) ，b 是h 关于g 的边界。如果对 于b 的任意偶子集s ，h 都有连通生成子图以t 满足0 ( 日s 户s ，则称h 是g 的次可折子 图( s u b - c o l l a p s i b l es u b g r a p h ) 。 关于次可折子圈，我们有以下命题： 稳r 题4 1 设h 是g 的次可折子图，则h e 乩。 证明：设b 是h 关于g 的边界，取妒b 由h 的定义，h 中有连通生成子幽h ，满 足o ( 凰) _ ，即q 是h 的欧拉生成子图。h 脱。证毕。 命题4 2 h i ，h 2 是图g 的次可折子图，e ( h i ) n e ( 凰产妒q 关于g 的边界b ( 辟1 ，2 ) 满足巩。nb 巩。如果v ( qu h 2 ) c v ( g ) ，则日lu h 2 是g 的次可折子幽。 证明：设b 是何iu 马关于g 的边界t 则b e _ 昂ub 也。取b 的任意个偶子集s 1 ) sn 为偶集，则s 、。量，也是一个偶集由于q 是g 的次可折子陶，所以存 在q 的连通生成子图只满足0 ( q ) = s n ，0 ( h 2 ) = s 、嘞。令 k h i u 马因为e ( 马) ne ( ) = 妒，所以以i ) n e ( h 2 。) = ，从而 o ( h ) = d ( 日) a d ( ) = d ( 玩) u d ( 以) = s 。 y ( ) n 矿( 2 ) 2 巩n 妒所以日是连通的 曩 2 ) snb m 非偶集，同样s 、b 机亦非偶集取x b 川nb 乩，则 彳l = 工) a ( s n 。) 毋为偶集，h i 是g 的次可折子图存在连通生成子酗h l ，满 足d ( h i 。) = 4 。类似地，a 2 = x ) ( s 、：) 巩。亦为偶集，h 2 中有连通生成子幽 h 2 。 蓠足o ( h 2 ) = 彳2 。令日t - h l u - 1 2 ，同1 ) h l 是h i u h 2 的连通生成子图， o ( h ) = s 。由s 的任意性知，h 。u h 2 是g 的次可折子幽。证毕- 确r 题4 3h l ，h 2 是g 的次可折子图。e ( h , ) n e ( h 2 ) = , 1 6 。如果g = g 【v ( h 1u 也) 1 是2 边连通圈，则g es l 。 证明：设置是羁关于g 的边界，i = 1 ，2 。i ) 属n9 2 = 妒，则有h lnh 2 = 。g = g v ( h i u h 2 ) 】是2 边连通阔所以存在q e 2 e ( g ) 使得h i + 吼+ q + p 2 连通 v ( e l ue 2 ) b 。若q 、e 2 相邻接，不妨设公共点在里t 由次可折子i ! 目的定义，h i 中 有连通生成子图日，d ( q ) = 妒；中市连通生成子豳吼满足d ( 吐) 。 。 _ v ( e lue 2 ) n v ( h ) 。令日= 日i + h 2 + q + p 2 则h 是g 的生成欧拉于l 璺i 。若q 、e 2 不 邻接由次可折子图的定义，珥中有连通生成子l 璺1 日，- 满足0 ( e ) = v ( e lue 2 ) n v ( 珥) 。令h = h l + h 2 + e l + 岛，则h 是g 的生成欧拉子| 鳘i 。 2 ) b l n 暖。则v ( h 1 ) n v ( h 2 ) 。由命题1 ) ，知h ，s l 存在欧拉生成子翻h ，。 令h k 日1 u h 2 - 因为e ( 且) ne ( 日2 ) - 妒所以o ( h ) = o ( h l 。) u o c h 2 ) = 矿，即h 是g 的生成欧拉子图。证毕。 推论4 3 连通阔g 可以分解成次可折子图q ，即g = g 【u v ( h ) 】o 如果 ， e ( 珥) n e ( 以户，f ，则o 脱 证明：由命题4 3 ，用归纳法可得。证毕。 命厦4 4h 是闰g 的一个子图v ( h ) c v ( g ) ，b 是h 关于g 的边界。如果o ( h ) c z b ， 则h 是g 的次可折子图对b 的任意偶子集a 存在h 的子圈_ 使得o ( h j 户a h e ( h ) 连通 证明：设h 是g 的次可折子图。则对b 的任意偶子集a 令一= o ( h ) a a ，那么是b 的一个偶子集。由h 的定义，存在h 的连通生成子图使得o ( h 产彳。令h = h h ， 则o ( h j ) 旬( h ) o ( 日) = a ，h = h h ，连通- 反之，任取a 是b 的一个偶子集。令a = o ( h ) a ，则a 是b 的一个偶子集。由假设 对b 的偶子集a ，存在h 的子图h ，使得o ( j ，= a h e ( h ) 连通令= h h ， 则o ( ) = o ( h ) o ( 日j ) = 。由的任意性，h 是g 的次可折子圈。证毕。 是习里8h 是连通图g 的一个子图。如果h 是g 的次可折子图m i i g i h s g 乩。 证明：收缩关于超欧拉图是封闭的，故必要性成立。 反之，设g ，h 龇，则g h 有欧拉生成子图( 不妨设为g ) 。把g 看作g 的边的序列。则 g + 可以分解成r 个边不交的闭迹巧，和m 个极大开迹弓的并由于极人性，乃的端点两 两不交，且一盎 乃的端点i ，1 , 2 埘 v ( h ) 。设b 是h 关于g 的边界，则a b ，是b 的偶集由于h 是次可折的所以对a _ b ，存在h 的连通生成子图片，使得d ( ) = a 。 令晶2 层( 日一) u 岩e ( 乃) u 拦联巧) 则e ( g ) ，g f 日】就是g 的欧拉生成子幽- 冈 为1 ) v ( g 【反】产v ( g ) ，2 ) 由日j 和l 的构造，g 【岛】无奇顶点，3 ) 是连通的，所以在g 中， 以h 代替v ，得到g 的导出子图g 【瓯】也是连通的。证毕。 ( 豳四) 可以看出定理8 的适用范围比定理2 广。例如令h = e 伽4 ) ，g 是h 的超图。设h 关于g 的边界b = 1 1 卅u v ee ( g ) 勋| g h e 观营g 观如图四所示。但显然g 不 是g 的可折叠子图。 六其他( o t h e r s ) 用收缩法研究超欧拉图时，对于被收缩的子图h 的选择是十分重要的。当h e ( z 时 由定理2 ，g h 艇g 脱，从而可以简化问题的讨论。当h e 口，上述结论一般不 成立。那么这个问题是否有一种普遍性昵? 1 9 8 8 年，c m l m 提出如下猜想： c a r lir t - - 猜想设h 是一个连通图，如果h 仨c ，则存在h 的一个超图g ，使得 g h 舡g 脱不成立。【6 】 2 0 0 0 年赖虹建( h o 鹋- j i l a i ) 教授提出收缩核( c o n v a c t i o c o 哟的概念。令s - f 带有某 种性质的图) ，则定义s 的收缩核s o = h ：对于任何一个包含h 为子图的图 g ，g s o g 啊s 例如s _ 超欧拉图 ，则k 3 s o 。由定理l 知，c 己s o 。c a i l i 猜想即是说c 己= s o 。 本文得到如下命题： 龠墨6 1h 是一个图。如果存在v ( d 的一个偶子集) ( 使得每一个以x 为奇顶点集的h 的子图j 0 都不是h 的生成子图，则存在h 的一个超图g ，使得g 日脱c ，g 乩不 成立。 证明：设x = v 1 v 2 i 小“v l ，v 2 ) ， 吃，v ) 是集合x 的一个划分。令g 是h 添加k 条路鼻，只所得的超图，其中满足1 ) 鼻= v 2 _ 1 坼v 2 ，( 1 ，膏) ；2 ) ”，仨v ( h ) ( 1 i k ) ( 参阅图九) 。 假设g 皿，令g l 为g 的欧拉生成子图。显然g l 包含k 条路鼻，只。定义 日x 2 g 1 - u ”，则日x 是h 的生成子图，且o ( n x ) - x ，矛盾。因此g 萑乩。但显然g ，h 钇。证毕。 显然，要想证明c a t l i n 猜想，还必须解决如下问题： ( 图九) 问题：设h 是一个2 边连通图。如果存在v ( h ) 的一个偶子集s ，使得h 的任意子图拭， 如果满足t ) 髓是h 的生成子图。2 ) o ( 曩。) = s ，则有上不连通。那么是否有h 的超图g ， 使得g h 乩营g e 脱不成立? 从另一个角度看，当h 仨c l 时，要使“g m e l g 艟”继续成立，必须对g 或 h 作适当的限制。例如： 碡 ( 图十) 2 s ( 图十 2 命题6 2 ：令h 是如图十所示3 x 3 矩形网格图g 是h 的超图，g h e s l 。设h + 是g t l 的 欧拉生成子图h + 在g 中的诱导子图记为h 。若0 ( h ) 中，u 三v ( h ) ，则g e s l 。 证明：h u h 是g 的连通生成子图，记为g 。易见o ( h ) v ( h - - u ) ，又o ( h ) = 1 1 2 ，j i = 1 。2 3 4 ) ，所以o ( g ) = o ( h ) 0 ( i ) e v ( h - - u ) 。要证g e s l 只需证g s l 。 由定理8 的证明可知，只要h 中有边不交的路连接0 ( g + ) 的点，并且关于h 的补图连通 即可。以下分情况找出h 中符合要求的路。由于h 的对称性若出现已讨论过情况的对称情 形，将略而不论。 ( 1 ) 1 0 ( h ) = 2 1 ) 10 ( g + ) f = 6 ，则0 ( h ) = ，蚝 或f “，蚝 相应的0 ( g + ) = v ( h - - u ) 一 吩。 7 或v ( h - - u ) 蚝，t 7 。符合要求的路如图十一虚线所示( 下同) 2 ) 10 ( g + ) i = 4 2 ，类似可得。 ( 2 ) ；0 ( h ) i = 4 6 ，8 时。仿照( 1 ) 的讨论，容易找到满足要求的路。 综上可得，g 乩。 1 7 参考文献； 【l l j a b o n d ya n dus r m u r l y , “g r a p ht h e o r yw i t ha p p l i c a t i o n s a m e r i c a ne l s e v i e r , n e w y o r k ( 1 9 7 6 ) 【2 1 l wb e i n e k e ，& r jw i l s o n , “s e l e c t e dt o p i c si ng r a p ht h e o r y2 ”a c a d e m i cp r e s s ，n e w y o r k ( 1 9 8 3 ) 【3 】ftb o c s o h , c s u f f e l ，a n dr t i n d c l l ，t h es p a n n i n gs u b g r a p h so fe u l e r i a ng r a p h s j g r a p h t h e o r y1 ( 1 9 7 7 ) 7 9 - 8 4 【4 1 ej a e g e r , a n o t eo ns u b a n l e r i a ng r a p h s j g r a p h t h e o r y3 ( 1 9 7 9 ) 9 1 - 9 3 【5 1 w p u l i o y b l a n k , an o t eo ng r a p h ss p a n n e db ye u l e r i a ng r a p h s j g r a p ht h c o r y3 ( 1 9 7 9 ) 3 0 9 31 0 【6 1 a ab c t t o s s i ，e d g ch a m i l t o n i a np a t hp r o b l e mi sn p - - c o m p l e t e i n f o r m p r o c e s sl o t t 1 3 ( 1 9 8 1 ) 1 5 7 - 1 5 9 f 7 】pa c a t l i n ，ar e d u c t i i o nm e t