（计算机应用技术专业论文）图的交叉数问题研究.pdf

大连理工大学博士学位论文 摘要 图的交叉数问题是在实际应用中提出来的，在电子线路板的设计，c a d 领域有广阔 的应用目前已经确定交叉数的图类主要集中于顶点数较小或者交叉数较小的图本文对 一些项点数较大或交叉数较大的图的交叉数问题进行研究，将计算机构造性证明和数学 证明相结合。取得了较好的结果 本课题组给出的交叉数算法c c n 已被成功地用于计算顶点数较小的图的交叉数但 由于图的交叉数问题是n p 困难问题，对顶点数较大或交叉数较大的图，所需要的计算时 间仍然太多针对这一问题，本文给出了计算图的交叉数上界的算法c c n 。把计算图的 交叉数上界问题转化为计算往其子图的较少交叉点画法中回添边时所产生的交叉数的问 题，从而可以对较大规模的图的交叉数性质进行研究利用该算法计算了顶点数ps1 2 的 所有路径幂图砖和1 3 p 2 0 且k 9 的所有曩的较好的交叉数上界 对与圈g 交图的交叉数，目前研究的较多的是两个圈的交图以及顶点数较小的图与 圈交图的交叉数r i n g e i s e n 和b e i n e k e 对玉0 口g ，m 4 进行了研究本文对 口g 进 行研究，给出了相应的交叉数计数方法，确定了这类图的交叉数下界对m = 5 ，6 ，7 或者 n 为不小于4 的偶数，给出了交叉数上界及对应的画法；如果著名的完全图交叉数猜想对 j 岛+ 2 成立，则本文给出的交叉数上界就是完全图如与圈g 交图的交叉数 对与路径b 交图的交叉数，目前研究的较多的也是顶点数较小的图与路径交图的交 叉数1 ( 1 e 强等人对口一，m 5 进行了研究b o k a l 对蜀j 口一进行了研究黄元秋 与k l e g 分别研究了w m 口只的n 3 与m = 3 ，4 的情形；l 【l e 酪对3 口r 进行了研究本 文针对口r ，k m ，口r ，w 。口r 进行了研究，给出了这些图的交叉数上界并对其中 口只，砭f 口r ，h 0 口r ，睨。口只给出了相应的交叉数计数方法，进而导出了这些图 的交叉数下界并最终确定了磁口r ，岛j 口只，矸0 口r ，w 2 j l 口 的交叉数，扩展了与 路径交图的交叉数的研究结果 本文所给出的交叉数研究方法还可以用于研究其它图的交叉数问题作为应用实例， 本文确定了两类三正则图k n t i d e l 图 。和f l o w e rs n a r k 及其相关图只的交叉数相信 该方法在图的交叉数问题研究中还有更广泛的应用 关键词：交叉数；交图；正则图；路径幂图；圈；路径；完全图；完全二部图；轮图；双锥图； k n i i d e l 图：f l o w e rs n a r k 大连理工大学博士学位论文 c r o s s i n gn u m b e r s o fc e r t a i nf a m i l i e so fg r a p h s a b s t r a c t c r o s s i n gn u m b e r so fg r a p h sa r ei ng e n e r a lv e r yd i f f i c u l tt oc o m p u t e n e e x a c tc r o s s i n g n u m b e r so fv e r yf e wf a m i l i e so fg r a p h sa r ek n o w n u s i n gc o m p u t e ra l g o r i t h mt oc o m p u t e u p p e rb o u n d s a n du s i n gm a t h m a t i c a lt e c h n i q u e st og e tl o w e rb o u n d s ，t h i s 也e s i sr e s e a r c h e so n t h ec r o s s i n gn u m b e r so fs o m eg r a p h sw i t hr e l a t i v el a r g eo r d e ro rw i t hr e l a t i v el a r g ec r o s s i n g n u m b e r t h ee x i s ta l g o r i t h mc c n p r o p o s e di n2 0 0 2c o m p u t e st h ec r o s s i n gn u m b e r so fa l lt h e g r a p h sw i t hs o m eo r d e r u n f o r t u n a t e l y , t h ec r o s s i n gn u m b e ro fag r a p hi sn pc o m p l e t e ，a n d n o tm u c hh o p ei sh e l df o re f f i c i e n f l yf i n d i n ga l lo p t i m a ld r a w i n g s - - o re v e nas i n g l eo p t i m a l d r a w i n g - f o ra l lg r a p h s a na l g o r i t h mc c n * i sp r e s e n t e di nt h et h e s i st oc o m p u t eu p p e rb o u n d s o ft h ec r o s s i n gn u m b e ro fp a t hp o w e rg r a p h s 礴l e tp 2i v ( g ) i mu p p e rb o u n d so f c r o s s i n g n u m b e r s o f 畿w h e r e p 1 2o r l 3 p s2 0 w i t h k 9 a r ec o m p u t e d b y c c n t h e nw ei n v e s t i g a t et 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 t sw i t hc y c l e sa n dp a t h s f o r t h ec a r t e s i a np r o d u c to fc y c l ea n dc o m p l e t eg r a p h ，r i n g e i s e na n db e i n e k eh a v ep r o v e dt h a t c r ( c 3 口c n ) = na n dc r ( 商口c n ) = 3 n t h e t h e s i s o b t a i n sa l o w e r b o u n d f o r 口c nu s i n g a s p e c i a lc r o s s i n gc o u n t i n gm e t h o df b r 口g ，i e c “口c n ) n c r ( k i + 2 ) f o rn 3a n d m 5 i t i s a l s o p r o v e d t h a t , c r ( k m 口c 。) s ：l 警儿盆笋儿鼍儿咛j f o r m = 5 ，6 ，7a n d f o r 阱5 w i t h e v e n n 4 ，a n d t h ee q u a l i t y h o l d s f o r t e l = 5 ，6 ，7 a n d f o r m = 8 ，9 ，1 0 w i t h e v e n n 4 t h et h e s i sa l s os t u d i e st h ec a r t e s i a np r o d u c to fp a t h 奶t l lc o m p l e t eg r a p hj ，c o m p l e t e b i p a r t i t e g r a p h 1 a n d c o n e ，r e s p e c t i v e l y as p e c i a l c r o s s i n g c o u n t i n g m e t h o d f o r t h e c a r t e s i a n p r o d u c t w i t h p a t h s i s p r e s e n t e d t o o b t a i n l o w e r b o u n d s o f c r ( k m 口r ) ，c r ( k 2 a p n ) ，c r ( w m 口p n ) a n d c r ( w 2 j ，f 口p n ) a n d t h e c r o s s i n g n u m b e r o f k 6 口r ，砭口r ，w _ 口p n a n d w 枷口p n a r e d e t e r m i n e d f i n a l l y , w eu s e t h ec o u n t i n gm e t h o d sd e v e l o p e di nt h i st h e s i st os t u d yo t h e rc r o s s i n gh u m - b e tp r o b l e m s a sa p p f i c a t i o ne x a m p l e s ，t h ec r o s s i n gn u m b e r so fk n o d e lg r a p h 也ma n df l o w e r s n a r ka n dr e l a t e dg r a p hba r ed e t e r m i n e d k e yw o r d s ：c r o s s i n gn u m b e r ；c a r t e s i a np r o d u c t ；r e g u l a r ；p a t hp o w e r ；c y c l e ；p a t h ；c o m - p l e t eg r a p h ；c o m p l e t eb i p a r t i t eg r a p h ；w h e e l ；d o u b l ec o n e ；k n 6 d e lg r a p h ；f l o w e r s n a r k i 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学或 者其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：粹日期： 卜l 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子版， 允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文 作者签名 导师签名 竺垦j 月三日 洲，年月j 日 1 0 7 大连理工大学博士学位论文 1 绪论 图论的研究对象是图，即顶点以及它们的邻接关系；而拓扑图论关注的是如何在表面 上表示图例如如果一个图可以“嵌入”到平面( 球面，柱面) 上，边与边之间没有交叉，那 么这个图就是可平面的；反之，这个图就是不可平面的 画法是一个比嵌入更为广泛的概念与图的嵌入不同的是，它允许表面上的边交叉 画法中两条边的交点称为一个交叉点画法中的交叉点数目称为这个画法的交叉数，而一 个图的所有画法中最小的交叉数称为图的交叉数图的交叉数是图的一个拓扑不变量，它 给出了图的非平面性的一个量度f 1 - 3 】 图的交叉数问题最先是从p t u r h n 砖厂问题f 4 】提出来的在砖厂的砖出炉时，工人要 通过运行在轨道上的运砖车将砖运到仓库这些车在非轨道交叉点处运行快速简单在交 叉点处。运砖车会因为等待在交叉点处发生拥堵，而且运砖车也容易出轨这导致很多麻 烦t u r k 想到如果铁轨的交叉点数日最小，那么带来的损失也就能够最小t u r h n 砖厂问 题，用术语来讲，也就是完全二部图的交叉数 1 9 5 4 年，z a r a n k i e w i c z l 4 1 给出了完全二部图j 幻的交叉数： c ，( ) = z ( m ，d = l , 2 n “r a 2 - i 叫儿号j 1 9 6 9 年，g u y f 5 】指出在z a r a n k i e w i c z 的证明中存在错误，z a r a n k i e w i c z 给出的只是完 全二部图的交叉数猜想同时，g u y 给出了关于完全图交叉数的猜想： c r ( ) ，i 佃t t m z l j a w 2 儿孚j 迄今为止，完全二部图和完全图的交叉数仍然是拓扑图论领域公开的难题 1 9 8 3 年，g a r e y 和j o h n s o n t 6 1 证明了计算任意图的交叉数是n p - 完全的2 0 0 6 年， h 1 埘面证明了计算一个简单3 连通三正则图的交叉数是n p - 完全的 7 1 n p 一完全问题 被认为是难以得到有效算法的，因此任意图的交叉数问题被认为是难以处理的，人们往往 对特定图类的交叉数问题进行研究本文将对路径幂图、交图等图类的交叉数问题进行研 究 文中所考虑的图均为无自环、无重边的简单有限无向图，其中未定义的术语请参见 h a r a r y 的( g r a p ht h e o r y ) ) i s l ，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 ) ) 【9 1 ，以及徐俊明的 图论及其应用1 1 0 1 1 i 一些符号及预备知识 为了以后章节书写方便和连贯性，本小节将引入一些必要的记号和基本结论 图的交叉数问题研究 一个无向图g 定义为一个二元组( v e ) ，记作g = ( v ) ，其中v = v ( g ) 是一个非空 有限集，称作图g 的顶点集；e = e ( g ) 是由v ( g ) 中的元素构成的无序对集合，称为无向 图g 的边集，通常简记边( “，v ) 为“v p = 烈g ) = i 矿( g ) i 表示图g 中的顶点的数目q = q ( g ) = l e ( g ) l 表示图g 中的边的 数目 对于图g = ( k ) ，如果边e = “v e ，则称边e 连接顶点u 和顶点v ；称顶点u 和v 是 相邻的：顶点u ，v 与边e 相关联，同时也称边e 与顶点u ，v 相关联若两条不同的边x 和y 与一个公共的点关联，则称x 与y 是相邻的边 关联同一个顶点的边称为自环关联同一对顶点的两条或两条以上的边称为多重边 无自环，无重边的图称为简单图仅有一个点的简单图称为平凡图 本文涉及到的图均为无向的，非平凡的简单图 图g = ( 1 i , e ) ，设v 0 ，v 1 ，v 2 ，v ，由v o ，”2 ，v ，1 v ，组成的边的序列( 简记 为v o v l v 2 v m - 1 ) 称为联结v 0 到v m 的通道如果v o = v 。，称它为闲通道若它所有的 边都不同，称为是一条迹若它所有的点都不同，称它为一条路径若路径的起点和终点相 同，称它为一个圈或回路路径( 圈) 中边的数目称为这个路径( 圈) 的长度通常用r 表 示长度为，l 的路径，g 表示长度为n 的圈 若以册y ( g ) ，( 册e ( g ) ，则称图x 为图g 的子图若y ( 奶= y ( g ) ，e ( e ( g ) ，则称图日为图g 的生成子图 假设y ，是y 的一个非空子集以矿为顶点集，以两端点均在y 7 中的边的全体为边 集所组成的子图，称为g 的由矿导出的子图，记为g v 】，称为g 的( 点) 导出子图导出 子图g v 、y 】记为g 一矿，它是从g 中删除，7 中的顶点以及与这些顶点相关联的边所 得到的子图若矿= v ，则把g 一 v 简记为g v 假设f 是的一个非空子集以e 7 为边集，以e 7 中边的端点全体为顶点集所组成的 子图称为g 的由e 导出的子图，记为g e ， 称为g 的边导出子图边导出子图g e e ，】 记为g e ，：它是从g 中删除e 7 中的边所得到的子图类似地，在g 上添加边集e 中的 所有边得到的图记为g + e 7 若e ，- p l ，则分别用g e 和g + e 来表示g 一e 和g + e 1 顶点“的邻集是图g 中所有与u 相邻的顶点的集合，记作| ( h ) ，即n ( u ) = vi u 3 2 e ( g ) 1 记n u 】_ 似 u ( “) ，称作顶点u 的闭邻集 g 的顶点v 的度d ( v ) 是指g 中与v 关联的边的数目，即d ( v ) = l ( v ) 1 如果图g 各顶 点的度相同，则称g 为正则图；如果对任意的v g ) ，有政v ) = r ，则称图g 为r - t t - 月4 图 一个图g 称为是标定的，若它的每个顶点标以不同的名称，如标以v 1 v 2 ，v ，以不 区别例如图1 1 中的两个图g l 和g 2 是标定的，而g 3 不是 若在两个图g 和h 的点集之间存在一个保持邻接性的一一对应，则称它们是同构的， 记作g 兰h 例如，图1 1 中的g i 和g 2 在对应v i 一之下是同构的可以看出，g 3 与 g i 、g 2 中的任何一个都同构同构关系是图的一个等价关系同构的图具有相同的拓扑 2 大连理工大学博士学位论文 g l 图1 1 标定图和非标定的图 f i g 1 1l a b e l e dg r a p ha n dn o n l a b e l e dg r a p h 性质 图g l 和g 2 的迪卡尔乘积图记作g i 口g 2 ，是满足以下条件所构成的图类： ( 1 ) 它的顶点集v = f ( h ，v ) l 对于任意的u g l ，v g z ，即y e h g l ) v ( g 2 ) ( 2 ) 对于任意y 中的顶点“= ( u 1 ，u 2 ) ，v = o l ，7 2 ) ；当u 1 = v l 且u 2 和v 2 在g l 中相邻 或2 = v 2 且u l 和”l 在g 2 中相邻时，- 和v 在g l 口g 2 中相邻 图g l 和g 2 的迪卡尔乘积图也称为g l 和g 2 的交图根据交图的定义可得，g l 口g 2 = g 2 口g 1 图1 2 给出了r 口岛的例子 诏”2 碹醒迓 图1 2 n 口p s f i g 1 2 4 口p 5 图g 中，若i y ( g ) l = m ，且每一对顶点间都有边相连，则称该图为完全图 完全二部图局。是满足以下条件所构成的图类： ( 1 ) 顶点分为二个集合h ，也，其中i h | - z ，l v 2 | - m ； ( 2 ) 对于任意的h ，v y 若f 工则u ，v 相邻( f ，y = 1 ，2 ) 完全三部图甄。是满足以下条件所构成的图类： ( 1 ) 顶点分为三个集合，屹，码，其中j v i i _ z ，i u i _ m ，i v 3 l = n ； 3 图的交叉数问题研究 ( 2 ) 对于任意的u v i ，v v j ，若f ，则u ，v 相邻( f ，j = 1 ，2 ，3 ) 广义p e t e r s e n 图p ( n ，助是由顶点集v ( p ( n ，七) ) 和边集e ( p ( n ，) ) 构成的具有2 n 个顶点 的图，其中顶点集v ( p ( n ，女) ) = ，v l ，v 川，吒，嵋，v ：一1 ，边集e ( e ( n ，t ) ) = 坼v ；，v f l ， 叫屹t i i = 0 ，1 ，n 一1 l ，所有顶点下标对n 取模 循环图c ( ，z ；s ) 是一个n 个顶点的图，其中，顶点集，( c ( ，l ；s ) ) = v f0 f n l ，边 集e ( c ( ，z ；s ) ) = p i v j l0 s f n l ，0 j n 一1 ，( f d m o dn s ，s ( 1 ，2 ，n 2 路径幂图t 2 1 戌是指连接路径图r 中所有距离不超过t 的顶点对所得到的图 多锥图c k + 置是由一个长度为m 的圈c 以及z 个孤立点组成的图，其中每个孤立 点都与c k 的所有点有边关联，记作m 。当f = l 时，多锥图w 1 。= c s + 面就是轮图，也 记作h ，历当f _ 2 时，多锥图w 2 。= g - t - 恐称为双锥图 k n o d e l 图f 1 3 - 1 6 1 厶。是有n ( n 为偶数) 个顶点的彳正则图( 1 a l l 0 9 2 n j ) ，满足以下 条件： ( 1 ) 顶点分为二个集合v l = v 1 ，f 2 ，h ，2 j ，v 2 = u j ，u 2 ，“。，2 ) ； ( 2 ) 对于任意的v f v l ，若j = f + 字一l ( k = 0 ，a 一1 ) ，则v “，相邻，其中f ，j 对n 2 取模 s n a r k 【1 7 1 8 是不可三着色的非平凡连通三正则图 当n 为不小于5 的奇数时，f l o w e r s n a r k 图1 1 9 , 2 0 b = ( r ) ，e ( r ) ) 被定义为锄个 顶点的简单无向图，其中，( n ) = b i l 0 琏n - 1 u c f l 0 f 2 n - 1 u a f l o s i sn 一1 1 ， 且e ( b ) = 玩反“”r o o d 。1 0 f n 一1 u e i c ( i + 1 ) r o o d2 n 1 0 s i 2 n 1 ) u f a i b i ，a i c i ，a i c n + i 1 0 s f 雄一1 1 当n = 3 或n 为不小于4 的偶数时，凡被称为f l o w e r s n a r k 的相关图 路径幂图，多锥图，k n 6 d e l 图，f l o w e rs n a r k 及其相关图的图例将在论文相关部分给 出 如果一个图可以画在一个表面s 上且任何两条边仅在端点处相交，则称它可以嵌入 在表面s 上相应的画法称为种嵌入如果一个图可以嵌入平面，则称这个图为可嵌入 平面的，或称为平面图平面图g 的这样一种画法称为g 的一个平面嵌入平面图与可嵌 入球面的图是一样的图g 可嵌入平面当且仅当它可嵌入球面 本文中考虑的表面是平面或者与平面拓扑等价的球面或者柱面 并非所有的图都可以嵌入平面如果一个图不能被嵌入到平面上，则称之为非平面图 对于一个非平面图g ，若存在它的一个生成子图日，h 是平面图且对任意一条属于g 但不 属于日的边p ，日+ p 是非平面图，则把图圩称为图g 的极大平面子图一个非平面图可 能有不止一个极大平面予图 图g 在平面上的一个画法是指把图g 在平面上的一个同胚映射，使得图g 的顶点表 示为不同的结点，图g 的边表示为连接对应顶点对的简单连续弧，并且不包含结点在不 引起歧义的情况下，方便起见，也称结点为顶点，称弧为边，直接利用抽象图的元素来指代 它们的平面表示如果画法中，两条边除结点外有公共点x ，称这两条边在x 点交叉画法 4 大连理工大学博士学位论文 ( 1 ) 消除两条边相切产生的交叉点 ( 1 ) e l i m i n a t i n gat a n g e n t i a lc r o s s i n g 。 ( 2 ) 消除一条边自交产生的交叉点 ( 2 ) e l i m i n a t i n gas e l f - i n t e r s e c t i o no fa ne d g e ( 3 ) 消除由关联于一点的两条边产生的交叉点 ( 3 ) e l i m i n a t i n gac r o s s i n go ft w oa d j a c e n te d g e s 。八。 n ( 4 ) 消除两条边产生的多于一个的交叉点 “) e l i m i n a t i n gm u l t i p l ec r o s s i n g sb e t w e e ne d g e s ( 5 ) 三条边不能交叉于一点 ( 5 ) e l i m i n a t i n gac o m m o np o i n to fm o r et h a nt w oe d g e s 图1 3 将一个画法转换为好的画法 f i g 1 3h o w t om o d i f ya d r a w i n g t ob eg o o dd r a w i n g 5 图的交叉数问题研究 中的交叉点数目称为这个画法的交叉数 一个画法是好的画法倘若它满足以下条件：( 1 ) 交叉点不是由两条边相切产生；( 2 ) 没 有边自己相交又；( 3 ) 关联于同一个结点的两条边不交叉；( 4 ) 两条边之间至多有一个交叉 点；( 5 ) 三条或三条以上的边不能交叉于一点按如图1 3 所示的方法，可以将一个画法转 化成一个好的画法而不增加画法的交叉数 画法d 的交叉数记为v ( d ) 图g 的最优画法是指图g 的所有画法中交叉数最小的 画法，最优画法的交叉数称为图g 的交叉数。记为c r ( g ) 显然，一个图的最优画法一定是 一个好的画法，因此，除非特别指明，本文所提到的画法都是好的画法 一个图g 的一个不变量是与g 有关的一个数，它对于任何一个与g 同构的图有相同 的值交叉数是衡量图的非平面性的一个不变量平面图的交叉数为0 ，非平面图的交叉 数至少为1 设删是图g 的一条边，w 不是g 的一个顶点，则当用边u w 和w 来代替聊，丽g 的 其余顶点和边不变，这个步骤称作对图g 的边u v 的剖分如果对g 进行一系列剖分，最 后得到的图口q 做g 的个剖分图图1 4 所示为局3 的两个剖分图如果g l 和g j 为同 一个图g 的剖分图，则称g 1 和g 2 是同胚的如果g 1 和g 2 为同一个图g 的剖分图，则 c r ( g 1 ) = c r ( g 2 ) = c r ( g ) 图1 4 肠j 的剖分图 f i g 1 4s u b d i v i s i o ng r a p h so f 凰3 姐 v 2 地 k u r a t o w s l u 定理? 一个图是平面图，当且仅当它不包含与为3 或艮同胚的子图 e u l e r 定理：设有一个连通的平面图g ，共有p 个顶点4 条边和，个面，则欧拉公式 p q - i - r = 2 成立 令a 占是图g 的边集e ( g ) 的子集，且anb = 0 令d 是图g 的一个好的画法，由 边集a 中的一条边和边集b 中的另一条边交叉产生的交叉点数目记为7 d ( a ，口) ；由边集 a 中的两条边交叉产生的交叉点数目记为v d ( a ) 因此，v ( d ) = v d ( e ( g ) ) 在画法d 中，如果一条边没有被其它任何边交叉，称这条边在画法d 中是干净的；如 果这条边被至少一条边交叉，则称它在画法d 中被交叉如果一个边集中所有的边都是 干净的我们称这个边集在画法d 中是干净的，否则，我们称这个边集在画法d 中是不干 净的一个交叉点由两条边相交产生，称这个交叉点与这两务边中的每条边相关联，也称 6 大连理工大学博士学位论文 这两条边中的每条边与该交叉点相关联当一个交叉点与一个边集中的边相关联时称这 个交叉点与这个边集相关联，也称这个边集与该交叉点相关联 引理1 1令a b ，c 为e ( g ) 的互不相交的子集，那么 v o ( c a u 研= v d ( c , a ) + v o ( c , b ) ， y d ( a u b ) = v d ( a ) + v o ( b ) + 场( a ，口) 由【2 1 】可得， 引理1 2 如果图g 至少删掉f 条边才能够得到平面子图，那么州g ) 2 f 引理1 3令ace ( g ) ，若在画法d 中，a 上至少存在j 个交又点，删掉a 中的所有 边得到一个新画法d ，那么v ( d ) y ( ) + 工 a r c h d e a c o n 在文献【2 2 】中定义了完全图旋转系统的概念假设j | i 乙的顶点集是厶= f 1 ，m 1 由 0 的一个画法导出的顶点k 的旋转序列p t 指的是画法d 中与k 关联的边围 绕k 按照顺时针顺序而得到与边的另一个端点对应的的循环序列可以看出，p i 与i m 一 k l 的一个循环全排列对应j 乙的所有顶点的旋转序列构成了它的旋转系统 由完全图磊幺的一个平面上的画法得到的旋转系统可以唯确定图中相交叉的边。 从而确定这个画法的交叉点数目也就是说，边 曲，甜l 在画法中交叉，当且仅当由顶点 a ，抚c ，a q 导出的旋转序列给出了导出完全图肠的一个交叉数不为o 的画法 1 2 交叉数问题的研究现状 最古老的交叉数问题t u r i n 砖厂问题至今仍然是图论中公开的难题，没有人能够给 出完全的证明，也没有人能够给出任何反例1 9 8 3 年，g a r e y 和j o h n s o n 证明确定一个图 的交叉数是n p - 困难问题 6 1 2 0 0 4 年，g r o h e 证明了】计算一个图的交叉数是f p t ( f i x e d p a r a m e t e r t r a c t a b l e ) 的2 0 0 6 年，h l i n h 夕证明计算一个简单3 一连通三正则图的交叉数 是n i p 完全的m a j t a i 等人 2 4 1 和l e i g h t o n r 2 5 】分别独立的证明了“交叉数定理”：如果图g 的顶点数v ， 边数e 4 v 那么图g 的交叉数满足不等式： c r ( g m 妄 其中，c 0 是一个绝对常数2 0 0 6 年，p a c h 等 2 6 1 证明了：( 1 ) 如果一个图存在平面上的一个 画法，在这个画法中每条边至多与其它三条边交叉，那么这个图的边数不能超过5 5 d 一2 ) ； ( 2 ) 任意v 个顶点，e 条边的图的交叉数至少为；e 一萼( v 一2 ) 其中4 v e 5 v ；( 3 ) 交叉数 定理被改进为 c r ( g ) 焘j 一1 0 6 v 7 图的交叉数问题研究 如果e 警v ，那么 1 0 2 4e 3 。7 丽否 对交叉数的研究主要分为两个方向f 1 1 ：第一个是研究一般图的交叉数性质，改进交叉 数定理另一个是对特定的图类的交叉数进行研究本文研究属于后者对特定图类的交 叉数研究，通常用构造法给出图的好的画法，从而得到交叉数上界；用数学证明图的交叉 数下界；通过上下界逼近。最终确定这类图的交叉数 在研究特定图的交叉数方面，迄今为止，只有少数图族的交叉数得到了确定尽管如 此人们对交叉数的研究仍然有浓厚的兴趣完全图，完全多部图，广义p e t e r s e n 图，循环 图，交图，正则图等图族一直都是人们关注的研究对象 1 2 1 完全图的交叉数 1 9 6 0 年，g u y r ”1 给出了著名的完全图交叉数猜想 猜想1 1 c r ( k m ) = 地儿孚儿乎儿譬j 并证明了如果猜想1 i 对m 为偶数时成立，则猜想对m 一1 也成立同时，他还证明 了猜想在m 1 0 时是成立的1 9 9 6 年，a r c h d e a c o n 在文献【2 9 中指出ms1 2 时猜想 成立 g u v 【5 1 。b l a i _ e k 和k o m a n 叫给出了满足完全图交叉数猜想的好的画法：设肌为偶数， 将完全图毛画在一个圆柱体表面( 等价于平面，球面) 上，分另将m 2 个顶点等距离的放 于上底面圆周和下底面圆周用直线连接上底面圆周的各个顶点形成蜀l 2 同样用直线连 接下底面圆周的各个顶点上底面圆周的点和下底面圆周的点之间沿圆柱表面用最短的 螺旋状曲线连接从 的上述画法中，删去任一点以及与该点关联的所有边，就可以得 到奇数时的画法 表1 1 石r j 0 ) ，m s1 2 t a b 1 1 _ ( ) f o r m s1 2 m4567891 0l l1 2 石( j 0 ) 0 1391 93 66 21 0 21 5 3 还有一些学者对完全图的直线交叉数f 3 1 1 石玟如，) 进行研究 1 9 7 3 年。e r d 6 s 和g u y l 3 2 1 给出了ns9 时完全图的直线交叉数 完全图的直线交叉数进展很慢，直到2 0 0 1 年，b r o d s k y 等人 3 3 1 币d a i c h h o l z e r 等人耻1 分 别独立给出了蜀。的交叉数 8 大连理工大学博士学位论文 2 0 0 2 年，a i c h h o l z e r 等f 3 5 】证明了万( 蜀1 ) = 1 0 2 ，石( 蜀2 ) = 1 5 3 ，并且猜想否反k 1 3 ) = 2 2 9 完全图的直线交叉数的研究结果如表1 1 所示 1 2 2 完全二部图的交叉数 交叉数的研究是从对完全二部图如f 的研究开始的例1 9 5 4 年，z a r a n k i e w i c z l 4 构 造了完全二部图，的一个好的画法，从而给出了完全二部图交叉数猜想：c r ( 0 “) = z ( m ，2 ) = 【等j 【等1 j l j l 华j ，并且证明了这个猜想在m i n m ，f 1 = 3 时成立 z a r a n k i e w i c z 给出的好的画法构造如下：将l j 个顶点放于x 轴的负轴，玛1 个顶点放 于x 轴的正轴，l 丑j 个顶点放于y 轴的负轴，r 等1 个顶点放于y 轴的正轴；然后用m 条直线 段连接工轴和y 轴的顶点 1 9 7 0 年k l e i t m a n 证明当m i n m ，f 6 时，z a r a n k i e w i c z 猜想成立 3 7 1 ，且： c “蜀“) 2m ( m 一1 ) 嘲【譬j 5 1 9 9 3 年w o o d a l l 用计算机证明了z a r a n k i e w i c z 猜想对妫7 和k 7 9 成立口8 1 ，从而使得 这个猜想在m i n m ，f 6 或m 8 且f s1 0 时成立 2 0 0 3 年n a h a s 证明【3 9 】当m ，z 足够大时， c r ( k a m ( m 1 ) 嘲咛j 5 + 9 9 x1 0 - 6 m 2 f 2 2 0 0 6 年，k l e r k 等人证明，对于给定的m 9 ， 他在该文中还证明 1 i m ，。c “ 0 j ) z ( m ，020 8 3 m ( ，7 l 一1 ) 1 2 3 完全三部图的交叉数 l i m f 。c r ( k u ) z ( d 0 8 3 目前，完全三部图的交叉数基本上都建立在已知的完全二部图交叉数的研究基础上 1 9 8 6 年，a s a n o 4 1 】证明了c “k 1 3 。) = z ( 4 ，n ) - 1 - l ：j ，c r ( g ：3 。) = z ( 5 ，n ) + ，z 2 0 0 4 - 2 0 0 6 年，黄元秋等对已知的完全偶图的交叉数进行研究，并改进了证明方法，从 而证明了【4 “5 1 在完全二部图交叉数猜想成立的前提下，以下等式成立： ( 1 ) c ，( k 1 4 m ) = z ( 5 ，1 ) + 2 l ! j ；( 2 ) c r ( k l j 。) = z ( 6 ，n ) + 4 【! j ； ( 3 ) c r ( k 1 6 。) = z ( 7 ，柞) - i - 6 l j ；( 4 ) c r ( 9 1 , 7 ，。) = z ( 8 ，n ) + 9 l ! j ； ( 5 ) 州k i 8 。) = z ( 9 ，n ) + 1 2 1 1 j ；( 6 ) c r ( k i 1 岫) = z ( 1l ，n ) + 2 0 l ! j ； ( 7 ) c “足j 4 。) = z ( 6 ，n ) + 2 n 9 图的交叉数问题研究 1 2 4 广义p e t e r s e n 图和循环图的交叉数 广义p e t e r s e n 图是图论中大家熟知的一类图，其中以5 ，2 ) 就是著名的p e t e r s e n 图 1 9 8 1 年，e x o o 等人【4 6 1 证明，当n = 3 或者n 为偶数时，c r ( p ( n ，2 ) ) = o ；当n = 5 时， c r ( p ( n ，2 ) ) = 2 ；当n 为不小于7 的奇数时，c r ( p ( n ，2 ) ) = 3 2 0 0 5 年，马登举等人【4 7 1 用去边 法证明了c “p ( 2 m + 1 ，m ) ) = 3 1 9 8 6 年，f i o r i n i f 2 1 1 证明了：( 1 ) c r ( p ( 3 h ，3 ) ) = h ，h 2 ；( 2 ) 。豇+ l c r ( p ( 3 h + 1 ，3 ) ) + 3 ； ( 3 ) c r ( p ( 3 h + 2 ，3 ) ) = h + 2 ，h 2 并且给出c r ( p ( 9 ，2 ) ) = 2 ，c r ( p ( 4 h ，4 ) ) = 2 h 此外，f i o r i n i 证明了c r ( p ( 8 ，3 ) ) = 4 1 9 9 2 年d a n m c q u i l l a n 和r i c h t e r 证明f 4 8 1 c r ( p ( 1 0 , 3 ) ) 5 2 0 0 2 年r i c h t e r 和s a l a z a r 4 9 1 指 出f i o r i n i 证明中的错误，并以杨元生教授给出的c r ( p ( 1 0 ，3 ) ) = 6 ，c r ( p ( 1 l ，3 ) ) = 5 ，c r ( p ( 1 2 ，3 ) ) = 4 为起点，用数学归纳法证明了p ( n ，3 ) 的交叉数 c h i a 和l e e 5 0 1 证明了当k 4 时，鸭1 c r ( p ( 3 k ，女) ) k 2 0 0 3 年f i o r i n i 等f 5 1 】证明了当 k 4 时，c r ( p ( 3 k ，动) = k 2 0 0 5 年，s a l a z a r t 5 2 1 对n ，k 为整数，且七5 ，n k 的广义p e t e r s e n 图的交叉数进行研究给出： 【( 1 一 ) ( n 一矿) 】+ ( 4 k 2 + 1 一k a ) c r ( p ( n ，七) ) ( 2 一1 ) n + ( k , 2 2 + 七2 + 1 ) 1 9 8 6 年，f i o r i n i 证明【2 1 】当n 为8 或n 为不小于1 0 的整数时，c r ( c ( n ； 1 ，3 ) ) l j + 如m o d3 ) 2 0 0 3 年，马登举等【5 3 1 考虑环柄对循环图交叉数的影响，给出c r ( c ( 2 m ，f 1 ，m ) ) = c r ( c ( 2 m + 1 ； 1 ，m ) ) = 1 2 0 0 5 年，卢俊杰等】给出了5 肌s1 2 ，z = 3 时c ( m ，( 1 ，n ) 的交 叉数刘彦佩等 5 5 - 5 7 改进了循环图的交叉数上界；并且证明了c r ( c ( n ； 1 ，2 ) ) ) = 0 伽= 2 k ，k 2 ) ，c r ( c ( n ；1 1 ，2 1 ) ) = l 伽= 2 k + 1 ，k 2 ) ，并猜想c r ( c ( n ； 1 ，3 ) ) ) = ： ( n2 0 ，1 ( m o d 3 ) ) ，c r ( c ( n ； l ，3 ) ) = ：1 + 1 ( ，le2 ( m o d3 ) ) ，c r ( c ( 2 m ；f 1 ，m ) ) = m 一2 2 0 0 1 年，杨元生等【5 8 1 证明了c r ( c ( n ；f 1 【n 2 1 ) ) = 1 ( m = 【n 2 ，n 4 ) 2 0 0 4 年，林晓 惠等【5 9 - 6 1 1 确定了当n 为不小于8 的整数时循环图c ( ，l ： 1 ，3 1 ) ，当k 为不小于3 的整数时 循环图c ( 3 k ；f 1 ，七 ) 和当n 为不小于8 的偶数时循环图c ( n ； 1 ，n 2 1 )