（计算机软件与理论专业论文）Flower+Snark和Kltmgte□Pltngt的交叉数.pdf

大连理工大学硕士学位论文 摘要 图的交叉数是衡量图的非平面性的一个重要参数，计算图的交叉数是非常困难的， g a r e y 和j o l l 璐o n i l 】在1 9 8 3 年证明了计算图的交叉数问题是n p 完全的。目前只有很少的 图的交叉数的精确值是已知的，比如广义p e t e r s e n 图p ( 万，3 ) ，所有5 个顶点的图与路径 的交图等，而完全图、完全二分图等图族的交叉数仍然是拓扑图论中待解决的难题。 本文对三正则图f l o w e rs n a r k 及其相关图只伽3 ) 和t w i s t e df l o w e rs n a r k 及其相 关图e 0 3 ) 的交叉数进行了研究，分别给出了这两类图的交叉数的精确值。证明了 仃( e ) = 2 、c r ( f a = 3 、c r ( e ) = 4 、口( e ) = n ( n 6 ) ( e ) = l 、仃( e + ) = 2 、e r ( e ) = 4 、e r ( 只) = n ( n 6 ) 另外本文还研究了路径与图j 乙一p 的交图蚝一阳只的交叉数。首先给出了这类图的 交叉数上界： c r c 乏一阳班c 川，弓l 孚j 【刊龇字h 竿儿刊吐刊一褂+ 吉【字心l 字儿字卜s 脏 同时给出了x 。一e 口只的交叉数下界公式： c r ( 足：一e d p ) ( r - - 1 ) c r ( k + 2 2 k 2 ) + 2 c ，( k 册+ l p ) ，所4 ，疗i 进一步本文确定了疋一e q p 的交叉数： 仃( 瓦一阳只) = 1 2 n ，刀1 关键词：交叉数；交图；路径；正则图；完全图 查垄里奎堂堡主堂垡丝 t h ec r o s s i n gn u m b e ro f f l o w e rs n a r ka n dk s - e d p a b s t r a c t c r o s s i n gn u m b e ri s a l li m p o r t a n tc o n c e p tm e a s u r i n gt h en o n - p l a n a r i t yo fg r a p h s c a l c u l a t i n gt h ec r o s s i n gn u m b e ro fag i v e ng r a p hi s ，i ng e n e r a l ，a l le l u s i v ep r o b l e m i n1 9 8 3 ， g a r e ya n dj o h n s o n l l jh a v ep r o v e dt h a tt h ep r o b l e mo fd e t e r m i n i n gt h ec r o s s i n gn u m b e ro fa n a r b i t r a r yg r a p hi sn p - e o m p l e t e av e r yf e wg r a p h s c r o s s i n gn u m b e ri sd e t e r m i n i e d , s u c h 髂 t h eg e n e r a l i z e dp e t e r s e ng r a p hp ( n ，3 ) ，c a r t e s i a np r o d u c t so f p a t h sw i t h5 - v e r t e xg r a p h s t h e c r o s s i n gn u m b e r so ft h ec o m p l e t eg r a p ha n dt h ec o m p l e t eb i p a r t i t eg r a p ha r eo p e np r o b l e m s i nt o p o l o g i c a lg r a p h t h e o r y t h i sp a p e rf o c u s e so dt h ec r o s s i n gn u m b e ro ft h ef l o w e rs n a r ka n dr e l a t e dg r a p h e 3 ) a n dt h et w i s t e df l o w e rs n a r ka n dr e l a t e dg r a p he 即3 ) b o t ht h ee x a c t v a l u e so f t h ec r o s s i n gn u m b e ra r ed e t e r m i n e d ( 墨) = 2 、o r ( ) = 3 、o r ( 磊) = 4 、仃( e ) = n ( n 6 ) g r 暇) = 1 、仃幔) = 2 、盯以) = 4 、仃以) = n ( n 6 ) t h ec r o s s i n gn u m b e ro f 砖一p 口只i sa l s os t u d i e di nt h i sp a p e r f i r s t , t h eu p p e rb o u n d o f t h ec r o s s i n gn u m b e ro f 0 一p 口只i sd e t e r m i n e d ： 啾一班c 川，吼孚儿譬心【字h 孚儿刊+ 【刊一阱+ 圭 竿心【孚j 【字卜辘- a tt h es a m et i m e ，i ti s c o n f i r m e dt h a tt h el o w e rb o u n do ft h ec r o s s i n gh u m b e r o f 如一阳只i sd e t e r m i n e da sf o l l o w s ： e r ( 置：一阳只) ( n - - 1 ) c r ( 蚝+ 2 2 局) + 2 ( 足0 l - e ) ，m 2 4 ，玎1 f m t h e rm o r e ，i ti sp r o v e dt h a t ： o r ( 瓦一阳) = 1 2 n ，聆1 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 ；p a t h ；r e g u l a rg 咄c o m p l e t eg r a p h 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或i 正- t ；所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：叠聋盐1 日期：丝星：! ：丝 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：垡聋盘。 铈签名：拯笙： 2 1 显年l 月t 日 大连理工大学硕士学位论文 1 绪论 1 1 图的交叉数的研究意义 图的交叉数问题既有重要的理论研究意义，在实践中又有广泛的应用，是图论知识 体系中的一个分支。 理论意义有两个方面： ( 1 ) 平面性是图的一个重要属性。交叉数当然是图论知识系统中不可缺少的组成部 分，交叉数确定后，我们对这个图的本质属性就多了一个理解要素，对于图的其他属性 的研究有指导意义。 ( 2 ) 计算任意图的交叉数问题是n p 完全的。早在1 9 8 3 年，g a r e y 和j o h n s o n 】证明 了计算任意图的交叉数是n p 完全的。对于任何一个复杂问题的研究，以及某个复杂问 题的解决方案的给出，都有着重要的理论意义，我们可以从中吸取有益的思想火花。 图的交叉数在现实生活和生产中有着广泛的应用。现实中的很多实际问题都可以通 过抽象建模，转化成图的交叉数问题进行研究和解决。 如：在设计v l s i 芯片时，尽可能的避免线路交叉是设计者的追求且标。因为线路 的交叉，将影响芯片的大小和性能。芯片体积大，则成本高；线路交叉重叠会产生电容 耦合，降低芯片的性能。总之，线路交叉越少越好。那么，怎样才能设计出最少线路交 叉的芯片呢? 我可以通过这样的抽象建模：把芯片上的元器件看作顶点，元器件间的线 路看作边。从而问题转化为研究图的交叉数问题。此外，交叉数在c a d 领域也有广阔 的应用。如： ( 1 ) 草图的识别与重画问题，这是比手写汉字识别应用更为广泛的应用领域； ( 2 ) 电子线路板设计中的布线问题； ( 3 ) 软件开发工具中文档部分的e r 图等的自动生成； “) 化学分子结构图的自动生成，这在化工专利管理等系统中的有广泛的应用； ( 5 ) 生物工程d n a 的图示。 图1 1 显示的是打印口逻辑电路图，在保证电路逻辑结构正确的前提下，交叉点数 越少越好。 图1 2 显示的是b a 2 r e c u 3 0 9 6 超导体的化学键模型图，在保证分子结构正确的前 提下，交叉点数越少越好。 f l o w e rs n a r k 和j t 口r 的交叉数 图1 1 打印口逻辑电路图 f i g 1 1 t h el o g i c a lc i r c u i td i a g r a mo f l p t 图1 2b a 水e c m 阻5 超导体的化学键模型图 f i g 1 2 t h ec h e m i c a lb o n dm o d e lo f b a 2 r e c u 3 0 m 2 - 大连理工大学硕士学位论文 1 2 图及交叉数的基本概念 本节介绍与本文相关的交叉数的一些基本概念和术语。 定义1 1 图 一个无向图g 定义为一个二元组( k d ，记作g ( e 助，其中v = v ( a ) 是一个非空 集合，称作无向图g 的顶点集；五钮( g ) 是由矿( g ) 中元素构成的无序对集合，即 e ( g ) = ( ，v ) i ，v v ( g ) ) ，称为无向图g 的边集。 无向图与有向图统称为图。 边删的端点、v 称为相邻的。称一条边的端点为与这条边相关联，同时，也称一 条边为与它的端点相关联。若两条不同的边与一个公共的点关联，则称它们是邻接的边。 关联同一端点的一条边称为自环。两条或两条以上的边关联一对端点，称为多重边。 无自环，无多重边的图称为简单图。仅有一个点的简单图称为平凡图。 本文所涉及的图均为无向的，非平凡的简单图。 p = p ( g ) = i v ( g ) j 表示图g 中的顶点数，称为图g 的阶( o r d e r ) 。 q = q ( g ) = 陋( g ) 陵示图g 中的边数，称为图g 的大小( s i z e ) 。 能用较小和较简单的图来表达一个给定的图的结构是很方便的对经常出现的图运 算我们采用如下的简单记法： g - e l 8 2 瞄表示从图g 删除边8 1 e 2 “后所得到的图若k = l ，简记为g - e 。 g + e t e 2 耐表示图g 添加边e l ，也，吼后所得到的图若k = - i ，简记为g 地。 g - v ，, v 2 , ，) 表示图g 删除顶点v l v 2 ，毗及与其相关联的边后所得到的图。若 转1 ，简记为g - v 。 定义1 2 子图 若矿( 脚c 矿( g ) ，e c 万( g ) ，则称图日为图g 的子图。若y ( 功= 矿( g ) ，e ( 脚 笪( g ) ，则称图日为图g 的生成子图；若y c y ( g ) ，m , e e ( 劢当且仅当z g t ee ( g ) ， 且、瞧v c 功，则称图日为图g 的导出子图，记作：( 日) 。 定义1 3 交图 交图g i o g 2 是满足以下条件所构成的图类： ( 1 ) g 的顶点集弘 ( 虬d | 对于任意g l ，v g 2 ) ： ( 2 ) 对于任意俨( “i ，屹) ，俨( v b v 2 ) n 当u l 唧l 且u 2 和v 2 在g 2 中相邻或当地= v 2 且蝴和v l 在g l 中相邻时，“和v 在g l d g 2 中相邻。 定义1 4 嵌入与平面图 一3 一 f l o w e rs n a r k 和j 岛t 口r 的交叉数 如果一个图g 可以画在一个表面s 上，且任何两条边都不相交，则称g 可以嵌在 表面s 上。相应的画法称为一种嵌入。 一个图如果可以嵌入平面，则称之为可平面的，或称之为平面图。如果一个图不能 被嵌入到平面上，则称之为非平面图。 对于一个非平面图g ，若存在它的一个生成子图见日是平面图且对任意一条属于 g 但不属于日的边p ，月托是非平面图，则把图日称为图g 的极大平面子图，一个平 面图可能有不只一个极大平面子图。 定义1 5 画法与交叉数 图g 在表面上的一个画法是指把图的顶点画为表面上的结点，把图的边画为表面上 的弧。 图g 在表面上的一个好的画法是指图g 在表面上的一个画法，在该画法中连结同 一个结点的任意两条弧不相交；任意两条弧至多只有一个交点；任意一条弧不自交；任 意三条弧不相交于同一点。本文所涉及到的画法均为好的画法。 画法中两条弧的一个公共点称为一个交叉点。图g 在给定表面上的最优画法是指图 g 的所有好的画法中具有最少交叉点数的画法，这个数目称为图g 对于该表面的交叉 数。画法d 中交叉点的数目记为v ( d ) ，图g 在平面( 或球面) 上的交叉数简称为图的交 叉数，记为c r ( g ) ，显然c ，( g ) v ( d ) 。 定义1 6 路径与圈 一个图g 的一条通道是顶点和边的一个交替序列v o ，p l ，v l i l ，。有时也可记傲 v o ，v n 1 ，。这时称它是从到h 的长为”的通道。若它的所有边都不同，称之为一 条路径，记为r 。一条路径中边的个数称为这条路径的长度。若路径的起点和终点相同， 即= h 且它的前拧个点都不同，聆2 3 ，则称它为一个圈或回路，记作g 。一个圈中边 的个数称为这个圈的长度。 图g 的围长是指在图g 中最短的圈( 假如g 中有圈) 的长度。 定义1 7 映射和像 设z 和r 是任意两个集合，而厂是j 到r 的一个关系，如果对于每一个x e x 都有 唯一的y r ，使得缈乒则称厂为函数，记作，石一y o 假如q 户号 则称工为自变 元，y 称为在，作用下x 的像。从x 到y 的函数往往也叫做从x ny 的映射。 如果x 和l ，的元素数目相同，并且x 中没有两个元素有相同的像，则称这个映射为 一一映射。 定义1 8 同构 大连理工大学硕士学位论文 若在两个图g 和日的顶点集合之间存在一个保持邻接性的一一对应，则称它们是 同构的。即存在一个一一对应的映射正使得对任意v ( g ) ，有“) y ( 劢，同时满 足：( 甜，v ) e ( g ) 当且仅当抓v ) ) e e ( n ) ，记作g 望日。 定义1 9 同胚 若x = v 是g 的一条边，又w 不是g 的一个顶点，则当用边洲，和w 来代替x 时 称x 被细分。两个图是同胚的，若它们都可以从同一个图通过一系列边的细分得到。 同胚的图的可平面性是一样的。 定义1 1 0 连通 若一个图的每一对顶点都有一条路径连接，这个图称为是连通的。g 的一个最大的 连通子图称为g 的一个连通分支。 一个图的一个割点是这样一个顶点：移去它后使剩下的图的连通分支的数目比原来 的图有所增加。一条割边也是具有类似性质的一条边。无割点的连通图称为( 点) 二连通 图。g 的极大二连通子图称为g 的二连通分量。 连遥的、非平凡的而且没有割点的图称为不可分图。 图g 的一个极大的不可分子图称为图g 的一个块。 定义1 1 l 旋转系统 在画法d 中顶点v 的局部旋转系统是由该顶点出发的所有边的另外一个顶点按照逆 时针方向所构成的一个序列，记为r h o m 。画法d 的旋转系统是所有顶点的局部旋转 系统的集合。 如果两个画法存在相同的旋转系统，那么这两个画法中边的相交情况是相同的，具 有相同豹交叉数。 下面给出几个具体图的定义： 定义1 1 2 完全图 顶点数为聆且每一对顶点都相邻的图称为完全图，记为。 定义i 1 3 完全二分图与星图 完全二分图j k 。是满足以下条件所构成的图类： ( 1 ) 顶点分为二个集合h 、圪，其中l v d = m ，i v z l = m ( 2 ) 对于任意e k ，v 巧，若匀箩，则以v 相邻( 驴= 1 ，2 ) 。 对于完全二分图j 。，若m = l 或者r e = l ，我们就称它为一个星图，即s ，瑙。l = k 1 ，。 定义1 1 4 完全三分图 完全三分图墨。n , l 是满足以下条件所构成的图类： ( 1 ) 顶点分为三个集合n 、既、巧，其t 中l e l = m ，i 砼i 邗，i 巧i = h f l o w e rs n a r k 和岛口只的交叉数 ( 2 ) 对于任意“n ，v 巧，若f - 铲，则“、v 相邻( f ，= 1 , 2 ，3 ) 。 定义1 1 5f l o w e r s n a r k 及图e 、图e + 当疗为不小于5 的奇数时，f l o w e rs n a r k 图f - - - ( k d 被定义为4 疗个项点的简单无 向图。其中，矿= a i 0 f n - 1 ) u b ，l0 f s 胛- 1 j u c 1 10 f s 2 n - 1 ) 。e = 6 ，6 + l l m o d 。i o i n - l u c x ( + i ) m o d 2 。i o f ! 主2 即- 1 ) u 口f 6 l 口筘。口t 岛+ f i o f - 1 ) 。 当”= 3 或玎为不小于4 的偶数时，e 被称为f l o w e rs n a r k 的相关图。下文中，我 们用只表示f l o w e rs n a r k 及其相关图。 在文献【2 】中，将g o l d b e r gs n a r k 中特定边k iv 1 2 和v 4 v 1 4 v 3 2 州秽1 心 v 2 iv 3 2 习v 4 iv 1 2 替换产生的 新图称为t w i s t e dg l l d b e r gs n a r k 。仿照t w i s t e dg l l d b e r gs n a r k 的定义，我们称将图c 中 的边c o c 2 n - l 和c h i n - l 用新边c o c + l 与劬替换产生的新图为t w i s t e df l o w e rs n a r k 及其相 关图，用e 表示。不难发现，e 是图s ，d c 的子图。 最后，给出几个基本定理： k u r a t o w s k i 定理一个图是平面图，当且仅当它不包含与为3 或墨同胚的子图。 e u l e r 定理设有一个连通的平面图g ，共有v 个顶点p 条边和r 个面，则欧拉公 式v e + ，= 2 成立。 由以上的概念，我们可以得到以下三个显而易见的引理。 引理1 1 令4 ，召，c 为互( g ) 的互不相交的子集。那么 场( c a u b ) = ( c a ) + ( c ，b ) ； ( a u b ) = v d ( a ) + v d ( b ) + 殇( a ，b ) 引理1 2 如果图g 至少删掉i 条边才能够得到平面子图，那么i 州6 3 。 引理1 3 令爿血( g ) ，若在画法d 中，4 上至少存在x 个交叉点，删掉彳中所有的 边得到一个新画法d ，那么场( d ) + 压( d ) 。 1 3 图的交叉数的研究进展 i 3 1 完全图 1 9 6 0 年g u y 【3 1 提出完全图墨的交叉数的猜想： 喁，= 制孥j 降吲 1 9 6 9 年g u y l 蜘聒1 0 时，上述猜想成立。1 9 9 6 年d a r c h d e a c o n 在文献 5 中指出n _ 1 2 时，猜想成立。 大连理工大学硕士学位论文 2 0 0 2 年，o a i c h h o l z e r ，f a u r e n h a m m e r 和h k r a s s c r 【6 1 利用剪枝算法，用计算机穷 举方法证明了局1 和局2 的直线交叉数分别为1 0 2 和1 5 3 一 关于完全图的交叉数的下界，目前最好的结果是1 9 7 0 年k l e i t m a n 7 1 给出的，当1 足够大时： c r ( 民) n ( n 一1 ) ( n - 2 ) ( n 一3 ) 8 0 1 3 2 完全二分图 1 9 5 4 年，z a r a n k i e w i c z 【3 1 给出完全二分图。的交叉数猜想： 峨力钢埘一= 龇字脚爿 并验证了当r a i n ( 聊，n ) = 3 时，猜想成立。 1 9 6 9 年，g u y t 4 1 指出在z a r a n k i e w i c z i s 的证明中存在错误。 1 9 7 0 年，e i t n l 衄【_ 7 】证明当r a i n ( 现行) 甾时，z a r a n k i e w i c z 猜想成立，并证明关于 z a r a n k i e w i c z 猜想的最小反例必然出现在m 和行为奇数的情况。 1 9 9 3 年，w o o d a l l 9 1 利用计算机搜索进步验证了z a r a n k i e w i c z 猜想成立对于局7 和为9 成立。 2 0 0 3 年，n h n a h a s 1 田对完全二分图的交叉数下界进一步研究，给出当m , n 足够大 时： 瞩妒扣一d 龇孚j + 9 9 x 1 0 - - 6 批 2 0 0 6 年，k l e r k 1 1 】等人证明，对于给定r f t29 ， l i r a ，一仃( j ) z ( m ，) 0 8 3 m ( m 一1 ) 同时证明了 l i m ，一仃( 置j ) z q ，j ) o 9 3 1 3 3 完全三分图 对完全三分图的交叉数的研究始于1 9 8 6 年。1 9 8 6 年，k o u h e u 舢加o 1 2 1 利用k l e i l m a a 关于完全二分图的交叉数研究结果给出完全三分图蜀3 。和k 2 3 。的交叉数的计算公式： c r ( k i j ) = c r ( k 4 ) + i n 2 ；o r ( k j 。) = c r ( k 5 ，。) + 彪 2 0 0 4 - 2 0 0 6 年，黄元秋f 协1 6 】等在完全二分图研究的基础上，证明了在完全二分图猜 想成立的前提下，以下结果正确： f l o w e rs n a r k 和g , t 口只的交叉数 c r c 墨，= z c s ，一，+ 2 【三j ；c r c 蜀，= z c s ，力+ 4 【兰j ；c r c k 丘。，= z c ，疗，+ 6 【三j ； 仃c 墨，。，= z c s ，疗，+ ，i 呈j ；c r c 墨 。，= z c 。，n ，+ t 2 【兰j ：仃c 墨舯，。，= z c ，一，+ 2 。l 呈j ； 仃( 蜀_ 4 。) = z ( 6 ，n ) + 2 n 1 3 4 交图 ( 1 ) 两个圈的交图 1 9 7 3 年，h a r a r y i 】在给出如下猜想( 又称为h k s 猜想) ： c r ( c o c t ) = ( m - 2 ) 歼。 3 m r a n 9 ， 3 c r l ，则回添所删的边后得到的图g 的画法中至少有m c r l 个交叉点( 由极大平 面嵌入的定义，每回添一条所删边，至少增加一个交叉点) 。通常我们只需构造图g 的 一种最优画法。这时可把限界条件( 1 ) 改为：在步骤4 中按所有可能画法回添所删边时， 只有当d ( d c r i 时，我们才继续往回添其余所删的边；把限界条件( 2 ) 改为：只对m 仃i 的平面子图的每一种极大平面嵌入进行交叉数的计算，这样可提高算法的运行速度。 2 3 用算法c c n 计算给定图的交叉数 对于小阶图只、只+ ，算法c c n 的计算结果，如表2 1 和表2 2 所示。 表2 1 月1 1 ，e 的交叉数的上界 t a b 2 1 u p p e r b o u n d s o f t h ec r o $ $ h l gn u m b e r so fey o r n s l l 大连理工大学硕士学位论文 3f l o w e rs n a r k 的交叉数 3 1f l o w e r s n a r k 图 由定义1 1 5 ，b = ( 形西，其中 矿= 研i o 摧加1 ) u b , l o z - f n - l u c j l 0 _ i _ 2 n 1 ， e = b i b “+ 1 ) m a d h | o f n - 1 ) u 岛q 什1 ) 珥。口孙l o i _ 2 n - 1 u 口函d 口f c 。口，岛+ fj o 拄如一1 ) 又由定义1 1 5 ，e 是图s 口g 的子图。在这里，我们对，气= ( f d 重新表示如下： e = ，d 3 ) 为4 一个顶点的简单无向图，其中， v = a i1 0 f n - 1 u 6 j1 0 i n - 1 u c , 1 0 i n - 1 u d , 1 0 茎i n - - 1 ) ； e = 匆6 ( + i ) m o d 。1 0 i 疗一i u c , c o + 1 ) 皿。d 。i o f 疗一l u 4 暖，+ j m o d 。1 0 f 刀一1 u q 包，a , c z ，q t0 i s n - - 1 ) 图3 1 、3 2 分别给出了图e 及e 的一种画法。 图3 1e 的一个平面画法 f i g 3 1 ad r a w i n g o fe 图3 2 圪的一个平面画法 f i g 3 2 ad r a w i n go fe f l o w e rs n a r k 和k m - e c i p 的交叉数 3 2 e 的交叉数 3 2 1 图b 的交叉数的上界 定理3 1 对于3 n s 5 ，仃( ) s n - 1 ；对于 6 ，c r ( f n ) 打。 证明：图3 3 3 5 分别给出了e ( 3 胛5 ) 的有疗1 个交叉点的好的画法。图3 6 给出了只有6 个交叉点的好的画法，这一画法可以拓展为e 有 个交叉点的好的画法。 图3 3 e 的一个好的画法 f i g 3 3 ag o o dd r a w i n go fe 图3 4 只的一个好的画法 f 嘻3 4a g o o d d r a w i n g o f 五 图3 5e 的一个好的画法 f i g 3 5 ag o o dd r a w i n go fe 大连理工大学硕士学位论文 图3 6 只的一个好的画法 f i g 3 6 ag o o dd r a w i n go f 最 3 2 2 图e 的交叉数的下界 在图中，有一个2 n 圈，1 个行圈和疗个包含3 个叶子的星。对0 i n - - 1 ，令 置= z = e ( 墨) = q 岛，a i e t ，q c ：f 卅， 上l = 6 i 岛+ l ，e q + 1 ，q 帅q + l 棚) 互= z u 厶 除非特别指明，本节中，2 n 圈的顶点下标对知取模，其它顶点下标对疗取模。e ( e ) 被分为n 个不相交的子集磊，五，e - ，即e = u ：巨，置n 弓= o ( o i c j n - 1 ) 引理3 2 对于力3 ，令d 为e 的任一画法，如果在d 中，对所有的0 i n - l ， z 都是干净的，则1 ，( 上”总 证明：对o - i - n - 1 ，定义函数厶( f ) = ( 互) + v d ( e ，占一e ) 2 对d 中的交叉点进 行计数则有“d ) = ：厶( n 假设存在某个i ( o i n - 1 ) ，使得厶( 力 1 。不失一般性，假设厶( o ) 1 。令 蜀= 五u 互u 厶。因为瓦u 墨是干净的，且厶( o ) l ，与假设厶( 0 ) - 1 ，与假设 厶( o ) 1 与假设厶( o ) - i ，从而v ( d ) = ，n - 1 如t i , ) 以。 定理3 3c ，( e ) = 2 证明：由定理3 1 ，c ，( 巧) - 2 下面仅需证明c r ( f d 2 用反证法，令d 是e 的 一