（运筹学与控制论专业论文）嵌入图中的短圈问题及相关问题.pdf

d i s s e r t a t i o nf o r m a s t e rd e g r e e ，2 0 1 0 c o l l e g ec o d e ：1 0 2 6 9 舶舀s t e rn u m b e r ：5 1 0 7 0 6 0 1 0 1 2 e a s tc h i n an o r m a lu n i v e r s i t y s h o r tc y c l e si ne m b e d d e dg r a p h sa n d s o m er e l a t e dt o p i c s d e p a r t m e n t ： m a t h e m a t i c s m a j o r ： s u b j e c t ： o p e r a t i o n a lr e s e a r c ha n dc y b e r n e t i c s t o p o l o g i c a lg r a p ht h e o r y s u p e r v i s o r ：p r o f r e nh a n n a m e ： c a on i m a y ，2 0 1 0 s h a n g h a i 郑重声明 东师范大学攻 华东师范大学学位论文原创性声明 嵌入图中的短圈问题及相关问题，是在华 学位期间，在导师的指导下进行的研究工作及 取得的研究成果除文巾已经注明引用的内容外，本论文不包含其他个人已经发表或 撰写过的研究成果对本文的研究做出重要贡献的个人和集体，均已在文中作了明确 说明并表示谢意 作者签名：影像 日期：硼口年 j p j 2 歹日 华东师范大学学位论文著作权使用声明 嵌入图中的短矧问题及相关问题系本人在华东师范大学攻读学位期间在导 师指导下完成的班博士( 请勾选) 学位论文，本论文的研究成果归华东师范大学 所有本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和 相关机构如国家图书馆、中信所和”知网”送交学位论文的印刷版和电子版：允许学 位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入 全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编 出版，采用影印、缩印或者其它方式合理复制学位论文 本学位论文属于( 请勾选) 华东师范大学相关部门审查核定的”内部”或”涉密”学位论文木，于 年 月 日解密，密后适用上述授权 保密，适用上述授权 学位论文作者签名：皆仫 导师签名： 衫钐玄声 砂优年广月z ，罗日 涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审 定过的学位论文( 需附获批的华东师范大学研究生申请学位论文”涉密”审批表方为 有效) ，未经上述部门审定的学位论文均为公开学位论文此声明栏不填写的，默认为 公开学位论文，均适用上述授权) 曹倪硕士学位论文答辩委员会成员名单 姓名职称单位备注 洪渊教授华东师范大学数学系主席 张晓东教授上海交通大学数学系 郭军伟副教授华东师范大学数学系 摘要 本文首先研究图中短圈问题，设c 1 是一个图g 的由广探术所产生的基本圈的集 合，c 2 是由所有c l 中的两个圈的对称差所组成的集合我们将证明( 1 ) c = c lu c 2 包含一个一嵌入图g 的一个最短一双侧圈这将推出存在一个多项式算法用以发现 一个嵌入图的一个最短- 双侧圈，并且由此解决了一个由b m o h a r 和c t h o m a s s e n 提f ；的公开问题 g r a p h so ns u r a c e s ，2 0 0 1 ，p 1 1 2 ( 2 ) c 包含了一个图g 的所有可 能的最短偶圈，因此在任何一个图r f l 至多存在多项式多个最短偶圈( 3 ) 设c 0 是一一个 图g 的所有最短圈的集合则岛c 另外，许多类型的最短圈包含在c 0 ( c ) 中同 时无穷多个例子显示：在某些( 嵌x ) m 中可以分别存存指数多个最短奇圈，最短一单 侧圈，最短双侧圈在本文的第二部分，我们研究m s b i u s 梯子图的1 因子数和3 _ 边 染色数我们找到这些数的精确公式并且证明了在这类图中有指数多个1 因子和3 一边 染色( 即：1 因子分解数目) 关键词：h 一双侧圈，广探术( 广探树) ，嵌a m ；m s b i u s 梯子图，1 因子，边染色 a b s t r a c t i nt h ef i r s tp a r to ft h i sp a p e r w es t u d ys h o r tc y c l e si ne m b e d d e d 目印h s l e tc 1b et h es e to ff u n d a m e n t a lc y c l e so fb r e a d t h - f i r s t - s e a r c ht r e e si nag r a p hg ， a n dl e tc 2b et h es e to ft h es u i n so ft w oc y c l e si nc 1 t h e nw es h o wt h ef o l l o w i n g ： ( 1 ) c = c luc 2c o n t a i n sas h o r t e s ti i - t w o s i d e dc y c l ei nai i e m b e d d e dg r a p hg t h i si m p l i e st h ee x i s t e n c eo fap o l y n o m i a l l yb o u n d e da l g o r i t h mt of i n das h o r t e s t i i t w o s i d e dc y c l ei na ne m b e d d e dg r a p ha n dt h u ss o l v e sa no p e np r o b l e mo fm o h a r a n dt h o m a s s e nfg r a p h so ns u r y a c e s ，2 0 0 1 ，p 11 2 ( 2 ) cc o n t a i n sa l lt h ep o s s i b l e s h o r t e s te v e nc y c l e si nag r a p hg t h e r e f o r e ，t h e r ea r ea tm o s tp o l y n o m i a l l ym a n y s h o r t e s te v e nc y c l e si na n yg r a p h ( 3 ) l e tc ob et h es e to fa l lt h es h o r t e s tc y c l e so f ag r a p hg t h e nc oi sas u b s e to fc f u r t h e r m o r e 。m a n yt y p e so fs h o r t e s tc y c l e sa r e c o n t m n e di nc o ( c ) i n f i n i t e l ym a n ye x a m p l e ss h o wt h a tt h e r ea r ee x p o n e n t i a l l y m a n y s h o r t e s to d dc y c l e s s h o r t e s t 一o n e s i d e dc y c l e sa n ds h o r t e s ti i t w o s i d e dc y c l e s i ns o m e ( e m b e d d e d ) g r a p h s i nt h es e c o n dp a r to ft h i sp a p e rw es t u d yt h en u m b e r o f1 - f a c t o r sa n de d g e - c o l o r i n g so ft h em s b i u sl a d d e rg r a p h s w ef i n de x a c tf o r m u l a e f o rs u c hn u m b e r sa n ds h o wt h a tt h e r ea r ee x p o n e n t i a l l ym a n y1 - f a c t o r sa n de d g e - c o l o r i n g si ns u c h 铲a p l 培 k e yw o r d s ：s u r f a c e ，i i t w o s i d e dc y c l e ，b r e a d t h - f i r s t s e a r c ht r e e ，e m b e d d e d g r a p h ；m 6 b i n sl a d d e rg r a p h ，1 - f a c t o r ，e d g e - c o l o r i n g 1 1 目录 第一章在多项式时间内发现嵌入图中的短圈1 1 1 引言：1 1 2 主要结果的证明3 第二章m 6 b i u s 梯子图的1 因子数和边染色数7 2 1 引言7 2 2 主要结果的证明9 参考文献1 4 研究生期间所做的研究工作1 7 致谢：1 8 华东师范大学硕士论文嵌入图中的短圈问题及相关问题 第一章在多项式时间内发现嵌入图中的短固 1 1引言 c t h o m a s s e n 证明了如果一个圈的集合满足3 路条件，则存在一个多项式算法 用以发现该集合的一个最短圈【3 】作为应用，他证明了下列类型的最短圈能在多项式 时间内被找到 ( 1 ) 一嵌入图中的一个最短不可收缩髑； ( 2 ) i i 一嵌入图中的一个最短不可分离圈； ( 3 ) - 嵌入图中的一个最短n 单侧圈 然而对于那些不满2 = 3 一路条件的一族圈的集合，情况如何呢? 在他们的专著【2 ， p p l l 2 1 5 b ，b m o h a r 和c t h o m a s s e n 提出了如下公开问题： a ) 是否存在多项式算法用以发现嵌入图中的一个最短可收编圈2 ( b ) 是否存在多项式算法用以发瑗一嵌入图中的一个最短n 可分离圈2 ( c ) 是否存在多项式算法用以发瑷飘嵌入图中的一个最短n 双侧圈2 这里我们考虑连通图，所有用到的概念都如文献【1 ，2 】定义 设g 是一个嵌入图，已是g 的以z 为根节点的广探树设 c 1 = c ( t 。) 1 3 z y ( g ) ，c ( 瓦) 是死的一个基本圈) ； c 2 = c 1 3 x ，y v ( v ) c = c ( 瓦) oc ( 毛) ) ； c = c 1 u 饧， 这里”o ”运算按如下定义：对任意e ( g ) 的子集a ，b ”aob = ( a b ) u ( b a ) ” 1 华东师范大学硕士论文嵌入图中的短圈问题及相关问题 定理a 按上述方式定义的厨的集合c 满足以下条件? ( q ) c 包含一个最短一双侧圈( 在n 嵌入图中) ； ( b ) c 包含图中的每一个最短偶圈； ( c ) 如果图中的最短圈是奇圈，靴包含图中的每一个最短奇圈 尽管已有多项式算法用以发现图巾的一个最短偶圈，上述结果显示我们能够 用c t h o m a s s e n 的基本圈方法f 3 】走的更远 推论1 在任何一个图中至多有多项式多个最短倡厨 另外，定理a 可推出存在能够找到上述短圈的多项式算法 定理b 存在多项式算法用以发现一个嵌入图的一个最短n 双例圈以友一个图 的所有最短偶圈， 这将解决问题( c ) 因为射影平面上的嵌入图的每一个可能的双侧圈都可收缩， 所以我们得到如下结果： 摊论2 存在多项式算法用以发现一个射影平面上的嵌入图的一个最短可收缩圈 这样就回答了问题( a ) 一( c ) 在射影平面时的情形 以下例子说明在某些( 嵌入) 图中可以分别存在指数多个最短奇圈，最短单侧 圈或一双侧圈 2 华东师范大学硕士论文 嵌入图中的短圈问题及相关问题 1 2 主要结果的证明 一个曲面是一个连通的，紧的，h a u s d o r f f 的拓扑空间s ，并且局部同胚于平面 的开圆盘，即s 的每一点都有一个同胚于r 2 的单位开圆盘的开邻域 一个曲面上的图g 的一个广义嵌入方案是一个旋转系统7 r ( 丌= t r y i u y ( g ) ) ) 以及一个映射a ( 入：e ( g ) 一 - 1 ，+ 1 ) ，称为一个指派) 的集合，这里仉是v 的关联边的顺时针序我们定义i i = ( 7 r ，a ) 为图g 的一个嵌入方案嵌入图g 的一个 圈被称为是i i 双侧的，如果c 包含偶数个负指派的边；否则，被称为单侧的 对某个节点t ，y ( g ) ，我们可以改变顺时针序为逆时针序，即，被它的逆7 i 1 替换；同时，每条和口关联的边e 的指派a ( e ) 被一入( e ) 替换由此，我们得到另一个嵌入 方案h 7 = ( 7 r 7 ，入，) 显然一个圈是双侧的当且仅当它是一双侧的两个这样的嵌入 方案等价当且仅当其中一个能够通过一系列的局苦j 唼换变为另一个因此对嵌入图 的任意一个生成树t ，为了方便，我们可以假设t 的每条边e 都有指派入( e ) = + 1 设c 是图g 的一组圈的集合称c 满足3 一路条件若c 有以下性质：v g 的顶点x ，y ， p 1 ，恳，恳是连接z ，可的内部不交的路，若三个圈q j = 只u 易( 1 i d g ( z ，耖) 注：之后，我们将看到一个满足( 2 ) 的圈可以写成两个更短圈的和因此，一个满 足3 _ 路条件的圈的集合的最短元无法满足( 2 ) 引理1 如是一个无法写成两个刚1 ，c 2 的c 1o 伤的固，这里i q i i c l 0 = 1 ，2 ) 则c 是以c 上任意一点z 为根的广探树的基本圈 引理1 的证明容易看出c 满足条件( 1 ) ，但不满足条件( 2 ) 设z 是c 上的点，b 是 3 华东师范大学硕士论文嵌入图中的短圈问题及相关问题 以z 为根的广探树我们首先考虑i v i = 2 m 的情况设可是c 上满足d c ( z ，y ) = d g ( z ，y ) = 仇的点则我们断言死中惟一的( z 一秒) 路p 必定包含在c 内( 因为否则c 将 能写成两个不长于c 的圈的和) 设q 足c 上另一条连接x 和y 的路则根据之前同样的 理由，q 一可是已的路所以，c = pu ( q y ) + e ，这里e 是e ( c ) 一e ( 瓦) 中惟一的 边类似地，c 也是基本圈若它是奇圈 引理2 设g 及c 如定理a 中定义，c 足g 中满足俚j 的一个最短n 一双刎固她包 含g 的一个最短双侧阁 引理2 的证明我们假设g 有一个顺时针( 逆时针) 定向夺( 苓) ，对c 的任意两个 n u _ ；f n v ，记u 夸口( u 苓u ) 为沿着存( 苓) 的连接札到 的路类似地，我们定义u p 口为 路尸上连接u 到秽路如果牡是c 上的点，贝u i g u 一( 牡+ ) 为让沿着方的前继( 后继) 。 我们考虑c 上满足( 2 ) 且使得d g ( x ，剪) 达到最小的两个点z ，夥则对任意g 中最短 的( z y ) 路p ，p 内部无c _ h 的点( 因为否则，将有c 上满足( 2 ) 的另两个点x l ，y l 且 d g ( x l ，y 1 ) 如x ，) ) 设已是以z 为根的广探树则它包含一个缸一秒) 路p ，并且两 个圈p u z 虿可和p u z 巧妙中任意一个是满足( 1 ) 且比c 更短的单侧圈( 凶为否则其中 之一可以写成两个更短的圈的和，而这两个圈中有一个是双侧的) 在这个结构下， 由引理1 尸uz 刁y 年4 p u z 虿y 中的每一个都是以z 为根的广探树的基本圈这样就完 成了引理2 的证明 现在我们来处理满足( 1 ) 的圈首先，容易验证以下两个引理，所以我们略去证 弓理3 设c 是i - i 一嵌入图g 的满足( 1 ) 的最短一双侧圈则对任意c 的满足 嘶m = 嘶m = 【学j ， 的三个点z ，钍，t ，任意最短0 一u ) 路p 和z 苓口无内部公共点 弓理4 对一个满足引理3 中条件的最短双侧鼹c 以及以z 为根的广探w r x 中 的( z u ) 路p 1 与 一口) 路尼的最后一个公共点n 佛之为分支捌，x - v 1 1 , 1 ( = z 磊q ) 内 寿莎无z 苓u ( z 苔u ) 上的点 4 华东师范大学硕士论文 嵌入图中的短圈问题及相关问题 以下结果将完成定理a 的( n ) 部分的证明 引理5 设g 及c 如定理a 中定义，c 是g 中满足以) 的一个最短一双例阁贝犯包含一 个g 的最艇l 一双侧圈 引理5 的证明 情形1i c i = 2 n ，佗n 设z 和可是c 上满足d 6 ( $ ，y ) = d a ( x ，y ) = 几的两个点，已是以z 为根且所有边 的指派a = + 1 的，“探树则已包含一条一秒) 路p ，一条( z 一可一) 路p 1 ，以及一 条扛一矿) 路p 2 则可以看到( 耖，一) ，( y ，耖+ ) 中至少一条边不包含在死中 子情形1 1p 1cp 或易cp 若a ( ，y + ) = + 1 ，则只u 易u ( y ，矿) 包含一个c 1 中最短一双侧圈因此，不 失一般性，我们假设p 1cp 且入( 耖，y + ) = 一1 ( 因为( 秒，y + ) ge ( b ) ) 若p 不包含 在c 中，则pnc = x l ，z 2 ，z m 】，其中z = z 1 ，y = x r n 由引理3 ，我们可以选 择最小的指标i 使得g = x i p x i + 1uz i - d x 件1 是一个偶一单侧圈且p 在x i c 兢+ 1 上 无不同于x i 和x i + l 的内部点因为| a i i c l ，g 不能写成两个更短圈的和因 此，戗满足( 1 ) ，并且由引理l ，g 是以g 的一个点为根的广探树的基本圈现 在gu ( 见u p u ( 耖，矿) ) ) 包含一个岛中的最短一双侧圈 若pcc ，则尼不可能包含在c 中( 因为c 是一双侧的) 由之前的理由，存在一条 路c 的巧孑+ 1 且岛= 每巧+ 1 u 巧最4 - - 即+ 1 是基本圈，因此岛u ( 恳u p u ( 耖，暑，+ ) ) ) 包含一个已中的最短一双侧圈 子情形1 2 只zp 且尼茌p 若a ( 耖，y 一) = + 1 或入( 可，矿) = + 1 ，则p 1upu ( y ，耖一) 或而upu ( y ，y + ) 将包含 一个最短一双侧圈假设入( 剪，y ) = 入( ，y + ) = 一1 则p 1 up 2 u ( 秽，y 一) ，( 妙，矿) ) 也 会包含一个g 的最短双侧圈 情形2 i c i = 2 n + 1 ，n n 5 华东师范大学硕士论文嵌入图中的短圈问题及相关问题 现在边( 夕，y + ) ge ( 已) 设x ，y c 且幻( z ，y ) = d c ( z ，y + ) = 礼，b 是以z 为根 且所有边的指派入= + 1 的广探树则边( 可，+ ) ge ( 乃) 且( 由之前的理由) 我们可 以假设a ( 可，y + ) = 一1 现在瓦包含一条( z 一秒) 路p 1 ，一条( z 一+ ) 路恳以及一个分 支点q p 1np 2 显然p l 和岛中至少有一条不包含在c o o ( 因为否则c 将是g 的一 个单侧圈) 假设p 1 不是c 的一部分，则由我们在情形1 中所示，存在一个指标i 使 得q = 婉c 7 x i + 1 u 觋p 1 1 x i + 1 是基本圈，并且因此g up 1 u 尼u ( 可，矿) ) 包含一个c 2 中 的最短双侧圈这样就完成了引理5 的证明，并且因此，完成了定理a 的( a ) 部分的 证明 由定n a 的( a ) 部分的证明过程，可得定理a 的( b ) 部分和( c ) 部分的证明 由上面的陈述，定理a 证毕 6 华东师范大学硕士论文嵌入图中的短圈问题及相关问题 第二章m 5 b i u s 梯子图的1 因子数和边染色数 2 1 引言 本部分的所有图都是有限简单图( 无环和重边) 所有的术语都是标准的且都 如b o n d y 的书【l 】上定义 t u t t e1 一因子定理证明了一个无割边的3 _ 正则图一定有一个1 一因了( 或者某些 学者称之为完美匹配) 然而这样的图中有多少个1 因子呢? 在这个i 或l o v a s z i 和p l u m m e r 猜想这样的图有指数多个1 - 因子【l p 】到目前为止，这个猜想挑战了图论 界的每一个人并且关于这个猜想已有了一些重要的进展 ( 1 ) e d m o n d s ，l o v a s z 和p u u e y b l a n k 证明了在一个无割边的3 一正则图g 中至少 有1 + 卢( g ) 个1 - 因子【e l p 】，这里p ( g ) 是g 的b e t t i 数 ( 2 ) k r a l ，s e r e n ia n ds t i e b i t z 将这个界改进到量+ 2 k s s ( 3 ) v o o v h o e v e 在二部图的情形下解决了这个猜想【v 】 ( 4 ) s h r i j v e r 将上述结果推广至：u t k - 正则二部图f s 】 ( 5 ) 最近m c h u d n o v s k y u p s e y m o u r 对平面3 - 正则图证明了这个猜想【c s 】 在本文中，我们考虑m 6 b i u s 梯：子m c ( 2 m ，m ) ( 可由一个2 m - 圈c = ( 1 ，2 ，3 ，2 m ) 添加弦( ，i + m ) ，1 i m 得到) 最使我们惊讶的是c ( 2 m ，m ) 的1 因子数能由著名 的f i b o n a c c i 数列来表示即， 定理1 记 砂为m s b i u s 梯子图口( 2 m ，m ) ( 仇2 ) 的f 一因子数则 f ( m ) + 2 f ( m 一1 ) + 2 ， m 兰l ( m o d 2 ) ， h ( m ) = i ( m ) + 2 f ( m 一1 ) ，m 三o ( m o d 2 ) 7 ( 1 ) ( 1 7 ) 华东师范大学硕士论文 嵌入图中的短圈问题及相关问题 这里 ，( m ) 是满足以下条件的死6 d 扎o c c i 数列： ff ( m ) = f ( m 一1 ) + f ( m 一2 ) ，m 3 【f ( 1 ) = f ( 2 ) = 1 推论1 m s b i u s 梯孑：n c ( 2 m ，m ) ( m 2 ) 的j 因子数是： ( 2 ) ( 2 7 ) 、ff ( m ) + 2 f ( m 1 ) + 2 ， m 兰l ( m o d 2 ) ， ( 3 ) h ( m ) = lf ( m ) + 2 f ( m 一1 ) ， m 三o ( m o d 2 ) ( 3 7 ) 这旦肋) = 击 ( 学) m 一( 学) ) ( m 2 ) 这个n ：果不i n t - ( 1 ) ( 5 ) ，因为m s b i u s 梯子图c ( 2 m ，m ) 可以是非二部的和非平面 的另外，我们研究t m s b i u s 梯子图c ( 2 m ，m ) 的边染色数( 即这类图的l 一因子分解 数) ，并且证明t m s b i u s 梯子图c ( 2 m ，m ) 的( 正常) 边染色数也有指数多个更精确地 说，我们得到以下结果： 定理2 m s b i u s 梯子 蜃1 c ( 2 m ，m ) ( 亿2 ) 的征别边染色数是 盯( 佗) ：f2 ( 2 n 一：一( 一1 ) n 一1 ) + 6 ， n 兰1 ( m 。d 2 ) ， 【2 ( 吵一( 一1 ) n - 1 ) ，n 三o ( m o d 2 ) 8 ( 4 ) ( 4 7 ) 华东师范大学硕士论文嵌入图中的短圈问题及相关问题 2 2 主要结果的证明 本节，我们将证明定理1 和2 我们首先考虑定理l 的有效性 定理1 的证明设m s b i u s 梯子图c ( 2 仇，仇) 的顶点依次为 x l ，x 2 ，z m ，x m + l ，x 2 m 容易看出对较小的自然数结果是对的所以在以后的讨论中可假设整数m 4 每一个c ( 2 m ，m ) 的l 一因子f 包含x l z m + l ，x l x 2 ，x l x 2 m j 条边之一记 ( m ) 和厶( m ) 分 别为c ( 2 m ，m ) 的包含边x l x m + l 和边x l x 2 的1 - 因子数由对称性，c ( 2 m ，m ) 的包含 边z l z 2 m 的1 一因子数也是f 2 ( m ) 因此，c ( 2 m ，m ) 的1 一因子数是 h ( m ) = ( m ) + 2 1 2 ( m ) 情形1 1 一因子包含边x l ；t m + 1 显然包含x l x m + l 的1 一因子是由c ( 2 m ，m ) 一 x l ，z m + 1 ) 的1 一因子所决定的( 如 图1 所示) ：口兰 = 口：。 图1 我们将会看- 至u a ( m - 1 ) = c ( 2 m ，m ) 一 z 1 ，z m + 1 ) 中有m 一1 条水平的边j _ 己g ( m - 1 ) 是g ( 仇一1 ) 的1 一因子数则它的1 一因子包含j , 盘x 2 x 3 或z 2 z m + 2 若一个1 一因子包含 边z 2 z m + 2 ，贝u a ( m 1 ) 一 x 2 ，z m + 2 ) = a ( m 一2 ) 有g ( m - 2 ) 个1 - 因子；若一个1 一因子包 含边x 2 x z ，则它必须包含边z m + 2 z m + 3 ，进而g ( m 一2 ) 一 z 3 ，x m + 3 = a ( m 一3 ) 有g ( m - 3 ) 个1 因子因此，我们得到 夕( m ) ) 的递推关系： 9 华东师范大学硕士论文 嵌入图中的短圈问题及相关问题 m 一1 ) = 夕( m 一2 ) + g ( m 一3 ) 1 1 = 1 2 、= 2 这将推 g ( m ) 是f i b o n a c c i 数列且 f l ( m ) = g ( m 一1 ) = f ( m ) 情形21 因了包含边x l x 2 显然c ( 2 m ，m ) 的包含z l z 2 的1 因子t t l c ( 2 m ，m ) 一 z 1 ，x 2 ( i t j l 一因子决定( 如图2 所 示) 图2 x m + l 若一个1 因子包含x l z 2 和z m + i x m ，则当m 三l ( m o d 2 ) 时，恰有一个这样的1 一因 子；当m 兰o ( m o d 2 ) 时，没有这样的1 因子同时包含边z l z 2 和z m z m + 1 若一个1 一因子 包含边x l x 2 和z m + i x m + 2 ，则 g ( m 一2 ) = c ( 2 m ，m ) 一 x l ，x 2 ，z m + l ，x m + 2 将有9 ( m 一2 ) 个1 因子由我们在情形l 中的理由，g ( m 一2 ) = f ( m 一1 ) 所以 丘c m ，= f ( m - 1 ) + 1 ：三- - 。l 。( m m 甜o d 2 2 ； 现在将 ( m ) 和丘( m ) 代入 ( m ) = f l ( m ) + ，2 ( m ) ，我们得到如下公式： 1 0 y 眇 a 0 、l，、l， ，i 华东师范大学硕士论文 嵌入图中的短圈问题及相关问题 ff ( m ) + 2 f ( m 一1 ) + 2 ，m 三l ( m o d 2 ) ， 纵m 2 t ，( m ) + 2 ，( 仇一1 ) ， m 三o ( m 。d 2 ) 这样就完成了定理1 的证明 下面我们将证明定理2 ( 7 ) ( 7 7 ) 定理2 的证明记盯( n ) 为m 曲i u s 梯予图c ( 2 n ，n ) 的( 正常) 边染色数，这里色集为 l ，2 ，3 ) 我们依然把c ( 2 n ，礼) 画在射影平面上( 如图3 所示) 记边x i x i + l = p i ，玑玑+ 1 = q i ，x i y i = n ，1 i 佗一1 ，x n y l = p n ，y n t , l 2 q n ，z 竹y n = r n 我们用7 - ( n ) 来记c ( 2 n ，扎) 的满足边r 1 是c ( r 1 ) = 1 的边染色数，这 里c ( e ) 边e 的颜色则我们有 断言1 盯( n ) = 3 下( n ) 接下来，我们将确定下( n ) 的植( 即确定满足c ( r 1 ) = 1 的边染色数) 将有两种情形 需要考虑( 即c ( p 1 ) = c ( q 1 ) 及c 1 ) c ( q 1 ) ) 情形1c ( p 1 ) = c ( q 1 ) 我们用n ) 来记c ( 2 竹，扎) 的满足c ( r 1 ) = l 和c ( p 1 ) = c ( q 1 ) 的边染色数( 用您( 仃) 来 记c ( 2 n ，n ) 的满足c ( r 1 ) = l 和c ( p 1 ) c ( 9 1 ) 的边染色数) 则c ( p 1 ) = c ( q 1 ) 2 ，3 ) 用q ( 佗) 来记g ( 2 n ，仃) 的满足c ( ，1 ) = 1 ，c ( p i ) = c ( q 1 ) = 2 的边染色数则我们得到如下 结果： 1 1 华东师范大学硕士论文 嵌入图中的短圈问题及相关问题 断言2 n ( n ) = 2 q ( n ) 现在c 0 2 ) = o 1 ，2 ，3 ，一【2 ) 且c ( r 2 ) ( 1 ，3 ，一 o ，因此c ( 9 2 ) = a 一般地， 我们有： 断言3 c ( p i ) = c ( 吼) ，1si 扎 设a n 是满足以下条件的整数列 n 1 ，a 2 ，a n ) 的集合： a l = 2 ，a i + l f 1 2 ，3 ) 一 毗) ，1 i n 一1 设上和c t n 是a 。的子集且满足 3 = 口l ，a 2 ，口n ) a n i a n = 3 】1 = o l ，a 2 ，口竹】a 竹i n t l = 1 或2 ) 以下性质表明玩几乎决定了c ( 2 咒，死) 的边染色数 断言4 c ( 2 n ，仃) 的满足c ( r 1 ) = l 和c ( p 1 ) = c ( 9 1 ) = 2 的边染色数是i b n i ( = a ( n ) ) 证明设c 是如上定义的c ( 2 n ，n ) 的边染色，则 8 1 = c ( p 1 ) = 2 ，8 n = c ( p n ) = 3 ，8 i = c 慨) ，8 8 件l ，1s is 礼一1 所以， 3 1 ，s 2 ，s 仃) 既 反之，设 s 1 ，8 2 ，s n ) 3 我们可以定义c ( 2 n ，n ) 的边染色如下： c 慨) = c ( 仍) = a i ，c ( r i ) = z 1 ，2 ，3 ) 一 a 一1 ，啦) ，( a n + l = a 1 ) 容易看出c 是c ( 2 凡，佗) 的一个正常边染色且满足 a l = c ( r , 1 ) = c ( q 1 ) = 2 ，a n = 3 = c ) = c ( ) ，c ( r 1 ) = 1 断言5 i q i = i g 一1 i + 2 i g 一2 1 ，i 玩i = l 玩一1 i + 2 i 风一2 1 2 华东师范大学硕士论文嵌入图中的短圈问题及相关问题 证明设 a l ，a 2 ，n 七一1 ，a k b k 贝u o 南= 3 n a k 一1 l ，2 ) 所以，i b k i = l c k 一1 1 设 0 1 ，a 2 ，a k 一1 ，a , d c k 贝0 口知 1 ，2 h a k 一1 1 ，2 ，3 ) 一 n 七) 若口k 一1 = 3 ，则c k 中有2 l b 七一1 1 个子列；若a k 1 l ，2 ) 一 口j c ) ，则c k 中有l c k 一1 1 个子 列，因此，i 仉i = 2 i 玩一1 i - t - i 瓯一1 1 将l b k i = i 瓯一1 1 代入l g l = 2 i 玩一1 i - i - i g 一1 1 ，结 果成立 由断言5 中的递推关系，我们得到如下结论： 玩i = 丢( 2 n - - xm ( - 1 ) 州) ( 扎2 ) 7 1 ( 佗) = 2 1 出) 1 = 2 1 b i = ；( 2 n - 1 _ ( _ 1 ) 俨1 ) 情形2 c ( p 1 ) c ( 9 1 ) 在本假设下，当佗兰l ( m o d 2 ) l t c i ，c ( 2 n ，佗) 恰有2 个边染色；当佗兰o ( m o d 2 ) 时， c ( 2 n ，n ) 没有正常边染色 基于以上分析。我们得到 帖3 一( 2 n - 1 - ( - 1 ) n - 1 ) ，+ 2 ，= n = - - l ( m o d 2 2 l ) ； i 2 9 删i ： l t l c ( 2 n ，礼) 的正常边染色数是 忡2 ( 、2 n - i _ ( 、- - i ) n - 1 ) + 6 - 礼n 三- - - - 岬l ( m o d 2 ) ) ； 1 3 ( 8 ) ( 8 ) ( 9 ) ( 9 7 ) 华东师范大学硕士论文嵌入图中的短圈问题及相关问题 参考文献 j a b o n d ya n du s r m u r t 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 ，m a c m i l l a n ， l o n d o n ，( 1 9 7 8 ) b m o h a ra n dc t h o m a s s e n ，g r a p h so ns u r f a c e st h ej o h n sh o p k i n su n i v e r - s i t yp r e s s ，b a l t i m o r ea n dl o n d o n ，2 0 0 1 c t h o m a s s e n ，e m b e d d i n g so fg r 印l l sw i t hn os h o r tn o n c o n t r a c t i b l ec y c l e s ，z 盯c o m b i n t h e o r y ，s e tb4 8 ( 1 9 9 0 ) ，p p l 5 5 - 1 7 7 d o u g l a sb w e s t ，i n t r o d u c t i o nt og r a p ht h e o r y 【m 】c h i n am a c h i n ep r e s s ， 2 0 0 4 t u t t ew t t h ef a c t o r i z a t i o no fl i n e a rg r a 】) l l s j l o n d m a t h s o c 2 2 ：1 0 7 - 1 1 1 ， 1 9 4 7 m c h u d n o v s k ya n dp s e y m o u r p r e f e c tm a t c h i n gi np l a n a rc u b i cg r a p h ， p r e p r i n t 【k s s 】d k r a l ，j s s e r e n ia n dm s t i e b i t z ，an e wl o w e rb o u n do nt h en u m b e ro f p e r f e c tm a t c h i n gi nc u b i cg r a p h 【p 】j p e t e r s o n ，d i et h e o r i ed e rr e g u l a r e ng r a p h a c t am a t h 1 5 ( 1 ) ：1 9 3 - 2 2 0 ，1 8 9 1 f e l p 】j e d m o n d s ，l 1 0 v a s za n dw r p u l l e y b l a n k b r i c kd e c o m p o s i t i o n sa n dt h e m a t c h i n go fg r a p h s c o m b i n a t o r i c a ，2 ( 3 ) ：2 4 7 2 7 4 ，1 9 8 2 【l 】 l 1 0 v a s zm a t c h i n gs t r u c t u r ea n dt h em a t c h i n gl a t t i c e j c o m b i n t h e o r ys e t b ，4 3 ( 2 ) ：1 8 7 - 2 2 2 ，1 9 8 7 d n a d d e f r a n ko fm a x i m u mm a t c h i n gi nag r a p h m a t h p r o g r a m m i n g ， 2 2 ( 1 ) ：5 2 7 0 ，1 9 8 2 a s c h r i j v e r c o u n t i n g1 - f a v t o r si nr e g u l a rb i p a r t i t eg r a p h s j c o m b i n t h e o r y s e r b ，7 2 ( 1 ) ：1 2 2 - 1 3 5 ，1 9 9 8 m v o o r h o e v e al o w e rb o u n df o rt h ep e r m a n e n t so fc e r t a i n ( o ，1 ) - m a t r i c e s n e d e r l a k a d w e t e n s c h i n d a g m a t h ，4 1 ( 1 ) ：8 3 8 6 ，1 9 7 9 【l p 】 l 1 0 v a s za n dm d p l u m m e r ，s o m er e c e n tr e s u l t so ng r a p hm a t c h i n g ，g r a p h t h e o r ya n di t sa p p l i c a t i o n se a s ta n dw e s t ：p r o c e e d i n g so ft h ef i r s tc h i n a - u s ai n t e r n a t i o n a lg r a p ht h e o r yc o n f e r e n c e ，a n n a l so ft h en e wy o r k a c a d e m yo fs c i e n c e s ，5 7 6 ( 1 9 8 9 ) 3 8 9 - 3 9 5 【s e 0 1 】p d s e y m o u r ，o ni n c o m p a r a b l ec o l l e c t i o n so fs e t s ，m a t h e m a t i c a2 0 ( 1 9 7 3 ) ， 2 0 8 2 0 9 1 4 吲 同 心 陋 华东师范人学硕士论文嵌入图中的短圈问题及相关问题 【s e 0 2 jp d s e y m o u r ，an o t eo nac o m b i n a t o r i a lp r o b l e mo fe r d o sa n dh a j n a l ， j l o n d o nm a t h s o c ( 2 ) ，8 ( 1 9 7 4 ) ，6 8 1 6 8 2 【s e 0 3 】p d s