（运筹学与控制论专业论文）几类图的交叉数及其相关性质.pdf

北京交通大学硕士学位论文致谢 中文摘要 摘要：对图的性质的研究是图论中的一个重要部分，本文主要研究将图画在平面 上图的交叉数的确定并对循环图c ( 2 m ，仇) 嵌入在可定向蓝面上的亏格分布进 行了讨论 如果把图画在平面上，则对于一些图来讲，无论怎么画，它的边必然相交，图 g 的交叉数是指将它画在平面上边交叉的最少次数，记为c r ( g ) ，其中画法满足： ( 1 ) 任何两条边最多相交一次； ( 2 ) 边自身不相交； ( 3 ) 有相同端点的两条边不相交； ( 4 ) 没有三条边交于同一个点； ( 5 ) 任何一边不过除它端点之外的顶点 研究图的交叉数不仅有重要的理论意义，而且有较强的实际意义，如v l s i 芯 片设计 图g 在曲面上的2 一胞腔嵌入是指将图画在曲面上，使得g 的边只在它们的 公共顶点处相交且g 画在曲面上对应的每一个面同胚于一个开圆盘对图的2 一胞 腔嵌入的研究包含许多问题，比如：最大亏格，最小亏格，平均亏格，亏格分布等 本文共分为三章 第一章，介绍了一些本文需要的基本知识 第二章，在前人研究的基础上给出了两类图的交叉数，证明了c r ( 岛+ ) = n 2 一【詈j ，以及盯( p m ) = ( m 一1 ) 【詈儿孚j + ( m + 1 ) ，n 3 ，仇1 第三章，利用加边法给出了循环图c ( 2 m ，m ) 的亏格分布的递推公式 关键词：图；交叉数；嵌入；联图；笛卡尔积图；循环图 分类号：0 1 5 7 5 1 1 1 北京交通大学硕士学位论文 致谢 a b s t r a c t a b s t a c t ：i ti sa ni m p o r t a n tp a r tf o rs t u d y i n gt h ec h a r a c t e r so fg r a p h si n g r a p ht h e o r y t h i st h e s i si sm a i n l yo nh o w t od e t e r m i n et h ec r o s s i n gn u m b e ro fa g r a p hw h e nd r a w i n gw h i c ho nt h ep l a n e f u r t h e r m o r e ，t h eg e n u sd i s t r i b u t i o n so f e m b e d d i n gc i r c u l a r 孕印h sc ( 2 m ，m ) o no r i e n t a b l es u r f a c e sa r ed i s c u s s e d f o rs o m eg r a p h s ，s o m ee d g e so fw h i c hm u s tb ec r o s s e dw h a t e v e rt h e ya r e d r a w no i lt h ep l a n e t h ec r o s s i n gn u m b e ro fag r a p hg ，d e n o t e db yc r ( g ) ，i s t h em i n i m a ln u m b e ro fp a i r w i s ei n t e r s e c t i o n so fe d g e si na l lt h ed r a w i n g so fgo n t h ep l a n e ，w h e r et h ed r a w i n g ss a t i s f y ： ( a ) t w on o n a d j a c e n te d g e sc r o s sa tm o s to n c e ， ( b ) n oe d g ec r o s s e si t s e l f , ( c ) a d j a c e n te d g e sn e v e rc r o s s ， ( d ) n om o r et h a nt w oe d g e sc r o s sa tap o i n to ft h ep l a n e ， ( e ) t h ea r ci nt h ep l a n ec o r r e s p o n d i n gt oa ne d g eo ft h eg r a p hc o n t a i n sn o v e r t e xo ft h eg r a p h t h e r ea r en o to n l ye n o r m o u ss i g n i f i c a n c ef o rt h e o r e t i c so nr e s e a r c h i n gt h e c r o s s i n gn u i n b e r so fg r a p h s ，b u ta l s oe n o r m o u ss i g n i f i c a n c ef o ra p p l i c a t i o n 。f o r e x a m p l e ，t h ed e s i g no fv l s i sc h i p a2 - c e l le m b e d d i n go fag r a p ho nas u r f a c ei sd r a w i n gt h eg r a p ho nt h es u r f a c e s u c ht h a tt h ee d g e so ft h eg r a p hc r o s so n l ya tt h ec o m m o nv e r t e xo ft h e ma n de v e r y r e g i o no fw h i c hi sh o m e o m o r p h i ct oa l lo p e nd i s k m a n yp r o b l e m sa r ei n v o l v e di n t h e2 - c e l le m b e d d i n gi n v e s t i g a t i o n ，s u c ha st h em a x i m a lg e n u s ，t h em i n i m a lg e n u s ， t h ea v e r a g eg e n u sa n dg e n u sd i s t r i b u t i o ne t c i nt h i st h e s i s ，t h e r ea r et h r e ec h a p t e r s ： i nt h ef i r s tc h a p t e r ，s o m eu s e f u lk n o w l e d g ef o rt h et h e s i si si n t r o d u c e d i nt h es e c o n dc h a p t e r ，t h ec r o s s i n gn u m b e r so ft w ok i n d so fg r a p h sa r eg o t t e n b a s e do nt h ef o r m e rr e s u l t s 万( s + & ) = 船2 一【；ja n d 口( x p m ) = ( m 一 1 ) 【詈j 【孚j + ( m + 1 ) ，n 3 ，m 1w i l lb ep r o v e d i nt h et h i r dc h a p t e r ，e d g e - a d d i n gm e t h o dw i l lb eu s e da n dt h er e c u r r e n c e f o r m u l af o rg e n u sd i s t r i b u t i o no fc ( 2 m ，m ) w i l lb eg o t t e n 北京交通大学硕士学位论文致谢 k e y w o r d s ：g r a p h ；c r o s s i n gn u m b e r ；e m b e d d i n g ；j o i ng r a p h ；c a r t e s i a ng r a p h ； c i r c u l a rg r a p h c l a s s n 0 ：0 1 5 7 5 v 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定特授 权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并 采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家 有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者龆孙建根 签字日期：乒“年6 月多日 剔醴各前狠 签字日期：1 卯拜钿3 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书而 使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的况明并表示了谢意 学位论文作者签名：乡艮；差茸艮签字日期：加 年6 月多日 北京交通大学硕士学位论文致谢 致谢 在本文即将结束的时候，我要特另f j 向我的导师郝荣霞教授表示衷心的感谢，她 无论是在科研上，还是在平时的生活中都给了我无微不至的关怀与鼓励，当我在课 程学习中遇到困难的时候，她总是以循循善诱的授课方式使我豁然开朗；当我在科 研上遇到困难的时候，她给了我很多新的思路和方法，使我受益匪浅她严谨的治 学风格，广博的学识，精益求精的科研作风，敏锐的学术思想和忘我的工作态度极 大的影响了我本论文是在郝老师的精心指导和关怀下完成的无论是在研究生学 习过程中，还是在论文选题、研究、定稿的过程中，郝老师自始至终给了我大力的 支持和无私的关怀，在此向郝老师表示深深的感谢! 感谢我的同门师兄弟李兴阔，王力东，龚松珍等”三人行，必有我师”，共同 的学习生活中他们良好的学习研究氛围感染了我，他们优良的人格品质影响了我， 使我能够不断的发现自己的缺点，不断的完善自己在此我向他们表示我最诚心的 感谢! 感谢同窗两年的各位同学从他们身上我学到了很多有益的知识和学习方法 两年的同窗之谊，离别之际，更加珍惜我为自己两年来生活在那种坦诚相待，互 相帮助的氛围中感到莫大的荣幸! 感谢各位专家，学者在百忙中审阅我的论文，并给出宝贵的批评意见，使本论 文增色不少本论文的完成离不开各位专家学者的帮助! 最后，我要感谢我的父母和姐姐，有了他们才有了我现在读书的条件，是他们 辛勤的劳动换来了我今天这样舒适的学习环境树高千尺也忘不了根，我将用我的 所有来报答我的家人! 张建根 2 0 0 8 年5 月 于北京交通大学理学院 北京交通大学硕士学位论文第一章绪论 1 基本概念 第一章绪论 一个图g 是指一个有序三元组( y ( g ) ，e ( g ) ，忱r ) ，其中v ( c ) 是非空的顶 点集，e ( g ) 是g 的边集，而，g 是关联函数，它使g 的每条边对应于g 的无序 顶点对( 不必相异) 若e 是一条边，而牡和u 是使得妒g ( e ) = ( t t ，) 的顶点，则称 e 连接札和t ，；顶点让和v 称为e 的端点 一条边的端点称为与这条边关联，反之亦然与同一条边关联的顶点称为相邻 的，与同一个顶点关联的边也称为相邻的端点重合为一点的边称为环，顶点不相 同的边称为连杆没有环也没有两条连杆连接同一对顶点的图称为简单图顶点 的度，记为d ( v ) ，是指和v 相关联的边的数目，每个环算作两条边显然： 定理1 1 1 a l 2j e ( g ) l = d ( v ) v e v ( g ) 两个图g 和日称为同构的( 记为g 竺h ) ，如果存在两个一一映射p ： v ( g ) _ v ( h ) 和：e ( g ) _ e ( h ) ，使得妒g ( e ) = ( u u ) 当且仅当妒日( ( e ) ) = ( p ( u ) 仔( 可) ) ；这样一个映射对( p ，) 称为g 和日之间的一个同构 对图g 的一条边e = ( 牡可) 剖分是指在图g 中去掉边e ，同时加上一个新的 顶点铷以及两条边( t r y 0 ) 和( ? j r 0 ) 称g 0 是g 的剖分图，如果g o 是通过对g 的边进行有限次剖分得到的如果g o 和风分别是g 和日的剖分图，而g 和 日是同构的，则称g i ) 和凰是同胚的 称厅为g 的子图( 记为h g ) ，如果v ( h ) v ( v ) ，e ( h ) e ( c ) ；并 且矽日是此在e ( g ) 上的限制当日g ，但h g 时，则记为hcg ，并 且称日为g 的真子图若日是g 的子图，则g 称为h 的母图，g 的生成子图 ( 或生成母图) 是指满足v ( h ) = v ( c ) 的子图( 或母图) h 记g e 】为由图g 的 边子集e 构成的子图 完全图是指每一对不同的顶点之间都有一条边相连的简单图，在同构的意义 下，1 个顶点的完全图只有一个，记为空图是指没有任何边的图 偶图( 或二部图) 是指一个图，它的顶点集可以分解为两个子集x 和y ，使 得任何一条边都有一个端点在x 中，另外一端点在y 中；这样一种分类( x ，y ) 称为图的二分类完全偶图是指具有二分类的简单偶图，其中x 的每一个顶点都 与y 的每一个顶点相连；若l x l = m 而i y i = 珏，则这样的偶图记为西m 绍部 图和完全7 l 部图可以类似定义 设g l 和g 2 是两个点不交的图，它们的联图g 1 + g 2 是这样的图：v ( g l + g 2 ) = y ( g 1 ) uv ( c 2 ) ，e ( g 1 + g 2 ) = e ( g 1 ) ue ( g 2 ) u ( 牡秒) i u y ( g 1 ) ，” 北京交通大学硕士学位论文第一章绪论 y ( g 2 ) ， 设g 1 和g 2 是两个点不交的图，它们的笛卡尔积g 1 g 2 是这样的图：v ( e 1 g 2 ) = v ( g 1 ) v ( c 2 ) ，e ( g i g 2 ) = ( ( ( 地，吩) ( 魄，t | 奄) ) i ( 地= v h 且( u j u k ) e ( c 2 ) ) 或( 吻= t 七且( v i v h ) e ( g 1 ) ) ) 循环图g = c ( m ，z ) 是这样的图：它的顶点集为 铷，t ，l ，一1 ，边集是 ( 仇仇+ 1 ) ，( 仇优+ f ) 婶= 0 ，1 ，m 一1 ，这里m ，z 都是整数，并且f 小于m 2 ，同 时下标是在模m 的意义下 广义p e t e r s e n 图g = g ( n ，m ) 是这样的图：它的顶点集为 i l o ，t z l ，一l ， 珈，t ，1 ，一l ，边集是 ( t “t ，i ) ，( ? l , i l t i + 1 ) ，( t ，t t k + 。) l i = 0 ，1 ，7 , 一1 ) ，这罩7 , ， m 都是整数，并且m 小于n 2 ，同时下标是在模n 的意义下 2 图的交叉数 2 1 交叉数的背景知识 如果一个图能映射到平面上使得它的边仅在端点相交，则称这个图为可嵌入 平面的，或称为平面图有时我们必须把一个图映射到平面上，比如芯片上的线路 分布其实就是一个图并且必须在平面上实现有时这个电路图并不是平面图，这就 要求布线的时候应该让线路交叉的尽量少，因为线路交叉必然会减低芯片的性能 并可能存在潜在的问题，比如线路短路或断路交叉数的概念是在1 9 4 4 年提出来 的，当时匈牙利数学家p a u lt u r a n 在布达佩斯郊外的一家砖厂工作这家砖厂有 若干台烧砖的砖窑以及若干个堆砖场有铁路把每台砖窑和每一个堆砖场连接起 来工人把砖装在一辆小车上，推着它沿铁路到达一个堆砖场，然后把砖卸下来这 项工作本来比较容易，但是麻烦在于有一组铁路同另外一组的交叉在铁路交叉处 小车经常出轨，使砖掉下来工程师可能会考虑如何重新设计铁轨的交叉点但身 为数学家的t u r a n 则希望知道如何重新设计铁路的布局使得交叉点尽可能的少 经过几天的思考后，他意识到这家砖厂中有些铁路交叉点是多余的但他仍然对下 面这个一般性的问题继续感兴趣：如果有m 台砖窑和n 个堆砖场，并且假设每一 个砖窑都有铁路通向每一个堆砖场，则这个问题可以表述为：找出所有完全二部图 。的交叉数 图的一个好的画法是指把图在满足以下五个条件的情况下一一的连续的映射 到平面上： ( 1 ) 任何两条边最多相交一次； ( 2 ) 边自身不相交； ( 3 ) 有相同端点的两条边不相交； 2 北京交通大学硕士学位论文第一章绪论 ( 4 ) 没有三条边交于同一个点； ( 5 ) 任何一边不过除它端点之外的项点 图g 的交叉数是指在g 的所有好的画法中边交叉最少的次数，记为c ，( g ) 满足交叉次数最少的画法称为图g 的最优画法一般而言，确定个图的交叉数 是一个n p 难问题，并且没有比较好的固定的方法，一般的对一个图求其交叉数很 好的方法往往不能用到与其非常相似的图上，因此目前能够确定交叉数的图还很 少，有时候只能给出某些图类交叉数的上界对交叉数研究的结果主要集中在完全 图，完全n 部图，广义p e t e r s e n 图，笛卡尔积图，循环图上 2 2 关于交叉数已有的结果 本节将介绍一些已知的关于交叉数的结果 1 ，关于完全图的交叉数 g u y 在 1 0 】中猜想对于所有的礼有， c r ( k n ) = 凇j 【孚j 【等儿警j d r w o o d a l l 在 4 4 】中证明了当1 扎s1 0 的时候成立 2 ，关于完全二部图的交叉数 z a r a n k i e w i c z 在 4 8 】中“证明”了 c r ( k m ，。) = 【署儿鼍尹儿；儿孚jm 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 在【4 8 】中证明的错 误因而，确定完全二部图n 的交叉数问题目前仍足一个公开问题，习惯上把 z a r a n k i e w i c z 在 4 8 l 中的等式称为z a r a n l d e w i c z 猜想后来，k l e i t m a n 在【2 4 】中 证明了当m 6 时z a r a n k i e w i c z 猜想是成立的 3 ，关于完全n 部图的交叉数 a s a n o 在 1 】中证明了以下结果， c r ( k 1 ，3 ，n ) = 2 【量儿学j + 【詈j ，c r ( 鲍3 n ) = 4 【詈j 【孚j + 佗 黄元秋等在【1 6 ，4 0 】中先后证明了， c r ( k 1 ，4 n ) = n ( n 一1 ) ， c r ( k 1 5 ，n ) = 6 【詈儿孚j - i - 4 吲 4 ，关于广义p e t e r s e n 图的交叉数 马登举等在【3 7 】中证明了广义p e t e r s e n 图g ( 2 m + 1 ，m ) 的交叉数为3 林 晓辉等在文献 3 0 】中对p e t e r s e n 图的交叉数做了比较系统的研究，并给出了一些 算法，得到了c ( n ，k ) 当佗1 6 时的交叉数，最后给出了以下猜想， 3 北京交通大学硕士学位论文第一章绪论 c r ( g ( 4 h + 2 ，2 h ) ) = 2 h + 1h 3 ， c r ( g ( 4 h + 2 ，4 ) ) = 2 h + 2h 3 5 ，关于笛卡尔积图的交叉数 近年来很多学者对笛卡尔积图的交叉数进行了研究并得到了丰盛的结果，其 结果主要集中在顶点比较少的图与路，圈和星图的笛卡尔积图上，详见 2 ，5 ，1 8 ， 1 9 ，4 1 ，4 2 ，4 9 1 ，主要有， c r ( q q ) = 8 【5 】， 凹( 鲍，3 c 3 ) = 9 1 8 】， c r ( k 5 r ) = 6 n 1 9 】， c r ( p 3 ，1 r ) = 4 ( 礼一1 ) 4 1 】， 凹( k 3 ，3 r ) = 7 n 一1 4 9 】 此外m a r i 矗nk l e 吾5 在【2 0 ，2 3 】中确定了所有4 阶图以及部分5 阶连通图与 路的笛卡尔积图的交叉数 6 ，关于循环图的交叉数 循环图c ( m ，f ) 的交叉数问题最早见于 3 1 】，通过给出好的画法，作者给出了 一般循环图的交叉数的上界 c r c c c 2 仇，m ，( 言1 ) + ( 。喜1 ) ， c r c c c 仇，2 ，= 呈：三i ：+ 。竺量i ， 邢c 删 ：二融1 糍删l ( m o d 3 ， c r ( c ( m ，f ) ) 警+ 1 ， 郝荣霞在【1 2 】中对循环图c ( m ，f ) 的交叉数进行了进一步的研究，从而得到 了循环图的交叉数新的上界 c r c c c m ，3 ， 季 + lm m 三- - = 0 2 。, m l ( 。m 奶o d ，引， c r ( c ( 2 m ，m ) ) m 一2 ， c r ( c ( m f ) ) m ( z 一- 2 2 ) t + r ( f r ) + ，一2m r e = ：托i t + nr l ， 此后有许多学者对其进行了研究并得到了很多关于交叉数的精确结果f 2 7 ，3 5 ， 3 6 ，4 6 1 ，主要有， 4 北京交通大学硕士学位论文 第一章绪论 c r ( c ( 3 n ，他) ) = 住( n 3 ) 2 7 1 ， c r ( c ( 2 礼+ 2 ，佗) ) = n + 1 ( n 3 ) 【3 5 ， c r ( c ( 2 n ，佗) ) = 1 ( 佗6 ) 【3 6 ， c r ( c ( 2 钆+ 1 ，礼) ) = 1 ( 礼6 ) 3 6 】， c r ( c ( n ， 1 ，3 ) ) = 【3 j + n ( m o d 3 ) n 8 ) 【4 6 3 图的亏格分布 3 1 亏格分布的背景知识 图的嵌入理论是拓扑图论一个重要的研究内容，嵌入理论中主要的研究问题 有图的可嵌入理论和计数理论图的可嵌入理论的丰要应用包括：复杂的电子线路 ( 如超大规模集成电路( v i s i ) ) 的分析与设计，印刷电路板的设计与布线，逻辑电 路的分析与故障诊断等等而图的嵌入计数理论则与理论物理、量子力学以及统 计力学有着密切的关系 1 9 8 7 年，g r o s s 和f u r s t 在文献f 9 】中系统地研究图的嵌入不变量及其层次 关系时，引入图在可定向曲面上嵌入的亏格分布这一概念作为图的又一拓扑不变 量，图的亏格分布多项式包含的信息量远远超过图的最大亏格与最小亏格，因此其 研究难度也相应的增大近年来，一些学者对其进行了深入的研究同样确定一个 图的亏格分布也是一个n p 一难问题，所以，目前得到的结果还集中在一些比较简单 的图类上以下介绍一些亏格分布的基本概念 曲面在这里是指无边缘的二维紧流形事实上，可以视为平面上的一个偶多边 形，每边分配一个方向而且两两成对，将同一对边依方向合而为一所得到的注意， 在合而为一的过程中，可以收缩或伸长，但不能断裂 闭曲线公理1 3 4 】在曲面上的任何一条闭曲线，要么有两侧，要么只有一侧，二 者越居其一 一个曲面如果其上的所有闭曲线都是双侧的，则称它为可定向曲面，否则称它 为不可定向曲面在本文中，只考虑可定向曲面 在保持连通性不变的条件下，一个曲面所能劈分成的闭曲线的最大数目，称为 这个曲面的准亏格可定向曲面的亏格定义为其准亏格的一半( 可定向曲面的准 亏格总为偶数【3 4 】) 一般的，亏格为h 的可定向曲面瓯可以认为是在球面上增 加h 个手柄所得到的曲面 图g 在可定向曲面s 上的嵌入是指图g 到可定向曲面s 的一个一一的连 续映射，使得不同边的像只在他们公共端点的像处相交，如果图g 的像相对于可 5 北京交通大学硕士学位论文 第一章绪论 定向曲面s 的补的每一个联通分支( 称为嵌入的一个区域) 都同胚于个开圆盘， 则称该嵌入为胞腔嵌入( 或2 - 胞腔嵌入) 本文均考虑胞腔嵌入，在不至于混淆的 意义下也叫做嵌入 定理1 3 1 ( e u l e r 公式) 酬如果图g 可嵌入到亏格为g 的可定向曲面岛 上，则：i y l i e i + l f i = 2 2 9 其中：i v i 指图g 的顶点的个数，l e i 指g 的 边的个数，i f i 指图g 嵌入到曲面s 上区域的个数 设，和g 是g 到曲面s 上的两个嵌入，：g _ s 和g ：g _ s ，若存在保 持方向的s 的自同构映射h ：s _ s 使得h i = g ，则称这两个嵌入，和g 是相 同的 设i 为非负整数，吼( g ) 为g 在亏格为i 的曲面上不同的嵌入的个数，则g 的亏格分布是：踟( g ) ，g l ( g ) ，耽( g ) ，而g 的亏格分布多项式为： 尼( z ) = 玑( g ) i = o 设m 是一个曲面集，g i ( m ) 为m 中亏格为i 的不同曲面的个数，则m 的亏 格分布是：g o ( m ) ，g l ( m ) ，9 2 ( m ) ，而m 的亏格分布多项式为： 知( z ) = e g i ( m ) x 3 2 关于亏格分布已有的结果 自从g r o s s 和f u r s t 提出亏格分布的概念后，有很多学者对其进行了研究并 得到了一些图类的亏格分布，例如f u r s t 等已经得到梯图( c l o s e d - e n dl a d d e r s ) 和 鹅卵石路图( c o b b l e s t o n ep a t h ) 的亏格分布 4 ，6 】，m c g e o c h 等得到了圈梯图 ( c i r c u l a rl a d d e r s ) 和麦比乌斯梯图( m o b i u sl a d d e r s ) 的亏格分布【3 8 ，g r o s s 等人 利用j a c k s o n 给出的一个计算公式，得到了环束风( b o u q u e t so fc i r c l e s ) 的亏格 分布的递推公式【8 】；t e s a r 在2 0 0 0 年得到了环梯图( r i n g e ll a d d e r s ) 和鹅卵石路 ( c o b b l e - s t o n ep a t h ) 的亏格分布【4 3 】，k w a k 和l e e 给出了环束岛( b o u q u e t so f c i r c l e s ) 和双极图( d i p o l e ) 的亏格分布【2 5 】 此外郝荣霞，万良霞等利用刘彦佩提出的联树法得到了一些比较复杂的正则 图的亏格分布 1 4 ，1 5 ，4 5 】 6 北京交通大学硕士学位论文第二章关于交叉数新的结果 第二章关于交叉数新的结果 设a 和b 是图g 的边集的两个子集，咖是图g 的一个好的画法则记 c r ( a ，b ) 为在画法妒下一条边在a 中另一条边在b 中构成交叉点的个数特别 的记c r , ( a ，a ) 为c r a ( a ) ，而c r , ( g ) 表示在画法下g 的交叉点的个数 设a ，b 和c 是图g 的边集的不交子集，则下面公式显然成立： c r 妒( aub ) = c r 币( a ) + c r , ( b ) + c r , ( a ，b ) ； c r , ( a ，b u c ) = c t 西( a ，b ) + c ( a ，d ) ( 1 ) 1 k l ，1 ，3 ，n 和岛+ & 的交叉数 m a r i i nk l e 6 在文献 2 0 1 中给出了所有顶点数为4 的图分别与路或圈的联 图的交叉数，本节利用k o u h e ia s a n o 给出的完全三部图心加。的交叉数 1 】以及 黄元秋给出的完全三部图k 1 ，4 m 的交叉数【1 6 】，得到了完全四部图k 1 ，1 ，3 ，。的交 叉数，同时得到了& + 晶的交叉数，这里& 指完全二部图k 1 n 1 1 k 1 ，l ，3 ，。的交叉数 定理2 1 1 c r ( k l 1 3 ，住) = n 2 一引 证明：设k 1 ，l ，3 ，。是完全四部图，( x ，彬z ) 是它顶点集的一个划分，其中： x = z ，y = 箩 ，w = w l ，w 2 ，伽3 】i ，z = z l ，z 2 ，) 完全四部图 k 1 ，1 ，3 ，n 的边集为：e = ( z y ) u ( z 叫i ) i 毗) u ( 秒叫i ) l 妣) u ( x z i ) z i z ) u ( y z d l z _ i z u ( w i z j ) 1 w i 肜z j z 为了表明c r ( k 1 1 3 。n ) n 2 一【；j ，我们考虑将k 1 ，l 3 ，n 映射到平面上的画法 妒： ( 1 ) 妒( 茁) = ( 0 ，1 ) ( 2 ) 妒( ! ，) = ( 0 ，- 2 ) ( 3 ) o ( w 1 ) = ( 0 ，2 ) ，妒( 叫2 ) = ( 0 ，一1 ) ，( 训3 ) = ( 0 ，一3 ) ( 4 ) o ( z i ) = ( ( 一1 ) 【+ 2 1 j ，0 ) ，1 i 礼 ( 5 ) 边集 ( x z i ) z i z u ( y z i ) z i z ) u ( 桃乃) i 叫i 彤乃z ) 中每一条 边的像各自是一条直线段； 边( x ) - ) ，( x w 2 ) ，( y w 2 ) 和( y 叫3 ) 的像也各自是一条直线段； 边( t w 3 ) 交边集( 9 0 1 x i ) ，( i = o ( m o d 2 ) ) ； 边( z 秒) 交边集( w 2 z i ) ，( i = o ( m o d 2 ) ) ； 7 北京交通大学硕士学位论文 第二章关于交叉数新的结果 边( y w l ) 交边集( 叫3 z i ) ，“= 1 ( r o o d 2 ) ) 例如，我们画出k 1 。1 ，3 5 如图1 所示 。i 苄 陶1 ：k i 1 3 。5 容易计算出c r 妒( 坼1 3 ，n ) = n 2 一【j 这就表明c r ( k - ，。，3 ，n ) 冬n 2 一【詈j 因 此，我们只需要证明：对于尬，1 3 ，托的任意好画法妒有盯砂( k 3 ，n ) n 2 一l 罟i 假设存在图k 1 1 3 ，。的好画法满足c r 妒( k x ，l ，3 ，。) n 2 一l 等j 设e 1 是包含 k 1 ，1 ，3 ，n 的除了( x y ) 之外所有边的甄，l ，3 ，n 的边子集则由公式( 1 ) 有 ( 和( k 1 1 , 3 ，n ) = c ( 日) + c ( e 1 ，( z 可) ) + c r ( ( z 3 ，) ，( z y ) ) = c ( e 1 ) + c r y ( e , ，( z 可) ) 因为子图g e 1 】与完全三部图k 2 ，3 n 同构，所以由文献 1 】那么c r 妒( e 1 ) z ( 5 ，礼) + n ，z ( 5 ，n ) = 4 【；j 【堡尹j ，那么，c r ( 局，( 。耖) ) 【墨j 我们考虑与顶点y 关联的边集不失一般性，设在画法妒下，( z 箩) ，妒( y 1 ) ， ( y w 2 ) ，妒( y w 3 ) 在平面上围绕顶点( ) 以顺时针方向排列那么它们构成四个 角设a 1 ，a 2 ，a 3 ，a 4 分别是边集 ( y z d l = i z ，在下落入分别由( ( z 3 ，) ) 和 矽( ( 可伽1 ) ) ，( ( y 伽1 ) ) 和( ( y 叫2 ) ) ，( ( ! ，伽2 ) ) 和( ( ! ，叫3 ) ) ，( ( y 蚴) ) 和( ( z 可) ) 所 成的角中的边子集( 见图2 ) 所以ia 1i + ia 2i + ia 3i 十ia 4i = n 对于图坼，1 ，3 ，n 的画法来讲，一定存在一个足够小的实数e 使得对于k l 1 3 n 的每一条不与y 关联的边e 满足( e ) n ( ( 可) ，) = 0 ，其中( ( ) ，e ) = s r 2 j i i s 一( y ) j | ) ，i i s 一( 秒) | j 指在平面中8 与( ) 的距离下面分两种情况 8 北京交通大学硕士学位论文第二章关于交叉数新的结果 说明 图2 情况1 ：假设n 是偶数，因为考虑a l 和a 3 或考虑a 2 和a 4 是一样的，不 失一般性，我们考虑a 1 和a 3 如果i a l i l a 3 l ，那么通过以下的步骤可以构造出一个完全三部图k 1 , 4 ，n + l 以及它的一个好的画法 步骤1 ：在区域( 矽( 可) ，) 内妒( z 耖) 的附近增加一个新的顶点+ 1 步骤2 ：删除妒( y w i ) 落在( 妒( y ) ，) 中的部分，i = 1 ，2 ，3 步骤3 ：在( z ! ，) 附近用一条线连接( z ) 和z n + 1 使得它仅与边集f 中的边 在下的像相交，其中f = e e ( k 1 1 3 ，n ) i 妒( e ) n 妒( z 可) 谚 在矽( z 可) 附近用 一条线连接咖( ) 和+ l 使得它不与k l ，1 ，3 n 任意边的像相交 步骤4 ：用一条最初在( 妒( y ) ，e ) 内，然后沿着砂( ( y 姚) ) 的线连接+ 1 和 妒( 毗) ，i = 1 ，2 ，3 则结果如图3 所示 这样我们得到一个k 4 ，n + l 的一个好的画法，则容易得出： 盯( k 1 ，4 。n + 1 ) = c r 毋( k 1 ，1 ，3 ，n ) + c r 毋( e 1 ，( x y ) ) + 2 1 a 1 i + i a 2 i + i a 4 i + 1 因为i a l l i a 3 l ，c r 毋( e 1 ，( 叼) ) 【j ，所以， c r 4 y ( k 1 ，4 ，n + 1 ) 札2 一【詈j l + ；j 一1 + n + 1 = n 2 + 礼一1 ( n + 1 ) n = c r ( k 1 ，4 。n + 1 ) ， 这样产生矛盾 9 北京交通大学硕士学位论文 第二章关于交叉数新的结果 图3 2 如果i a l l i a 3 i ，那么通过以下的步骤可以构造出一个完全三部图k 1 ，4 ，1 以及它的一个好的画法 图4 2 步骤1 ：在( y 钮2 ) nj 7 v p ) ，) 的某一个位置增加一个新的顶点z n + 1 步骤2 ：删除( 3 妣) 落在n c e p c y ) ，e ) 中的部分，i = l ，3 步骤3 ：用一条最初在、，( ( 剪) ，e ) 内，然后在 y ) 附近的线连接+ 1 和( z ) 使得它仅与边集r 中的边在下的像相交，其中一= 【e e ( k t 3 ，n ) i 矽( e ) n ( z 可) 仍o re a 3ua 4 步骤4 ：用_ 条最初在( 矽( y ) ，e ) 内然后沿着( ( y 毗) ) 的线连接z n + 1 和 1 0 北京交通大学硕士学位论文 第二章关于交叉数新的结果 ( 铋) ，i = 1 ，3 则结果如图4 所示 这样我们得到一个j q ，钿+ 1 的一个好的画法扩，则容易得出： 口矽，( k i ，4 计1 ) = c ( k l ，1 3 ，n ) + c r 毋( e 1 ，( z ! ，) ) + 2 a 3 l + l a 2 l + l a 4 l n 2 一【j 一1 + 【j 一1 + 7 l = 佗2 + n 一2 ( 佗+ 1 ) n = c r ( k 1 ，4 ，n + 1 ) ， 这样产生矛盾 情况2 ：假设n 是奇数，则a l a 3 或a 2 a 4 ，否则n 为偶数不失一般 性，假设a l a 3 如果i a t l a 3 l ，那么通过与情况l 中i a l si a 3 l 完全相似的步骤可以构 造出一个完全三部图k ，4 t 珏+ l 以及它的一个好的画法l ，并且可以得出： c ，l ( k i ，4 ，n + i ) = c ( k l ，i ，3 m ) + c r 妒( e l ，( z 3 ，) ) + 2 1 a , f + i a 2 l + i a 4 i + i n 2 一【量j 一1 + 【詈j i - i - n 一1 + 1 = 礼2 + 扎一2 i a 3 i ，那么通过与情况l 中l a l i i a 3 l 完全相似的步骤可以构 造出一个完全三部图k l ，4 卅l 以及它的一个好的画法矽2 ，并且可以得出： c r 赴( 坼，4 ，竹+ 1 ) = c ( k i ，1 ，3 ，n ) + c r o ( e l ，( z y ) ) + 2 1 a 3 i + l a 2j + j a 4 i n 2 一【；j l + 【詈j 一1 + n 一1 = 佗2 + n 一3 ( n + 1 ) 孔= c r ( k 1 ，4 ，n + 1 ) ， 这样产生矛盾 综合情况1 和情况2 ，假设( 所，1 , 3 ，n ) n 2 一【；j 错误定理得证1 1 2 岛+ 晶的交叉数 定理2 1 2 c r ( 岛+ & ) = n 2 一【j 证明：设x ，y ，缈，z 是定理2 1 1 证明中k i ，1 3 ，拜的顶点集的划分因为 x u 彤以及边集 ( x w i ) i w i 构成岛，yuz 以及边集 ( 蔬) i 忍z ) 构成 & 同时边集 ( z y ) u ( 可砒) h ，u ( x z i ) i z i z u ( 毗勺) 彬乃z 连接岛和& 因此岛+ 岛和k 1 ，l ，3 ，。是同构的两个图，所以有c r ( 岛+ 岛) = c r ( k 1 l 3 ，n ) = n 2 一【；j 此定理证毕! 北京交通大学硕士学位论文 第二章关于交叉数新的结果 2x 的交叉数 轮图是一个孤立点的图与圈图g 的联图，其中g 指包含讫条边的圈 设f ，m 指包含m 条边的路，于平和黄元秋在文献【4 7 】中对p m 的交叉数的 上界进行了研究，并给出了的交叉数的一个上界： 仃( 帆x ) ( m 1 ) 【詈儿孚j + ( m + 1 ) 进一步他们证明了当_ m 3 时等式成立m a r i 宣nk l e 酌在文献2 0 ，2 3 1 中证明了 当礼4 时等式成立 本节利用d r a g ob o k a l 的理论，证明了对与任意礼3 和m l 时文献 47 】 中上界等号仍然成立 定理2 2 1 c r ( p m ) = ( m 一1 ) 【；儿孚j + ( m + 1 ) ，n 3 ，m 1 为了证明w 。p m 的交叉数是( m 一1 ) 【詈儿孚j + ( m + 1 ) ，先介绍一些定义： 对于i = l ，2 ，设g 是两个图并且仇是g t 的度为d 的顶点设批= n o 。似) 是g i 中与v 相邻的顶点集，7 ：n 1 _ 2 是一个一一映射则g 1 和g 2 关于7 的 链积( z i pp r o d u c t ) g 1o ，g 2 指由顶点集y ( g 1o ，g 2 ) = v ( g l v 1 ) u y ( g 2 - - i7 2 ) 和边集e ( g 1o ，g 2 ) = e ( g x v 1 ) ue ( g 2 一u s ) u ( u 7 - ( u ) ) i u n 1 ) 构成的图 对于i = 1 ，2 ，设d 是图g t 的最优画法并且是g 的度为d 的顶点， 那么g i 的最优画法皿在平面上确定了批中的点围绕仇排列的顺序设双 射丌i ：她_ 1 ，2 ，d 是将m 中的点按其围绕优排列的顺序分别映射到 1 ，2 ，d 的一一映射，则定义d l 和d 2 关于t ，l 和耽的链映射( z i pf u n c t i o n ) 盯为盯：1 _ k ，仃= 町1 7 r 1 引理2 2 2 1 2 1 对于 = 1 ，2 ，设d i 是图g l 的最优画法并且仇是g i 的度为d 的 顶点，盯是d l 和现关于t ，l 和t j 2 的链映射，则c r ( g 1o 口g 2 ) c r ( g 1 ) + c r ( g 2 ) 设s 是图g 的顶点集的子集且isi = 佗，如果