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

摘要 自p a u lt u r i n 于上世纪七十年代提出交叉数的概念以来，研究图的交 叉数逐渐成为国际上一个非常活跃的数学分支，吸引了国际上众多的数 学家和计算机科学家们的关注，尤其是很多图论专家对这方面进行了深 入的研究然而，m r g a r e y 等( 文献【l 】) 已经证明确定图的交叉数是一 个n p 一完全问题因此，到目前为止有关图的交叉数的结果甚少，其研 究前景非常广阔，但其难度也比较大，一直以来进展缓慢目前，关于图 的交叉数研究主要集中在以下两个方面：其一，确定一些特殊图类的交 叉数；其二，研究图的交叉数的性质本文主要确定了一些五阶图与路 的联图的交叉数以及一些六阶图与星图叉的笛卡尔积图的交叉数全文 的结构如下： 在第一章中详细地介绍了交叉数的起源，交叉数研究的理论与实际 意义，交叉数在国内外研究情况同时简要介绍了本文写作背景，以及 将要解决的问题和文章的创新之处 在第二章中给出一些与交叉数有关的基本概念和性质，同时介绍了 阅读本文所需要的预备知识 在第三章中确定了4 个五阶图与路r 的联图的交叉数 在第四章中着重研究了心。与星图& 的笛卡尔积图的交叉数 在最后一章中，简要地介绍了作者今后研究的方向和重点，同时指出 了一些有待解决的问题 关键词：交叉数；联图；路；星图；笛卡儿积；好画法 a b s t r a c t s i n c et h ei n t r o d u c t o r yi n v e s t i g a t i o no fc r o s s i n gn u m b e r so fg r a p h sb yp a u l t u r i ni ne a r l y1 9 7 0 s ，t h es t u d y i n go nt h ec r o s s i n gn u m b e r so fg r a p h sh a v eb e c o m ea v e r ya c t i v ef i e l dg r a d u a l l yi nt h ew o r l d i ta t t r a c t e d al a r g en u m b e ro fi n t e r n a t i o n a l m a t h e m a t i c i a n sa n dc o m p u t e rs c i e n t i s t st oc o n c e r na b o u t ，i np a r t i c u l a r ，al o to f g r a p ht h e o r ye x p e r t sc o n d u c t e di n - d e p t hs t u d i e si nt h i sa r e a b u t ，m r g a r e ye ta l 【1 】1 h a v ep r o v e nt h a tt od e t e r m i n et h ec r o s s i n gn u m b e r so fg r a p h si sn p c o m p l e t e a tp r e s e n tt 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 e v e r ys c a r c e i th a sv e r yb r o a dp r o s p e c t sf o rt h es t u d y i n g h o w e v e r ，b e a u s eo fi t s d i f f i c u l t y , t h e r ea r eo n l ys l o wp r o g r e s sf o rl o n gt i m e a tp r e s e n t ，t h es t u d y i n go nt h e c r o s s i n gn u m b e r so fg r a p h sm a i n l yc o n c e n t r a t e di nt h ef o l l o w i n gt w oa r e a s ：o nt h e o n eh a n d ，t od e t e r m i n et h ec r o s s i n gn u m b e ro fs o m es p e c i a lc l a s s e so fg r a p h s ；o n t h eo t h e rh a n d ，t or e s e a r c ht h ep r o p e r t yo ft h ec r o s s i n gn u m b e r t h i sp a p e rm a i n l y d 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 ej o i no fp a t h srw i t hs o m e5 - v e r t e xg r a p h s ， a n dt 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 so fs t a r s & w i t hs o m e6 - v e r t e x g r a p h s t h es t r u c t u r eo ft h ep a p e ri s a sf o l l o w s 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 do r i g i n so ft h ec r o s s i n gn u n l - 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 tt h e m e a n i n g so ft h er e s e a c ha n dt h ep r o b l e m sw h i c hw ew i l 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 gb u m b c 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 nt h ec 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 ej o i no fp a t h s r w i t hf o u r5 - v e r t e xg r a p h s i nt h ec 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 n p r o d u c t so fp a t h sr w i t hk 2 4 i i i 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 f0 1 1 1 r 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 l lg oa h e a d k e y w o r d s ：c r o s s i n gn u m b e r s ；j o i n ；p a t h ；s t a rg r a p h ；c a r t e s i a np r o d u c t ；g o o d d r a w i n g i v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的研究成果除了文中特别加以标注引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完全 意识到本声明的 学位论文作者签 干o 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，研究 生在校攻读学位期间论文工作的知识产权单位属湖南师范大学同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分内 容编人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存和汇编本学位论文 本学位论文属于 1 ，保密口，在年解密后适用本授权书 2 、不保密口 ( 请在以上相应方框内打“ ) 日 日 妇弘e l 6 月绎日 竽 、弘似 揣影 签 签 者 师 关于图的交叉数研究 1 导论 图的交叉数是图论中的一个重要概念，从上个世纪七十年代初匈牙 利数学家p a lt u r 五n 根据其在一个砖厂碰到的实际难题( t u r i n sb r i c kf a c t o r y p r o b l e m ) ( 见文献 2 ) ，从而提出了交叉数的概念以来，图的交叉数问题逐 渐成为国际上一个非常活跃的图论分支，很多图论专家对这方面进行了 深入研究研究图的交叉数不仅具有重要的理论意义，而且有较强的现 实意义，在许多领域有着非常广泛的应用，例如： v l s t 中的圈布局问题； 草图的识别与重画问题，具有比手写汉字识别更为广泛的应用领域； 工业上电子线路板设计中的布线问题； 生物工程d n a 的图示； 软件开发过程中文档部分的e r 图( 实体联系图) 等的自动生成； 在几何学、堆垒数论与测度论等理论中的应用 然而，文献【1 】1 证明了确定图的交叉数问题属于n p - 完全问题由 于其难度，目前国际上对交叉数的研究进展十分缓慢，范围也受到了局 限，能确定交叉数的图类很少也正因为如此，使得这项研究更具有挑 战性随着对图的交叉数问题研究的深入，我们发现值得研究的内容也 日益丰富一方面希望确定具体图类的交叉数，另一方面希望得到与图 的交叉数有关的其它性质，如确定图类交叉数的较好上界；研究图的交 叉数与图的结构、图的其它参数之间的关系；研制有关确定图的交叉数 算法目前来看，主要集中在以下几个方面： 1 一些特殊图类的交叉数 】 高校教师在职攻读硕士学位论文 这些图类主要包括结构特殊，规律性较强的图类一部分已经确定 了交叉数的精确值，还有一部分只给出交叉数的上下界或猜想具体结 果如下： ( 1 ) 笛卡儿积图的交叉数： 对于长度分别为仇，n 的圈的笛卡尔积图，f h a r a y 等在1 9 7 3 年提出 了著名的猜想【3 】： c 7 ( c mx 瓯) s ( m 一2 ) n ，( 3 m n ) r i n g e i s e n 和b e i n e k e 在1 9 7 8 年证明了c ：r ( c 3xg ) = h i 4 ，1 9 8 0 年证明 了盯( qxg ) = 2 n 5 ，1 9 9 6 年m k l e 酌和r i c h t e r 证明凹( g g ) = 3 n 6 ， 2 0 0 1 年r i c h t e r 证明仃( g g ) = 4 n 7 ，2 0 0 4 年a d a m s s o n 和r i c h t e r 证 明了c r ( c 7xg ) = 5 仃【8 】另外，一些阶数确定的圈与圈的笛卡尔积图的 交叉数，如c r ( a c 4 ) = 8 1 9 ，甜( gxg ) = 1 5 1 1 0 ，c r ( g c 6 ) = 2 4 1 1 1 ， c r ( c 7 岛) = 3 5 1 1 2 】等都已经得到证明 上世纪八十年代初，b e i n e k e 和r i n g e i s e n 及j e n d r o l 和s c e r b o v a 等人 确定了所有4 阶图与圈的笛卡尔积图的交叉数【5 ，1 3 从二十世纪后期起，捷克数学家m k l e 吾6 等人开始研究阶数较小的图 与路r ，星图& ，圈g 的笛卡儿积的交叉数( 见文献【1 4 【2 1 】) 由于阶数 为3 的连通图或同构于路b 或同构于g 圈，它交叉数显然为0 因此这 方面系统的研究从4 阶连通图开始的m k 1 e 酌1 9 9 4 年确定了所有4 阶连 通图与路r ，星图岛的笛卡儿积的交叉数( 见文献【1 5 】) 之后，他又陆续 给出了所有5 阶连通图与路r 的笛卡儿积的交叉数( 见文献【1 6 一【2 1 】) ，以 及给出了部分五阶连通图与星图晶，圈g 的笛卡儿积的交叉数最近， 在黄元秋教授的带领下，他的学生也给出许多5 阶图与星的笛卡尔积图 的交叉数填补了m k l 西芒许多未完成了空白表1 - 1 是我们总结的最新 5 阶图与星岛的笛卡尔积图的交叉数结果 2 关于图的交叉数研究 g 0 1 rt 吼穴 g 侈 g 4 囱 钒ri g 6 g 一 二二斗a ll _ z ( 5 n )n ( n l 、n ( n 1 ) c r ( o s n ) 【2 2 】【2 3 】【2 3 】 g 八g 。 q 岗 g 1 j 苌 国囱 0 1 冷0 1 # g tll 心凶 il 幽- - z ( 5 ，n )n ( n 一1 )z ( 5 n ) + 2 nn ( n 一1 )n ( n 一1 ) z ( 5 ，n ) + l 号j n ( n 一1 ) c r ( g i ) 【2 2 l【2 3 】【1 7 】【2 1 】【2 4 】【2 5 】【2 1 】 g t q 岗q 6 囟 q 氏 0 1 卤q 硷劬囱。2 囱_ c r ( g s n )引街2 ” z ( s ，n j + 2 n z ( 5 j 个l 2 n 引5 饼2 “ z o ，n ) + 4 n 蜀 钱p【2 甸【2 0 】1 矧【2 8 】 表1 - 1 已有的五阶图与星图的笛卡尔积图的交叉数统计表 ( 2 ) 完全图的交叉数： 完全图的结构特殊，任意两个顶点之间都有且只有一条边相连关 于完全图的交叉数有一个重要的猜想，即g u y 猜想： c r ( ) = 如1n j 【孚j 【字j 【字j 其中，【n j 表示不超过n 的最大整数。 目前仅证明了等号对于n 1 0 成立即当完全图k 顶点数分别为 n = 1 ，2 ，3 ，1 0 时，其交叉数分别为0 ，0 ，0 ，0 ，1 ，3 ，9 ，1 8 ，3 6 ，6 0 ( 3 ) 完全二部图的交叉数： t u r a n 的“砖厂问题”实际上等价于确定完全2 部图，n 的交叉数 z a r a n k i e w i c z 在文献 3 0 】中“证明”了 ，盯( ，。) = 【筹j 【孚j 【兰j 【孚j ，( m 纠 但r i n g e l 和k a i n e n 不久各自独立发现z a r a n k i e w i c z 在文献 3 0 】中的证明有 误( 参见文献【3 1 1 ) ，因而确定完全2 一部图，n 的交叉数目前仍然是一个公 开问题习惯上把上式称之为z a r a n k i e w i c z 猜想，把上式右端记为z ( m ，礼) 3 高校教师在职攻读硕士学位论文 d j k l e i t m a n 在1 9 7 0 年证明了等号对于m i n ( m ，仃) 6 时成立( 见文献【3 2 1 ) w o o d a l l 于1 9 9 3 年证明了当m = 7 且n 1 0 时等号也成立( 见文献【3 3 】) 到目前为止还没有关于此方面的新结果 ( 4 ) 完全三部图的交叉数： 目前，有关确定完全孓部图交叉数的文献很少，且证明基本上建立 在已知的完全2 一部图交叉数的基础上 上世纪八十年代，k a s a m o 3 4 1 证明了 c r ( k 1 ，3 ，n ) = z ( 4 ，n ) + 【昙j ，c r ( 鲍，3 ，。) = z ( 5 ，礼) + 礼 之后，很长时间未见其他相关文献出现直至2 0 0 4 年，黄元秋和赵 霆雷【2 3 证明了 c r ( k l ，4 一) ：n ( n 一1 ) ：z ( 5 ，n ) + 2 罟- j 后来梅汉飞又与黄元秋【3 5 】合作证明了 c r ( k 1 ，5 ，n ) = z ( 6 ，n ) + 4l 罟j 之后黄元秋教授又与赵霆雷【3 6 】合作证明了 c r ( 尬，4 n ) = z ( 6 ，竹) + 2 n 同时在假设z a r a n k i e w i c z 猜想对于m = 7 成立的前提下，黄元秋教 授与赵霆雷确定了c r ( k 1 ，6 ，n ) = z ( 7 ，n ) + 6 【j ( 见文献 3 7 】) ；其后不久又在假 设z a r a n k i e w i c z 猜想对于m = 8 ，仇= 9 成立的前提下，确定了k 1 ，7 ，n ，k - 跏 的交叉数( 见文献【3 8 ，3 9 ) ( 5 ) 循环图的交叉数： 循环图c ( n ，s ) 是指具有顶点集v ( c ( n ，s ) ) = v t i o i 竹一1 ) 和边集 e ( c ( n ，s ) ) = v i v j i o i n 一1 ，0 歹n 一1 ，( i - j ) m o dn s ，s 1 ，2 ，【詈j 4 关于图的交叉数研究 的图由于循环图c ( 仡；( 1 ，七 ) 可以通过对广义p e t e r s e n 图p ( n ，后) 收缩其 轮而得到，因此确定循环图d ( n ； 1 ，后) ) 的交叉数与确定广义p e t e r s e n 图 p ( n ，k ) 的交叉数紧密相关 1 9 8 6 年f i o r i n i 研究了广义p e t e r s e n 图p w ，后) 的交叉数 4 0 1 ，并得到 c r ( c ( 礼； 1 ，3 】) ) 引三j + nr o o d3 ( 仡= 8 或n l o ) 但r i c h t e r 和s a l a z a r 发现其证明有误【4 1 】，m c q u i l l a n 和r i c h t e r 4 2 ，s a r a z a n 4 3 j 等人也得到了一些循环图的交叉数 国内杨元生等人获得了一些循环图的交叉数【4 4 ，4 5 】郝荣霞，刘彦佩 等也对一类循环图给出了其交叉数上界【4 6 ，4 7 与循环图的交叉数有关 的其他结果参见【4 8 】- 5 l 】 ( 6 ) 联图的交叉数 与笛卡尔积图相比，两个图的联图是另一种运算，目前就联图的交 叉数讨论还很不充分，最先是b o g d a no p o r o w s k i 等在 5 2 】中证明了c r ( c 3 ) v g ) = 6 2 0 0 7 年，t a n gl i n g ，w a n gj i n g 5 3 等证明了： c r ( p mvr ) = 【m m + l n l _ 写_ l j ( m z1 , n 1 ，m 饥 m ，扎 5 ) c r ( v r ) 叫詈j 【字岣m l - - - “- r - j + l ( m 3 ，n 狙砌h n - i - i 6 ) c r ( vq ) = 【等儿竺jl - ；l 孚j + 2 ( m 3 ，钆3 ，m 饥 m ，n 6 ) 并假设在z a r a n k i e w i c z 猜想对7 m n 成立，则有： c r ( p mvr ) ：k 2 j m + l , nn + 1 j ( m 1 ，礼1 ，m i n m ，礼) 芝6 ) c r ( v r ) 引詈j 【萼j 【纠k - - 时互- 1 j + x ( m 3 , n 1 ，砌慨n - p 1 7 ) c r ( vg ) = 目【掣岣【孚j + 2 ( m23 舵3 ，咖 m n ) 27 ) 最近，黄元秋与他的硕士研究生也得到了一些小阶图与路r 联图的 5 高校教师在职攻读硕士学位论文 交叉数读者可参阅【5 4 】 2 有某种特点的图的交叉数的一些性质 因为具体确定某个图的交叉数比较困难，所以换个角度从交叉数的 性质如临界交叉数，正则图的交叉数，交叉数的奇偶性等着手研究( 文 献 5 5 一 5 9 】) ，希望能得到图的交叉数的一些比较好的性质 3 图g 及其线图l ( g ) 的交叉数之间的关系 图g 的线图l ( g ) 是指顶点集为e ( g ) 的图，其中两个顶点相连当且 仅当它们在g 中为相邻的边一般来说，图g 和它的线图l ( g ) 的交叉 数满足c r ( a ) c r ( l ( g ) ) 上世纪六十年代初，s e d l a c e k 6 0 】得到一个平面图g 的线图l ( g ) 是 平面图的充要条件1 9 7 9 年，k u l l i ，a k k a 6 1 】等获得了一个平面图的线图 的交叉数为1 的充要条件1 9 9 7 年a k k a ，j e n d r o f , k l e s c 等研究了平面图 的线图的交叉数为2 的情形【6 2 】 受到这些文献的启发，应用并创新某些方法，在m k 蛾等人研究阶 数较小的图与星图岛的笛卡儿积的交叉数的基础上，本文给出了鲍4 等 3 个六阶图与星图& 的笛卡儿积的交叉数，以及4 个五阶图与路的联图 的交叉数所用方法有数学归纳法，反证法，以及利用矩阵为工具研究 图的交叉数分布情况等 6 关于图的交叉数研究 2 基本概念和性质 本章给出涉及到的基本概念和性质，未作特别说明时均同文献【6 3 】； 且无特别说明所涉及的图均指简单连通图 一个图g 是指一个有序三元组( y ( g ) ，e ( g ) ，惦) ，其中v ( c ) 是非空 的顶点集，e ( g ) 是不与v ( g ) 相交的边集，而惦是关联函数，它使g 的每条边对应于g 的无序顶点对对任何边子集e e ( g ) ，用( ) 表示 由边集e 7 导出的子图；特别的令e 为图g 的一条边，用g 【e ) 表示从g 中删除边e 后所得到的图图g 中一个度为k 的顶点，我们称为k 度点 定义2 1 图g 在画法西下的交叉数是指在画法咖下边与边产生的 交叉点的个数，用c f 西( g ) 表示 定义2 2 图g 的交叉数，用c r ( g ) 表示，是指图g 在平面上的所有 画法下交叉数的最小值，即m i n c r 西( g ) 口 定义2 3 图g 在平面上的一个最优画法是指恰好达到交叉数的画 法 定义2 4 图g 在平面上的一个好画法是指图g 在平面上的画法满 足以下四个条件： 1 ) 连接同一个结点的任意两条边不相交； 2 ) 边不能自身相交； 3 ) 任何两条相交的边最多交叉一次； 4 ) 没有三条边交叉于同一个点 注1 定义2 4 中第四种画法是为了研究而统一规定不允许的前三 种画法1 ) ，2 ) ，3 ) 在最优画法中是不会出现的，因为如果出现这些情况，我 们可以对画法改进，从而可以得到一个具有更小交叉数的画法( 见图2 - 1 ， 7 高校教师在职攻读硕士学位论文 图2 - 2 ) 图2 - 1 ：图g 的好画法中不允许出现的四种 图2 - 2 ：对图2 - 1 中前三种画法的改进 注2 定义2 1 一定义2 4 中的“平面”可改为“曲面”，且相关定义可 推广到曲面的情况目前国内外大多是对在平面上的交叉数的研究，但 也有讨论环面等曲面上的交叉数( 见文献 6 4 】) 在这里我们仅讨论平面上 的情形 定义2 5 设图g 在平面上的一个画法为，h 是g 的子图，则在 子图日上的限制画法为画法中与子图日有关的部分，记做e 1 日 定义2 6 设图g 在平面上的一个画法为，g 在咖中的交叉点是指 在咖中图g 的两条边和非结点处的相交点 例如，图2 - 3 中z 是一个交叉点 定义2 7 设图g 在平面上的一个画法为，则将由顶点，边，交叉 点以及边的片段围成的部分称为在画法下的一个区域 例如，在图2 - 3 中分别指出了完全图蚝在画法下的8 个区域 两个图g - 和g 2 的笛卡儿积图用g 。g 2 表示，它是这样的图： 点v ( g l g 2 ) = v ( c 1 ) xy ( g 2 ) ；边集e ( c 1 g 2 ) = ( u ，v j ) ，( u _ i i ，v k ) i u t = 札 且 吻，v k ) e ( g 2 ) ，或者吻= v k 且 u i ，u h e ( g 1 ) ) 在笛卡尔积g & r * ( i 况 觎 ) 关于图的交叉数研究 中，晶表示星k l ，n ，我们可以方便的用g o ，g 1 g t l 表示g 的n + 1 个拷 贝 两个点不相交的图g - 和g 2 的联图，用g - vg 2 表示，它是在g 。和 g 2 的并图中，把g ，的每个顶点和g 2 的每个顶点连接起来所得到的图 设为图g 的好画法，若g 。，g 。和g 。为g 的边不相交子图，用 c r ( e ( g 。) ，e ( g 2 ) ) 表示发生在图g - 的边与g z 的边之间的交叉数，显然有： 引理2 1 令是图g 的一个好画法且g 1 ，g 2 和g 3 是图g 的彼此互 不相交的边集，则有 ( 1 ) ( g lug 2 ) = 哪( g 1 ) + 哪( g l ，g 2 ) + c r y ( g 2 ) ； ( 2 ) ( g 1ug 2 ，g 3 ) = c ( g l ，g 3 ) + c r y ( g ：，g 3 ) ( 3 ) c r ( g t ) c r ( v ) ，( i = 1 ，2 ，3 ) 若对于图f 某些边加入或抹平2 度点( 均可反复多次) ，得到的图与 图日同构，则称f 和何同胚，记为f 日以下引理是显然的 引理2 2 若f 日，则有c r ( f ) = c r ( h ) 图2 - 3 ：k 5 在画法下的8 个区域：r ( i = 1 ，2 ，8 ) 9 关于图的交叉数研究 3 五阶图与路r 的联图的交叉数 到目前为止关于两个图的联图的交叉数的讨论还很不充分，最先仅 有b o d g a n 5 2 】等人证明了c r ( c 3v 倪) = 6 ，在此基础上，后来唐玲等人给出 了vg ，vr 以及p mvr 的交叉数( 【5 3 】) 最近，李波等人得到了 一些小阶图与路r 的联图的交叉数( 1 5 4 1 ) 此外，未曾发现有联图的交叉 数的文章出现基于此目的，在这章中我们将讨论四个五阶图与路的联 图的交叉数这四个五阶图见图孓1 g ig 奎g sg 4 图3 - 1 ：4 个五阶图 3 1 g vr ( t = 1 ，2 ) 的交叉数 因为g t = p s ，g 2 = g ，由文献 1 4 】，我们有以下定理 定理3 1 1c r ( a , vr ) = z ( 5 ，n ) ，n 1 定理3 1 2 凹( g 2vr ) = z ( 5 ，n ) + 1 ，n 1 3 2 g ivr ( t = 3 ，4 ) 的交叉数 为了得到g 3 与路r 的联图的交叉数，首先构造一个新图风：在顶 点集划分为 t t ，t z ，n ) 和 v l ，也，1 1 3 ，v 4 ，u s 的完全2 一部图蚝，n 中，增加 4 条边v l v 3 ， u 1 v 2 ，i ) 2 1 4 ，v 1 显然，以中包含几个5 度点，3 个礼+ 1 度 点，1 个n + 2 度点，1 个n + 3 度点，5 n 十4 条边( 如图3 - 2 ) 不难发现 1 1 高校教师在职攻读硕士学位论文 4 = g 3 u 蚝m 其中蚝，n 的5 个礼度点和g 3 是相同的用正( 江1 ，2 ，礼) 表示与顶点t t 关联的边集( 见图参3 左边) 显然有 风= g 3uk 5 ，n = g 3u ( u 于) ( 3 1 ) i = 1 图3 - 2 ：巩 图3 - 3 ：f 与pup 引理3 2 1 设是以的一个好画法，若存在1 i 歹竹，使得 c ( ，p ) = 0 ，则c r ( g 3 ，t i u p ) 1 证明因为c ( p ，p ) = 0 ，所以t ut j 由导出的子画法妒必同构 于图3 3 右边的图因为g 3 包含一个3 度点，所以g 3 的边和t ut j 在 画法下至少有一个交叉，即c t 毋( g 3 ，t u p ) 1 _ 定理3 2 1 口( 以) = z ( 5 ，n ) + 引，n 1 证明：由图3 - 2 的画法知道 c r ( 以) z ( 5 ，n ) 4 - 【昙j( 3 2 ) 1 2 关于图的交叉数研究 因此，我们只需证明不等式3 2 的反向不等式成立，即 c r c h ) z ( 5 ，n ) + 目 ( 3 3 ) 为了证明不等式3 3 ，我们对n 用数学归纳法当n = 1 时，不等式3 3 显 然成立当t ：2 时，因- 2 包含一个子图同胚于k 3 3 所以 c r ( 风) c r ( k 3 ，3 ) 1 = z ( 5 ，2 ) + 【去j n 即，不等式3 3 对n = 2 成立现在假设对于z n ，有 c k g , ) z ( 5 ，f ) + 嘲 ( 3 4 ) 同时，假设存在巩的一个好画法砂使得 c r 咖( ) 1 ) 则h 可以收缩到点o ( 见图 4 - 4 ) ( 或6 ( 见图4 - 5 ) ) 且交叉数至少减少2 图4 - 4 ：h 收缩到点a 交叉数至少减少2 图4 - 5 ：日收缩到点b 交叉数至少减少2 若对任意i = 1 ，2 ，3 ，4 都有q 1 且c 1 ，则 4 ( q + ) 8 i = 1 由不等式( 4 1 ) 可以得出 4 ( 甄+ z ：) 4 i = 1 ( 4 1 ) ( 4 2 ) 高校教师在职攻读硕士学位论文 又因为g 日包含子图同胚于，4 所以c r ( g 】；f ) c r ( 蚝，4 ) = 2 于是 4 2 ( 戤+ ) 4 ( 4 3 ) i = l 下面根据( 戤+ z ：) 的值分三种情况讨论 情形1 ( 戤+ z ：) = 2 显然方程蚤4 ( 而+ ) = 2 的非负整数个数为( 8 + 三一1 ) = 3 6 但根 据图，4 的对称性，这3 6 个解又可分为4 种情形不失一般性，我们可 以假设为以下4 种解 ( 1 ) ( 3 ) ( 2 ) ( 4 ) 对于前三种解我们总可以将h 收缩到点b 使得交叉数减少2 具体 收缩方式见图4 6 2 2 1 0 0 0 0 1 0 0 1 0 0 o 1 0 0 0 研勉如孔呓 研现黝孔q砭 1 1 0 0 0 0 0 o 2 0 0 0 0 0 o 0 n娩弛吐吐 研现如孤吐吐吐 关于图的交叉数研究 口 i ：解为( 1 ) 时的收缩方式 ( i i ) ：解为( 2 ) 时的收缩方式 ( i i i ) ：解为( 3 ) 时的收缩方式 图4 - 6 ：h 收缩到点b 且交叉数减少2 高校教师在职攻读硕士学位论文 当解的形式为第四中情形，显然，此时日边上的两个交叉一定是g 的边与h 的边相交得到而由好画法可知，此时日至少有三条边上有交 叉显然与假设矛盾 4 情形2 ( 魏+ ) = 3 i = l 若存在i l ，2 ，3 ，4 ，使得戤2 不失一般性，设x 1 2 则可按图 4 - 6 ( 1 1 1 ) 方式将日收缩到点b 且交叉数减少2 d 若对于任意z = 1 ，2 ，3 ，4 ，都有搦1 此时根据的对称性，( 毛+ ) = 3 的解只有如下3 种情形 z 1 z 2 z 3 z 4 x i z ： z ： ( 2 ) z 1 z 2 z 3 z 4 z i z ： z ： ( 3 ) z 1 z 2 z 3 z 4 z j z ： z ： 吐 不管是那种情形的解我们都可以用类似于情形1 的分析，不难发现 日可以收缩到点b 或a 且交叉数减少2 4 情形3 ( x i + z ：) = 4 i = l 若存在i 1 ，2 ，3 ，4 ) ，使得x i 2 ，不失一般性，设z 1 2 ，且= 0 则 可如图4 - 6 ( i i i ) 方式将日收缩至点b 且交叉数减少2 若对任意i = 1 ，2 ，3 ，4 ，都有戤1 ，x ：1 ，此时根据日的对称性， ( 甄+ ) = 4 的解只有以下5 种情形 2 4 1 1 o 0 1 0 0 0 关于图的交叉数研究 ( 3 )( 4 ) z 1 z 2 z 3 飘 耐 z ； z ： z ： 对于前4 中解的情形，类似于情形1 的分析，不难发现日可以收缩 到点b 或n 且交叉数减少2 对于第五种情形，g 日的画法必同构于图 垂7 ( 口) ( 其中图中的圆圈表示图g ) 此时，我们可以修改画法( 见图4 - 7 ( b ) ) ， 于是同图4 - 6 ( i i ) 将h 收缩至点b 且交叉数减少2 图4 _ 7 修改画法 2 5 1 1 l 0 1 0 0 o 研现瓤吐吐 1 l 1 0 0 0 0 1 钆沈现瓢吐西矗吐 1 1 0 o 0 o 1 1 研勉如乳吐呓吐 1 1 0 o l 0 1 0 1 l 0 0 1 1 0 o 研现奶孔吐吐 高校教师在职攻读硕士学位论文 综合以上各种情况分析，引理4 1 1 证毕 _ 黄元秋，赵霆雷在文献【3 6 】中得到了完全孓部图，4 n 的交叉数即 如下引理 引理4 1 2c r ( 恐，4 ，n ) = z ( 6 ，n ) + 2 n 图乒8 尬4 & 的一个好画法 4 2 乃x d = 1 ，2 ，3 ) 的交叉数 定理4 2 1c r ( 鲍。4 晶) = z ( 6 ，礼) + 4 n 证明：由图垂8 可知：盯( k 2 ，4 ) z ( 6 ，n ) + 4 n 下面我们证明相 反的不等式设妒是k 2 4 & 的一个最优画法在画法下，我们将，。 的所有边收缩成一点t ；，此时所得到的图同构于完全3 部图 4 。，由引理 4 1 2 可知 ，c r ( k 2 4 n ) = z ( 6 ，n ) + 2 n 又由引理4 1 1 可知，每收缩一个鲍4 至少减少2 个交叉数，现收缩 2 6 关于图的交叉数研究 n 个4 ，所以至少减少交叉数2 n 个于是有 c r ( 鲍，4 & ) c r ( k 2 ，4 ，n ) + 2 n = z ( 6 ，n ) + 2 n + 2 n = z ( 6 ，n ) + 4 n 定理4 2 1 得证 一 定理4 2 2c r ( 乃x ) = z ( 6 ，7 ) + 4 n ，u = 2 ，3 ) 证明：图4 _ 9 是r & 一个好画法，图4 - 1 0 是f 3 的一个好画 法显然，不难发现 c r ( b 晶) z ( 6 ，n ) + 4 n ，( j = 2 ，3 ) 又因为乃x 岛u = 2 ，3 ) 包含子图同胚于k 2 ，4 由引理2 1 及定理4 2 1 可知 汀( 毋岛) 之钟( k 2 ，4 & ) = z ( 6 ，珏) + 4 n ，0 = 2 ，3 ) 于是定理4 2 2 得证 2 7 高校教师在职攻读硕士学位论文 图垂9 见x & 的一个好画法 图4 - 1 0f 3 & 的一个好画法 2 8 关于图的交叉数研究 5 后记 全文着重研究了一些小阶图与路的联图的交叉数以及与星图的笛卡 尔积图的交叉数其中最主要是创造性的确定了k 2 t 的交叉数所 用方法也有创新之处正如摘要中提到的一样，目前对于交叉数的研究 主要集中在两个方面：其一是确定具体图类的交叉数；其二是研究交叉 数的性质值得说明的是本文所研究的都是确定具体图类的交叉数，忽 略了对与图的交叉数有关的其它性质的研究，今后将从以下几个方面继 续进行： 1 确定完全2 一部图，n ( 仇n ) 的交叉数当m 6 时，。的交 叉数已经确定尽管z a r a n k i e w i c z 猜想为n 在其它情形时的交叉数给 出了一个较好的上界，但怎样确定它们的交叉数到目前为止仍然一无所 知因此这是本文作者今后的一个重要研究内容我们可以首先研究当 m = 7 ，8 时，n 的交叉数，发现新的规律和方法，最终部分解决或完全 解决z a r a n k i e w i c z 猜想同时，借助对完全2 部图交叉数的研究结果，我 们将有望确定其它完全多部图的交叉数 。 2 得到若干新的笛卡尔积图的交叉数尽管已有一些笛卡尔积图的 交叉数已经被确定，但国内外已有结果都是局限在第一个因子图点数较 小的情形下我们将不断深化已有的研究方法，在扩展第个或第二个 因子图成为其它更多更广的图类的基础上，研究笛卡尔积图的交叉数 3 研究图的交叉数与图的结构特征，图的其它参数之间的关系，研 究蛋正则图的交叉数的插值猜想等，但如何进一步探讨这些关系，仍有 着丰富的研究内容 4 确定图在其它曲面上的交叉数我们已经知道考虑图的交叉数必 须与曲面密切联系，我们将确定一些特殊图类在一些亏格较小的曲面上 的交叉数，如胎面，射影平面等 2 9 高校教师在职攻读硕士学位论文 综上所述，由于确定图的交叉数是n p 完全问题，而且当两个图的 在结构上出现细小差别时，就有可能需要使用完全不同的证明思路和方 法来计算它们的交叉数这导致研究过程缺乏参照性和连续性因而长 期以来，与交叉数有关的研究进展一直很难取得很大的突破一段实践 以来，研究图的交叉数主要集中在平面上，多采纯数学方法来证明，如数 学归纳法，反证法，组合法等等在证明过程中由于关系到交叉数的上 界或下界，甚至会出现一些繁琐的计算或必须使用局限性较大的技巧 这些方法对于某些图是适用的然而随着研究对象的阶数不断增大，其 画法的数量也急剧增加，采用原有的方法进行研究将越来越困难近年 来，在一些文章中出现了采用计算机进行分析或结合其它学科中相应方 法来探讨图的交叉数，这对我们今后的研究起到了很好的提示作用如 何尝试这些新的方法用以解决与交叉数有关的问题，是作者今后一段时 间内将面临的极具挑战性的工作 参考文献 m r g a r e ya n dd s j o h n s o n ，c r o s s i n gn u m b e ri sn p c o m p l e t e j ，s i a m j a l g e b r a i c d i s c r e t em e t h o d s4 ( 1 9 9 3 ) ，3 1 2 3 1 6 【2 】p t u r a n ，an o t eo fw e l c o m e j ，j o u r n a lo fg r a p ht h e o r y , 1 ( 1 9 7 7 ) ，7 - 9 【3 】f h a r a l p c k a i n e na n da j s c