（基础数学专业论文）若干图类交叉数的研究.pdf

摘要 图的交叉数问题，起源于二战期间p u a lt u r i n 在砖厂碰到的一个 实际难题，逐渐发展成为图论学科中非常活跃的一个分支，吸引着国 内外许多学者的关注然而，确定一般图的交叉数是一个n p - 完全问 题，因此，到目前为止有关交叉数的结果比较少，仅限于一些特殊简单 图的交叉数甚至在许多情况下，试图找出图的交叉数的一个好的上 界或下界也很困难本文运用组合方法和归纳思想以及反证法，确定 了一些特殊图类，如广义p e t e r s e n 图p ( 3 k ，七) ，循环图c ( 3 七一1 ； 1 ，七 ) ， r ，两个特殊的六阶图与星& 的笛卡尔积图，星图与路r 、 星图岛与圈g 的联图的交叉数的精确值或者其上、下界，并试图研 究交叉数的一般性质，从画法上着手得到了一个好画法为最优画法的 充分条件全文由9 个章节组成 第一章较为详细地交代了交叉数的起源，研究工作的理论与实际 意义，以及目前交叉数研究在国内外的发展动态同时还简要介绍了 本文的主要结构 。 第二章介绍了阅读本文所要用到的图的交叉数方面的基本概念和 预备知识 第三章得到了当k 4 时，广义p e t e r s e n 图p ( 3 k ，k ) 的交叉数为后 第四章讨论了当七3 时，循环图c ( 3 后一1 ； 1 ，七) ) 交叉数的上界和 下界 第五章确定了对任意的仇3 和n 1 ，轮与路r 的笛卡尔 积图的交叉数 第六章对两个特殊的六阶图与星晶的笛卡尔积图的交叉数进行 了研究 第七章讨论了当仇= 3 ，4 ，5 时，星与路r 的联图的交叉数，和 当m = 3 ，4 时，星与圈g 的联图的交叉数 第八章研究图的交叉数的一般性质，并从画法上着手得到了一个 好画法为最优画法的充分条件 第九章给出了本文的总结和对未来工作的展望 关键词：图；画法；交叉数；广义p e t e r s e n 图；循环图；笛卡尔积 图；联图 a bs t r a c t t h ec r o s s i n gn u m b e ro fg r a p h sc o m e sf r o mt h ep u a lr i l r 五n sb r i c kf a c t o r y p r o b l e md u r i n gt h ew o r l dw a ri i ，a n di tb e c o m e s av e r ya c t i v eb r a n c hi ng r a p h t h e o r y , m a n ya u t h o r sh a v es t u d i e dt h i sa r e a h o w e v e r ，d e t e r m i n i n gt h ec r o s s i n g n u m b e ro fg r a p h si sn p c o m p l e t e b e c a u s eo fi t sd i f f i c u l t y , t h e r ea l eo n l yv e r y s c a r c es p e c i a lc l a s s e so fg r a p h sw h o s ec r o s s i n gn u m b e r sa r ed e t e r m i n e d e v e ni n s o m ec a s e s ，i ti sv e r yd i f f i c u l tt of i n dt h eu p p e ro rl o w e rb o u n d so ft h ec r o s s i n g n u m b e ro fg r 印h 8 i nt h i sp a p e r ，w es t u d yt h ec r o s s i n gn u m b e ro fs o m es p e c i a l g r a p h s ，s u c ha st h eg e n e r a l i z e dp e t e r s e ng r a p hp ( 3 k ，七) ，t h ec i r c u l a n tg r a p h c ( 3 七一1 ； 1 ，q ) ，t h ec a r t e s i a np r o d u c to f & w i t h t w os p e c i a l6 - v e r t e xg r a p h s ， r ，vr ，v g ，e t c t h ep a p e ri sc o n s i s to f 9c h a p t e r s ： i nc h a p t e ro n e ，w ei n t r o d u c et h eo r i g i n sa n db a c k g r o u n d so ft h ec r o s s i n g n u m b e r ，i t st h e o r i c a la n dp r a c t i c a lm e a n i n g s ，a n di t sd e v e l o p m e n ta r o u n dt h e w o r l d c h a p t e rt w og i v e ss o m ec o n c e p t i o n sa n dp r o p e r t i e so ft h ec r o s s i n gn u m b e r ， a n di n t r o d u c e st h er e q u i r e dk n o w l e d g ef o rr e a d i n gt h i sp a p e r c h a p t e rt h r e ed e t e r m i n e st h a tt h ec r o s s i n gn u m b e ro ft h eg e n e r a l i z e dp c - t e r s e ng r a p hp ( 3 k ，k ) i skf o ra r b i t r a r yk 4 c h a p t e rf o u rs t u d i e st h eu p p e ra n dl o w e rb o u n d so ft h ec r o s s i n gn u m b e r o ft h ec i r c u l a n tg r a p hc ( 3 k 一1 ； 1 ，尼) ) f o rk 3 c h a p t e rf i v ei n v e s t i g a t e st h ec r o s s i n gn u m b e ro fc a r t e s i a np r o d u c to ft h e w h e e l w i t hp a t hr f o rm 3a n dn 之1 i nc h a p t e rs i x ，t h ec r o s s i n gn u m b e r so ft h ec a r t e s i a np r o d u c to f & w i t h t w os p e c i a l6 - v e r t e xg r a p h sa r ed e t e r m i n e d c h a p t e rs e v e ns t u d i e st h ec r o s s i n gn u m b e r so f & vr f o rm = 3 ，4 ，5a n d f o ra l ln ，a n dt h ec r o s s i n gn u m b e r so f vg f o r 仇= 3 ，4a n df o ra l ln c h a p t e re i g h ti n v e s t i g a t e st h eg e n e r a lp r o p e r t yo ft h ec r o s s i n gn u m b e ro f g r a p h s ，a n dp r e s e n t sas u f f i c i e n tc o n d i t i o nt oe n f o r c eag o o dd r a w i n gt o b e o p t i m a l i i i i nt h el a s tc h a p t e r ，w em a k es o m ec o n c l u s i o n so fo u rr e s e a r c hw o r ka n d p u tf o r w a r ds o m er e l a t i v ep r o b l e m sw h i c hw ew i l lg oa h e a d k e yw o r d s ：g r a p h ；d r a w i n g ；c r o s s i n gn u m b e r ；t h eg e n e r a l i z e dp e t e r s e n g r a p h ；c i r c u l a n tg r a p h ；c a r t e s i a np r o d u c t ；j o i ng r a p h i v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果除文中已经注明引用的内容外，本论文不含任何其它个人 或集体已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明本人完全意识到本声明的法律结果由本人承 担 学位论文作者签名：王i ； i 冲产月；日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅本人授权湖南师范大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印，缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 1 、保密口，在 年解密后适用本授权书 2 ，不保密d ( 请在以上相应方框内打) 作者签名：王f ；2 0 导师签名：凌乞牡 日期：功、芦月3 日 日期：知仟月弓日 若干图类交叉数的研究 1 1 研究背景介绍 1 绪论 图论起源于哥尼斯堡七桥问题，经过近三个世纪的发展演变，图论 已经成为现代数学中一个非常重要的学科而研究图的交叉数问题， 是图论学科中一个活跃的分支，吸引着国内外许多学者的广泛关注 图的交叉数问题，通俗地讲，是研究怎样把一个图画在平面( 或曲 面) 上，使得边与边产生交叉的数目最少在( ( j o u r n a lo fg r a p ht h e o r y 的创刊里，p u a lt u r c i n ( 1 2 7 描述了他于1 9 4 4 年在b u d a p e s t 附近的一个 砖厂所碰到的实际难题： w ew o r k e dn e a rb u d a p e s t ，i nab r i c kf a c t o r y t h e r ew e r es o m ek i l n sw h e r e t h eb r i c k sw e r em a d ea n ds o m eo p e ns t o r a g ey a r d sw h e r et h eb r i c k sw e r es t o r e d a l lt h ek i l n sw e r ec o n n e c t e db yr a i lw i t ha l lt h es t o r a g ey a r d s t h eb r i c k sw e r e c a r r i e do ns m a l lw h e e l e dt r u c k st ot h es t o r a g ey a r d s a l lw eh a dt od ow a st o p u tt h eb r i c k so nt h et r u c k sa tt h ek i h l s ，p u s ht h e t r u c k st ot h es t o r a g ey a r d s ， a n du n l o a dt h e mt h e r e w eh a dar e a s o n a b l ep i e c er a t ef o rt h et r u c k s ，a n dt h e w o r ki t s e l fw a sn o td i f f i c u l t ；t h et r o u b l ew a so n l ya tt h ec r o s s i n g s t h et r u c k s g e n e r a l l yj u m p e dt h er a i l st h e r e ，a n dt h eb r i c k sf e l lo u to ft h e m ；i ns h o r tt h i s c a u s e dal o to ft r o u b l ea n dl o s so ft i m ew h i c hw a sp r e c i o u st oa l lo fu s w ew e r e a l ls w e a t i n ga n dc u r s i n ga ts u c ho c c a s i o n s ，it o o ；b u tn o l e n sv o l e u st h ei d e a o c c u r r e dt om et h a tt h i sl o s so ft i m ec o u l dh a v eb e e nm i n i m i z e di ft h en u m b e r o fc r o s s i n g so ft h er a i l sh a db e e nm i n i m i z e d b u tw h a ti st h em i n i m u mn u m b e r o fc r o s s i n g s ? ir e a l i z e da f t e rs e v e r a ld a y st h a tt h ea c t u a ls i t u a t i o nc o u l dh a v e b e e ni m p r o v e d b u tt h ee x a c ts o l u t i o no ft h eg e n e r a lp r o b l e mw i t hmk i l n sa n d t ls t o r a g ey a r d ss e e m e dt ob ev e r yd i f f i c u l ta n da g a i nip o s t p o n e dm ys t u d yo f i tt ot i m e sw h e nm yf e a r sf o rm yf a m i l yw o u l de n d ( b u tt h ep r o b l e mo c c u r r e d t om ea g a i nn o te a r l i e rt h a n1 9 5 2 ，a tm yf i r s tv i s i tt op o l a n dw h e r eim e e t z a r a n k i e w i c z im e n t i o n e dt oh i mm y “b r i c k - f a c t o r y - p r o b l e m ”) 从上述描述我们可以得到，把m 个砖窑和n 个仓库都看成“顶点”， 把拖拉机看成“边”，p u a lt u r s n 的砖厂难题实际上是研究怎样把完全 1 湖南师范大学2 0 0 9 届博士学位论文 二部图。画在平面上使得边与边产生交叉的数目最少p u a lt u r 6 n 的砖厂难题是研究图的交叉数问题的起源简单的讲，图g 的交叉数， 盯( g ) ，是把g 画在平面上边与边产生交叉数目的最小值例如，图1 1 给出了完全二部图蚝4 的两种画法，根据图1 1 右边的画法，我们可以 很容易地得出凹( k 3 ，4 ) 2 已经知道，c r ( g a ，4 ) = 2 对于凹( 娲，4 ) 2 这 种反向的不等式的验证，就是图的交叉数的主要研究内容之一 图1 1 k a 4 的两种画法 研究图的交叉数，有着很强的现实意义： 超大规模集成电路v l s i 中的圈布局问题【1 1 ，1 7 ，1 8 ，7 6 】； 草图的识别与重画问题，使之具有比手写汉字识别应用更为广泛 的应用领域； 工业上电子线路板设计中的布线问题； 生物工程d n a 的图示； 软件开发过程中文档部分的实体联系图等的自动生成； 在几何学、堆垒数论与测度论等理论中的应用 研究图的交叉数是一项有意义且富有挑战性的工作多年来，国 内外许多学者都从事过图的交叉数这一问题的研究，见文献【2 l ，3 1 ，1 2 4 ， 1 2 8 但是到目前为止，还没有有效的算法能确定任意图的交叉数事 实上，g a r e y 和j o h n s o n 已经证明了确定一个图的交叉数是n p - 完全问 题【2 7 】正是由于其难度，国内外在这方面的研究进展缓慢，研究对象 若干图类交叉数的研究 也主要集中在一些具有特殊结构图的交叉数的具体数值或者研究其 上界、下界，和研究图的交叉数的一般性质上具体来讲，主要分为以 下几个部分 一、一些具有特殊结构图类的交叉数 j 完全图 g u y 在 3 2 】中猜想完全图的交叉数c r ( 珞) 为 z ( n ) = 搁【- 字儿字儿字j 对任意实数z ，例表示不超过z 的最大整数 将完全图的顶点映射到同构于单位球的圆柱体的顶部和底部 的圆盘面上，在顶部和底部的圆盘面上的点相连形成两个分别同构于 确鲁l 和所鲁1 的完全图( 对任意实数z ，x l 表示不小于z 的最小整数) ， 在顶部和底部的点之间，用圆柱体上最短的螺旋状路将相应的点连接 起来，就得到了完全图的一个画法，见f 1 0 4 ，并且在此画法下的交 叉数为z ( n ) ，所以很容易有c r ( 玩) z ( n ) 另一方面，k l e r k 等【6 2 】得到 l i m 号裂0 8 3 ，文献【6 3 】证明了0 8 5 9 4 z o o c r ( ) r 所以一般地， n _ 么 nj 。 我们有 0 8 5 9 4 z ( n ) c r ( ) z ( n ) g u y 3 2 】证明了当n 1 0 时，c r ( 虬) = z ( n ) ，并且当n = 4 ，5 ，6 ，7 ，8 时，确定了以的最优画法的个数分别为1 ，1 ，1 ，5 ，3 s h e n g j u np a n 和 r b r u c er i c h t e r 【1 2 2 得到了一l 与珞的交叉数之间的关系： c r ( ) f 禹c r ( 一t ) 1 并在此基础上，运用算法确定了完全图尬。和噩。的交叉数分别为1 0 0 和1 5 0 ，同时还得到了完全图硒和硒。的最优画法的个数分别为3 0 8 0 和5 6 7 9 2 完全二部图 我们知道，p t u r s n 的砖厂难题事实上等价于确定完全二部图，n 一3 湖南师范大学2 0 0 9 届博士学位论文 的交叉数在【1 3 9 】中，z a r a n k i e w i c z 断言他证明”了 c r ( k m 一= 吲m 【孚心【孚j ( 1 - 1 ) 我们一般把上式右边记为z ( m ，n ) ，文献【1 0 4 】中给出了完全二部图，n 达到此交叉数的画法 在1 9 6 9 年，g u y 发现z a r a n k i e w i c z 在【1 3 9 】中的证明有误后来， k l e i t m a n 在文献【6 0 】中证明了上式对于m i n m ，扎) 6 成立，并且得出 了如果c r ( k m 知一1 ) = z ( m ，2 s 一1 ) ，则能得到c r ( g m ，孙) = z ( m ，2 8 ) w o o d a u 【1 3 3 】证明了当m = 7 ，n 1 0 时上式也成立在【6 2 】中，d e k l e r k 等人得 到了当m 9 时，有 n 1 + i m c 獭r ( k m 川, n ) 一 0 8 3 当；和熙涮 o 8 3 在【6 3 】中，d e k l e r k 等人给出了完全二部图，n 的新下界：c r ( ，。) 0 8 5 9 4 z ( m ，n ) 所以，0 8 5 9 4 z ( m ，n ) c r ( ，。) z ( m ，礼) ，对于其它的情 形，到目前为止还没有任何新的进展因此确定完全二部图n 的交 又数仍然是一个公开问题，习惯上我们称式( 1 - 1 ) 为z a x a n k i e w i c z 猜想 只完全多部图 很自然地，我们可以把z a r a n k i e w i c z 猜想推广到其它的完全多部图： 完全多部图的交叉数是多少? 在【3 9 】中，h a r b o t h 给出了一般的完全多部图。，n 。，棚。的上界，特 别地，他证明了 c r ( k ，m ，n ) z ( m + 1 , n + 1 ) 一【筹ji 兰j 1 9 8 6 年，a s a n o 在【9 】中证明了完全三部图甄 3 。和鲍，3 ，。的交叉数分别 为z ( 4 ，n ) + 【芸j 和z ( 5 ，n ) + n 之后很长的一段时间内，都没有相关的 新结果出现 直到最近几年，黄元秋和赵霆雷 4 9 】运用不同于以往方法的“局部 点度修改法”证明了完全三部图k 。舢的交叉数为 c r ( 虬，4 ，n ) = z ( 5 ，n ) + 2 l 等i 若干图类交叉数的研究 2 0 0 7 年，梅汉飞和黄元秋【9 1 】合作证明了 c r ( k 1 ，s ，n ) = z ( 6 ，礼) + 4 【- 兰j 后来，黄元秋和赵霆雷 5 0 】又证明了 c r ( 鲍 4 n ) = z ( 6 ，n ) + 2 n 上述结果都是建立在z a r a n k i e w i c z 猜想对m 6 成立的事实上后 来黄元秋与赵霆雷【5 1 ，5 2 】又假设z a r a n k i e w i c z 猜想对m = 7 和m = 9 成立，得到了 c r ( k 1 ，6 n ) = z ( 7 ，佗) + 6 【三j c r ( k 1 8 n ) = z ( 9 ，n ) + 1 2 l 三j 王晶和黄元秋【1 2 9 】在假设z a r a n k i e w i c z 猜想对m = 1 1 成立的基础 上，得到了 c r ( k 1 ，l o ，竹) = z ( 1 1 ，n ) + 2 0 引 何小年 4 0 】、王晶【1 3 0 】和p t h o 4 4 】独立研究了完全三部图硒m 。 的交叉数并得到了如果z a r a n k i e w i c z 猜想对仇= 2 m + 1 成立，则 c r ( 枷) = m 2l 半堆j - j 对于其它的完全多部图，p t h o 在c 4 5 】中计算出了甄，1 l l ，珏，k 2 2 n 和虬1 ，l 2 n 的交叉数 彳笛卡尔积图 笛卡尔积图( 见定义2 1 1 ) 是一类重要的图，由于其在结构上具有 很特殊的可重复性，所以笛卡尔积图交叉数的研究一直吸引着国内外 广大学者的注意 h a r a r y 等在【3 7 】中给出了c m g 的一个画法，使得g 在此 画法下的交叉数为( m 一2 ) n ，并由此猜想 凹( c m c k ) = ( m 一2 ) 礼，( n m )( 1 - 2 ) 5 湖南师范大学2 0 0 9 届博士学位论文 这个猜想一经提出，就引起了国内外广大学者的极大关注在过去的 3 0 多年间，许多学者都从事过这个问题的研究1 9 7 3 年，h a r a x y 3 7 】等人 得到了岛xc z 的交叉数是3 ；d e a n 和r i c h t e r 【1 9 】研究了q c 4 的交 叉数为8 ；r i c h t e r 和t h o m a s s e n 【1 0 5 】确定了c 5 侥的交叉数是1 5 ；在 文献【6 】中a n d e r s o n 等人证明了c 6 c 6 的交叉数是2 4 ；6 7 岛的交叉 数在【7 】里得到了证明运用上述结论做为归纳基础，【2 ，1 0 ，6 4 ，1 0 6 ，1 0 9 】 分别证明了对任意的n ，当m = 3 ，4 ，5 ，6 ，7 时，上述猜想( 1 - 2 ) 是成立的 从交叉数的定义( 见定义2 3 ) 可以很容易得到，要确定图的交叉 数，主要在于确定其下界所以xg 交叉数的下界也是一个重要 的研究方向s m a z a r 证明了当m 3 时，g 的m 一交叉数( 见文 献【1 1 3 ) 满足 熙错= 1 n _ i m 一2 ) n 1 9 9 8 年，s h a h r o k h i 等【1 2 1 】证明了凹( g ) 竿；2 0 0 0 年，s a l l a z a r 改进了这一结果【1 1 4 1 ，得到了c r ( g ) ( m 下- 2 ) n ；s a l a z a r 【1 1 5 】和 j u a x e z 、s 8 l a z a r 【5 7 证明了在一些有限制条件的特殊画法下，g 的 交叉数至少有( m 一2 ) n ；s a l a z a r 和u g m d e 【1 1 9 】证明了对任意的0 ， 如果m 足够大，且当n m ，时，有 c r ( g ) ( 0 8 一e ) m n 2 0 0 4 年，g l e b s k y 和s a l l a z a r 【2 9 】证明了 盯( g ) = ( m 一2 ) n ，n 仇( m + 1 ) 这证明了当n 充分大时，猜想( 1 - 2 ) 是成立的，并且使得圈与圈的笛卡 尔积图交叉数的研究有了极大的进展 除了圈与圈的笛卡尔积图的交叉数，还有其它笛卡尔积图g h 的交叉数也一直吸引着人们的关注和研究，关于这方面的已有结果具 体可分为3 个方面： ( 1 ) g 和日都是阶数比较小的图k l e g 苞【6 5 研究了k 2 ，3 c a 的交叉 数这些结果通常是被用来做为确定第( 2 ) 类图的交叉数的归纳基础 6 若干图类交叉数的研究 ( 2 ) g 是阶数较小的图，而何是某一类型的图b e h a e k e 和r i n g e i s e n 在文 献【1 0 】中得到了除岛以外所有的4 - 阶图与圈g 的笛卡尔积图的交叉 数，而j e n d r o l 等人在文献【5 4 】中填补了这一空白，确定了c r ( s 3 g ) k l e 澎在文献【6 6 】中得到了所有的垂阶图g 与路r 和星图& 的笛 卡尔积图的交叉数对于5 阶图g 与路、星、圈的笛卡尔积图的交 叉数，k l e 澎在这方面做了大量的工作，【6 7 - 6 9 】确定了任意的5 - 阶图 g 与路r 的笛卡尔积图的交叉数，他也证明了一些特殊的5 _ 阶图与 圈、星图的笛卡尔积图的交叉数，见【7 0 - 7 3 对于一些特殊的昏阶图 g ，p e n g 等人研究了p e t e r s e n 图p ( 3 ，1 ) 与路r 的笛卡尔积图的交叉 数( 1 0 0 ；对于仇3 ，n 1 ，郑文萍等给出了c r ( r ) 的上界，并得到 了c r ( r ) = 1 5 n + 3 ，见文献【1 4 0 ；本文的作者( 1 3 1 】确立了完全二部 图托。4 与路r 的笛卡尔积图的交叉数文献 4 1 ，8 2 ，1 3 2 ，1 3 4 ，1 3 7 ，1 3 8 ，1 4 2 】 得到了一系列阶数较小的图与路、星图的笛卡尔积图的交叉数 ( 3 ) g 和日都是某一类型的图d b o k a l 【1 3 】运用一种完全不同于以 往所用的新方法：z i pp r o d u c t ( 见定义2 1 2 ) ，确定了对任意的仇3 和 n 1 ，有 c r ( r ) = ( n 一1 ) 引i 竿i 唐玲等【1 2 5 】和郑文萍等f 1 4 1 】运用不同的方法，各自独立的证明了 c r ( 鲍，m r ) = 2 n i 罟i i 竺i ， 仇2 ，n 1 5 循环图和广义p e t e r s e n 图 循环图c ( n ； 1 ，七) 和广义p e t e r s e n 图p ( n ，k ) 的定义分别见定义 2 8 和定义2 9 显然，收缩广义p e t e r s e n 图p ( 他，老) 中的边集 地优悼= 0 ，1 n 一1 ，得到的图即为循环图c ( n ； 1 ，七 ) ，所以确定g ( n ； 1 ，七) ) 的 交叉数与确定p ( n ，k ) 的交叉数有密不可分的联系 杨元生等研究了一些循环图的交叉数，在【1 3 5 】中，他们证明了 c r ( c ( n ； 1 ，3 ) ) ) = _ 【芸j + n 模3 ，( n 8 ) 在【7 7 】中，他们给出了c ( m k ； 1 ，后) ) 交叉数的上界，并证明 c r ( c ( 3 k ； 1 ，七) ) ) = 七，( k 3 ) 7 o 湖南师范大学2 0 0 9 届博士学位论文 在【7 8 】中，他们得到了当n 为8 的偶数时，c ( n ； 1 ，吲一1 ) ) 的交叉数 是n 2 ；当n 为1 3 的奇数时，有 邢 l ，【争1 ) ) ) 倦h 4 h ： f + i4 h + n = 8 h + 1 n = 8 h + 3 n = 8 h + 5 ， n = 8 h + 7 ， 马登举等【8 4 】确定了当m 3 时，循环图c ( 2 m + 2 ； 1 ，m ) ) 的交叉 数是m + 1 p t h of 4 6 】研究了循环图c ( 3 k + 1 ； l ，七 ) 的交叉数，并且证明了 c r ( c ( 3 k + 1 ； l ，七 ) ) = k + 1 ，k 3 s a l a z a r 【1 1 6 得到了对于任意的k 5 ，n k 4 ，有 ( 一昙) n + ( 4 k 2 + 1 - k 3 ) 邢( 州1 , k ( 1 一昙) 他+ ( 等+ 妻+ 1 ) 最开始研究广义p e t e r s e n 图交叉数的是e x o o ，在 2 2 】中，他得到了 当n 是大于或等于4 的偶数时，c r ( p ( n ，2 ) ) = o ；当n 是大于或等于7 的 奇数时，c r ( p ( n ，2 ) ) = 3 ；且c r ( p ( 3 ，2 ) ) = 0 和c r ( p ( 5 ，2 ”= 2 f i o r i n i 【2 5 】证 明了p ( 9 ，3 ) 的交叉数为2 ，他断言确定了p ( 1 0 ，3 ) 的交叉数是4 ，并且 ( h 4 ) + 1 ，3 ) ) h + l ( h 3 ) = h + 2 ( h 2 ) 1 9 9 2 年，m c q u i l l a n 和r i c h t e r 【8 9 】发现f i o r i n i 关于p ( 1 0 ，3 ) 交叉数的 证明有错误，他们证明了p ( 1 0 ，3 ) 的交叉数至少是5 2 0 0 2 年，r i c h t e r 和s a l a z a r 【1 0 7 】发现f i o r i n i 在【2 5 】中的证明所用的方法存在漏洞，用 盯( p ( 1 0 ，3 ) ) = 6 ，c r ( p ( 1 1 ，3 ) ) = 5 ，a r ( p ( 1 2 ，3 ) ) = 4 做为归纳基础，他们得 8 一 卜 即 捌 ” 0 2 弗 盯 + 鼽 人i 鼽 以 c ? 以 ，- 、 ，f 凹 凹 ，l-rl-j、ljili_l 若干图类交叉数的研究 到了 3 ，3 ) ) = h( h 4 ) 3 + 1 ，3 ) ) = h + 3 ( h 3 ) 3 i l + 2 ，3 ) ) = h + 2 ( h 3 ) s a r a 乏i n 在文献【8 0 】中得到了c r ( p ( 1 0 ，4 ) ) = 4 s a l a z a r 【1 1 6 】得到了对 于任意的k 5 ，n k ，有 孤一昙) ( n 一酽) 十( 4 k 2 + l k 3 ) 即( 啪) ) ( 2 一要) 佗+ ( 等十耋+ 1 ) 其他与循环图和广义p e t e r s e n 图交叉数有关的研究结果，请参看 文献【3 6 ，7 9 ，8 l ，8 5 ，8 6 】 尻超立方体q n 超立方体q 。是指这样的图，它的顶点是0 和1 组成的有序n 元 组，两个顶点相连当且仅当他们恰有一个坐标不同从定义我们可以 看出超立方体图骗有2 ，1 个顶点，n 2 舻- 条边 由于随着佗的增大，超立方体q 。结构变得非常复杂，所以目前这 方面有关研究的结果也甚少因为q 。是平面图，因此显然有c r ( q 3 ) = o ；， 由于q 4 同构于q c 4 ，所以c r ( q 4 ) = c r ( a c 4 ) = 8 ( 见( 1 9 】) h a r a r y 在 文献【3 8 】指出，对于n 取其它数值时，甚至连q n 交叉数的猜想都很难 给出1 9 7 0 年，e g g l e t o n 和g u y 2 0 】称找到q 。的一种画法，使得当n 3 时，有 嘲n ) 鑫4 n 一【掣p 2 1 9 7 1 年，g u yf 3 3 发现文献【2 0 】中的构造存在问题，然而e r d o s 和g u y 【2 1 】 仍然猜想上式中等号成立m a d e j 在【8 7 】中给出q n 的一个画法，使q n 在其下的交叉数为 妻4n一舻2棚一32州+森10 ( 一2 ) n 4 芍 s y k o r a 等【1 2 3 】证明了 c r ( q n ) 熹4 ”一o ( n 2 2 “) 。 9 一 湖南师范大学2 0 0 9 届博士学位论文 f a r i a 和f i g u e i r e d o 2 3 将m a d e j 给出的上界改进到 嵩4 n 一( 2 n 2 1 1 n + 3 4 ) 2 卜3 在【2 4 】中，f a r i a 等给出了q n 的一个好画法( 见定义2 5 ) ，使得q n 在其 下的交叉数为刍4 n l - 竺芋j 2 铲2 7 联图 与上述图类交叉数的研究相比，有关联图交叉数方面的研究结果 较少，目前仅有文献【9 3 】得到了c 3vc 6 的交叉数，以及文献【1 2 6 研究 了p mvr ，尸mvg 和vg 的交叉数 & 其它曲面上特殊图类的交叉数 1 9 6 8 年，g u y 等人【3 4 】开始研究完全图在胎面上的交叉数，r i s k i n f 1 1 0 】得到了完全图娲在亏格为2 的曲面上的交叉数为4 ( 曲面亏格的 定义见【3 0 】) g u y 和j e n k y n s 较早从事完全二部图在其它曲面上交叉 数的研究，在【3 5 】中他们证明了蚝，n 在胎面上的交叉数为【掣j ， 1 9 9 6 年，r i c h t e r 和船毓将这一方面的结果进一步推广【1 0 8 ，得到了 k 3 ，n 在欧拉示性数为e 的曲面上的交叉数为【石j n 一 + 1 ) ( 1 + 【石j ) 2 0 0 5 年，p t h o 【4 7 】得到了k 4 ，n 在射影平面上的交叉数， 随后，p t h o 4 8 】和吕胜祥等【8 3 】各自独立证明了甄。n 在胎面上的交 叉数为三f 2 n 一4 ( 1 + 兰) 1 r i s k i n 1 1 l 】得到了当m = 3 ，4 ，5 ，6 时，g 在k l e i n 瓶上的交叉数分别为t ，2 ，4 和6 其它有关的结果请参看文 献【2 8 ，5 8 ，1 1 2 二、交叉数的下界 对任意的简单图g = ( y ( g ) ，e ( g ) ) ，= i v ( c ) l ，e = i e ( c ) i 目前很 多学者也致力研究于用图的点数和边数e 来确定一般图交叉数的 下界 e u l e r 公式告诉我们，对任意的平面图有3 v 一6 ，因此，我们可以 马上得出c r ( g ) 一3 v + 6 1 9 7 3 年，e r d o s 和g u y 分别猜想当较大时，存在一个正数c 使得： c r ( a ) c e 3 沪a j t a i 等【4 】和l e i g h t o n 7 6 】分别独立证明了当e 4 v 时， 若干图类交叉数的研究 有c 击p a c h 等在文献【9 4 】中证明了当e 1 5 v 2 时，c 丢随 后，p a c h 等人在【9 5 】中证明了当e 1 0 3 v 1 6 时，有c = 苷矗其它与 此相关的文献请参看【2 6 ，9 2 ，9 6 】 三、与一些参数相关的交叉数性质 直接确定某个图的交叉数是很困难的，所以人们也常常会依据图 的某些参数来研究图的交叉数的性质 f 临界交叉数 如果c r ( g ) 七，而y e e ( g ) ，有c r ( g e ) k ，则称g 是如交叉临 界图令触= g l g 是k - 交叉临界图) 陆毓在文献【5 6 】中证明了当k 3 时，存在无穷多3 - 连通临界 图，且其交叉数为k ，在文末，他猜想当k = 2 时，没有交叉数为2 的 无穷多的3 - 连通临界图k o c h o l 在【8 8 】中构造了一个反例从而否定 了前述猜想r i c h t e r 和t h o m a s s e n 在【1 0 3 中证明了如果g 鲰，则 c r ( g ) 2 5 k + 1 6 ，同时，他们得到了若触有无穷多的r - 正则简单图， 则r = 4 或r = 5 ，并给出了一个r = 4 ，k = 3 的例子s a l a z a r 在f 1 1 7 - 中将【1 0 3 1 的结果改进到文g ) 2 k + 3 5 ，他在【1 1 8 】中构造了无穷多 的k 交叉临界图，并且其平均度q 可以是区间 4 ，6 ) 中的任意实数， p i n o n t o a n 和r i c h t e r 在【1 0 1 】中将平均度q 从【4 ，6 ) 推广到( 3 5 ，6 ) 在文 献【4 2 】中，h l i n 芭n y 证明了若g 纵，则存在与k 有关的函数，( 七) ，使得 g 的路宽( p a t h - w i d t h ) 最多为，( n 2 正则图的交叉数 正则图交叉数的研究是一个比较热门的方向r i c h t e r 证明了一个 交叉数2 的3 正则图含有交叉数为2 的子图【1 0 2 m c q u i l l a n 、r i c h t e r 【9 0 】和m n 百n 矽【4 3 】也都对3 正则图的交叉数进行了研究杨元生等 【1 3 6 】利用计算机编程，给出了阶数1 2 的所有四正则图的交叉数 & 图与其线图的交叉数 图g 的线图l ( g ) 是指顶点集为e ( g ) 的图，其中两个顶点相连的 当且仅当它们在g 中为相邻的边因为图g 的线图l ( g ) 包含一个 子图同胚( 见定义2 1 5 ) 于图g ，见文献【5 5 】，所以一般地有：c r ( g ) 湖南师范大学2 0 0 9 届博士学位论文 c r ( l ( g ) ) 1 9 6 2 年，s e d l 毛s e k 在文献【1 2 0 】中得到平面图g 的线图l ( g ) 是平面 图的充分必要条件1 9 7 9 年，k u u i ，a k k a 和b e i n e k e 【7 5 】获得了平面图的 线图的交叉数为1 的充分必要条件；1 9 9 7 年，a k k a ，j e n d r o ，k l 战等研 究了平面图的线图的交叉数为2 的情形【5 】对其它情形的研究一直没 有进展1 9 9 9 年j e n d r o 讲1 k l e 誊5 证明了图g 和其线图i ( a ) 的交叉数都 是1 的充分必要条件【5 5 1 ，2 0 0 1 年，j e n d r o i 和k l e 琵【5 5 】确定了非平面图 的线图的交叉数为1 的充分必要条件，2 0 0 5 年黄元秋和赵霆雷给出了 图及其线图的交叉数都是k 的充分必要条件【5 3 】 四、其它类型的交叉数 i 直线交叉数 图g 的直线交叉数，万( g ) ，是指在g 的每条边都是直线的画法下 边与边产生交叉数目的最小值根据交叉数和直线交叉数的定义，显 然有c r ( g ) 万( g ) 文献 1 2 】给出了一些图，其交叉数是4 ，但其直线 交叉数可以任意大所以，图g 的交叉数与直线交叉数是两个不同的 概念 文章【1 5 】确定了完全图虬。的直线