（基础数学专业论文）关于一些特殊图类的交叉数研究.pdf

摘要 图的交叉数是在近代图论中发展起来的一个重要概念，主要研究如 何把图画在一个平面上，使其交叉的数目最少通常这项研究都采用纯 数学方法证明然而，确定一般图的交叉数是一个n p - 完全问题，因此， 到目前为止有关交叉数的结果比较少，仅限于一些特殊图和简单图的交 叉数甚至于在许多情况下，试图找出图的交叉数的一个好的上界或下 界也很困难本文运用组合方法和归纳思想以及反证法，确定了一些特 殊图类与路的笛卡尔积的交叉数，并且研究了联图的交叉数，还探讨了 将图画在胎面上的交叉数问题，求出了段。在胎面上的交叉数等全文 由六个章节构成 在第一章中较为详细地交代了交叉数的起源，交叉数研究的理论及 实际意义，以及这项研究工作在国内外发展的动态同时还简要介绍了 本文的写作背景，将要解决的问题和文章的创新之处 在第二章中对与交叉数有关的一些基本概念和性质进行了解析，同 时介绍了阅读本文所需要的预备知识，并介绍了在后续文章中将会出现 的定义、记号以及常用到的一些性质对于部分使用较少的概念我们放 到具体的章节中来交代 在第三章中着重研究了与笛卡尔积交叉数有关的问题，确定了两类 具体图与路r 的笛卡尔积的交叉数，分别是完全2 一部图。与8 阶循 环图c ( s ，2 ) 在第四章中，探讨了与联图有关的交叉数一方面，在假定z a r a n k i e w i c z 猜想成立的基础上得到了圈与路的联图的交叉数；另一方面，计算出了 一类特殊图与一个点的联图的交叉数 在第五章中，讨论了如何把一个图画在胎面上，使其交叉的数目最 湖南师范大学2 0 0 7 届博士学位论文 少，同时计算出完全2 。部图了甄，。在胎面上的交叉数 上述内容充实和发展了图的交叉数的研究成果，并为交叉数的研究 提供了新的方法和思路 在最后一章中，简要地介绍了作者今后研究的方向和重点，同时指出 了一些有待解决的问题。 关键词：匿，画法， 交叉数，笛卡尔积，联图。 至薹 关于一些特殊图类的交叉数研究 a b s 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 si sav i t a lc o n c e p ti nm o r d e ng r a p ht h e o r y i t s a p p l i c a t i o ni si m p o r t a n tn o to n l yi nt h e o r y , b u ta l s oi np r a c t i c e t h e ni th a sa t t r a c t - t e dm a n yg r a p ht h e o r ye x p e r t st os t u d y w eh a v ea l r e a d yk n o w nt h a tt od e t e r m i n e t h ec r o s s i n gn u m b e r so fg r 印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 , a tp r e s e n t t h ec 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 sh a v eb e e nd e t e r m i n e da r ev e r ys c a r c e ， a n dt h e r ea r eo n l ys o m es p e c i a l 蓼a p l l sw h o s ec r o s s i n gn u m b e r sa r ek n o w n e v e n i ns o m ee 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 r so fg r a p h s 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 r so ft h ec a r t e s i a n p r o d u c t so fp a t h sw i t hs o m es p e c i a l 伊印h ss u c ha st h ec o m p l e t eb i p a r t i t eg r a p h k 2 ，m ，a n dt h ec i r c u l a rg r a p hc ( s ，2 ) ，a n dw ed i s c u s st h ec r o s s i n gn u m b e r so ft h e j o i n ，a tl a s tw eo b t a i nt h et o r o i d a lc r o s s i n gn u m b e ro f 致弦 a tf i r s t ，i nc h a p t e ro n e ，w ei n t r o d u c et h eb a c k g r o u d sa n d o r i g i 璐o ft h ec r o s s i n g n u m b e ra n di t sd e v e l o p m e n t sa n dr e c e n ts i t u a t i o n sa r o u n dt h ew o r l d ，a n dp r e s e n t t h em e a n i n g so ft h er e s e a r c ha n dt h ep r o b l e m sw h i c hw ew i ls o l v e i nc h a p t e rt w o ，w eg i v es 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 et h er e q u i r e dk n o w l e d g e sw h i l er e a d i n gt h i sp a p e r i nc h a p t e rt h r e e ，w ed e t e r m i n et 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 t s o fp a t h srw i t ht h ec o m p l e t eb i p a r t i t eg r a p h 鲍，仇a n dt h ec i r c u l a rg r a p hc ( 8 ，2 ) i nc h a p t e rf o u r ，w ed i s c u s st h ec r o s s i n gn u m b e ro ft h ej o i n o no n eh a n d ，w e g e tt h ec r o s s i n gn u m b e ro ft h ej o i no fc y c l e sc a n dp a t h sr i ft h ez a r a n k i e w i c z s c o n j e c t u r ei sh o l d ；o nt h eo t h e rh a n d ，w ed e t e r m i n et h ec r o s s i n gn u m b e ro ft h ej o i n o ft h ec l a s so fs p e c i a lg 阳p h sa n do n ev e r t e x i nc h a p t e rf i v e ，w es t u d yh o wt od r a wag r a p hi nt h et o m s ，a n dc a l c u l a t et h e t o r o i d a lc r o s s i n gn u m b e ro ft h ec o m p l e t eb i p a r t i t ek 4 ，n i i i 湖南师范大学2 0 0 7 届博士学位论文 i nt h el a s tc h a p t e r ，w ei n t r u d u c et h ed i r e c t i o n so fo u rr e s e a r c hw o r ka n dp u t f 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 ug oa h e a d k e y w 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 ，c a r t e s i a np r o d u c t ，j o i n i v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果除文中已经注明引用的内容外，本论文不含任何其它个人或集体 已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担 学位论文作者签名： 膨往如7 年，z 月曙日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅本 人授权湖南师范大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密 ( 请在以上相应方框内打” ) 作者签名：尼晦日期：砷年f 2 月。3 日 导师繇甍旭期呻朔。铲日 关于一些特殊图类的交叉数研究 第一章导论 图论( 【1 】- 3 】) 是一个内容非常丰富而且应用十分广泛的数学分支，起 源于著名的哥尼斯堡七桥问题 在哥尼斯堡的普莱格尔河中有两个岛，七座桥将河岸与岛以及岛与 岛联接起来问题在于能否从四块陆地中任何一块出发，在通过每座桥 恰好一次后回到起点人们经过数次尝试后都没有成功欧拉在1 7 3 6 年 解决了这个问题，他将陆地看成点，桥看成边，构造了一个图，再用与图 有关的方法证明了这个问题没有解因此，欧拉成为了图论的创始人 如今图论已经发展出很多分支，并且和实际应用联系非常紧密图的交 叉数正是在近代图论中发展起来的一个重要概念，简单说来，主要研究 如何把图画在一个平面上，使其交叉的数目最少 1 9 7 7 年匈牙利数学家p a u lt u r i n 在图论杂志创刊时撰文“an o t e o fw e l c o m e ”【4 】，提到了他于2 0 世纪4 0 年代在布达佩斯工作时碰到的问 题“t u r a n sb r i c kf a c t o r yp r o b l e m ”( 见文献【2 ，5 ，6 1 ) ，即平面图的交叉数问 题他在文中写道： “i nj u l y1 9 4 4t h ed a n g e ro fd e p o r t a t i o nw a sr e a li ab u d a p e s t a n dar e a l i t y o u t s i d eb u d a p e s t w ew o r k e dn e a rb u d a p e s ti nab r i c kf a c t o r y t h e r ea r e8 0 m e k i l n sw h e r et 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 s w 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 e b r i c k sw e r ec a r r i e do ns n m 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 o d ow a st op u tt h ek i l n so nt h et r u c k sa tt h ek i l n s ，p u s ht h et r u c k st ot h es t o r a g e y 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 d t h ew o r ki t s e l f r 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 sc a u s e d al o to ft r o u b l ea n dl o s so ft i m ew h i c hw a sr a t h e rp r e c i o u st oa l lo fu s w ew e r ea l l 湖南师范大学2 0 0 7 届博士学位论文 s 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 s - v o l e n st h ei d e ao c c u r r e d t 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 ro fc r o s s i n g so f t 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 ro fc r o s s i n g s ? ir e a h 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 eb e e ni m p r o v e d ，b u t t 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 铭s t o r a g ey a r d ss e e m e d t 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 fi tt ot i m e sw h e nm yf e a r s f 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 dt om ea g a i nn o te a r l i e rt h a n 1 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 tz 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 y e r s 【5 】，t u t t e 【7 】，e r d s s 和g u yi s 等人对这一段历史作了较为详细的 介绍，此外p a c h 和t 6 t h 9 1 一 1 1 l 也就交叉数的概念及成果给逝了详尽的 介绍。自从交叉数的概念被提出以来，研究图的交叉数逐渐成为国际上 一个非常活跃的数学分支，吸引了国际上众多的数学家和计算机科学家 的关注，尤其是很多图论专家对这方面进行了深入研究，如l e i g h t o nf 1 2 ， g a x e y 和j o h n s o n 【1 3 等 事实上，研究图的交叉数不仅具有重要的理论意义，而且其有较强的 现实意义，在许多领域有着非常广泛的应用，例如： ( 1 ) 超大规模集成电路v l s i 中的圈布局闻题【1 2 ，1 4 ，l 嗣； ( 2 ) 草图的识别与重画问题，使之具有比手写汉字识别应用更为广泛 的应用领域； ( 3 ) 工业上电子线路板设计中的布线问题； ( 4 ) 生物工程d n a 的图示； ( 5 ) 软件开发过程中文档部分的e r 图( 实体联系图) 等的自动生成； ( 6 ) 在几何学、堆垒数论与测度论等理论中的应用【1 6 1 _ 一2 _ 关于一些特殊图类的交叉数研究 然而，一般说来要确定图的交叉数是十分困难的，g a r e y 和j o h n s o n 在文献 1 3 】证明了确定图的交叉数问题属于n p - 完全问题由于其具备 一定难度，目前国际上对交叉数的研究进展十分缓慢，范围也受到了局 限，能确定交叉数的图类型较少也正因此，使得这项研究更具有挑战 性随着对图的交叉数问题研究的深入，我们发现值得研究的内容也日 益丰富一方面希望确定具体图类的交叉数，另一方面希望得到与图的 交叉数有关的其它性质，如确定图类交叉数的较好上界；研究图的交叉 数与图的结构、图的其它参数之间的关系；研制有关确定图的交叉数的 算法等 1 7 - 2 0 1 目前看来，主要集中在以下几个方面： 1 一些特殊图类的交叉数 这些图主要包括结构特殊，规律性较强的图类一部分已经确定了交 叉数的精确值，还有一部分只给出了交叉数的上下界或猜想具体结果 如下： ( 1 ) 平面图 平面图的交叉数为0 例如，完全图，当讫 5 时是平面图，从而其交叉数为o ；对完全2 部图n ，当m ，1 1 , k 4 ，存在图g ，使得c r ( a ) = k ，但是万( g ) 仇 b 若c r ( a ) 3 ，贝0 琶矛( g ) = c r ( g ) c 若用多个直线段代替直线边，并记此时图的交叉数为c r 2 ( g ) ，则 c r 2 ( g ) ( c r ( g ) ) 2 他们特别介绍了一些图，有4 个交叉数，但是直线交叉数可以任意 大 任给图g 和整数k ，确定图g 的直线交叉数厉( g ) 七是n p - 完全问 题【9 5 目前我们能确定直线交叉数的图类很少对于完全图，当其顶 点数n = 4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，1 1 ，1 2 时，已确定相应的完全图玩的直线交叉数 分别为0 ，1 ，3 ，9 ，1 9 ，3 6 ，6 2 ，1 0 2 ，1 5 3 ( 9 6 ) ( 2 ) 奇交叉数 图g 的奇交叉数o d d c r ( g ) 是指当图g 有最小交叉数时，相交奇数 次的边对 e ，e ， 的数目 一般地， o d d c r ( g ) p a i r c r ( g ) c r ( g ) 万( g ) ， 其中p a i r c r ( g ) 是指图g 有最小交叉数的边对 e ，e ，) 的数目 9 7 】 j a n o sp a c h 等提出 9 】： 9 - 湖南师范大学2 0 0 7 届博士学位论文 对任意图g ，是否有o d d 一秽( q p a i r 一嚣( g ) = 苈( g ) ? 图g 的任意一对边如果楣交偶数次，则一定可以得到它的交叉数为 0 。也就是说，若o d d c r ( a ) = 0 ，则c r ( g ) 一0 ，即万( g ) = 0 。 p e l s m a j e r 等人对环面上图的映射的奇交叉数做了较为详细的研究【9 8 ， 对任意图g ，都有c r ( a ) 2 ( o d d c r ( g ) ) 2 ( 9 ，1 4 】) ( 3 ) 正则图交叉数 对正则图交叉数的研究也是一个较热门的方向r i c h t e r 等研究了孓 正则图的交叉数【9 9 】杨元生等利用计算机编程，给出了张1 2 的所有四 正更| j 图的交叉数稀髂1 6 的随机四正则图的交叉数【王习，并猜想四正则图 的交叉数的平均交叉数为o ( n 2 ) 馥) 临界交叉数 m a r t i nk o c h o l 研究了临界图的结构，得到了具有n ( n 2 ) 个交叉数的 孓连通临界简单图的结构【1 0 0 r b r u c er i c h t e r ，c a r s t e nt h o m a s s e n 等人 也对该图做了大量的研究工作，在【1 0 1 】中证明了：若图g 中具有交叉数 最少为惫的最小的图，则( g ) 2 5 k + 1 6 此外关于临界交叉数的结果见 f 1 0 2 一 1 0 4 1 。 3 图g 及其线图l ( g ) 的交叉数之闻的关系 图g 的线图l ( g ) 是指顶点集为e ( g ) 的图，其中两个顶点相连的充 要条件是它们在g 中为摆邻的边。一般来说，图g 和它的线图l ( g ) 的 交叉数满足：( g ) c r ( 厶( g ) ) 上世纪六十年代初，s e d l 泌e k 【1 0 5 】得到一个平面图g 的线图l ( g ) 是 平面图的充分必要条件1 9 7 9 年，k u l l i ，a k k a 和b e i n e k e 1 0 6 】获得了一 个平面图的线图的交叉数为1 的充分必要条件1 9 9 7 年，a k k a ，j e n d r 0 ， k l 躐等研究了平面圈的线图的交叉数为2 的情形【1 0 8 ， 一1 0 关于一些特殊图类的交叉数研究 1 9 9 9 年j e n d r o f 和k l e i n ：已经证明了图g 和线图的交叉数都是1 的充 分必要条件【1 0 7 2 0 0 1 年，j e n d r o f 和k l 战【1 0 7 研究了非平面图的线图 的交叉数情形，确定了非平面图的线图的交叉数为1 的充分必要条件 2 0 0 5 年黄元秋和赵霆雷给出了图及其线图的交叉数都是七的充分必要条 件1 0 9 4 图的交叉数的下界 设图g = ( ke ) ，使得i e ( g ) i 7 5 1 v ( g ) i ，则有【1 2 ，1 4 ，1 1 0 】 c r ( g ) 熹丽i e ( g 研) 1 3 对任意图g = ( v e ) ，若有i e ( g ) i 4 1 v ( a ) l ，则有 9 】9 删刮g ) 击嬲 除此以外，关于交叉数的研究还可以参考 1 1 1 一 1 1 4 ，例如从具体画 法上着手 2 4 ，1 1 0 ，1 1 5 ，或者讨论交叉数的奇偶性【1 1 6 ，1 1 7 以及计算复杂 度【1 1 8 】等值得一提的是，方体作为一种特殊的结构，也得到了不少图 论专家的关注 1 1 9 一 1 2 1 正是在这些文献的启发下，同时在已有结果的基础上应用并创新相 关方法，我们推广了笛卡尔积图的交叉数，并研究了联图的交叉数以及 胎面交叉数等问题 关于一些特殊图类的交叉数研究 第二章相关概念的解析 本文涉及到的基本概念和性质，未作特别说明均同文献【1 】，且无特别 说明时文中所涉及的图均指简单连通图 图g 是指一个有序三元组( y ( g ) ，e ( g ) ，惦) ，其中v ( g ) 是非空的顶点 集，e ( g ) 是不与v ( g ) 相交的边集，而妒g 是关联函数，它使g 的每条 边对应于g 的无序顶点对 定义2 1 图g 在平面上的一个画法d ，是指把图的顶点画为平面上 的结点，把图的边画为平面的弧 定义2 2 图g 在画法d 下的交叉数，是指在画法d 下边与边产生的 交叉点的个数，用c r d ( g ) 表示 定义2 3 图g 的交叉数，用c k g ) 表示，是指图g 在平面上所有画法 的交叉数中的最小值，即c r ( g ) = 蝉n c r d ( g ) ) 定义2 4 图g 在平面上的一个最优画法，是指产生的交叉数目恰好 等于图g 的交叉数的画法 定义2 5 图g 在平面上的一个好画法，是指图g 在平面上同时满足 以下四个条件的画法： ( 1 ) 连接同一个结点的任意两条边不相交； ( 2 ) 边不能自身相交； ( 3 ) 任何两条相交的边最多交叉一次； ( 4 ) 没有三条边交叉于同一个点( 见图2 1 ) 1 3 湖南师范大学2 0 0 7 届博士学位论文 图2 1 图g 的好画法中不允许出现的四种情况 注1 定义2 5 中的条件4 ) 是为了研究赢统一规定的 前三个条件( 王) ，( 2 ) ，( 3 ) 是最优画法中必然满足的因为如果不满足， 我们可以对画法进行改进，从而得到一个具有更小交叉数的画法，这与 最优画法的定义矛盾( 见图2 2 ) ) (l 图2 2 对图2 1 中前三种画法的改进 注2 定义2 1 定义2 4 中的“平面”可改为“曲面”，且相关定义可推 广到曲面的情况，本文将在第五章中讨论图在胎面上的交叉数 定义2 , 6 设图g 在平面上的一个画法为d ，日是g 的子图，则d 在 子图h 上的限制吾法为萄法d 中与子圈h 有关的的部分，记作秽k 定义2 7 设图g 在平蜀上的一个画法为d ，g 在d 中的一个交叉点 是指在p 中图g 的两条边在非结点处的楣交点 例如，图2 3 中的点z 是一个交叉点 定义2 8 设图g 在平面上的一个画法为d ，则将由顶点，边，交叉点 以及边的片断围成的部分称为在画法d 下的一个区域 1 4 关于一些特殊图类的交叉数研究 例如，在图2 3 中分别指出了完全图蚝在画法d 下的8 个区域 图2 3 蚝在画法d 下的8 个区域：冠( i = 1 ，2 ，8 ) 两个图g 。和g 2 的笛卡尔积图，用g t g 2 表示，它是这样的图：点 集v ( c 1 g 2 ) = v ( g 1 ) xv ( g 2 ) ；边集e ( g 1 g 2 ) = ( 讹，v j ) ，( ，) ) ：地= 且 ， e ( g 2 ) ，或者( 妣，) e ( g 1 ) 且吩= ) 两个点不相交的图g ，和g 2 的联图，用g 。vg 2 表示，它是在g 。和 g 2 的并图中，把g 。的每个顶点和g 。的每个顶点连接起来所得到的图 性质2 1 设d 为图g 的好画法，若g 1 ，g 2 和g 3 为g 的边不相交子 图，则 c r d ( c lug 2 ) = c r d ( g 1 ) + c r d ( c 2 ) + c r d ( g 1 ，g 2 ) ， c r d ( c lug 2 ，g 3 ) = c r d ( g 1 ，g 3 ) + o r b ( g 2 ，g a ) 若从图f 的某些边中加入或抹平2 度点( 均可反复多次) 得到的图与 图日同构，则称f 和日同胚，记为f 一日 性质2 2 若f 一日，则有：c r ( f ) = c r ( h ) 性质2 3 若日是图g 的子图，则有：c r ( h ) c r ( g ) 性质2 4 若图g 有t t ( n 3 ) 个顶点和m 条边，则c r ( g ) m 一3 n + 6 1 8 1 一1 5 湖南师范大学2 0 0 7 届博士学位论文 性质2 5 若图g 是孓连通平面图，则g 的平蘧嵌入是唯一的【i 2 2 。 1 6 关于一些特殊图类的交叉数研究 第三章与路r 的笛卡尔积有关的图的交叉数 从2 0 世纪后期起，m k l 毯黾等人对阶数较小的图与路，星，圈的笛 卡尔积图的交叉数进行了研究，见文献( 【5 4 】- 【6 2 】) 肖文兵等人开始研究昏 阶图与路，星的笛卡尔积图的交叉数( 见文献 6 3 1 ，【1 2 3 ) 作者在这些结果 的基础上研究了两类图与路的笛卡尔积图的交叉数，一类是点数可以任 意大的完全2 - 部图另一类是8 阶循环图c ( 8 ，2 ) 3 ( 2 m r 的交叉数 因为完全2 一部图虬，m 与星图同构，到目前为止对跹，。和路或圈 的笛卡尔积的交叉数的研究，已有不少结果，其中最重要的结果要数2 0 0 6 年d b o l m l 1 2 4 1 证明了： 对任意的仇，i t 1 ，c r ( r ) = ( n 一1 ) 【筹儿警j 其它的还包括j e n d r o i 和雪浼r b o v 五求出了c r ( s 3 g ) 【5 3 】，m k l e 吾芒得到 c r ( g ) 【5 4 】，以及周志勇和黄元秋确定了c r ( 瓯xg ) 1 2 5 】 至于完全2 - 部图恐已知的结论比较少特别的，因为k 2 ，2 = q ， 所以k 2 ，2 r 是平面图在( 1 2 6 】中已经知道了虬，2 g 的交叉数 m k l 醋芒在【5 7 】中证明了 c r ( 尬，3 r ) = 2 n c r ( 鲍，3 & ) = 4 2 jl t i t - 1 j 十2 竹 他在计算出c r ( 鲍，s 岛) = 9 时还给出了一个猜想： 当n 4 时，c r ( ，3 q ) = 4 n 6 2 1 此外王晶和黄元秋得到了c r ( 恐，4 r ) = 4 n 【1 2 3 1 7 湖南师范大学2 0 0 7 届博士学位论文 在本节中，我们利用稿拉链积嚣【1 2 4 这一术语研究了与路有关的笛 卡尔积的交叉数，主要结果如下： 定理3 1 1 对任意的m 芝2 且掘1 ，a - ( 9 2 ，m 臻) = 2 n t 警ji 警j 。 在证明定理3 1 。1 之前，我们先来证明几个引理 设恐娜的两个m 度点分别为a 穰b ，其余的2 - 度点记作1 ，2 ，孤 路r 的点分别记作0 ，1 ，n 且将两个端点分别用0 和礼表示；对于 z 一1 ，2 ，他一1 ，点i 分别与i 一1 和i 十1 相邻 图施，m r 有( m + 2 ) + 1 ) 个点：( a ，i ) ，( b ，i ) 以及( j ，i ) ，其中j = 1 ，2 ，m 且i = 0 ，1 。，嚣在k 2 ，m 磊中，楣邻的点对是 ，i ) 和( j ，i ) 其 中茹一a ，b ，j = l ，2 ，m 且i = 0 ，1 。，镁( 髫，i ) 和x ，l - i - 1 ) 其中茹= a ，b 且 i 一0 ，1 ， 一1 ；0 ，i ) 和( j ，i + 1 ) 其中j 一1 ，2 ，m ，且i = 0 ，1 ， 一1 为方便表示，设a i 和玩分别表示点( a ，i ) ，( 6 ，i ) ，其中i 一0 ，1 ，n ，且用 鹚m 0 0 ，i ，髓) 表示k 2 ，m r 中由点a i ，玩以及，i ) ( 其中j = l ，2 ，m ) 导出的子图。由点a o ，a l 。，导出的路称为8 路，记作严同样的定义 b 路，用p 表示用记号9 2 , m f n 表示从。mxr 中去掉p 和p 6 的 各条边得到的图 引理3 1 1 当m 2 且铭之1 时，存在k 2 m r 的一个好画法d 使 c r , ( 9 2 。m r ) = 2 礼 2 j m - 1 一1 8 _ 关于一些特殊图类的交叉数研究 图3 1 1k 2 mxr 的好画法d 证明从图3 1 1 知，对于江0 ，1 ，n ，有【罟j 个点在啦的上方，这 些点是( 歹，i ) ，其中歹= 1 ，2 ，【罟j 同时有詈1 个点在a i 的下方，这些点 是( 歹，i ) ，其中歹= l 詈j - t - 1 ，【詈j - i - 2 ，m 当i = 1 ，2 ，n 一1 时， ( ) = 1 + 2 + + ( l 2 j 一1 ) 】+ 【1 + 2 + + ( 筹卜1 ) 】 叫署j 【孚j 同样地，c r d ( 驴) = 【罟儿下r n - - 1j 由此c r d ( 鹚，m ) = 2 【詈儿孚j 当i = o ，礼时，有c r d ( a i ) = l 等儿字j ，由于c r d ( b i ) = 0 ，则有c r d ( 鹚，仇) = 【詈儿孚j 在图3 1 1 中，任意两条发生交叉的边中总有一条属于某个e ( 鹂m ) 而 且当i j 时，c r d ( 碰，m ，砭。m ) = 0 于是 盯。( 配，仇r ) ：壹c r d ( 鹚，m ) = 2 ( n - 1 ) l 2 jl - - r - - 1 j + 2 【筹j 【孚j = 2 n 【筹j 【字j 一1 9 湖南师范大学2 0 0 7 届博士学位论文 值得注意的是在图3 。l 。1 中严和p 的边没有发生交叉 接下来，将介绍文献【1 2 4 中的相关概念。 对于i l ，2 ，设国是一个图，且点戗y ( g ) 是小度点用贼= n v ；m ) 表示点忱的邻点组成的集合，设仃：n 1 _ 2 是一个双射，则将盯称为g 1 和g 2 在点t ，。和v 2 处的拉链作用由此两个图g t 和依据盯得到的拉 链积定义的是一个图g ，o 萨g 2 ：从g l 一管l 和g 2 一您的点不楣交的并图中 添加边链莎( 豁) ，其中珏越。 设d i 是图酝的好画法由画法得到点铖关联的边的一个循环序， 这个顺序可以扩展到它的邻域胍上设双射讹：m _ 1 ，2 ，田是其中 相应的一组标号于是定义矿：l _ n 2 ，拶= 巧1 砸，称之为画法d t 和伤 在点壤和v z 处的拉链作用。裙应的d ，和侥依据得到的拉链积是指 画法d ，o 莎d 2 ：先从d ；中增加如的一个镜面复制，并将原来藏在无界面 上的咖不相交的画入画法d ，中包含点可。的某个面，在一个包含u 。和t 1 2 的小圆盘内同时去掉这两个点，然后根据仃作用连接相应的边因为 代表了分别与现和睨关联的边的顺序，在d 。和伤之闻的边不会产生 新的交叉。易见d ：o 矿d 2 是g ，o ，侥的一个好画法，由此有以下结论： 引理3 1 2 对于i = 王，2 ，设甄是最的最优画法，锾y ( & ) 是d 一 度点，且设伊是d l 和d 2 在移l 和铑处的拉链作用，则嚣( 8 lo 帝g 2 ) c r ( g 1 ) 十盯( g 2 ) 【1 2 4 对于图g ，设s v ( g ) 且f s i = n 将s 称为在g 中是k 一星连通的：若 存在k 个不相交的边子集r ，昂，鼹冬e ( g ) ，使得要么g 【捌是某个星 2 0 。 关于一些特殊图类的交叉数研究 岛的满足所有叶子都在s 中的剖分，要么g 【只】是某个星& 一，的满足所 有叶子以及中心都在s 中的剖分相应的，将每个只称为s 的一个星 集( 与这些概念有关的其它内容，可以参考 1 2 4 ) 引理3 1 3 设g 1 和g 2 是两个点不相交的图，协y ( g ) ，且d e g ( v o = d ， 设v i 的邻点集m 在g 一v i 中是2 星连通的，其中i ；1 ，2 ，则c r ( g l o 口g 2 ) 防( g 1 ) + c r ( g 2 ) ，对于任意的双射盯：g x n 2 【1 2 4 引理3 1 4 设g 1 和g 2 是两个点不相交的图，眈是g t 的最优画法 对于l = 1 ，2 有他y ( g ) 是相应的d 一度点，且v i 的邻点集肚在g t 一哦 中是参星连通的，已知盯是画法d 。和现在口1 和v 2 处的拉链作用于 是c r ( g 1o ，g 2 ) = c 7 ( g 1 ) + c r ( g 2 ) 证明由引理3 1 2 和引理3 1 3 ，结论显然 口 用倪表示从鲍m 中增加点x ，并将z 与所有的2 一度点连边得到的新 图( 见图3 1 2 ) 类似的用倪v 表示从恐，m 中增加两个点z 和y ，并将z 和 y 分别与所有的2 度点连边得到的新图( 见图3 1 3 ) 考虑到g 。和g z 的 对称性，接下来用g log 2 表示g 1o 盯g 2 z y 图3 1 2图3 1 3 引理3 1 5 以 c r ( g 2 ) = 【等儿孚j ，而且n ( x ) 在g z z 中是参星连通 的； 例c r ( c = 掣) = 2 【筹j 【孚j ，而且( z ) 绒者( y ) ) 在倪掣一z 绒者g 耖一y ， 相应的夕中是争星连通的； 2 1 矧贸( 虢。岛) = 3 i 警i 孚，而且n ( x ) 在( 饶g 岛) z 中是舅星连 通的 证明( 1 ) 由于瓯= 甄，m ，有c r ( q ) = 凹( 蚝，m ) 一【警儿字j 由图3 1 2 显然有n ( x ) 在倪一嚣中是2 - 星连通的 ( 2 ) 由予岛蓼一k 4 结论同样成立j a t 壅l3 1 。3 中可见( 或者( 瞽) ) 在一舅( 或者一y ，裾应的) 中是星连通的。 ( 3 ) 易见z y ( 瓯) 以及y y ( 倪掣) 都是胁度的点在( 1 ) 和( 2 ) 的基 础上，( 茹) 在瓯一搿中是2 _ 星连通的，且( 可) 在瓯”一y 中是3 - 星连 通的再由引理3 1 4 ，有 c r ( 瓯og 掣) =凹( 瓯) + c r ( g v ) 3 l 2 jl _ z _ m - i 不难看出在图3 1 4 中( 。) 在( g o 瓯p ) 一髫中是3 - 星连通的。 图3 。1 4 引理3 1 6 对于任意的m 2 且n 1 ，甜( 噩i i 巧) = 2 n l m 一 i r a 。- t 1 一 证明当n 一1 时，由于砭i i 珂= g 。o 瓯，利用引理3 1 4 和引理 3 1 5 ( 1 ) ，有 = 甜( 瓯) - f 秽( 饶) 一2 。m 2 。m 2 - 1 j 。 当锫2 时，蕊= g x e 墅旦垒譬旦生。g x 。函j + j l + 3 州3 ) ， 2 2 关于一些特殊图类的交叉数研究 c r ( gog 叫) = 3 【詈儿孚j ，而且( z ) 在( 倪og 叫) 一z 中是孓星连通的 由引理3 1 4 ， c r ( go og 品) = c r ( ( qog z ，) o 倪掣) = c r ( a xo g x 可) + c r ( 倪l ，) = 5 【罟j 【孚j ， 而且n ( x ) 在( 瓯og 王掣o ) 一z 中是3 _ 星连通的，重复以上步骤 得到c r ( 倪o 鱼! 旦竺三兰旦：旦竺：多2 ( 2 礼一1 ) 【罟儿孚j ，而且( z ) 在( 倪。 n - 1 g 兰旦垦兰2 ：旦竺夕- - x 中仍然是3 - 星连通的，于是 n - 1 贸( 鲍，mxr ) = c r ( g zop 。! ，og 。掣o og 。o g 。) n - - 1 = c r ( ( go 倪og ! ，o og $ 掣) og 霉) 、一、，一， n - - l = c r ( g zo g 。og 。掣o o 倪掣) + c r ( g 。) 、。_ _ 。l - n - 1 = 2 n 自【字j 图3 1 1 中的限制画法d l 瓦赢再是瓦i i 瓦的最优画法 下面我们证明定理3 1 1 定理3 1 1 的证明 由引理3 1 1 ，有c r ( 鲍，mxr ) 2 n l 筹j 【孚j 由引理3 1 6 ，因为瓦i 丽：是恐，价r 的子图，由性质2 3 有c r ( 恐，m r ) 2 n 【等儿孚j 从而完成了定理3 1 1 的证明 口 事实上图3 1 1 中的画法d 是鲍m r 的最优画法 一2 3 湖南师范大学2 0 0 7 届博士学位论文 3 2c ( s ，2 ) 只的交叉数 循环图c ( n ，2 ) 表示由圈g 增加边忱q + 2 0 1 ，2 ，n ，i + 2 ( r o o d 他) ) 得 到的图到目前为止，循环图g ( 他，2 ) 与路r 的笛卡尔积的交叉数研究得还 不充分。在同梅意义下，c (