（运筹学与控制论专业论文）循环图的交叉数.pdf

摘要 本文主要研究几类特殊图的交叉数问题一个图g 是平面图当且仅当它的交叉数 为0 因此交叉数是图的一个很重要的拓扑性质图的交叉数问题是图论研究领域中的 一个重要方面相对于其它较为成熟的图的研究理论而言，图的交叉数的研究显得 不是特别系统至于其原因，主要在两个方面：一方面是确定一个图的交叉数是很困难 的就这类问题的复杂度而言，g a r e y 和j o h n s o n 在文献 3 6 】中证明了确定任意一个图的 交叉数问题是n p 完备的另一方面是人们在研究这类问题时，往往很大程度上依赖于 研究对象自身的特殊性结构，故很多方法并不能推广到一般性情形，这样导致了这方 面的研究，很难形成系统性的方法 本文基于众多的图的交叉数的研究结果，对这方面的研究和进展作了一次整合， 集中关注循环图的交叉数，并得到了一些结果，具体有如下： ( 1 ) 循环图c ( 3 ，l ，1 ) 的交叉数为m ( ，l 3 ) ( 2 ) 循环图c ( 1 6 ，4 ) 的交叉数为8 关键词：完全图，笛卡尔乘积图，循环图，交叉数，h a r n j l t o n 圈，画法。 a b s t r a c t t h i sp a p e rm a i n l ys t u d i e st h ec r o s s i n gn u m b e ro fs e v e r a ls p e c i a lg r a p h s ag r a p hi s p l a n ei fa n do n l yi fi t sc r o s s i n gn u m b e ri s z e r o s ot l l ec r o s s i n gn u n l b e ri sa ni m p o n a n t t o p o l o g i c a lp r o p e r t yo fag r a p h h o w e v e r c o m p a r e dw i mo t h e rg r a p hm e o r i e s ，l es t u d yo n c r o s s i n gn u m b e rh a sb e e nm u c hl e s ss y s t e m a t i c a l t 1 1 e r ea r et w om a i nr e a s 叽sf b rt l l i s ：o n e i st 1 1 a ti ti sv e 叫d i 币c u l tt 0d e t e 肌i n em ec r o s s i n gn u m b e ro fag e n e r a lg r a p h i n 【3 6 ，g a r e y a 1 1 dj o h n s o nh a v ep r o v e dt 1 1 a ti ti sn p - h a r dt 0d e t e n 】1 i n e 山ec r o s s i n gn u m b e rf o ra na r b i t r 哪 铲a p h t h eo 山e rr e a l s o ni st h a tw er e l ym u c h o nm es p e c i a ls t m c t u r e so ft t l eg r 印h sw h e nw e s t u d ym e m w h i c hm a l si th a r dt og e n e r a l i z e b a l s e do nm a l l yr e s u l t so nc r o s s i n gn u i l l _ b e r ，w ef b c u so n 山ec r o s s i n gn u m b e ro fat y p e o fc i r c u l a rg r a p h sa n do b t a i n 山ef o u o w i n gr e s u l t s ： ( 1 ) t h ec m s s i n gn u m b e ro fc ( 3 m ，肌) i s ，z ( ，l 3 ) ( 2 ) t h ec r o s s i n gn u m b e ro fc ( 1 6 ，4 ) i s8 k e yw o r d s ：c o m p l e t eg r a p h s ，c 矾e s i a np r o d u c tg r a p h s ，c 沁u l a rg r a p h s ，c r o s s i n gn u m b e r d r a w i n g 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成果。 据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写 过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说 明并表示谢意。 作者签名： 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留学 位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文 的内容编入有关数据库进行检索。有权将学位论文的标题和摘要汇编出版。保密的 学位论文在解密后适用本规定。 学位论文作者签名：型鳌攀 日期：超重! 苎：芝里 导师签名 日期：塑：圭：i2 ： 第一章绪论帚一早三百下匕 图论是组合数学的一个主要组成部分近几十年里，它已经发展成数学的一个重要 分支由于图论的本身魅力和其在信息社会中一些科学领域诸如计算机，运筹学，系统 工程以及物理学，电子学，生物学，化学等方面的广泛应用，它正越来越受到科学界尤其 是数学界的重视和关注由于与组合数学、代数学、拓扑学以及概率方法的结合，现代 图论除了传统的研究领域外，还发展了包括代数图论，拓扑图论以及随机图论等分 支在内的多个新的领域拓扑图伦作为它的一个重要领域，更是一个非常活跃的研究 方向，它极大丰富了拓扑学和图论本身的研究同时，图论也迅速带动了其他学科的 飞跃和一些困难问题的解决，例如计算机理论研究的成熟与完善，有限单群分类问 题的解决，以及生物d n a 遗传结构的逐步破译等等 1 1 基本概念 一个图g 是指一个有序三元组( y ( g ) ，e ( g ) ，妒( g ) ) ，其中y ( g ) 是非空顶点集，y ( g ) = 【l ，1 屹，1 ，。l ，y ( g ) = m 称为图g 的阶数；e ( g ) 为边集，e ( g ) = 旧，p 2 ，已。 ，s ( g ) = 吲称为图g 的边数。妒( g ) 是关联函数，它使g 的每条边对应于g 的无序项点对如 果妒g ( e ) = h v e ，则称顶点“与v 相邻接，记做“v ；否则称为不相邻，记做“币v 。 若“和v 是边已的两个端点( 记做p = “v = ( h ，v ) ) ，则称h ( 或v ) 与已关联。与l ，关联的边数称 为，的度( 次) ，记做如g g ( d = 如( 力。图g 中最大，最小的度数分别记做( g ) 和6 ( g ) 。 称图日为图g 的一个子图，如果y ( 王，) y ( g ) ，e ( 乒d e ( g ) ，并且蛐是上的限 制g 的生成子图是指满足y ( 印= y ( g ) 的子图日设矿是y 的一个非空子集，以y 为顶 点集，以两个端点均在y 中的边的全体为边集所组成的子图，称为g 的由导出的子 图，计为g 【矿】 如果一个图能画在平面上，使得它的边仅在端点相交，则称这个图为平面图 第一章绪论 2 两个图g 和h 称为是同构的，如果存在两个一一映射p ：y ( g ) _ y ( 日) ，和妒： e ( g ) _ e ( 忉，使得妒g ( p ) = m 1 ，当且仅当仲( 妒( p ) ) = p ( m ) p ( d ；这样的一个映射对( 口，妒) 称 为g 和日之间的一个同构对于两个简单图g 和h ，它们同构当且仅当存在一个一一映 射8 ：y ( g ) - y ( z ，) ，使得“ ，e ( g ) 当且仅当臼( “) 口( v ) e ( 日) g 的一条途径r 通道j 是指一个有限非空序列w = v o 已l v l p 2 耽鲰魄，它的项交替 地为节点和边，使得对1 f 七，巳的端点是y “和u ；其中和分别称为w 的起点和 终点，而y l v 2 ，y l 称为w 的内部节点整数j i = 称为w 的长若途径的边p l ，e 2 ，鲰互 不相同，则w 称为迹称一条途径是是闭的，如果它的起点和终点相同若一条闭 迹的起点和内部顶点互不相同，则它称为困。一个图的最小的圈的长称为这个 图的围长若途径w 的边p 1 ，p 2 ，吼互不相同，则称w 为路包含g 的每个顶点的路称 为g 的h a i t l i l t o m 路：类似的，g 的h a 耐l t o m 圈是指包含g 的每个顶点的圈 图g 的两个顶点“和y 称为连通的，如果g 中存在从“到l ，的路连通是顶点集y ( g ) 上 的一个等价关系于是存在y ( g ) 的一个分类，把y ( g ) 分成非空子集，班，使得 两个顶点砧和l ，是连通的当且仅当它们属于同一个子集，子图g 【】，g 【场】，g k 】称 为g 的连通分支若g 只有一个分支，则称g 是连通的；否则，称g 是不连通的 循环图c ( ，l ，m ) 是一钟简单图，它的节点集为 咖，l ，l ，h l ，边集为( 【， ，f + l l ， i y i ，v j + 。li f - o ，1 ，n 一1 ) 这里加法是在模，l 的意义下，且2 m 【扎 c = ( ，v l ，一1 ) 称为循环图的主圈，记为g 两个图g 和日的笛卡尔乘积图g 日表示的是这样的一个图： 点集y ( g 印= y ( g ) y ( 奶 边集e ( g 日) = i ( 地，v 从，魄) ：地= 蝴和u 仇e ( 印或者w = 收和啦e ( g ) ； h f ，朋 y ( g ) ，巧，垤y ( f ，) ) 曲面是一个紧的连通的2 维闭流形，可分为可定向曲面与不可定向曲面一个可定 向曲面s ( j f l o ) 是由一个球面添上j 1 1 个环柄得到不可定向曲面m ( 七1 ) 是由一个球面 挖掉| i ：个圆盘而分别补上胸易协5 带得到其中，s o 称为球面，s l 称为环面，l 称为射影平 面，2 称为克莱因瓶 如果一个图画在曲面s 上使得它的边仅仅在端点处相交，则称这个图嵌入到曲 第一章绪论 3 面s 上图g 嵌入曲面s 上称为2 胞腔嵌入，如果s g 中每个分支均同胚于一个开圆盘 此时，称每个分支为g 在曲面s 上嵌入的一个面 一个曲面s 的e u l e r 示性凯( s ) 定义如下： r2 2 ， s = s 彳( s ) = ” 、2 一七，s = m 定理1 1 1 ( e u l e r 公式【1 8 】) 设g 是一个2 胞腔嵌入在曲面s 上的图，如果g 札个顶 点，鼋奈边，在曲面s 上，有厂含面，则，z g + 厂= 疋( s ) 设g 是一个简单图g 在平面砰上的一个画法是指存在一个浸入：g 砰使得 ( 1 ) 对任意的v y ( g ) 以及工( y ( g ) ue ( g ) ) 一y ，有驴( v ) n ( 曲= o ( 2 ) 对于g 的任意一条边已，( p ) n 是有限的 g 在平面缮上的一个画法( 简称一个平面画法) 称为是好的，如果对所有的( e ) 中的 元素满足下列要求：( 1 ) 任何一个不与自身相交，( 2 ) 任何两个相交不多于一次，( 3 ) 多于三 个的元素不会相交于平面的同一点在g 的一个好的平面画法中，矽( 日中的两个元素的 一个交点，称为一个交叉对于g 的任何一个好的平面画法，总可以计算它的所有交叉的 和，并且这些和一定有最小值g 的一个好的平面画法称为是最优的，如果它的所有交叉 的和达到了这个最小值g 的交叉数是指它的任意一个最优的平面画法的所有交叉的 和，记为c r ( g ) 一个图g 是平面图当且仅当它的交叉数为o ，因此交叉数是图的一个很重要的拓 扑性质 一般说来，确定一个图的交叉数是很困难的g a r e y 和j o l l i l s o n 在文章 3 6 】中证明了 确定任意一个图的交叉数问题是n p 一完备的 1 3 本文的主要内容和主要结论 通过各方的阅读，本文追循着交叉数的研究的历史进展，介绍了前人的一些工作，总 结了由始至今这个方面的一些研究方法，列示了几类特殊图的交叉数研究成果在此基 第一章绪论 础上，我们集中关注循环图的交叉数，并且得到以下两个结果： 定理1 3 1 循环图c ( 3 m ，m ) 的交叉数为优( m 3 ) 定理1 3 1 循环图c ( 1 6 ，4 ) 的交叉数为8 4 第二章前人工作 弟一早 剧j 八上lf 研究图的交叉数的文章大致可分为两类：一类是给出某类图的交叉数的精确值或 给出某类图的交叉数的界，包括研究完全图砀及完全二部图朋的交叉数的文章，主要 结果有c r ( ) ；【；儿譬儿譬儿丝j ，c 厂( 朋) 【；儿譬儿号儿譬j ；当n 1 2 时，的交叉数 的精确值就是上面给出的界( 见文章【3 7 】【3 8 】) ；当n ，l 中的最小值不大于6 时，朋的交叉 数的精确值就是上面给出的界( 见文章【3 9 】) ，而为，7 局，8 局，9 ，局，l o 的交叉数的精确值也是 上面给出的界( 见文章【3 7 】) 也包括有研究广义心绍r 5 p ，l 图和循环图的交叉数的文章还 包括有研究两个圈的g g 积的交叉数的文章，文章【1 1 憎猜想c 厂( c 小g ) = 一2 ) n ，这 里3 m ，l ，现在已经证明当m n ，m 6 使这个猜想成立，( 见文章 5 】【1 1 】【2 4 】【2 6 】) 另 一类用图的某个( 或某些) 参数来研究图的交叉数或交叉数的界包括有利用边数，节 点数来研究图的交叉数的界的文章这些文章中有一个重要的结果是当一个圈的边数 m 册时，其交叉数至少会是! 舌孚，这里以是节点数，z 是边数，c 是常数，见文章 4 0 】这类 文章也包括利用图的嵌入来研究图的交叉数的文章，见文章【4 1 】还有其他一些文章，这 里不一一列举 2 1 完全图的交叉数 g u y 【3 2 】猜想完全图蜀的交叉数为 z = 扣【孚j 【孚j 【字j 他证明了当n 1 0 时，这个猜想成立同时也确定，当，l = 4 ，5 ，6 ，7 ，8 时，全图的 最优画法分别有1 ，1 ，1 ，5 ，3 种图l - a ，1 _ b 分别是岛和凰的一种最优画法 5 第一章魄论 a d l b 移 图一l ( a ) d ( 凰) 和( b ) d ( 局) 6 一般而言，我们知道o 8 5 9 4 z ( ，1 ) sc r ( 局) z ( 肛) 后半个不等式，由文章【3 3 】中所列的 画法的存在而成立；前半个不等式，在文章【3 4 】中得以证明 在文章 3 l 】中，s h e n 舀u np a i l 和r b r u c e 硒c h e r 采用一些计数原理，用该计数规则证 明c ，- ( k 1 1 ) z ( 1 1 ) 特别的，他们还确定了完全图玛有3 0 8 0 种最优画法，k l o 有5 6 7 9 种最优 画法循着这条路径，他们肯定地回答了文章【3 5 】中，b r o d sk ) r ，d u r o c h e r 和g e t h n e r 所提的 公开问题当，l 1 2 时，的交叉数的精确值就是上面给出的界( 3 7 】【3 8 ) 关于完全2 一部 图 0 ，z a r a n “e w i c z 猜想它的交叉数为 c ，( = l 筹j 【孚儿兰j 【孚j 记上式右边的表达式为z 沏，n ) ，习惯上称上式为z a r a n k i e w i c z 猜想目前只是 证明了，当n ，m 中的最小值不大于6 时，瓦。的交叉数的精确值就是上面给出的 界【3 9 】，而局7 局，8 局，9 ，局1 0 的交叉数的精确值也是上面给出的界【3 7 】之后又有人 对完全3 一部图局，。一的交叉数产生兴趣显然，我们可以想象，确定一般完全3 部图冉的 交叉数，决不会比确定一般完全2 部图m 的交叉数容易到目前为止，只对，和m 取较小 值的情况进行了研究一个结果是上世纪八十年代，a s a n o 在文献【4 】中确定了完全3 部 图k 1 3 t ，l 和局3 ，| 的交叉数： c 帆3 一) = 2 【掣曲一l 争 c r ( 恐却) ：4 【半j 【掣卜3 ，l 第一章绪论 7 此后相当长的一段时间，关于完全3 一部图的交叉数一直没有新结果后来，黄元秋 确定了完全3 一部图k l 加的交叉数，又与梅汉飞合作确定了完全3 一部图k l 加的交叉数阅 读发现，蜀舢及k l 5 。的交叉数结果的得到，都利用到文献【3 9 】的结论，即当咒，m 中的最小 值不大于6 时，z a r a n b e w i c z 猜想为真之后又有人，分别假设z a r a n l ( i e w i c z 猜想对m 7 ， m 8 ，m 9 和m = 1 1 成立，用了不同的方法分别在假设成立的前提下，确定了完全3 部 图k l ，6 ，k 1 7 鼻，k l 。8 一和k l ，1 0 一的交叉数【1 8 ，1 9 ，2 0 ，2 l 】( 文献【2 0 】和【1 8 】方法类似) 名o 图- 2d ( k l 朋，a 图一3d ( 砭，m ，i ) 第一章 绪论 8 关于k l 州与砭m ，l ，目前只找到它们的一些好画法，但并未能确定其交叉数 图一2 给出了k 1 州的一个好画法，其上有【字儿考儿譬儿 j 一【考儿 j 个交叉 图一3 给出了砭州的一个好画法，其上有【竽儿警儿等儿譬一m z 个交叉 最近，又有人在完全图与路径的笛卡尔乘积图的交叉数方面做了一些结果，这将在 下一小节中展示 2 2 笛卡尔乘积图的交叉数 2 2 1 研究背景 各种图的笛卡尔乘积图的丰富形式，反映在他们的画法上，使得图的笛卡尔乘积图 成为能够确切得到图的交叉数的，为数不多的图类中的一种 而关于笛卡尔乘积图的交叉数的研究，可追溯到1 9 7 3 年，当h a r a 叮等人在文 章 1 l 】中确定了图c 3 c 3 的交叉数为3 ，并且猜想当3 研，l 时，笛卡尔乘积图c m g 的 交叉数为c ，( c m g ) = ( ，l 一2 ) ，1 2 2 2 研究成果 融n g e i s e n 和b e i n e k e 在文章 2 6 】中，证明当m = 3 时猜想成立，即c ，( c 3 g ) = n ；在 文章【5 】中，证明当m = 4 时c r ( c 4 g ) = 2 ，l ，支持h 抓q 等人在文章【1 l 】中所提的猜想成 立接着是一段空白期，在将近十五年长的时期里，这类问题的研究几乎没有令人满意的 结果 一直到上个世纪九十年代中期，k 比j 若和r i c h t e r 与s t o b e r t 各自独立地在文 章【1 9 】中，证明了当m = 5 时，c r ( c 5 g ) = 3 ，l ，猜想是成立的； 在文章【2 4 】中，r i c h t e r 与s a l a z a r 证明了当m = 6 时，c ，( c 6 g ) = 4 ，z ，猜想成立；接着， 在文章 1 伸，a d a m s s o n 与r i c h t e r 证明了当，l = 3 时，猜想成立 第一章绪论 9 以上的各位作者，在对m = 3 ，7 所作的证明中，很大程度上有赖于数学归纳 法，至于归纳法基础的情形，分别在文章 2 ，3 ，9 ，1l ，2 5 】给出： 在【2 中，m a n d e r s o n ，r b r i c h t e r 和p r o d n e y 证明c r ( 瓯c 6 ) = 2 4 ； 在 3 】中，m a n d e r s o n ，r b r i c h t e r 和pr o d n e y 又给出c ，( c 7 g ) = 3 5 ； 在【9 】中，a m d e a na n dr b r i c h t e r 给出c ，( c 4 g ) = 8 ； 在【1 l 】中，h 娥町等人确定c 厂( g c 3 ) = 3 ； 在【2 5 】中，r b 融c h t e ra n dc 1 1 1 0 m a s s e n 给出c r ( c 5 c 5 ) = 1 5 通过各方阅读和了解，就我们的知识范围所知，目前关于这个问题的最新进展，是文 章【l o 】中，g l e s b s k y 和s a l a z a r 所给的结果： 当肌3 且甩 + 1 ) 沏+ 2 ) 时，c r ( c m g ) = 沏一2 ) 厅 除了两个圈的笛卡尔乘积图外，还有其它一些笛卡尔乘积图交叉数的精确结果： 在文章【5 】中，b e i n e k e 和r i n g e i s e n 确定了除星形图s 3 = k 1 3 以外的任意4 一阶 图g ，g g 的笛卡尔乘积图的交叉数这个缺口被j e n d r o l 和s 沈而d 诟所弥补。 在文章【1 2 】中，j e n d r o l 和雪沈而d v 丘确定了s 3 g j 3 厶和s 4 p 2 的交叉数同时 他们还提出猜想：对任意的星形图，s 。= k 刀3 ，以及任何长为，l 1 的路径厶，有 c 邢。厶) ：沏一1 ) 【昙j l 掣j 二二 这个猜想又是由尉p 资在文章【1 4 中证明了其成立同时，k 跆资也确定了当m 3 时，s 4 g 的交叉数 对一般的自然数j r l ，在文章【7 】中，d b o k a l 证明了猜想成立在文章【1 8 】中，k 跆论确定 了对任何4 一阶图g ，笛卡尔乘积图g p m 和g s 。的交叉数 在文章【1 8 】中，k 彪菇确定了对任何5 阶图g ，笛卡尔乘积图g 的交叉数但是还 有一些5 一阶图g ，它们与g 或s 。的笛卡尔乘积图的交叉数仍然未确定( 见表1 ) e r 垮s i n g 翡| l m b 盯 n l e 鲡挑m 删l b 盯 q l 即p | ；印巳；g ，蛾 o ，x 靠；6 j x c 。；o j xs - 卢 ： ： 一 o o 量凸 o：o： 6 1 2 囱 2 ( 酗1 )：孙i ： ： 誊众 2 ( 瓤1 ) ：2 i - 台 n 1 ： 3 ，l： ：_ ， ：嚣，q ： ， 念 钒气 _ l ： n 2 ( n 1 ) ； 3 l l ； n ( 口l 。 5 - ：曩5 矗 产 q 么 n i ： _ 风 3 小i ： ! ，。， 0 - 。1 ； n 吼6 囟 如l i 鳓+ 潜l j ) ； 声 2 n 2 n i ： 4 i i 4 l ；i i i ，l “z 玎 仇匪 2 抽1 )i 2 l i ： 一一 n ， 声 仓 3 n i ： j q 臼 n - l ! 知 ：霸，3 害 0 ： 3 n 。- ，a 3 | 卜l i i ：瞳砷 锄囱 4 n i ； q r 2 ( 日1 ； 2 n - - 、 ：n ，5 濑 芝囱 6 | i： ：孙： 嵯j 玎 7 j 叫b !： 声 - 0 l t 自 2 陋1 ) ：n 睡1 ) 表1 文献【3 0 】中，可知r i n g e i s e n 和b e i n e k e 给出c 厂( k l ，r ) = 一1 ) 嵯儿譬j 文章【4 5 】【2 7 】，郑 文平等给出： ( 1 ) 当m 3 ，l 埘，有c 厂( r ) 【孚儿孚j 譬j 譬j + 字j ) ；c ，( 只) = 1 5 ，l + 3 ( 2 ) 当，l 3 ，m 5 时，有c r ( 孟乙岛) ，l c r ( + 2 ) ；当m = 5 ，6 ，7 ，咒任意，以及当m 8 ，l 为 大于或等于4 的偶数时，均有c r ( 靠) ：l 警儿警j 筹j 譬j 。进一步，当，l = 5 ，6 ，7 ， 第一章绪论 咒任意，以及当，l = 8 ，9 ，1 0 ，l 为大于或等于4 的偶数时，此不等式等号成立其画法可见 图一4 ，5 ，6 当m i n ( m ，n ) 2 时，有c r ( ，f r ) 一1 ) ( l 警【譬j 譬j 譬j m d + 2 ( 字【警j 譬j j 一 【墨【 j ) ，当，l 伽( m ，1 ) = 2 ，不等式等号成立可见图一7 b 图- 4 ( a ) c ，( 飓g ) = 2 7 ，( b ) 髦j f i 比和( c ) c r ( 恐g ) = 9 九( n 为奇数) b 图一5 ( a ) c ，( & g ) = 5 4 ，( b ) 磁5 f 泷和( c ) c ，_ ( 拖g ) = 1 8 以( n 为奇数) 第一章绪论 b 图- 6 ( a ) c ，( 局g ) = 1 0 8 ，( b ) 蜀盯泷和( c ) c r ( 局g ) = 3 6 ，z ( n 为奇数) 图一7d ( f 岛) 1 2 第一章绪论 1 3 除此之外，还有其他一些图的笛卡尔乘积图的交叉数未有结果【1 4 一1 7 ，1 9 】而以上各 个结果，处理方法主要依赖于这些笛卡尔乘积图自身所具有的高度对称性，并且大部 分采用以下方法：若g 的任何一个拷贝上都没有足够多的交叉数，则在画法中一定可以 找到足够多的交叉数；否则断言由归纳可得当然，笛卡尔乘积图边的技巧性分组也是常 用的 在文章 7 】中，d b o k a 建议用了另外一种分析证明的途径：没有直接从图g 着手，而是 从能通过重复构造产生图g 的小图切入；从小图的重复迭代产生图g 的一个画法于是 可通过研究小图的变动，所导致的交叉数的变化，来确定图g 的交叉数在文章【6 】中，d b o k a 采用了类似的方法，同时将画法限定在圆盘上，证明了某些图交叉的必不可少性 更早的，在文章【2 3 】中b p i n o n t o a n 和r b r i c h t e r 已经运用了类似的方法，同时将画法 限定在圆盘上，证明了序列图交叉的必不可少性在将画法限定在圆环上的同时，m j p e l s m a j e r ，m s c h a e f e r 和d t e f a n k o v i 也运用了此技巧，可见文章【2 2 】 以上关于g 日的交叉数的确切结果，可分为三种类型： 1 ) g 和日两个都是小图； 2 ) g 是一个小图，但日是无限图族中的一个； 3 ) g 一种无限图族中的一个，而日也属于无限图族，但可能是另外一种； 类型1 ) 主要用于在确定类型2 ) ，所采用的数学归纳法中的归纳基础；而关于类型 3 ) ，目前仅有的属于此类的图为厶g ，以及k l 鼻p m 之后，d b o k a l 给出了树的笛卡尔乘积图的交叉数，见文章 3 0 】 第三章循环图的交叉数 3 1 研究背景 由循环图的定义知，当，l = 2 m 时，是一个3 一正则图；其他情况下，它是一个4 一正则 的h 锄i l t o n 图，而且大多数的循环图是非平面的对循环图的研究具有很强的实际意 义例如，在r 锄s e y 定理中，有些循环图有助于确定一个r 锄s e y 数的下界 由循环图的定义还可知，c ( 3 ，2 ) = 玛，c ( 4 ，2 ) = 砀以及c ( 5 ，2 ) = 飓 当2 m 【；j 时，如果将广义p p f p r 韶n 图g ( n ，m ) 中所有的边啦，f 0 ，1 ，n l 收 缩，那么得到的图是循环图因此，在条件2 m l ；j 下，循环图是广义p p f p r j p n 图 的子式( m f 门d 厂) 一个图的子式是指对这个图经过去边、去孤立点和收缩边得 到的图反过来，通过分裂循环图c ( m ，d 的每一个节点，我们可以得到一个一 般的p p f p ，s p ，l 图g ( m ，f ) 当m 和n 互素时，所有的边i + 研i f = o ，1 ，l lj 构成一 个n 圈；当m 和，l 不互素时，所有的边( y f + 。k = 0 ，l ，l 1 ) 构成足个等长的圈，其中足是 m 和n 的最大公约数 循环图的交叉数最早由刘同映和刘彦佩研究，在文章 4 3 】中，他们给出了循环图的 交叉数的上界，并且证明了 c r ( c ( ，l ，2 ) ) ：f o n = 2 七 七2 ； 、1 ，n = 2 七+ 1 ，七2 随后，在文章【1 8 】中，郝荣霞和刘彦佩进一步改进了循环图的交叉数的上界，给出了 下面的结果： ，l 一2 厅= 打竹； c ，( c ( n ，m ) ) s 、( ，竹一2 ) f + s ( ，z j ) + s 一2 ，甩= 加+ s ( 1sj5 ，行一1 ) 1 4 第三孝循环图的交叉数1 5 文献【4 4 】中，马登举，任韩等，首先把循环图嵌入在环面上，然后还原到平面上，得出其在平 面上的画法，在某种情况下改进了上述结果 c ，( c ，d ) 砌 m = 一。) m 卸2 ，； t f + l r 一产+ m i n 一2 f + r 一1 3 f + 4 ，+ f 一5 2 _ r + f l ，挖= 缸+ 厂( 1 r z 1 ) 本章也将研究循环图的交叉数，所用的方法与文章【4 3 】和 4 4 】采用的方法不一样 对初始小图的交叉数值，主要通过分析其特殊结构来确定交叉数；对之后无限图，采用的 是数学归纳法 3 2 循环图c ( 3 m ，m ) 的交叉数 引理3 2 1 ( 【4 2 】) 循环图c ( 9 ，3 ) 的交叉数为c r ( c ( 9 ，3 ) ) = 3 用以下方法在平面上将循环图c ( 3 m ，m ) 画出：将m 个节点峋，y 一l 画在同一 列，m 个节点，+ l 一l 画在第一列的右侧同一列，1 个节点，+ l 码。一l 画在 第一列的左侧同一列；再添上c ( 3 m ，肌) 的边。此画法可见图一8 所示为了方便起见， 我们采用以下几个记号 记g = ( ，n + m ，h + 抽) 为3 一圈， = n ，n + m ，厂f + 拥 ，以及q = c fu ，其中n = y “m ， ，f + m2 + m + 2 m ，n + 2 m = 1 ，f + 2 m v “3 m ，上l f = 0 ，1 ，m 一1 假设q ，q f + l 皆为图g 的子图，对图g 的以下两个改动，在我们的证明中需用到： 改动一：将图的3 圈c j 边去掉，并收缩以的边； 改动二：将图五中的边收缩，+ m ，肌2 ，1 分别是u l ，+ l + 历，+ l + 2 ，l 的复制，再分别紧 贴并沿着边n ，r f 十m ，r j + 2 ，i 依次用边将节点连接：0 l = + l u l + m ，名l + m = y j 十l + 小u l 砌， 0 l + 加= y f + 1 + 2 ，l + 1 然后去掉3 一圈c f 和g + l 的边 1 6 设d 是图g 的一个画法，z ( d ) 表示图g 在画法d 中的交叉数d m 是图g 的一个最优画 法，满足z ( k ) = c r ( c ( 3 ，l ，小) ) c ( 3 m ，m ) 的一个最优画法 引理3 2 2 对任意的f ( f = o ，l ，m 一1 ) ，我们对循环图c ( 3 m ，m ) ，m 4 完成变动 一后，所得的图为循环图c ( 3 ( ，l 1 ) ，m 1 ) 证明：我们考虑如下定义的h a 嘶l t o n 圈c 3 m ： ( y o v 2 ，l v 2 ，l + l v l + 1 + 2 也v 抽+ 2 v 拥+ 3 1 ，3 + 3 v 3 m 一2 一2 v 加一2 v 2 ，i 一1 一l v 3 m 一1 ) ， ，l 三l ( m o d 2 ) ； ( 1 ，l v m + 1 v 2 m y 2 m + l v 2 m + 2 v 2 ，m + 2 v m + 3 v 3 v 2 m + 3 1 ，3 m 一2 v ，卜2 v 2 押一2 v 2 ，l - 1v ，竹一lv 3 肺一1 ) ，挖三o ( m o d 2 ) 而从图1 ，我们不难发现，e ( c ( 3 ，l ，m ) ) = e ( c 3 m ) 中的边亦构成一个h a m i l t o n 圈，记为 第三章循环图的交叉数 c 3 m 如下： q 小= ( v 1 v 2 v 3 一1 ，m + l v 抽+ l v m + 2 v 2 ，l + 2 + 2 如肌一3 v 加一3 ，拥一2 v 3 m 一2 v 3 舻lv 2 ，l ly 2 ，1 ) ，m 三1 ( r n o d 2 ) ； ( ，l v 2 1 ，3 一1 1 ，2 ，l v 2 ，l l y 3 卅- 1 b m 一2 v 2 m 一2 v 2 m 一3 玢用一3 v 2 ，l + 3 v 2 ，l + 2 ，m + 2 v 卅+ 1v 2 ，i + 1 ) ，l 兰o ( m o d 2 ) 1 7 故有，c ( 3 m ，1 ) = c 3 。u 3 历对某一取定的f ( f = o ，l ，m 一1 ) ，边y “m 和 1 ，j + m v “1 + m 或v i + 2 m y “l + 2 m 均是c 3 m 的边类似，v f + m 瞻2 ，l ，y f u l 和1 ，f 十2 j ，l l + 2 ，l 或u m 肌i + 坍 均是c ，3 。的边 引理3 2 3 循环图c ( 3 m ，m ) 的交叉数c ，( c ( 3 小，m ) ) m 证明：我们在平面上画循环图c ( 3 肌，m ) 如图一8 所示，并将此画法记为d 。经过简单 计数，易知画法d m 中c ( 3 小，1 ) 的交叉数为m 引理3 2 4 循环图c ( 3 m ，m ) 的交叉数c 厂( c ( 3 m ，m ) ) c 厂( c ( 3 ( m 一1 ) ，m 1 ) ) + 1 证明：设是m 是循环图c ( 3 m ，m ) 的一个好画法，我们将分两种情况对d m 做改动： 情形1 ：若存在某个f ，使得g 上有交叉对q ，在d m 进行改动一显然所得的图的最优 画法d m l 中，至少比d m 的交叉数少一个由引理3 2 1 可知所得的图是c ( 3 ( m 一1 ) ，l 一 1 ) ，并且有 c r ( c ( 3 ( m 一1 ) ，l 1 ) ) z ( d m 1 ) c r ( c ( 3 m ，m ) ) 一1 情形2 ：循环图c ( 3 m ，m ) 中所有的3 一圈g ( 江0 1 ，聊一1 ) 上均无交叉断言：五中 的边定会有一个交叉 若非如此，假设j i 上无交叉，由于g ( f = 0 ，1 ，m 1 ) 是干净的，且不存在分离 的3 一圈，对某个取定的f ，c ( 3 m ，聊) 的所有节点，除了y f ，1 ，f + m 和抽外，一定在圈c j 所分平 面的同一个区域内不失一般性，可设y ( d 小) y ( g ) 皆在g 的外部区域 又由于g + l 也是干净的，故c ( 3 m ，m ) 的所有节点，除了u l ，+ m + l 和肌2 ，l + l 外，也一定 在圈c j + l 所分平面的同一个区域内我们已经假设c l 的内部区域不含任何c ( 3 m ，m ) 一 第三章循环图的交叉数 g 的节点和边，因此y ( d 。) y ( c f + 1 ) 应在g + l 的内部区域( 如图9 所示) 图一9 c ( 3 m ，小) 的一个画法，有三个4 - 圈c ：，c 主a n dc ； 1 8 现在，由图一9 所示，平面上，d i 与c j + l 一同组成三个圈，即： c ：= ( h ， ，“l ，+ 用+ l + m ) ，q = ( n + 坍，+ m + l + 2 m + l u + 2 m ) ，c ；= ( + 2 m + l ，v “l h + m + l ，u ) ， 并且以上三个圈的边均为干净的。 考虑路径：p l = ，f + l 坼2 + 巾l + 。我们断言： ( 1 ) 路径尸l 的内部节点一定都在g ( 七= l ，2 ，3 ) 所分平面的同一区域内； ( 2 ) 路径p 1 的内部节点一定都在由c ：所分平面的内部区域中。 根据j o r d a n 曲线定理，( 1 ) 显然成立。至于( 2 ) ，若其不成立，由( 1 ) 它们应在q 或g 所 分平面的同一区域内对此进行以下分析： ( i ) 若它们在q 所分平面的内部区域，则n 埘应在q 的外部区域由j o r d a n 曲线定 理，q 定与边白+ m = l ，“m v i + m + l 交叉，与之前假设矛盾故p l 的内部节点应全部在q 所分 平面的外部区域内 对q ，我们可进行类似于q 的讨论故可得知，p l 的内部节点应全部在g 与c ；所分 平面的外部区域内 ( i i ) 注意到圈g + l 的外部区域和圈。的内部区域无公共节点由( i ) ，我们可得路 径p l 的内部节点只能都在由c ：所分平面的内部区域中即( 2 ) 成立 进一步，类似于路径p l ，有路径p 2 = + m + 1 y + 2 + 2 ，l l 耽+ 2 m 的内部节点一定都在 第三章循环图的交叉教 1 9 由c 所分平面的内部区域中 现在，节点玢+ 2 与磷枷+ 2 位子a 所分平面的不同区域内，但它们有边关联，根据j o r d a n 蓝 线定理，c ；上必有交叉但c ；是图以ug uc 0 l 的子图，并且g ，c f + l 上是干净的，则n = 砖硌l 或。= n + 掰砖攥+ 1 定被交叉所潋五上至少有一个交叉在这种情况下，我们对 画法队作改动二在画出l ，呱删+ 1 和撕十。时，无交叉产生当收缩 中的边，同时去 掉g 稻g + ，的边，所减少的交叉不会少于一个故有： c r ( c ( 3 ( ，牲一1 ) ，栉一1 ) ) z ( 扔m 一1 ) 蜒c ，( c ( 3 ，扎，牡) ) 一1 基于以上的分析，我们可得 到此引理3 2 4 得证 甜( c ( 3 ( 珑一1 ) ，脚一1 ) ) 叫a 3 m ，掰) ) 一1 引理3 2 sc ，( c ( 3 ，m ) ) 肌 证明：由引理3 2 。2 和引理3 。2 。4 ，结论显然成立。 定理a 循环图c “c ( 3 m ，m ) ) 的交叉数为m 证明：由引理3 2 。3 程引理3 1 2 5 ，直接可褥 3 3 循环图c ( 1 6 ，4 ) 的交叉数 定理b 循环图秽( e ( 1 6 ，4 ) ) 的交叉数为8 为了得到此结果，我们先要完成提出几个引理 引理3 3 1 【4 2 】循环图g = c ( 1 2 ，3 ) ，其交叉数为c k g ) = 4 引理3 3 2 循环图g = c ( 1 6 ，4 ) ，其交叉数满足c “g ) 8 第三章循环图的交叉数2 0 证明：如图一l o 所示，为循环图g = c ( 1 6 ，4 ) 的一个好画法，可知，在此画法中，交叉 数为8 即有c ，( g ) 8 图1 m 1 c ( 1 6 ，4 ) 的一个最优画法 图l m 2 c ( 1 2 ，3 ) 的一个最优画法 图一l o 用d 表示循环图c ( 1 6 ，4 ) 在平面上的一个好画法为了我们阐述的方便，我们在画 法d 中将c ( 1 6 ，4 ) 的边按以下方法染色：主圈c 4 m = ( v o ， ，l ，一1 ) 中的边染成蓝色， 剩下其他的边染成红色 对于那些红色4 一圈，我们按顺序，依次将其命名为q o ，q l ，q 2 ，q 3 故对每一 条蓝色边，其必连接q 和q f 的各一个节点，这里右下角标号f = o ，l ，2 ，3 ( 模4 ) 对f _ 1 ，2 ，3 ，4 ，用竭表示c ( 1 6 ，4 ) 中由y ( q f 1uq f ) ( f m o d4 ) 引出的诱导子图因 此日l 有8 条红色边和4 条蓝色边，每条红色边的两个端点分别在两个q f 中，每条蓝色边 端点恰都在一个q f 中 图凰的权z ( 凰) 表示飓所包含的交叉数总和，如下情形计数： ( 1 ) 图凰的一条蓝色边与图q fuq + 1 的一条红色边之间的交叉； (