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

关于图的交叉数的研究 摘要 图的交叉数是图论中的一个重要概念，目前图的交叉数问题已成为 国际上一个非常活跃的图论分支研究图的交叉数不仅具有重要的理论 意义，而且具有特有的实践意义，在许多领域有着非常广泛的作用，如 工业上电子线路板设计中的布线问题；生物工程d n a 的图示；软件开发 过程中文档部分的e r 图( 实体联系图) 等的自动生成等等 已经知道确定图的交叉数是一个n p 完全问题( 见文献【1 】) ，因此，到目 前为止有关交叉数的结果比较少，特别是对于星图与轮i v 的笛卡儿 积的交叉数，六阶图与星图& 的笛卡儿积的交叉数的研究更少本文首 先介绍了交叉数的背景和预备知识，然后在第二章证明了星图岛与轮 的笛卡儿积的交叉数为2 t ( - - f _ j + 【鸶j + 5 ，竹3 ，在第三章证明了轮矾与 星图晶的笛卡儿积的为交叉数为z ( 5 ，礼) + 2 n + 悖j ，几1 ，在第四章确定一 个六阶图f 与星图晶的笛卡儿积的交叉数为z ( 6 ，几) 十2 【罢j ，竹1 ，在第五 章确定了两个完全二部图去边后的交叉数即c r ( 凰，。e ) = z ( 3 ，n ) 一f 鸶1 + 1 ， c r ( 甄，。e ) = z ( 4 ，n ) 一f 碧1 + 1 最后提出了研究工作在发展中的一些问题 以及作者在以后将致力于前进的方向 关键词：交叉数；轮；路；星图；笛卡儿积；好画法 关于图的交叉数的研究 a b s t r a c t t h e c r o s s i n gn u m b e ro fag r a p hi sav e r yi m p o r t a n tc o n c e p ti ng r a p ht h e o r y i ti sh a sb o t ht h e o r i t i c a la n dp r a t i c a lm e a n i n g s a n di th a sb e e na p p l i e dt om a n y a r 船8 ，s u c ha st h ev s l ip r o b l e m ，e t c i ti sk n o w nt h a td e t e r m i n i n gt h ec r o s s i n gn u m b e r so ff 印h 8i sn p - c o m p l e t e ( 8 e e 【1 】) t h e r ea r eo n l yaf e wr e s u l t so nt h ec r o s s i n gn u m b e r so fg r a p h sf o ri t s c o m p l e x i t y i nt h i sp a p e r ，f i r s t l y , w ei n t r o d u c e8 0 m eb a c k g r o u n d s t h e nw ep r o v e t h ec r o s s i l l gn u m b e r so f 岛a n d 眠x & i nc h a p t e rt w oa n dt h r e e ，r e s p e c t i v e l y i nc h a p t e rf o u r ，t h ec r o s s i n gn u m b e ro ft h ec a r t e s i a np r o d u c to fa6 - v e r t i c e sg r 印h 8 w i t h 晶i sd e t e r m i n e d a n dw ep r o v et h a t 盯( g ，。e ) a n dc r ( g ，n e ) i nc h a p t e r f i v e k e y w o r d s ：c r o s s i n gn u m b e r s ；w h e e l ；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 i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的研究成果除了文中特别加以标注引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完全 意识到本声明的法律后果由本人承担 学位论文作者签名：联玲歇州年，f 月，p 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，研究 生在校攻读学位期间论文工作的知识产权单位属湖南师范大学同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分内 容编人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密缸 ( 请在以上相应方框内打誓 膏) 作者签名： 导师签名： 桉佩阢 该。劾。 日期：弘砷年1 月f 罗日 嗡刁年| l 旯i 即 关于图的交叉数的研究 第一章引言 图的交叉数是图论中的一个重要概念，从上个世纪七十年代初匈牙 利数学家p a lt u r a n 根据其在一个砖厂碰到的实际难题( t u r a n sb r i c kf a c t o r y p r o b l e m ) ( 见文献【2 】) ，从而提出了交叉数的概念以来，图的交叉数问题逐 渐成为国际上一个非常活跃的图论分支，很多图论专家对这方面进行了 深入研究研究图的交叉数不仅具有重要的理论意义，而且有较强的现 实意义，在许多领域有着非常广泛的应用，例如。 ( 1 ) v l s t 中的圈布局问题； ( 2 ) 草图的识别与重画问题，具有比手写汉字识别更为广泛的应用领域； ( 3 ) 工业上电子线路板设计中的布线问题； ( 4 ) 生物工程d n a 的图示； ( 5 ) 软件开发过程中文档部分的e r 图( 实体联系图) 等韵自动生成 然而，文献【1 】证明了确定图的交叉数问题属于n p - 完全问题由于 其难度，目前国际上对交叉数的研究主要集中在以下几个方面： 1 特殊图类的交叉数其中一些给出了其交叉数的上下界或猜想， 但具体结果较少，主要有 ( 1 笛卡儿积的交叉数： 对于猜想c r ( xg ) ( m 一2 加，( 仇n ) ，r i n g e i s e n ，b e i n e k e ，m k 1 e 吾芒 和r i c h t e r ，j a ya d a m s s o n 等证明等号对m = 3 ，4 ，5 ，6 ，7 成立( 见文献【3 】 1 0 1 ) 从二十世纪后期起，捷克数学家m k 1 e 酌等人开始研究阶数较小的图 与路r ，星图& ，圈g 的笛卡儿积的交叉数( 见文献【1 1 【1 8 】) 由于阶数 为3 的连通图或同构于2 路或同构于3 圈，它与路r ，星图& 的笛卡 儿积的交叉数显然为0 因此系统的研究从4 阶连通图开始的 m k l 馘 高校教师在职攻读硕士学位论文 1 9 9 4 年确定了所有4 阶连通图与路r ，星图& 的笛卡儿积的交叉数( 见 文献【1 3 】) 之后，他又陆续给出了所有5 阶连通图与路r 的笛卡儿积的 交叉数( 见文献f 1 4 - 1 8 】) ，以及给出了部分五阶连通图与星图& ，圈g 的 笛卡儿积的交叉数 ( 2 ) 完全图的交叉数： 关于完全图的交叉数的猜想： c r ( ) = ：1l 2 jl 孚j 【孚j 【字j 目前仅证明了等号对于n 1 0 成立汀( g ) 表示图g 的交叉数；h 表 示不超过竹的最大整数 ( 3 ) 完全二部图的交叉数： t u r a n 的“砖厂问题”实际上等价于确定完全2 一部图。的交叉数 z a r a n k i e w i c z 在文献【2 】中“证明 了 c r ( ，n ) = 【筹儿竺jl 三jl 竺 j ，( m n ) 但r i n g e l 和k a i n e n 不久各自独立发现z a r a n k i e w i c z 在文献【2 】中的证明 有误( 参见文献 1 9 】) ，因而确定完全2 一部图，。的交叉数问题目前仍然 是一个公开问题习惯上把上式称之为z a r a n k i e w i c z 猜想，把上式右端 记为z ( m ，n ) d j k l e i t m a n 在1 9 7 0 年证明了等号对于m i n ( m ，礼) 6 时成 立( 见文献 2 0 1 ) w o o d a u 于1 9 9 3 年证明了当m = 7 且n 1 0 时等号也成 立( 见文献 2 1 】) 到目前为止还没有关于此方面的新结果 ( 4 ) 完全三部图的交叉数： 上世纪八十年代，k a s a m o 证明了c r ( k 1 3 。) = z ( 4 ，n ) + 【詈j ，c r ( ，3 ，。) = z ( 5 ，礼) + 礼( 见文献【2 2 】) 最近黄元秋教授证明了c r ( k 1 ，a ，。) = n ( n 一1 ) = z ( 5 ，n ) + 2 吲( 见文献【2 3 】) ；后梅汉飞教授又与黄元秋教授合作证明了c r ( 艇，跏) = z ( 6 ，n ) + 4 引( 见文献【2 4 1 ) ；2 0 0 5 年黄元秋教授又与赵霆雷合作证明了 一2 关于图的交叉数的研究 k 2 ，4 ，。= z ( 6 ，n ) + 2 n ( 见文献【2 5 1 ) ；同时在假设z a r a n k i e w i c z 猜想对于m = 7 成立的前提下，黄元秋教授与赵霆雷确定了c r ( k ，6 ，n ) = z ( 7 ，n ) + 6 【刳( 见 文献【2 6 】) ；其后不久又在假设z a r a n k i e w i c z 猜想对于仇= 8 ，m = 9 成立的 前提下，确定了艇，功，8 ，n 的交叉数( 见文献【2 7 2 8 1 ) 2 有某种特点的图的交叉数的一些性质 因为具体确定某个图的交叉数比较困难，所以换个角度从交叉数的 性质如临界交叉数，正则图的交叉数，交叉数的奇偶性等着手研究( 文 献【2 9 】障】) ，希望能得到图的交叉数的一些比较好的性质 3 线图的交叉数 l ( g ) 表示图g 的线图，已经证明了c r ( l ( a ) ) = 1 与c r ( l ( g ) ) = 2 的充 分必要条件( 见文献【3 6 ， 3 7 】) 受到这些文献的启发，应用并创新某些方法，在m k l 荫苞等人研究阶 数较小的图与路r ，星图岛，圈g 的笛卡儿积的交叉数的基础上，本文 给出了星图与轮眠的笛卡儿积的交叉数，轮与星图& 的笛卡儿 积的交叉数，一个六阶图与星图晶的笛卡儿积的交叉数以及几个完全二 部图去边后的交叉数 下面给出以后各章节涉及到的基本概念和性质，凡未说明的概念均 同文献【3 s ，f 3 9 】；且无特别说明所涉及的图均指连通简单图 一个图g 是指一个有序三元组( y ( g ) ，e ( g ) ，惦) ，其中v ( a ) 是非空的 顶点集，e ( g ) 是不与v ( c ) 相交的边集，而惦是关联函数，它使g 的 每条边对应于g 的无序顶点对对任何边子集e ( g ) ，用e ) 表示由 边集e 7 导出的子图；特别的令e 为图g 的一条边，用g e ) 表示从g 中 删除边e 后所得到的图图g 中一个度为k 的顶点，称之为珏度点 定义1 图g 在画法下的交叉数是指在画法下边与边产生的交 3 高校教师在职攻读硕士学位论文 叉点的个数，用c r , ( g ) 表示 定义2 图g 的交叉数，用仃( g ) 表示，是指图g 在平面上的所有画 法下的交叉数的最小值，即m i nc r 毋( g ) ，咖取遍图g 在平面上的所有好画 珊 法 定义3 图g 在平面上的一个最优画法是指恰好达到图g 的交叉数 的画法 定义4 图g 在平面上的一个好画法是指图g 在平面上的画法满足 以下四个条件： 1 ) 连接同一个结点的任意两条边不相交； 2 ) 边不能自身相交； 3 ) 任何两条相交的边最多交叉一次； 4 ) 没有三条边交叉于同一个点 注：定义1 定义4 中的“平面”可改为“曲面”，且相关定义也可推 广到曲面的情况目前国内外大多是研究平面上的交叉数，但也有研究 环面等曲面上的交叉数的( 见文献【2 6 】) 在本文中作者仅讨论平面上的交 叉数 两个图g 。和g 2 的笛卡儿积用g ，g 2 表示，它是这样的图：点 集v ( g l g 2 ) = v ( a 1 ) v ( a 2 ) ；边集e ( c l g 2 ) = ( 吻) ，( u 。，) ) ：= u n 且 ，) e ( g 2 ) ，或者“，) e ( g 1 ) 且= ) 用星图& 表示完全 二部图k 。”在笛卡尔积g & 中，可以方便的用g o ，g 1 g ，l 表示图g 的t t - 4 - 1 个拷贝 令咖为图g 的好画法，若g z 和g z 为g 的边不相交子图，用哪( e ( g ) ) 表示在好画法下发生在图g 的边上的交叉的数目；用c r 曲( e ( g 1 ) ，e ( g 2 ) ) 表示发生在图g 。的边与g 。的边之间的交叉数，其中g ，g 。是边互不相 4 关于图的交叉数的研究 交的图显然有， 引理2 1 令咖是图g 的一个好画法且g l ，g 2 和g 3 是图g 的彼此边互不 相交的子图，则有 ( 1 ) c r 4 ( e ( g , ) ue ( g 2 ) ) = c r 妒( e ( g 1 ) ) + 仃西( e ( g 1 ) ，e ( g 2 ) ) + c r 庐( e ( g 2 ) ) ( 2 ) c r 4 ( e ( g 1 ) ue ( g 2 ) ，e ( g 3 ) ) = c r 毋( e ( g 1 ) ，e ( g 3 ) ) + c r 妒( e ( g 2 ) ，e ( g 3 ) ) ( 3 ) c r ( g ) c r ( g ) g = l ，2 ，3 ) 若在图f 的某些边上加入或抹平2 度点( 均可反复多次) ，得到的图 与图h 同构，则称图f 和图日同胚，记为f 一日由同胚的定义易知： 叫f ) = c r ( 日) 一5 一 关于图的交叉数的研究 第二章星图& 与轮眠的笛卡儿积的交叉数 r 表示长为n 的路，晶表示星图k 1 n ，轮巩表示由一点到一个圈的 悬挂，也就是从独点凰向圈g 的所有个点分别连一条边所得到的图，其 中g 表示长为礼的圈图g 的顶点个数用v ( v ) 表示，如果v ( e ) = 几那 么我们就称图g 为n 阶图在文献【1 3 】中m k l e 琵证明了星图岛与4 阶 图的笛卡尔积的交叉数，在文献【1 5 】中m k 埘苞又证明了完全二部图鲍，3 与星图& 的笛卡尔积的交叉数，在文献【4 5 】中于平证明了轮巩与路岛 的笛卡尔积交叉数，但是对于轮与星图的笛卡尔积交叉数却一直 没有结果本章中证明了星图岛与轮眠的笛卡尔积的交叉数 下面是本文的一个主要定理t 定理2 1 c r ( 岛) = 2 【与半j + 【鸶j + 5 ，n 3 为了方便证明星图岛与轮的笛卡尔积的交叉数，记岛眠的点 为戤，z = a ，b ，c ，d ；i = 0 ，1 ，2 肌边为死+ 1 个星g ，4 个轮瞬，其中z o 为 哚的n 度点( 即中心点) 设正i = 1 ，2 竹为由点a o ，b o ，c o ，d o ，a i ，兢，q ，也及 边( a o ，d t ) ，( b o ，兢) ，( c o ，白) ，( d o ，吨) ，( 吼，玩) ，( c ，玩) ，( 吨，玩) 构成的子图，如图2 1 ( a ) 并先给出下面的两个引理 ( a ) 正 孙 吣) ( b ) 岛 图2 1 ( c y r 一1u 死 引理2 1 设d 为昆眠的一个好画法，若在好画法d 中c r d ( 死一l u 死) = 0 ， 7 一 高校教师在职攻读硕士学位论文 则盯d ( 岛，瓦一1u 死) 1 、 证明：令矿为d 导出的耳一lu 的子图，如图2 1 ( c ) ：d 将平面分 成四个区域，而6 0 ，而位于两个不同的区域，根据j o r d a n 曲线定理，要连 接6 0 ，d o 两点，边( b o ，d o ) 与d 。的边至少交叉一次，即甜d ( s o ，瓦一l u 死) 1 引理2 2 设d 为岛x 眠的一个好画法，若在好画法d 中( 死一1 u 已) = 0 ， 贝1 ic r o ( v , ，一1u 冗) 2 ，i = 1 ，2 ，礼 证明：如图2 1 ( c ) ：在由死一，u 瓦导出的子图驴中，任意一个区域只包 含a o ，b o ，c o ，d o 中的两个点，且任意两个相邻的区域中最多只包含a 。，b o ，c o ，d o 中的三个点现在考虑由一。u 已u 互( 江1 ，2 竹一2 ) 导出的子图，不管 把a t ，b i ，c d ，也是全部放在一个区域还是放在两个或者两个以上的区域，正 与死一lu 瓦至少发生两次交叉即c r d ( 互，瓦一1u 矗) 2 图2 2p ax 眠 图2 3 岛x 8 啼 关于图的交叉数的研究 定理2 1 ：c r ( 昆) = 2 【与芋j + 【詈j + 5 ，n 3 证明：首先证明c r ( 魄) 2 【与竽j + 【詈j + 5 图2 2 和图2 3 分别给出了s 3 巩与忍眠的一个好画法，通过比 较，可以发现图2 3 比图2 2 只多了连接b 0 和d o 引起的交叉数【刳+ 1 ，而根 据文献 4 5 】c r ( 岛帆) = 2 l l 学- j + 4 ，所以凹d ( 岛) 2 【垃j + l 詈j + 5 下面用数学归纳法进行证明c r ( 岛w n ) 2 【华j + 【詈j + 5 当仃= 3 时，岛w 3 与s 3 致同构，根据文献 1 3 】c r ( 岛弛) = 8 ， 则，盯( 岛) = 8 假设上式对于大于3 小于几的整数都成立，下面我们 考虑s 3 的一种好画法d ，根据死是否与其他互有交叉，分两种情 况： ( i ) 若c r d 僻，死) 1 对任意的江l ，2 n - 1 都成立，则咖( u e - - ? 正，死) 礼一1 那么在岛帆中移去死中的所有边，得到一个同胚于岛帆一1 的图利用归纳假设，得 c r o ( s 3 v ) c r o ( s 3 v 一1 ) + c ， d ( u 互，死) 2 【华孚j + 5 帕叫 = 2 【华抄5 ( 对n 分奇偶两种情况证明，过程如下) 9 一 高校教师在职攻读硕士学位论文 当礼= 2 k 时： 2 【学字j + 5 均- 1 ) = 2 【 当n = 2 k + 1 时： ( 2 k 一2 ) 2 4 = 2 ( k 2 2 k + 1 ) + ( k 一1 ) + 5 + ( 2 k 一1 ) = 2 ( k 2 一k ) + k + 5 2 【竿川孚帕_ 1 ) = 2 【 ( 2 k 一1 ) 2 4 + 5 j + l 孚j + 5 + 2 k = 2 ( k 2 一k ) + k + 5 + 2 k 2 掣+ 孚+ 54 2 2 【竿j+ 9 + 5 ( 2 ) 若存在i ，不妨设为礼一1 ，使得盯d ( 瓦_ l 死) = 0 则由引理2 ， 凹d ，瓦一1u 死) 2 ，i = 1 ，2 n 一2 ，则c ? ii ，n - 2 正，死一1u t n ) 2 ( n 一2 ) 同 时由引理2 1c r d ( 岛，已一1u 死) 1 ，那么在岛帆中去掉已一1u 死的所 一1 0 关于图的交叉数的研究 有边，得到一个同胚于s 3 一。的图。利用归纳假设，得； c r d ( s 3xw n j = c r d ( 岛一2 ) + c r d ( u 正，已一lu 瓦) + c r d ( s o ，瓦一lu 死) 2 【华字+ 2 ( n _ 2 ) + 1 = 2 【华川抄5 ( 与( 1 ) 中情形一样对n 分奇偶两种情况可证明，过程略) 证毕 盖业i 她壅 一 第三章 轮w 4 与星图r 的笛卡儿积的交叉数 士，位，噘【1 叫甲m - k 1 e 资给出t 皿r 和凰晶的交叉数以及在文 献f 4 j 中l w b e i n e k e 和r d r i n g e i s e n 给出了k 4 g ，的夺v 特3 办：二= ! 竺k 麟：圣孽到了蚝的交叉数，但是对于w 4x 瓯与& 萏萎 至登芝兰没亨结果本章中证明了轮胍与星图& 的笛毒菜积磊萎主 数为了证明轮啦与星图& 的笛卡尔积的交叉数，先构造下面爵。i 乏： 。、羔之墨兰样一个图：顶点集为 坳，仇，吻，蚴，蛳) ，其中蜘与奶( 1 i 4 ) 都有边相连，口t 一忱一蚴一地一功构成一个4 圈把0 矗l 嘉 曼? 二1 ：咙，地，坝) 与另外礼个顶点如o = 1 ，2 n ) 分别相连我们得到个 翌要，苎置三竺记为在图巩中，用五 ：1 2 一表示, , - - 苫j 羞；如妻 竺竺边苎( 见图3 2 ) ；用晶表示嗽中与顶点相关岳的i 集，葛葛妥 示中圈饥一现一均一舰一饥中的边集于是易得 ”6 “ 以唱呱u 吲正) ( 3 0 1 】， 玩 蟊蕊 遥切 夕， 图3 1 巩及其一个好画法 下面是本文的两个主要定理： 定理3 1 c r ( 巩) = 孢扎) + n + l 詈j ，n 1 定理3 2 盯( & ) = z ( 5 ，住) + 轨+ 【剽，佗1 1 3 图3 2 乃 高校教师在职攻读硕士学位论文 3 1 定理3 1 的证明 引理3 1 令是图g 的一个好画法且e 1 ，易和岛是图g 的彼此互不相 交的边集，则有 以，c r ( 毋ue 2 ) = c r 毋( e 1 ) + c r , ( e 1 ，易) - - i - c r 毋( 岛) j 俐盯曲( 日u 易，e 3 ) 1 1 _ c r ( e x ，e 3 ) + c 啷( 场，e 3 ) 证明：根据交叉数的定义，结果显然 引理3 2 令为图风的一个好画法，若m ，t 2 ) = 0 ，则有c r , ( e o u e 。，死u t 2 ) 3 ，且c r a t 3 ，乃ut 2 ) 4 u 1 图3 3c r 西m ，t 2 ) = o 时的好画法 证明：令h = ( 噩ut d ) 为风的边导出子图显然日同构于具有二部划 分【t 1 ，t 2 ) 和【咖，t ，1 ，忱，均， 的完全二部图鲍，5 因为唧( 噩，t 2 ) = 0 ，所以 子图h 的由导出的子画法必同构于图3 3 在图3 3 中，边集岛ue 中的边子集 咖忱，r o y 2 ，v l 地) 中的每一条边与边集噩u 死都至少有一个交 叉，于是可得c r 毋( 晶u b ，乃u t 2 ) 3 又因为( 乃u 死u 死) ) 的边导出子图 同构于完全二部图蚝，5 ，但是盯曲m ，t 2 ) = 0 则c r y ( t 3 ，7 1u t 2 ) c r ( 蚝，5 ) = 4 d 引理3 3 c r ( h 1 ) = 1 证明：因为皿有一子图同构于蚝 3 所以显然有c r ( h 1 ) = 1 口 定理3 1 c r ( 风) = z ( 5 ，n ) 十竹- t - 吲，n 1 一1 4 关于图的交叉数的研究 证明：下面我们先构造巩的一个好画法口：在平面直角坐标系上，把巩 的顶点集 伽，v l ，v 2 ，地，魄， 放在y 一轴上，其中坳放在原点，口l ，忱放在y 一 轴的正半轴上，地，钒放在y 一轴的负半轴上；把顶点集 - ，t 2 t n 放在x - - 轴上，其中【号j 个点放在负半轴，嘲个点放在正半轴，然后把各边用 适当的直线或者曲线表示出来，见图3 1 显然在图3 1 中，风 疡u 尻 同构于地。，且在伊下的子画法也正好就是蚝，。的一个最优画法( 见文 献【2 0 1 ) ，所以卿( 风【岛ue o ) = c r ( 蚝，。) = z ( 5 ，n ) ；而c r o ( e ou 及，正) = 2 ( 当t t 位于负半轴) ，c r o ( e ou 忍，互) = 1 ( 当t i 位于正半轴) ；且c r o ( e oue ) = 0 于是结合式3 0 1 及引理3 1 得 n 凹口( ) = c r o ( h e ou 玫) + c r o ( e ou 鼠，u 正) + c r e ( e ou 及) i = l = z ( 5 ，礼) + c r o ( e o ue 。，) + o o ( e ouz 。) i - - - - 1 = z ( 5 ，n ) + 凡+ 【芸j 根据交叉数的定义则易知c r ( g ) c r o ( h ) = z ( 5 ，n ) + + 【銎j ，扎1 所以我 们只需证明对于以的达到c r ( 风) 的好画法下，e r 曲( 风) z ( 5 ，竹) + n + 捌 由文献( 2 3 0 ，可得c r ( k 1 ，4 ，n ) = 礼( n 一1 ) = z ( 5 ，n ) + 2 吲由于玩忍同 构于尬。撕所以由式( 3 0 1 ) 及引理3 1 可得 c r 毋( ) = ( 玩噩) + ( 及，u t d + ( 玩) i = l n c r ( 硒，4 ，n ) + 哪( 尻，u 正) + c r 毋( 尻) i = l n = z ( 5 ，礼) + 2 【等j + c ( 忍，u 五) + c ，_ ( e ) r ( 3 1 2 ) 一 i = 1 所以若c r 咖( 取，u ：。正) 鸶1 ，财由式( 3 1 。2 ) ，可得 c ( 以) z ( 5 ，佗) + n + 【芸j 这样结论成立于是在下面的证明中我们假设凹( e ，u ：。正) 0 ，则c r 曲亿，e ot 9 最u 丑) 3 ，并且当c r 毋伍，最) 1 时， 才有c r y ( t , ，e oue cu 噩) = 3 ( 2 ) 在图3 5 ( a ) 中，当顶点岛( 2 i 功位于其他区域时则汜，e o u 尻u t 1 ) 4 于是利用与情况1 相似的方法也可得结论 而在图3 5 ( b ) ( c ) 中，不论顶点t i ( 2 i 礼) 位于标记哪个区域都有c r y ( t , ，e o u 噩u 乃) 4 于是在此情况下结论也成立 子情况2 2 ：对所有的岛q ，c 亿，e o ) 2 1 8 关于图的交叉数的研究 由于i n i 【鸶j ，结合引理3 1 及式( 3 0 1 ) 得 ( ) = c , - 母( e o u 尻u u 正) i = l nn = 哪( e ou 最，u 互) + 哪( 岛u 忍) 十( u 正) ( 佗一l q i ) + 2 i n i + z ( 5 ，n ) 于是结论成立 现在此定理证毕 = z ( 5 ，n ) + 几+ 1 q l z c s , n ) + n + 3 2 定理3 2 的证明 令h 为同构于眦的图用g 日表示把图h 的五个顶点与3 - 边连通图g 的其中五个顶点分别相连所得到的图；用g 备表示收缩图h 所有的边到 一点h 后所得蓟的图 j 1 个交叉 图3 7 边集易没有交叉 一1 9 高校教师在职攻读硕士学位论文 弓l 理3 4 c f ( g 备) c r ( g h ) 一1 证明：令妒为g 日的一个最优画法首先若把图h 的5 个顶点与一点z 都相连，则可得到一个同构于凰的图由于c r ( h 1 ) = 1 ，于是在画法妒下 在图h 的边上至少有1 个交叉令边集e 2 ：= 1 也， u 2 v 3 ， 0 3 7 1 4 ，v 4 v 1 ) ，于是按 边集马上的所发生的交叉数目分下面两种情况来讨论： 情况( 1 ) ：在画法妒下，边集如上至少有1 个交叉见图3 6 由于日含 有一个以为垂度点的子图& ，所以g h e 2 同构于g 备，且c r ( g 备) = c r ( g h z 免) c ( g 日易) c r v , ( g h ) 一1 = c r ( g h ) 一1 情况( 2 ) ：在画法矽下，边集易没有交叉，见图3 7 因为在图日的边 上至少有1 个交叉，所以在与顶点v o 关联的边上至少有1 个交叉，我 们假设边伽钉。上的交叉最多，则边u o v 。上的交叉数至少为1 于是我们 按着图3 7 所示方法收缩到点h ，则发生在边v o v - 的交叉就减少了，所 以c r ( g 备) c r , ( g z ) 一1 = c r ( g z ) 一1 口 定理3 2 c r ( 晶) = z ( 5 ，n ) + 2 n + 【詈j ，礼1 证明：在图3 8 中，将每个哦0 = 1 ，2 n ) 的边分别收缩到点如则得到 一个同胚于巩的图，且其对应的画法正好是巩的一个最优画法，收 缩后每个w i ( i = 1 ，2 n ) 也正好减少1 个交叉，所以可得盯( 胍x & ) z ( 5 ，n ) + 2 n + 吲下面我们证明相反的不等式也成立令妒为w 4 & 的一 个最优画法在画法妒下，我们将每个川的边分别收缩到点岛0 = 1 ，2 n ) 则得到一个同构于风的图于是根据定理1 及及反复应用引理3 4 可得 c r ( 胍& ) = c r 妒( w 4 晶) c r ( 风) + n = z ( 5 ，礼) + 亿十【三j + n = z ( 5 ，n ) + 2 n + 【j 2 0 关于图的交叉数的研究 证毕 图3 8w 4x & 的一个好画法 2 1 第四章一个六阶图f 与星图& 的笛卡儿积的交叉数 图g 的顶点个数用y ( g ) 表示，如果y ( g ) = n ，那么我们就称图g 为n 阶图r 表示长为n 的路， & 表示星，即虬，。本章中的f 均 指六阶图近年来，笛卡尔积图的交叉数的研究引起了人们的注意，文 献f 1 1 ，1 2 ，1 3 ，1 4 ，1 5 ，1 7 】确定了一类笛卡尔积图的交叉数。文献【4 5 】于平 等证明了p m 的交叉数，文献【1 6 】【1 7 】【18 】中m k l e s v 列举并证明了完 全图砥及它的一部分子图与路r ，圈瓯，星图& 的笛卡尔积交叉数， 文献f 4 2 】肖红兵等证明了一个六阶图与星图岛的笛卡尔积交叉数但 是对于大部分六阶图与路r ，圈g ，星图岛的笛卡尔积交叉数却一直没 有确定本章在此基础上证明了一个六阶图f 与& 的笛卡尔积交叉数 为z ( 6 ，竹) + 2 【考j 在这里【鸶j 表示不超过鸶的最大整数为了证明一个六 阶图f 与星图& 的笛卡尔积的交叉数，我们先构造下面的一个新图风： 图4 1 首先我们构造风的一个好画法d ：在平面直角坐标系上，把玩的顶 点集 伽， 1 ，忱，忱，) 放在y 轴上，其中咖放在原点，t j l ，也，放在可轴 负半轴上，鸭放在y 轴正半轴上；把顶点集 t t ，t 。，) 放在z 轴上， 其中l 薹j 个点放在负半轴，f 詈1 个点放在正半轴，然后把各边用适当的直 线或曲线表示出来，见图4 1 ( b ) 我们把6 条与t t 关联的边记为正见图4 2 2 3 高校教师在职攻读硕士学位论文 ( a ) 显然在图4 1 ( b ) 中，4 去掉边r o y l ， l 忱，v 2 v 3 ，v 3 v 4 ，v 4 v 5 ，v 5 v 0 ，r o y 2 ，r o y 4 后同构于完全二部图 下面是本文的两个主要定理： 定理4 1 c r ( h ) = z ( 6 ，n ) + 2 【鸶j ，n 1 ； 定理4 2 c r ( fx & ) = z ( 6 ，n ) + 2 【詈j ，礼1 4 1 定理4 1 的证明 为了证明定理4 1 和定理4 2 ，我们先给出下面的几个引理： 引理4 1 令d 是图g 的一个好画法，毋，易和局是图g 的彼此互不相 交的边集，则有 以，) c r d ( e 1ue 2 ) = c r d ( e 1 ) + c r o ( e 2 ) + c r d ( e 1 ，局) i 俐c r d ( e 1u 易，e 3 ) = c r d ( 局，e 3 ) + c r d ( e 2 ，e 3 ) 证明：根据交叉数的定义，结果显然 口 ( b ) 图4 2 ( c ) 引理4 2 令d 为也的一个好画法，若c r o ( v l ，t 2 ) = 0 ，则有盯d ( 只乃u 死) 2 证明：令日= 7 1u t 2 ，如图4 2 ( b ) 所示，显然日同构于完全二部图恐6 一2 4 关于图的交叉数的研究 因为c r d m ，t 2 ) = 0 ，所以h 的画法必同构于图4 2 ( b ) ，在图4 3 ( a ) 中，f 的边子集 伽t j 2 ，r o y 4 与乃u 死中的边至少要发生二次交叉，于 是c r d ( e 丑u t 2 ) 2 口 引理4 3 c r ( h 1 ) = 0 ，c r ( h 2 ) = 2 证明：由图4 3 ( b ) 知，胁为平面图，显然c r ( h 1 ) = 0 下面证明c r ( 阮) = 2 首先由图4 3 ( a ) 可知存在一种好画法d 使得c r d ( h 2 ) 2 成立，下 设c r d ( 岛) z ，那么在飓的画法d 中，去掉x 条边后成为平面图，根据 欧拉定理有：8 一( 2 0 一z ) + ，= 2 ，即，= 1 4 一z ，又因为去掉z 条边后的平面 图形的围长至少是3 ，所以2 ( 2 0 一z ) 3 ( 1 4 一z ) ，解得z 2 ，所以c r ( h 2 ) 2 ， 因此凹( - 2 ) = 2 口 图4 3 ( b ) 定理4 1 凹( 巩) = z ( 6 ，n ) + 2 【詈j ，礼l ； 证明：由图4 1 可知： c r ( 巩) z ( 6 ，n ) + 2 【刳n 1 我们对n 用归纳法 证明相反的不等式由引理4 3 我们可得c r ( h 1 ) = z ( 6 ，1 ) + 2 t ；j = 0 以及 c r ( 也) = z ( a ，2 ) + 2 t - g j = 2 即当n = 1 ，n = 2 时结论成立 2 5 高校教师在职攻读硕士学位论文 现在假设当n 3 时： c r ( 风一2 ) z ( 6 ，n ) + 2 【j 现在考虑巩的一个好画法d 使得，c r d ( 以) z ( 6 ，n ) + 2 【孙 情形1 ：若存在两个正，t j ( 1 i ，歹n ，i 歹) 使得汀d ( 正，乃) = 0 不失 一般性，不妨设为死“使得c 7 d 陬- 1 死) = 0 由于对于每一个i ( i = 1 ，2 ，n - 2 ) ，已u 已一l u 互同构于蚝，6 ，而且c , - ( k 3 ，6 ) = 6 ，因为c r d ( t - l ，死) = 0 ，所以有： c r o ( t , , u 瓦一1 ，互) = c 7 d ( 蚝，6 ) 一c r o ( t u 足一1 ) 一c r o ( t , ) 6 0 0 = 6 又fu ( 旧正) 同构于玩一2 ，再根据引理4 2 n 一2 c r d ( 风) = c r d ( t u 死一1u ( f uu t d ) i - - - - - 1 n - - 2 = c r d ( 死u 瓦- 1 ，u 正) + c r o ( t u 死“f ) i = l n - 2 + c r d ( fuu 正) i = l 6 ( n 一2 ) + 2 + c r d ( 风一2 ) z ( 6 ，n ) + 2 t 罟j 情形2 ：若对任意两个正，t j ( 1 i ，j n ，i 歹) 都有c r d ( t , ，t j ) 1 ，则 仃d ( 4 ) = c r d ( 甄，。) + c r d ( f ) + c r d ( 只k 6 ，。) z ( 6 ，n ) + c r d ( f ) + c r d ( 只k 6 ，n ) = z ( 6 ，竹) + c r d ( 只u 互) i = 1 根据前面的假设，( 以) z ( 6 ，竹) + 2 【昙j 综合情形1 ，2 可知对于风的任意画法d 都有c r d ( 巩) z ( 6 ，n ) + 2 【詈j 成立，则盯( 风) = z ( s ，他) + 2 引( 讥1 ) ，证毕 b 4 2 定理4 2 的证明 定理4 2 盯( f & ) = z ( 6 ，礼) + 2 【詈j ，n 1 证明：由图4 4 可知存在一种好画法d 使得凹( f & ) z ( 6 ，钆) + 2 【鸶j ( n 1 ) 又因为fx & 包含一个同构于风的子图，再根据定理4 1 有 2 7 高校教师在职攻读硕士学位论文 c r ( f 晶) z ( 6 ，n ) + 2 i 鸶j ，因此c r ( f & ) = z ( 6 ，礼) + 2 t 詈j ( n 1 ) ，证毕口 图4 4 2 8 关于图的交叉数的研究 第五章几个完全二部图去边后的交叉数 从上个世纪七十年代初匈牙利数学家p a lr i k 缸根据其在一个砖厂碰 到的实际难题( t u r s n sb r i c kf a c t o r yp r o b l e m ) ( 见文献【2 】) ，从而提出了交叉 数的概念以来，图的交叉数问题逐渐成为国际上一个非常活跃的图论分 支然而t u r a n 的“砖厂问题”实际上等价于确定完全2 部图。的交 叉数z a r a n k i e w i c z 在文献【2 】2 中“证明”了 c r ( ，。) = 【等儿竺儿等儿堡 j ，( m n ) 但r i n g e l 和k a i n e n 不久各自独立发现z a r a n k i e w i c z 在文献【2 】中的证明 有误( 参见文献f 1 9 1 ) ，因而确定完全2 - 部图，。的交叉数问题目前仍然 是一个公开问题习惯上把上式称之为z