（运筹学与控制论专业论文）联图与笛卡尔积图类的交叉数研究.pdf

摘要 图的交叉数是在近代图论中发展起来的一个重要概念，主要研究如何 把图画在一个平面上，使其交叉的数目最少通常这项研究都采用纯数学 方法证明然而，确定一般图的交叉数是一个n p 一完全问题，因此，到目前 为止有关交叉数的结果比较少，仅限于一些特殊图和简单图的交叉数甚 至于在许多情况下，试图找出图的交叉数的一个好的上界或下界也很困 难本文运用组合方法和归纳思想以及反证法，研究了关于联图的交叉数 以及一些图与星的笛卡尔积的交叉数全文由四个章节构成 在第一章中较为详细地交代了交叉数的起源，交叉数研究的理论及实 际意义，以及这项研究工作在国内外发展的动态同时还简要介绍了本文 的写作背景，将要解决的问题和文章的创新之处 在第二章中对与交叉数有关的一些基本概念和性质进行了解析，同时 介绍了阅读本文所需要的预备知识，并介绍了在后续文章中将会出现的 定义、记号以及常用到的一些性质对于部分使用较少的概念我们放到具 体的章节中来交代 在第三章中探讨了与联图有关的交叉数一方面，在假定z a r a n l 【i e 而c z 猜想成立的基础上计算出了一些五阶图和六阶图与路的联图的交叉数；另 一方面，给出了vr 的交叉数 在第四章中着重研究了与笛卡尔积交叉数有关的问题，确定了一些特 殊六阶图与星& 的笛卡尔积的交叉数 在结语中简要地介绍了作者今后研究的方向和重点，同时指出了一些 有待解决的问题 关键词：图，画法，交叉数，笛卡尔积，联图 a b s t r a c t t h ec r o s s i n gm l b e ro fg r a p h s 诲av 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 1 s oi np r a c t i c e t h e ni th a u sa t t r a c 七 t e dm a n yf a p ht h e o r i s tt os t u d yw eh a v ea l r e a d yk n a w nt h a tt od e t e r m i n a t i o no f t h ec r o s s i n gd 1 1 1 n b e r sf o rg r a p h si sn p c o m p l e t e b e c a u s eo fi t sd i m 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 l l sw h o s ec r o s s i n gn u 瑚l b e r sh a 鹏b e e nd e t e r m i n e d 甜ev e 巧s c a r c e ， a 1 1 dt h e r e 雒eo n l ys o m es p e c i a lg r a p h sw h o s ec r o s s i n gi m 珈【b e r s 缸el 【n 伽m e v e n i ns o m ec a s e s ，i ti sv e 可d 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 l l i d b e r so fg r a p b s i nt l l i sp a p e r ，w es t u d yt h ec r o s s i n gn u i i 【b e r so ft h ec a n e s i a n p r o d u c t so fp a t h sw i t hs o m eg r a p h s ，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 t l l i sp 印e ri sc o n s i s to ff o u rc h a p t e r s ： 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 s ，t h eo r i g i 璐o ft h ec r o s s i n g n u m b e r ，t h ed 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 璐a r o u n dt h ew d r l d ，a n dp r e s e n tt h e m e a l l 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 us o l v e i nc h a p t e rt w d ，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 i n - b e r ，a n di i l 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 出n gt h i sp a p e r i nc h a p t e rt h r e e ，w ed i s c u s st h ec r o s 8 i n gm l i 】由e ro ft h ej o i n 0 no n eh a n d ，w e d e t e r 面n et h ec r o s s i n g 肌瑚【b e ro ft h ej o i no fs o m e 孓v e r t e xg r a p h sa n ds o m e5 一v e r t e x g r 印h sa n dp a t h sri ft h ez a r a i l l 【i e w i c z sc o n j e c t u r ei sh o l d ；o nt h eo t h e r h a n d ，w e g i v et h ec r o s s i n g 肌l b e ro f vr i nc h a p t e rf b u r ，r 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 fs t a u r & w i t hs o m es p e c 试6 - v e r t e xg r 印h s i nf i n a u y ，w ei n t r u d u c et h ed i r e c t i o l l so fo u rr e s e a r c hw o r ka 1 1 dp u tf o r w a r d s o m er e l a t i v ep r o b l e m sw h i c h 、ew i l lg oa h e a d k e y w d r d s ：g r a p h ，d r a w i n g ，c r o s s i n gn u l b e r ，c a r t e s i a np r o d u c t ，j o i n i i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果除文中已经注明引用的内容外，本论文不含任何其它个人或集体已 经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体，均已在文 中以明确方式标明本人完全意识到本声明的法律结果由本人承担 学位论文作者签名：力濉 - 了”胪日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅本人 授权湖南师范大学可以将本学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 l 、保密口，在年解密后适用本授权书 2 、不保密曲 ( 请在以上相应方框内打 ) 作者签名膨降 导师签 日期： 日期： 年媚幻 年矿月喃 毋-一、只， 联图与笛卡尔积图类的交叉数研究 1 引言和文献综述 图论( 1 】 3 】) 是一个内容非常丰富而且应用十分广泛的数学分支，起 源于著名的哥尼斯堡七桥问题 在哥尼斯堡的普莱格尔河中有两个岛，七座桥将河岸与岛以及岛与岛 联接起来问题在于能否从四块陆地中任何一块出发，在通过每座桥恰好 一次后回到起点人们经过数次尝试后都没有成功欧拉在1 7 3 6 年解决 了这个问题，他将陆地看成点，桥看成边，构造了一个图，再用与图有关的 方法证明了这个问题没有解因此，欧拉成为了图论的创始人如今图论 已经发展出很多分支，并且和实际应用联系非常紧密图的交叉数正是在 近代图论中发展起来的一个重要概念，简单说来，主要研究如何把图画在 一个平面上，使其交叉的数目最少 1 9 7 7 年匈牙利数学家p a u lt u r 缸在图论杂志创刊时撰文“an o t eo f w ，e l c o m e ( 4 】) ，提到了他于2 0 世纪4 0 年代在布达佩斯工作时碰到的问题 “r 1 1 u r 缸sb r i c kf a c t o r yp r o b l e m 静，即平面图的交叉数问题自从交叉数的概 念被提出以来，研究图的交叉数逐渐成为国际上一个非常活跃的数学分 支，吸引了国际上众多的数学家和计算机科学家的关注，尤其是很多图论 专家对这方面进行了深入研究 事实上，研究图的交叉数不仅具有重要的理论意义，而且具有较强的 现实意义，在许多领域有着非常广泛的应用，例如： ( 1 ) 超大规模集成电路y l s ，中的圈布局问题； ( 2 ) 草图的识别与重画问题，使之具有比手写汉字识别应用更为广泛 的应用领域； ( 3 ) 工业上电子线路板设计中的布线问题； ( 4 ) 生物工程d 4 的图示； 湖南师范大学2 0 0 9 届硕士学位论文 ( 5 ) 软件开发过程中文档部分的e r 图( 实体联系图) 等的自动生成； ( 6 ) 在几何学、堆垒数论与测度论等理论中的应用 然而，一般说来要确定图的交叉数是十分困难的，g a u r e y 和j o h n s o n 在 文献( 5 】) 证明了确定图的交叉数问题属于n p - 完全问题由于其具备一 定难度，目前国际上对交叉数的研究进展十分缓慢，范围也受到了局限，能 确定交叉数的图类型较少也正因此，使得这项研究更具有挑战性随着对 图的交叉数问题研究的深入，我们发现值得研究的内容也日益丰富一方 面希望确定具体图类的交叉数，另一方面希望得到与图的交叉数有关的 其它性质，研制有关确定图的交叉数的算法等目前看来，主要集中在以下 几个方面： 1 一些特殊图类的交叉数 这些图主要包括结构特殊，规律性较强的图类一部分已经确定了交 叉数的精确值，还有一部分只给出了交叉数的上下界或猜想具体结果如 下： ( 1 ) 平面图 平面图的交叉数为o 例如，完全图，当n 5 时是平面图，从而其交叉数为o ；对完全2 部图当m ，n 3 时也有相同结果 从图论知识中我们已经知道一个图是平面图的充分必要条件是： k u r a t o w s l ( i 定理( 【6 】i 【7 )图g 是平面图当且仅当它没有同胚于图蚝 或甄3 的子图 ( 2 ) 完全图 完全图结构特殊，任意两个顶点之间都有且只有一条边相连关于完 联图与笛卡尔积图类的交叉数研究 全图的交叉数有一个重要的猜想，即g u y 猜想： c r ( ) = 汹l 字儿孚儿字j 这里用仃( g ) 表示图g 的交叉数；对任意实数n ，用m j 表示不大于n 的最大整数 当我们将完全图的顶点映射到同构于单位球的圆柱体的顶部和底 部的圆盘面上时，在圆盘的顶部和底部相连的点形成两个同构于珞2 的 完全图，在顶部和底部的点间，考虑圆柱体上最短的螺旋状的路，就可以得 到g u y 猜想中的交叉数 目前，已经知道当完全图的顶点数分别为佗= 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，1 1 时，其交叉数分别为o ，o ，o ，o ，1 ，3 ，9 ，1 8 ，3 6 ，6 0 ，1 0 0 最新的结果证明了上述猜 想对于n 1 1 成立( 【8 】- 1 2 】) ( 3 ) 完全2 一部图 实际上，n r a n 的“砖厂问题 等价于确定完全2 部图，n 的交叉 数1 9 5 4 年，z 盯a n l 【i e w i c z 在文献( 【1 3 】) 中“证明 了 c r ( 一= 倒l 孚堆儿孚j ，( m 剑 ( 习惯上称之为尻他扎舰e 砸c z 猜想) 然而在1 9 6 9 年，m n g e l ( 1 4 】) 和k a i n e n 各自独立发现z a r a n l 【i e w i c z 在文 献( 1 3 】) 中的证明有错误，同时指出z a r a n l 【i e w i c z 猜想至少是某个精确值的 上界，因而确定完全2 部图m 的交叉数问题目前仍然是一个公开问题 ( 1 5 】) 1 9 7 0 年d j k l e i t m a n 证明了等号对于m i n ( 仇，n ) 6 成立( 1 6 】) ，1 9 9 3 年w b o d a l l 证明了m = 7 且n 1 0 时z a r a n k i e w i c z 猜想成立( 17 】) ，直到目 前为止还未看到关于此方面的更新结果 ( 4 ) 完全3 - 部图 3 一 湖南师范大学2 0 0 9 届硕士学位论文 目前，有关于确定完全3 部图交叉数的文献很少，且证明基本上建立 在已知的完全2 部图交叉数的基础上 上世纪八十年代，k a s a m o 证明了c r ( k ，3 ，n ) = z ( 4 ，佗) + l 詈l ，仃( 恐，3 ，n ) = z ( 5 ，佗) + n ( 【1 8 】) 之后，很长时间未见有其它文献出现直到2 0 0 4 年，黄元秋 等人陆续证明了c r ( 虬，4 ，n ) = 礼( n 一1 ) = z ( 5 ，n ) + 2 l 号l ；c r ( 虬，5 ，n ) = z ( 6 ，n ) + 4 l 鸶i ；c r ( ，4 ，n ) = z ( 6 ，礼) + 2 n ( ( 1 9 】_ 【2 1 】) 这些结果都是建立在z 盯a n l 【i e w i c z 猜想对于m 伽( m ，n ) 6 成立的事实基础上后来黄元秋和他的学生在假 设z a r a n l 【i e w i c z 猜想对于m = 7 成立的前提下，改进了证明方法，通过对已 知的完全盆部图的交叉数的研究，讨论m ，n 的奇偶性，确定了部分k n 的交叉数( 【2 2 】- 2 5 】) 国外学者p - t h o 也在这方面作出了一些结果( 2 6 】) ( 5 ) 完全垂部图 目前，仅有黄元秋及其学生钱春华在完全三部图的基础上，对完全缸 部图作了一定的研究( 【2 7 】) ( 6 ) 联图 目前就联图的交叉数的讨论还很不充分，仅有k u l l ia d l dm u d d e b i h a l 给 出了两个图的联图是平面图的性质( 2 8 】) 以及b o g d a no p o r o w s l 【i 等证明了 凹( gvg ) = 6 ( 2 9 】) 后来m a r i 缸k l e 誊亡给出了路与路，路与圈，圈与圈的联 图的交叉数： 盯( p 仇vr )= z ( m ，佗) ( m 1 ，n 1 ，m 饥 m ，佗) 6 ) ； c r ( p mvg )= z ( 仇，佗) + 1 ( m 2 ，佗3 ，m 饥_ m ，n ) 6 ) ； 仃( vg )= z ( m ，礼) + 2 ( m 3 ，礼3 ，m 饥 m ，佗) 6 ) 并确定了阶数不大于四的所有图与路，圈的联图的交叉数的具体值( 3 0 】) 另外，黄元秋及其学生在这方面也得到了类似的结果，参见( 3 1 】) ( 7 ) 笛卡尔积图 一4 一 联图与笛卡尔积图类的交叉数研究 与联图相比，两个图的笛卡尔积图是另一种图运算，对于长度分别为 m ，n 的圈的笛卡尔积图，f h a r 哪等在1 9 7 3 年提出了著名的猜想( 【3 2 】) ： c r ( g ) = ( m 一2 ) 佗，( 3 m n ) n 础n ec m ”r s 在文献( 6 】) 中对这个猜想的起源，发展过程以及现状等都 做了较为详尽的介绍 m n g e i s e n 和b e i n e k e 在1 9 7 8 年证明了c r ( 岛g ) = 礼( 3 3 】) ，在1 9 8 0 年 证明了c r ( a g ) = 2 佗( 【3 4 ) ，1 9 9 6 年k l e 吾芒和瞰d l t e r 证明c r ( g g ) = 3 n ( 【3 5 】) ，2 0 0 1 年m c h t e r 证明c r ( g g ) = 4 礼( 3 6 】) ，2 0 0 4 年a d 锄s s o n 和磁c h t e r 证明了c r ( 岛g ) = 5 仃( 【3 7 】) 另外，一些阶数确定的圈与圈的笛卡尔积图 的交叉数，如盯( q q ) = 8 ( 3 8 】) ，凹( g g ) = 1 5 ( 3 9 】) ，盯( 瓯g ) = 2 4 ( 4 0 】) ，c r ( 岛g ) = 3 5 ( 4 1 】) 等都已经得到证明，其他与圈的笛卡尔积有关 的结论参考( 4 2 】- 4 5 】) 上世纪八十年代初，b e i n e k e 和n g e i s e n 及j e n d r o i 和沈r b o 晒等人确定 了所有4 阶图与圈的笛卡尔积图的交叉数( 3 4 ， 4 6 】) 路是图论中最基本最简单的研究对象之一，很多文献都对路与其它图 的笛卡尔积图的交叉数进行了讨论，3 阶连通图同构于路忍或圈g ，交叉 数显然为o 因此这方面系统地研究从4 阶图开始捷克数学家k l 战等研 究了一些路与星的笛卡尔积图的交叉数( 4 7 】， 4 8 】) ，1 9 9 4 年确定了所有4 阶 连通图与路的笛卡尔积图的交叉数，之后他又陆续给出了所有5 阶连通图 与路的笛卡尔积图的交叉数( 4 9 】- 5 5 】) 在黄元秋教授的带领下，他的学生 们也先后做出了很多新的结果，参见( 5 6 】一 6 7 】) 2 有某种特点的图的交叉数的一些性质 因为具体确定某个图的交叉数比较难，所以换个角度从交叉数的性质 如临界交叉数，正则图的交叉数，交叉数的奇偶性等着手研究，希望能得出 一5 一 湖南师范大学2 0 0 9 届硕士学位论文 一些有关图的交叉数方面比较好的结果 3 线图的交叉数 图g 的线图l ( g ) 是指顶点集为e ( g ) 的图，其中两个顶点相连的充要 条件是它们在g 中为相邻的边一般来说，图g 和它的线图l ( g ) 的交叉 数满足：c r ( g ) c r ( 三( g ) ) 正是在这些文献的启发下，同时在已有结果的基础上应用并创新相关 方法，我们研究了一些五阶图和六阶图与路r 的联图的交叉数，还得到了 vr 的交叉数；并推广了笛卡尔积图的交叉数，得到了几个六阶图与星 晶的笛卡尔积的交叉数 一6 一 联图与笛卡尔积图类的交叉数研究 2 基本概念和性质 本文涉及到的基本概念和性质，未作特别说明均同文献( 1 】) ，且无特 别说明时文中所涉及的图均指简单连通图 图g 是指一个有序三元组( y ( g ) ，e ( g ) ，妒g ) ，其中y ( g ) 是非空的顶点 集，e ( g ) 是不与y ( g ) 相交的边集，而惦是关联函数，它使g 的每条边对 应于g 的无序顶点对 定义2 1 图g 在平面上的一个画法d ，是指把图的顶点画为平面上的 结点，把图的边画为平面的弧 定义2 2 图g 在画法d 下的交叉数，是指在画法d 下边与边产生的 交叉点的个数，用c r d ( g ) 表示 定义2 3 图g 的交叉数，用c r ( g ) 表示，是指图g 在平面上所有画法 的交叉数中的最小值，即盯( g ) = 蝉n 盯d ( g ) ) 定义2 4 图g 在平面上的一个最优画法，是指产生的交叉数目恰好等 于图g 的交叉数的画法 定义2 5 图g 在平面上的一个好画法，是指图g 在平面上同时满足 以下四个条件的画法： ( 1 ) 连接同一个结点的任意两条边不相交； ( 2 ) 边不能自身相交； ( 3 ) 任何两条相交的边最多交叉一次； ( 4 ) 没有三条边交叉于同一个点( 见图2 1 ) 一7 一 湖南师范大学2 0 0 9 届硕士学位论文 图2 1 图g 的好画法中不允许出现的四种情况 注1 定义2 5 中的条件( 4 ) 是为了研究而统一规定的 前三个条件( 1 ) ，( 2 ) ，( 3 ) 是最优画法中必然满足的因为如果不满足，我 们可以对画法进行改进，从而得到一个具有更小交叉数的画法，这与最优 画法的定义矛盾( 见图2 2 ) ) ( 图2 2 对图2 1 中前三种画法的改进 注2 定义2 1 一定义2 4 中的“平面 可改为“f h l 面 ，且相关定义可推 广到曲面的情况，本文将在第五章中讨论图在胎面上的交叉数 定义2 6 设图g 在平面上的一个画法为d ，日是g 的子图，则d 在子 图日上的限制画法为画法d 中与子图日有关的的部分，记作d k 定义2 7 设图g 在平面上的一个画法为d ，g 在d 中的一个交叉点 是指在d 中图g 的两条边在非结点处的相交点 例如，图2 3 中的点z 是一个交叉点 定义2 8 设图g 在平面上的一个画法为d ，则将由顶点，边，交叉点以 及边的片断围成的部分称为在画法d 下的一个区域 8 一 联图与笛卡尔积图类的交叉数研究 例如，在图2 3 中分别指出了完全图蚝在画法d 下的8 个区域 图2 3 玩在画法d 下的8 个区域：e = 1 ，2 ，8 ) 两个图g ，和g 2 的笛卡尔积图，用g 。g 2 表示，它是这样的图：点 集y ( g 1 g 2 ) = y ( g 1 ) y ( g 2 ) ；边集e ( g 1 g 2 ) = ( u t ，) ，( u n ，) ) ：= 且 ，) e ( g 2 ) ，或者 仳 ，u n ) e ( g 1 ) 且= ) 两个图g - 和g 2 的并图g 。ug 2 是指g 的一个子图，其顶点集为 y ( g 1 ) uy ( g 2 ) ，其边集为e ( g 1 ) e ( g 2 ) ；如果g 。和g 2 是不相交的，有时就 记其并图为g ，+ g 2 两个点不相交的图g - 和g 2 的联图，用g 。vg 2 表示，它是在g t 和g 2 的并图中，把g 。的每个顶点和g 2 的每个顶点连接起来所得到的图 图g 的一个剖分图是指把g 的边进行一系列剖分而得到的一个图 若从图f 的某些边中加入或抹平2 度点( 均可反复多次) 得到的图与 图日同构，则称f 和日同胚，记为f 一日 性质2 1 设d 为图g 的好画法，若g 。，g 2 和g 3 为g 的边不相交子图， 则 c r d ( g 1ug 2 ) = c 砀( g 1 ) + 盯d ( g 2 ) + 盯d ( g 1 ，g 2 ) ， c r d ( g 1ug 2 ，g 3 ) = 仃d ( g 1 ，g 3 ) + 盯d ( g 2 ，g 3 ) 性质2 2 若f 一日，则有：c r ( f ) = c r ( ) 一9 湖南师范大学2 0 0 9 届硕士学位论文 性质2 3 若日是图g 的子图，则有：c r ( 日) c r ( g ) 一1 0 联图与笛卡尔积图类的交叉数研究 3 与联图有关的交叉数 目前就联图的交叉数的讨论还很不充分，仅有k u u ia n dm u d d e b i h a l 给 出了两个图的联图是平面图的性质( 2 8 】) 以及b o g d 锄o p o r o w s l 【i 等证明了 c r ( gv 醌) = 6 ( 【2 9 】) 后来m a r i 五nk 1 e 己给出了路与路，路与圈，圈与圈的联 图的交叉数：盯( p m v r ) = z ( 仇，n ) ( m 1 ，钆1 ，m 饥 m ，佗) 6 ) ；c r ( 岛v g ) = z ( m ，n ) + 1 ( m 2 ，n 3 ，m i n m ，竹) 6 ) ；盯( v g ) = z ( m ，n ) + 2 ( m 3 ，n 3 ，m 饥 m ，仇) 6 ) 并确定了阶数不大于四的所有图与路，圈的联图的交叉 数的具体值( 3 0 】) 另外，黄元秋及其学生在这方面也得到了类似的结果， 参见( 【3 1 】) 本章在此基础上进一步确定了一些五阶图和一些六阶图的联 图的交叉数( 见图3 1 ) 叁金 g 1 = &g 2 g 3g 4g 5 唇佟蜃 g 6 = 昆 g 7g 8 g 9 g 1 0 图3 1 四个五阶图和六个六阶图 本章的结果是如下定理： 定理：设q = 1 ，2 ，1 0 ) 为上述所示的图，r 是有n 个顶点的路，则 湖南师范大学2 0 0 9 届硕士学位论文 有 ( 1 ) 仃( g jvr ) ( 2 ) 盯( qvr ) ( 3 ) c r ( qvr ) ( 4 ) c r ( q v r ) z ( 5 ，n ) + 2 【昙j ，歹= 1 ，2 ，3 z ( 5 ，n ) + 【昙j ，歹= 4 z ( 6 ，n ) + 2 【昙j ，歹= 5 z ( 6 ，n ) + 4 【芸j ，歹= 6 ，7 ，8 ，9 ，1 0 3 1五阶图与路r 的联图的交叉数 本节中我们在m a r i 丘nk l e 琵的基础上确定了一些五阶图与路r 的联 图的交叉数 3 1 1 g 1vr ，g 2vr 和g 3vr 的交叉数 图3 1 1g 1vr 的一个好画法 图3 1 2g 2vr 的一个好画法 1 2 联图与笛卡尔积图类的交叉数研究 图3 1 3g 3vr 的一个好画法 定理3 1 1c r ( qvr ) = z ( 5 ，他) + 2 【鸶j = 死一1 ) 0 = 1 ，2 ，3 ) ，其中佗1 证明：图3 1 1 ，图3 1 2 ，图3 1 3 说明了盯( g tvr ) z ( 5 ，n ) + 2 【鸶j = 4 【詈儿孚j + 2 【詈j = n ( n 一1 ) 0 = 1 ，2 ，3 ) 因为g 包含了一个同构于k t ，4 ，n 的子 图，且仃( ，4 ，n ) = 礼( n 一1 ) ( 见参考文献【1 9 】) 所以我们可得到盯( g tvr ) c r ( 托，4 ，n ) = z ( 5 ，礼) + 2 【詈j = 几( n 一1 ) ( i = 1 ，2 ，3 ) d 3 1 2 g 4vr 的交叉数 彳念 j 夕叶弋 忒髟 巩的一个好画法 图3 1 4 6 c 图3 1 5图3 1 6 g 4 ( b ) 首先，我们来构造下面的图玩：在顶点划分为_ t t ，2 如) 与 u ，耽， ，) 的完全二部图玩，n 中，增加g 4 ( 见图3 1 ) 的五条边，则可得到一个新 图玩；其中风包含n 个5 一度点、2 个( n + 1 ) 一度点、1 个( 佗+ 2 ) 一度点、2 个( 竹+ 3 ) 一度点和5 礼+ 6 条边( 见图3 1 4 ) 在图巩中，用正( i = 1 ，2 ，钆) 一1 3 一 e d 湖南师范大学2 0 0 9 届硕士学位论文 表示与顶点屯关联的边集( 见图3 1 5 ) 于是易得 巩= g 4u 蚝，n = g 4u ( u 于) t = 1 引理3 1 2 令矽为风的一个好画法，若存在1 l 歹n ，使得 c r 西( ，p ) = o ，则有 c ( g 4 ，矿up ) 1 证明：令日= 为巩的边导出子图由于哪( ，p ) = o ， 且在好画法中连接同一个结点的任意两条边不相交，故由咖导出的子画 法pu p 必同构于图3 1 6 ( a ) 用口，6 ，c ，d ，e 来表示g 4 的五个顶点( 见图 3 1 6 ( b ) ) 显然，对于任意z y ( g 4 ) ，都恰有g 4 的另外两个顶点在包含 z 的区域边界上又因为d g 。( 6 ) = 3 ，从而g 4 中与点6 关联的三条边中 至少有一条边与日交叉一次同样d g 4 ( d ) = 3 ，故g 4 中与点d 关联的三 条边中至少有一条边与日交叉一次如果此两个交叉不相同，则显然有 c r 毋( g 4 ，pup ) 1 ；如果此两个交叉相同，此时与边集日交叉的边只能是 磁，同样g 4 至少有一条边与日交叉一次从而也有郇( g 4 ，pup ) 1 综 上所述，结论成立，证毕 口 定理3 1 3 c r ( ) = z ( 5 ，礼) + 吲，n 1 证明：图3 1 4 说明了 c r ( 巩) 盯( 蚝一) + 【昙j ：z ( 5 ，n ) + 【昙j 因此，为了证明定理成立，我们只需要证明对巩的任意画法都有盯( 玩) z ( 5 ，礼) + 【詈j 成立我们对n 用归纳假设法来证明相反的不等式当佗= 1 时不等式显然成立，当n = 2 时不等式也成立，因为凰包含了一个同构于 虬，3 的子图，其交叉数为1 现假设对佗3 时，有 仃( 巩一2 ) z ( 5 ，佗一2 ) + 【兰丢兰j 一1 4 联图与笛卡尔积图类的交叉数研究 又考虑到存在矾的一个好画法咖使得： a o ( 日n ) z ( 5 ，礼) + 【等j 下面我们根据两个不同的子图和p 在画法中是否交叉来分情况讨 论： 情况1 ：对任意的1 i 歹礼，都有c ( 铲，p ) 1 结合性质2 1 ，有 盯庐( 巩) = ( 蚝，n ) + 哪( g 4 ) + ( 玩朋g 4 ) z ( 5 ，佗) + c r 妒( g 4 ) + ( g 4 ，于) = 1 结合假设，则有 哪( g 4 ) + 郇( g 4 ，于) 引罟j i = 1 一 说明在巩的好画法中，至少存在某个于，不妨设为p 使得c ( g 4 ，p ) = o 一所以存在一个圆盘c 使得g 4 的顶点都位于c 的边界上，g 4 的边都位 于c ! 的内部，而点t n 及与k 关联的边都位于c 的外部考虑由导出的 g 4 u p 的子画法4 ，注意到图g 4 包含了2 个孓度点且这两个点相互关联， 由g 4 的对称性，我们可以得出矿的不同画法有如下5 种( 见图3 1 7 ( 1 ) 一图 3 1 7 ( 5 ) ) 由观察可知在画法下子图有不多于【詈j 个p 与g 4 交叉，且至 少有个詈 个p 不与g 4 交叉下面我们来考虑，它满足c r 多( g 4 ，p ) = o 不失一般性，我们假设( g 4 ，p ) = o 并令f 为巩中的子图g 4u p 函良邀炱凼 ( 4 )( 5 ) 图3 1 7 子画法矿的5 种不同的画法 考虑由分别引出的g 4 和f 的子画法矿和”由于c r ( g 4 ，p ) = o ， 子画法4 划分圆盘用这样一种方法使得所有的顶点都在一个区域的边界 一1 5 湖南师范大学2 0 0 9 届硕士学位论文 上我们不难得到所有可能的子画法矿如图3 1 7 所示因而，所有可能的 子画法咖木如图3 1 8 所示 ( 1 )( 2 )( 3 ) 图3 1 8 子画法咖料的6 种不同的画法 ( a ) ( g 4up ) 的子画法”同构于图3 1 8 ( 1 ) 当顶点岛( 1 i n 1 ) 位于标记为u 的区域时，有c r 妒( p ，g 4up ) 1 ，利用( ，p ) 1 ，则有 ( p ，g 4up ) 2 ；当顶点屯位于其他区域时，有凹毋( p ，g 4 u p ) 3 假设有z 个顶点如位于标记为u 的区域，则其他仡一1 一z 个顶点位于 其他区域前面已经证明z 不超过【鸶j ，所以由性质2 1 ，有 ( 风) = 仃妒( g 4u puu p ) i = 1 n 一1n 一1 = 盯妒( g 4up ，u 一) + c r 西( g 4up ) + c r 西( u 于) t = 1 = 1 z ( 5 ，几一1 ) + 2 z + 3 ( n 一1 一z ) 4 哪孚j + 3 n 一3 一目 z ( 5 ，n ) + 【昙j 一1 6 _ 联图与笛卡尔积图类的交叉数研究 ( b ) ( g 4up ) 的子画法料同构于图3 1 8 ( 2 ) 当顶点如( 1 n 1 ) 位于标记为e 的区域时，有c r 西( ，g 4u p ) 2 ；当顶点如位于其他区域时， 有( ，g 4 u p ) 3 利用类似于3 1 8 ( 1 ) 的方法，有c r 西( 巩) z ( 5 ，n ) + 【孙 ( c ) ( g 4u p ) 的子画法咖+ + 同构于图3 1 8 ( 3 ) 一3 1 8 ( 6 ) 不论如位于哪个 区域，都有( ，g 4up ) 3 然后由性质2 1 ，有 哪( 巩) = ( g 4u p uu 于) t = 1 = 仃毋( g 4up ，u 一) + 凹毋( g 4 u p ) + c r 妒( up ) t = 1t = 1 z ( 5 ，几一1 ) + 3 ( 佗一1 ) z ( 5 ，n ) + 【三j 与假设矛盾 情况2 ：假设存在至少两个不同的子图p 和p 使得它们在画法妒中 互不交叉 不失一般性，我们假定仃西( p 一，p ) = o 由引理3 1 2 ，c r 咖( g 4 ，p _ 1u p ) 1 ，又因为c r ( 飓，5 ) = 4 ，对所有江1 ，2 ，n 一2 ，都有盯妒( p ，p _ 1 u p ) 4 则 哪( 巩_ 2 ，p 。1up ) 4 一2 ) + 1 = 4 n 一7 因为风= 风一2u ( p 一1up ) ，于是有 ( 巩) = 凹毋( 以一2 ) + 仃咖( p 一1u p ) + ( 巩- 2 p 一1u p ) 4 【孚j 【字j + 【字j + 轨一7 = z ( 5 ，n ) + 目 这与假设矛盾所以结论成立 定理3 1 3 证毕 一1 7 湖南师范大学2 0 0 9 届硕士学位论文 定理3 1 4 凹( g 4vr ) = z ( 5 ，n ) + 【鸶j ，n 1 证明：图3 1 9 说明了c r ( g 4 v r ) z ( 5 ，n ) + 【孙比较图3 1 9 与图3 1 4 ， 不难得到g 4vr 包含一个同构于巩的子图，其交叉数为在定理3 1 3 中 证明为z ( 5 ，n ) + 吲所以有盯( g 4 v r ) c ? ( 风) = z ( 5 ，n ) + 吲 定理3 1 4 证毕口 图3 1 9g 4vr 的一个好画法 3 2六阶图与路r 的联图的交叉数 阶数不大于5 的有关的联图的交叉数已经有了一些确切的结论，在本 节中我们更进一步研究六阶图与路的联图的交叉数并确定了岛vr 以及 其它5 个六阶图g j vr d = 5 ，7 ，8 ，9 ，1 0 ) 的交叉数 3 2 1g 5vr 的交叉数 在本文中，为了证明g 5 v r 的交叉数的交叉数，我们先构造下面的一个 图a ：在顶点划分为 u 1 ，吨，蛳， 5 ，) 与 t 1 ，z 2 如) 的完全二部图m 中，将g 5 的六个顶点 u 1 ，晚，地，蛳，) 与另外n 个顶点如( i = 1 ，2 竹) 分别 相连我们可得到一个新图，记为a ( 见图3 2 1 ) 在中，用互( 江1 ，2 竹) 一1 8 联图与笛卡尔积图类的交叉数研究 表示与顶点岛关联的边集( 见图3 2 2 ) ；于是易得 a n = g 5u 甄，n = g 5u ( u 于) t = 1 么汤 三鬈三二r ： 太髟 a n 的一个好画法 图3 2 1图3 2 2 引理3 2 1 令为图a n 的一个好画法，若存在1 t 歹扎，使得 c ( 铲，印) = o ，则有( g 5 ，pup ) 2 证明：令a = ( pu 印) ) 为a n 的边导出子图因为c ( ，印) = o ，且 好画法中关联于同一个点的两条边不相交，所以子图矿up 的由导出 的子画法必同构于图3 2 3 因为图g 5 中包含了两个3 一度点以及三个 2 一度点，用d ，6 ，c ，d ，e ，来表示图g 。中的六条边；若o ，6 ，c ，d ，e ，中的任何 一个点为3 一度点则它与其它三个点连边至少要与a 产生一个交叉，两个 3 一度点则产生至少两个交叉若这两个交叉发生在不同的边上，则引理 得证若交叉只发生在一条边上，则考虑到图g 5 包含了一个4 一圈，它与 a 必产生两个交叉于是可得盯毋( g 5 ，pu p ) 2 口 图3 2 3 如屯 - 1 9 一 图3 2 4 湖南师范大学2 0 0 9 届硕士学位论文 引理3 2 2c r ( a 1 ) = o ，c r ( a 2 ) = 2 证明：首先证明c r ( a 。) = o 从图3 2 1 可知，a 。为平面图，显然有 c r ( a ，) = o 下面证明c r ( a 2 ) = 2 由图3 2 1 可知，存在一个好画法圣， 使得凹圣( a 2 ) = 2 ，根据交叉数的定义知c r ( a 2 ) 仃圣( a 2 ) = 2 下面我们证 明对a 2 的任意好画法 ，均有( a 2 ) 2 若c r ，l ( t 1 ，铲) = o 由引理2 可 得c r ，l ( a 。) 2 若盯_ i ( t t ，p ) = 1 此时画法 的同构画法只有唯一一种， 见图3 2 4 图中的点o ，6 ，c ，d ，e ，代表点u 1 ，t j 2 ，蛳，在图3 2 4 中若点 n ，6 ，c ，d ，e ，中任何一个点是3 一度点，它与其它三个点连边至少要与t 1 u 严 产生一个交叉，根据条件( t 1 ，t 2 ) = 1 ，显然有c r ( a 2 ) 2 若d 是3 一度 点，则它与其它三个点连边可能与t u p 不产生交叉，而点o ，6 ，c ，e ，中还 有一个点是3 一度点，无论哪个点是3 一度点，它与其它三个点连边至少要 与t 1u 严产生一个交叉，从而此时显然也有c r ( a 2 ) 2 若( t 1 ，铲) 2 显然有c r l ( a 2 ) 2 综上所述，对于a 2 的任意好画法 ，均有c r ( a 2 ) 2 从而有c r ( a 2 ) = 2 凸 定理3 2 3 c r ( a n ) = z ( 6 ，n ) + 2 【詈j ，竹1 证明：由图3 2 1 有： c r ( a ) c r ( 甄，n ) + 2 【三j - z ( 6 ，n ) + 2 l 争 因此，为了证明定理成立，只需证明对任意a 的好画法都有c r ( a n ) z ( 6 ，n ) 十2 【鸶j 成立下面我们对佗用归纳假设法来证明相反的不等式由 引理3 2 2 ，我们有c r ( a ，) = o 和c r ( a z ) = 2 ，不等式成立现假设对佗3 有： c r ( 缸2 ) z ( 6 ，几一2 ) + 2 【字j 又考虑到存在的一个好画法使得： 仃咖( a n ) z ( 6 ，佗) + 2 【昙j 一9 n 一 联图与笛卡尔积图类的交叉数研究 下面我们根据两个不同的子图铲和p 在画法中是否交叉来分情况讨 论： 情况1 ：对任意的1 i 歹礼，都有c r 毋( ，p ) 1 结合性质2 1 ，有 哪( a ) = c r 妒( 风，n ) + 仃妒( g 5 ) + 盯西( 玩，n ，g 5 ) z ( 6 ，n ) + ( g 5 ) + ( g 5 ，于) i = 1 结合假设，则有 ( g 5 ) + ( g 5 ，于) 一 湖南师范大学2 0 0 9 届硕士学位论文 这与假设矛盾 在图3 2 5 ( 2 ) 中，若觑位于标记为e 的区域，f 的边上可以产生3 个交 叉，于是有c r 砂( p ，g 5up ) 3 若甄位于其它区域，不难得出p 上的边与 g 5up 产生至少5 个交叉，即有盯毋( p ，g 5up ) 5