（运筹学与控制论专业论文）图的最大亏格与三类图的1因子数目.pdf

m a s t e rc a n d i d a t e ：l ig a n g 2 0 11 4 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文图的最大亏格与三类图的1 因子数目，是在 ， 华东师范大学攻读硕扫博士( 请勾选) 学位期间，在导师的指导下进行的研究工作及取 j 得的研究成果除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写 过的研究成果对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并 表示谢意 、 作者签名：垒红堡牡日期：沙l f 年月1 日 华东师范大学学位论文著作权使用声明 图的最大亏格与三类图的1 一因子数目系本人在华东师范大学攻读学位期间 ， 在导师指导下完成的硕劫博士( 请勾选) 学位论文，本论文的研究成果归华东师范大学 所有本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和相 关机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版：允许学位 论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采 用影印、缩印或者其它方式合理复制学位论文 本学位论文属于( 请勾选) () 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文幸，于 年月日解密，解密后适用上述授权 ， ( v ) 2 不保密，适用上述授权 导师签名：彳丝链本人签名：缸 秒。，年占月1 日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位论 文( 需附获批的 t 百n ； ( 3 ) 如果g 3 ，gcg l 和g g 2 ( g l 和g 2 如图2 4 ) 所示，那么y j | i f ( g ) 詈+ 1 6 l 2 4 最大亏格与色数 图2 4 图的色数是图的染色理论中的一个重要变量，与图的最大亏格也有一些联系 h u a n g 【1 0 】在这方面上曾做过一些研究，并运用x u o n g 的关于最大亏格的定理得出了 一些结果这里我们用z ( g ) 表示图g 的色数并用g 。表示g 的补图 定理2 4 1 ( 1 0 1 ) 设g 是一个k 3 的七一连通图，x ( g 。) = m ，则g 的亏数f ( g ) 的上界 为： ( 1 ) k = 1 ，f ( g ) ，l ； ( 2 ) k = 2 ，手( g ) m a x m 一1 ，1 l ； ( 3 ) k = 3 ，f ( g ) m a x m 2 j 一1 ，1 1 定理2 4 2 ( 【l o 】) 存在无穷多个图g ，其中m = x ( g 。) 可以任意大，可达到定理2 4 1 中 的上界 些奎堕堇盔堂里塑墨查三堡墨三耋里塑! ：垦王墼旦 根据上面两个定理以及x u o n g 的关于最大亏格的结果 7 】，h u a n g 进一步得到了以 下结果： 定理2 4 3 ( 【l o 】) 设g 是一个k 3 的b 连通图，x ( g c ) = m ，则有如下的t m ( g ) 的下界， 并且这些下界是最好的 ( 1 ) 七：1 ，t m ( g ) 壁! 掌； ( 2 ) 七：2 , t m ( g ) f l ( g ) - m a _ x m - 一i , i ； ( 3 ) 七：3 , t m ( g ) 丝立掣掣2 上业 2 5 最大亏格与2 因子 这一部分我们主要介绍关于图的最大亏格与图的2 因子之间的联系的一些结果 图的一个2 因子是指每个分支都是圈的图的一个生成子图 定理2 5 1 ( 【3 0 】) 设g 是一个3 - 正则连通图，n = i v ( g ) i ，如果g 存在一个由三角形所 构成的2 - 因子，则有t m ( g ) = 兰+ 1 o 定理2 5 2 ( 3 0 】) 设g 是一个3 一正则连通图，n = i v ( g ) i ，如果g 存在一个由四圈所构 成的2 - 因子，则有g 是上可嵌入的，也就是说，t m ( g ) = 孑+ 1 叶 定理2 5 3 ( 【3 0 】) 设g 是一个连通图，如果对于所有的1 ，y ( g ) ，有如( v ) = 3 ( m o d4 ) ， 那么g 是上可嵌入的 2 6 最大亏格与嵌入图 这一部分主要介绍图的最大亏格嵌入的问题h u a n g 【3 1 】曾经从对偶图的角度给 出了图的上可嵌入性的必要条件h u a n g 【3 1 】的结果如下： 定理2 6 1 ( 【3 l 】) 设g 二胞腔嵌入在射影平面上如果它的对偶图g 为哈密尔顿图 则有f ( g ) l ，也就是说g 是上可嵌入的 定理2 6 2 ( 【3 i i ) 设g 二胞腔嵌入在可定向曲面上如果它的对偶图口包含一个 上的可分离圈那么f ( g ) l ，也就是说g 是上可嵌入的 面的大小是指这个面所包含边的数目2 0 0 0 年，h u a n g 和l i u 在他们的文章中对最 大亏格与面的大小之间的关系做了一些工作 3 2 并解决了n e d e l a 和s k o v i e r a 提出的 两个猜想之一，结果如下： 1 2 华东师范大学图的最大亏格与三类图的1 因子数目 定理2 6 3 ( 3 2 1 ) 设g 是一个简单图如果g 能够二胞腔嵌入在一个闭曲面上s ( 可定 向或不可定向) 使得每个面的大小都不超过7 ，则g 是上可嵌入的 一旦确定了一个图的最大亏格，剩下的只需找到怎样将一个图最大亏格嵌入的算 法1 9 8 8 年，f u r s t ，g r o s s 和m c g e o c h 6 】等人发明了一个寻找最大亏格嵌入的多项式 算法这个构造性算法是建立在x u o n g 的关于最大亏格的结果上的 我们回忆一下关于图的最大亏格的两个基本结果一个是x u o n gf 7 1 和l i u 8 】的 找最优树方法，这个方法能够有效的计算出图的最大亏格，并且也提供了找图的最大亏 格嵌入的算法另一个是n e b e s k ：定理，这个定理通常用来判断一个图是不是上可嵌入 的 x u o n g 和l i u 的方法包含两个部分：第一是找到一棵最优树t ；第二是将 ( g ) ( r ) 中的边进行划分使得 e ( g ) ( 丁) = e l ，e 2 ，e 2 ，lu 五，正，厶 ， 这里e 2 f _ 1ne 2 i o ( 1 f m ) 并且c r b s ) nc r 昕) = 0f o rl f h ( 2 i 1 ) + 3 ( 2 ) 冒 化简( 2 ) 我们可知h ( 2 n 1 ) = 5 h ( 2 n 一3 ) 一h ( 2 n 一5 ) 我们已得h ( 1 ) = 3 ，再由( 2 ) 式就有h ( 3 ) = 1 5 1 9 华东师范大学图的最大亏格与三类图的1 因子数目 故有递推式 d v 2 ，l 一1 图3 30 3 拓l h ( 2 n 一1 ) = 5 h ( 2 n 一3 ) 一h ( 2 n 一5 ) ，h ( 1 ) = 3 ，h ( 3 ) = 1 5 解线性递推式( 3 ) ，得 ( 2 n - 1 卜孚( 学) “+ 孚( 学) ” 证毕 下面来看一个例子 ( 3 ) 例2 图0 3 ，3 共有1 5 个不同1 一因子，设v ( 0 3 3 ) = o ，u l ，u 2 ，1 1 3 ，v l ，v 2 ，v 3 , w l ，w 2 ，w 3 ，则 这1 5 个不同1 因子分别为： g l2 u l v l ，o w l ，u 2 v 2 ，u 3 1 。3 ，w 2 w 3 ；m 22 o u l ，v i w i ，u 2 v 2 ，3 1 3 ，w 2 w 3 , m 32 ( u l w i ，o v i ，u 2 v 2 ，u 3 v 3 ，w 2 w 3 ；m 42 u l u 2 ，v i v 2 ，u 3 1 3 ，o w l ，w 2 w 3 , m 52 u l v i ，o w l ，u 2 w 2 ，u 3 w 3 ，1 1 2 1 ：3 ； m e2 o u l ，v i w i ，, 2 w 2 ，u 3 w 3 ，v 2 v 3 ) ； m 72 o v i ，u l w i ，u 2 w 2 ，u 3 w 3 ，v 2 v 3 ；m s2 0 1 , 1 ，u l u 2 ，w i w 2 ，u 3 w 3 ，v 2 v 3 ； m 92 o w l ，n i l , 1 ，u 2 v 3 ，v 2 均，w 2 w 3 ；m i o2 o u l ，v i w i ，u 2 u 3 ，v 2 v 3 ，w 2 w 3 ； m 1 15 o v i ，u l w i ，u 2 - 3 ，1 ：2 1 ：3 ，w 2 w 3 ； m 1 2 = o w l ，h 1 1 ，l ，u 2 u 3 ，v 2 w 3 ，v 3 w 3 ； m 1 32 o u l ，1 , i w l ，u 2 u 3 ，1 2 w 2 ，v 3 w a ；m i 42 o v i ，u l w i ，2 3 ，v 2 w 2 ，v 3 w 3 ； m 1 52 o u l ，v 1 i 2 ，w i w 2 ，u 3 u 3 ，v 3 w 3 ； 华东师范大学图的最大亏格与三类图的1 因子数目 3 4 总结 在上述三个定理的结果中可以看到，对于一些特殊的图，我们可根据其自身的一些 性质去求它们的1 因子数目，比如对称性并且还可以看出，上述三个定理的结果与斐 波那契数列的通项公式相似，说明图的l 一因子计数是有一定组合性质的问题另外对 于上述三个图，当，l 趋于无穷大时，l 一因子数目是指数多个并也是趋于无穷大的，这也 说明了l o v a s z 和p l u m m e t 的猜想在这三类图上是成立的 2 1 参考文献 1 】n o r d h a ue ，s t e w a r tb ，w h i t ea o nt h em a x i m u mg e n u so fag r a p h j jc o m - b i nt h e o r yb ，1 9 7 1 ，11 ：2 5 8 2 6 7 【2 】b o n d yj aa n dm u r t yus r g r a p ht h e o r yw i t ha p p l i c a t i o n m n e wy o r k ： m a c m i l l i a n ，1 9 7 6 3 】g r o s s 几a n dt u c k e rt w t o p o l o g i c a lg r a p ht h e o r y m n e wy o r k ：w i l e y - i n t e r s c i e n c e ，19 8 7 4 】d u k er a t h eg e n u s ，r e g i o n a ln u m b e r , a n db e t t in u m b e ro fag r a p h j c a n a d j m a t h ，1 9 6 6 ，1 8 ：81 7 8 2 2 【5 】t h o m a s s e nc t h eg r a p hg e n u sp r o b l e mi sn p - c o m p l e t e j j a l g o r i t h m s ，1 9 8 9 ， 1 0 ：5 6 8 5 7 6 【6 】6 f u r s tm ，g r o s s 儿，m c g e o c hl a f i n d i n gam a x i m u mg e n u sg r a p hi m b e d - d i n g j j a s s o c c o m p u t m a c h ，1 9 8 8 ，3 5 ：5 0 7 5 3 7 【7 】x u o n gn h h o wt od e t e r m i n et h em a x i m u mg e n u so fag r a p h j jc o m b i nt h e o r y b ，1 9 7 9 ，2 6 ：2 1 7 2 2 5 【8 】l i uy p t h em x i m u m o r i e n t a b l eg e n u so fa g r a p h o s c i e n t i as i n i c a l ，s p e c i a li s s u eo n m a t h i i ，1 9 7 9 ，4 1 - 5 5 【9 】n e b e s k ? l an e wc h a r a c t e r i z a t i o no ft h em a x i m u mo fg r a p h s j c z e c h o s l o v a k m a t h j ，1 9 8 1 ，3 1 ( 1 0 6 ) ：6 0 4 6 1 3 【1 0 】h u a n gy q ，m a x i m u mg e n u sa n dc h r o m a t i cn u m b e ro fg r a p h s j d i s c r e t em a t h ， 2 0 0 3 ，2 7 1 ：11 7 1 2 7 2 2 华东师范大学图的最大亏格与三类图的1 一因子数目 【l l 】k u n d us b o u n d so nn u m b e ro f d i s j o i n ts p a n n i n gt r e e s j j c o m b i n t h e o r yb ，1 9 7 4 ， 1 7 ：1 9 9 2 0 3 【1 2 】x u o n gn h u p e m b e d d a b l eg r a p ha n dr e l a t e dt o p i c s j j c o m b t h e o r y , s e r b ， 19 7 9 ，2 6 ：2 2 6 2 3 2 【1 3 】c h e nj ，k a n c h is p , g r o s s 几at i g h tl o w e rb o u n do nt h em a x i m u mg e n u so fa s i m p l eg r a p h j d i s c r e t em a t h ，1 9 9 6 ，1 5 6 ：8 3 1 0 2 【1 4 】k a n c h is pa n dc h e n j at i g h tl o w e rb o u n do nt h em a x i m u m g e n u so fa 2 - c o n n e c t e d s i m p l eg r a p h 0 m a n u s c r i p t ，1 9 9 2 【15 】c h e nj ，a r c h d e a c o nd ，g r o s s 几m a x i m u mg e n u sa n dc o n n e c t i v i t y 【j 】d i s c r e t em a t h ，1 9 9 6 ，1 4 9 ：1 9 2 9 【16 】a r c h d e a c o nd ，c h e nj ，h u a n gy q ，k a n c h is p , l id ，l i uy p , n e d e l a ra n ds k o v i e r am m a x i m u mg e n u s ，c o n n e c t i v i t y , a n dn e b e s k p st h e o r e m j t o a p p e a ri nd i s c r e t em a t h 【17 】h u a n gy q t h em a x i m u mg e n u so na3 - v e r t e x c o n n e c t e dg r a p h j g r a p h sa n d c o m b i n a t o r i c s ，2 0 0 0 ，16 ：15 9 16 4 【1 8 】c h e ny ca n dl i uy p an o t eo nt h el o w e rb o u n df o rt h em a x i m u mg e n u s j u t i l i m a t h ，2 0 0 7 ，7 3 ：2 3 - 31 【1 9 】n e b e s k i ? l e v e r yc o n n e c t e d ，l o c a l l yc o n n e c t e dg r a p hi su p e m b e d d a b l e j j g r a p h t h e o r y , 1 9 8 1 5 ：2 0 5 2 0 7 【2 0 】h u a n gy q d i s s e r t a t i o no fp h d 【j 】n o r t h e r nj i a o t o n gu n i v e r s i t y , 1 9 9 5 【2 1 】c h e ny ca n d l i uy p u p - e m b e d d a b i l i yo fag r a p hb yo r d e ra n dg i r t h j g r a p h sa n d c o m b i n a t o r i c s ，2 0 0 7 ，2 3 ( 5 ) ：5 2 1 5 2 7 【2 2 】s k o v i e r am t h em a x i m u mg e n u so f d i a m e t e rt w o j d i s c r e t em a t h ，1 9 9 1 ，8 7 ：1 7 5 一 1 8 0 【2 3 】f uh a n dt a s im t h em a x i m u mg e n u so fd i a m e t e rt h r e eg r a p h s j a u s t r a l a s i a nj c o m b i n ，1 9 9 6 ，1 4 ：1 8 7 1 9 7 华东师范大学图的最大亏格与三类图的1 因子数目 【2 4 】h u a n gy qa n dl i uy p o nt h em a x i m u mg e n u so fg r a p h sw i t hd i a m e t e rt h r e e j d i s c r e t em a t h ，1 9 9 9 ，1 9 4 ：1 3 9 1 4 9 【2 5 】h u a n gy qa n dl i uy p t h em a x i m u mg e n u so fg r a p h sw i t hd i a m e t e rf o u r j a c t a m a t h s c i ，2 0 0 1 ，2 1 a ( 3 ) ：3 4 9 - 3 5 4 ( i nc h i n e s e ) 【2 6 】h u a n gy q m a x i m u mg e n u sa n dg i r t ho fg r a p h s j d i s c r e t em a t h ，1 9 9 9 ，1 9 4 ：2 5 3 2 5 9 【2 7 】c h e ny ca n dl i uy p m a x i m u mg e n u s ，百r t ha n dm a x i m u mn o n a d j a c e n te d g es e t j a r sc o m b i n ，2 0 0 6 ，7 9 ：1 4 5 - 15 9 【2 8 】o u y a n gz d ，t a n gl ，h u a n gy q u p p e re m b e d d a b i l i t y , e d g ei n d e p e n d e n c en u m - b e ra n dg i r t h j s c i e n c ei nc h i n as e r i e sa ：m a t h e m a t i c s ，2 0 0 9 ，5 2 ：19 3 9 - 19 4 6 【2 9 】h u a n gy qa n dl i uy p m a x i m u mg e n u sa n dm a x i m u mn o n s e p a r a f i n gi n d e p e n d e n t s e to fa3 - r e g u l a rg r a p h j d i s c r e t em a t h ，1 9 9 7 ，1 7 6 ：1 4 9 - 1 5 8 【3 0 】h u a n gy qa n dl i uy p m a x i m u mg e n u sa n d2 - f a c t o r j c h i na n n o fm a t h ，1 9 9 7 ， 5 ( 18 a ) ：5 8 7 - 5 9 6 【31 】h u a n gy q m a x i m u mg e n u so f ag r a p hi nt e r m so fi t se m b e d d i n gp r o p e r t i e s ，d i s c r e t e m a t h ，2 6 2 ( 2 0 0 3 ) ，1 7 1 - 1 8 0 【3 2 】h u a n gy qa n dl i uy p f a c es i z ea n dt h em a x i m u ng e n u so fag r a p h j jc o m b i n t h e o r ys e rb ，2 0 0 0 ，8 0 ：3 5 6 3 7 0 【3 3 】r e nh ，z h a oh t l ih l f u n d a m e n t a lc y c l e sa n dg r a p he m b e d d i n g s j s c i e n c ei n c h i n as e r i e sa ：m a t h e m a t i c s ，2 0 0 9 ，5 2 ：1 9 2 0 1 9 2 6 【3 4 】m i c a l isa n dv a z i r a n lw ：a nd ( 恫i e i ) a l g o r i t h mf o rf i n d i n gm a x i m u mm a t c h i n gi ng e n e r a lg r a p h s j i n ：p r o c 2 1 s ti e e es y m p f o u n d c o m ps c i ，n e wy o r k ：a c m p r e s s ，1 9 8 0 ，1 7 - 2 7 【3 5 】g i l er o p t i m u mm a t c h i n gf o r e s ti ：s p e c i a lw e i g h t s j m a t hp r o g r a m ，1 9 8 2 ，2 2 ：l 一 1 1 华东师范大学图的最大亏格与三类图的1 一因子数目 【3 6 】s t a h ls o nt h en u m b e ro fm a x i m u mg e n u so fe m b e d d i n g so fa l m o s ta l lg r a p h s j e u r o p j o f c o m b i n ，1 9 9 1 ，1 3 ：11 9 - 1 2 6 3 7 】r i n g l eg m a pc o l o rt h e o r e m j s p r i n g e r - v e r l a g ，b e r l i n ，1 9 7 4 【3 8 】r e nh a n dg a oy b l o w e rb o u n do ft h en u m b e ro fm a x i m u mg e n u se m b e d d i n g s a n dg e n u se m b e d d i n g so fk 1 2 j + 7 j 】 3 9 】l l o v d s za n dm d p l u m m e r , m a t c h i n gt h e o r y , a n n d i s c r e t em a t h 2 9 ，n o r t h h o l l a n d ， a m s t e r d a l n ，1 9 8 6 4 0 】s t a h ls r e g i o nd i s t r i b u t i o no fs o m es m a l ld i a m e t e rg r a p h s 叨d i s c m a t h ，1 9 9 1 ，8 9 ： 2 81 - 2 9 9 41 】g o d d y nl ，b r u c er r ，s i r a nj t r i a n g u l a re m b e d d i n g so fc o m p l e t eg r a p h sf r o m g r a c e f u ll a b e l i n g so fp a t h s j jc o m b i nt h e o r ys e rb ，2 0 0 7 ，9 7 ：9 6 4 9 7 0 4 2 】a l d r e dr l e ，s i r a nj ，s i r a nm an o t eo nt h en u m b e ro fg r a c e f u ll a b e l i n g so f p a t h s j d i s c r e t em a t h ，2 0 0 3 ，2 61 ：2 7 3 0 4 3 】g g h a l ag r a p h i cm o d e lo fac l a s so fm o l e c u l e s ，i n t j m a t h e d u s c i t e c h n 0 1 4 ( 19 7 3 ) 2 3 3 2 4 0 4 4 】l p a u l i n g t h en a t u r eo fc h e m i c a lb o n d ，c o m e r u n i v p r e s s ，i t h a c a , n e wy o r k ，19 3 9 4 5 】r s w i n b o m e s h e l d r a k e ，w c h e r n d o n ，i g u t m a n ，k e k u l 垂s t r u c t u r e sa n dr e s o n a n c ee l l - e r g i e so fb e n z e n n o i dh y d r o c a r b o n s ，t e t r a h e d r o nl e t t ( 1 9 7 5 ) 7 5 5 7 5 8 4 6 】e w k a s t e l e y n g r a p ht h e o r ya n dc r y s t a lp h y s i c s ，i n ：e h a r a r y ( e d ) ，g r a p ht h e o r ya n d t h e o r e t i c a lp h y s i c s ，a c a d e m i cp r e s s ，l o n d o n ，1 9 6 7 ，p p 4 3 11 0 【4 7 】m c i u c u e n u m e r a t i o no fp e r f e c tm a t c h i n g si ng r a p h sw i t hr e f l e c t i v es y m m e t r y , j c o r n - b i n t h e o r ys e r a7 7 ( 1 9 9 7 ) 6 7 9 7 4 8 】i f i s c h e r , c h c l i t t l e ，e v e nc i r c u i t so fp r e s c r i b e dc l o c k w i s ep a r i t y , e l e c t r o j c o m b i n 1 0 ( 2 0 0 3 ) r 4 5 【4 9 】wj o c k u s c h p e r f e c tm a t h i n g sa n dp e r f e c ts q u a r e s ，j c o m b i n t h e o r ys e r a 6 7 ( 1 9 9 4 1 1 0 0 - l1 5 华东师范大学 图的最大亏格与三类图的1 一因子数目 【5 0 】b r i g h t w e l lgr ，w i n k l e r 只h a r dc ，e ta 1 a d v e n t u r e sa tt h ei n t e r f a c eo fc o m b i n a t o r i e s a n ds t a t i s t i c a lp h y s i c s i c m ，2 0 0 2 ，i i i ：6 0 5 6 2 4 【51 】z h a n ghet h ec o n n e c t i v i t yo fz t r a n s f o r m a t i o ng r a p h so fp e r f e c tm a t c h i n g so fp o l y o m i n o e s d i s c r e t em a t h e m a t i c s ，1 9 9 6 ( 1 5 8 ) ：2 5 7 - 2 7 2 5 2 】z h a n ghez h a n gf j p e r f e c tm a t c h i n g so fp o l y o m i n og r a p h s g r a p h sa n dc o m b i n a - t o r i c s ，1 9 9 7 ( 1 3 ) ：2 5 9 - 3 0 4 5 3 】z h a n gl i a n z h u t h ee n u m e r a t i o no fp e r f e c tm a t