（运筹学与控制论专业论文）关于一些图类的交叉数的研究.pdf

摘要 图的交叉数是在近代图论中发展起来的一个重要概念，主要研究如何 把图画在一个平面上，使其交叉的数目最少通常这项研究都采用纯数学 方法证明然而，确定一般图的交叉数是一个n p 一完全问题，因此，到目前 为止有关交叉数的结果比较少，仅限于一些特殊图和简单图的交叉数甚 至于在许多情况下，试图找出图的交叉数的一个好的上界或下界也很困 难本文运用组合方法和归纳思想以及反证法，确定了一些六阶图与星的 笛卡尔积的交叉数，并且研究了联图的交叉数全文由五个章节构成 在第一章中较为详细地交代了交叉数的起源，交叉数研究的理论及实 际意义，以及这项研究工作在国内外发展的动态同时还简要介绍了本文 的写作背景，将要解决的问题和文章的创新之处 在第二章中对与交叉数有关的一些基本概念和性质进行了解析，同时 介绍了阅读本文所需要的预备知识，并介绍了在后续文章中将会出现的 定义、记号以及常用到的一些性质对于部分使用较少的概念我们放到具 体的章节中来交代 在第三章中着重研究了与笛卡尔积交叉数有关的问题，确定了几个六 阶图与星晶的笛卡尔积的交叉数 在第四章中，探讨了与联图有关的交叉数，得到了几个六阶图与路的 联图的交叉数 上述内容充实和发展了图的交叉数的研究成果，并为交叉数的研究提 供了新的方法和思路 在最后一章中，简要地介绍了作者今后研究的方向和重点，同时指出 了一些有待解决的问题 关键词：图，画法，交叉数，笛卡尔积，联图，同胚 a b s t r a c t t h ec r o s s i n g 肌n l b e ro fg r a p h si sa 、r i t a lc o n c e p ti nm o d e r ng r a p ht h e o r y i t s 印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 l l s oi np r a c t i c e t h e ni th a s a t t r a c t e dm a n yg r a p ht h e o r y 唧e r t st os t u d y w bh a ea l r e a d y 妯【o w nt h a tt o d e t e r m i n et h ec r o s s i n gn _ u 瑚b e r so fg r a p l l 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 tt h ec l a s 8 e so fg r a p h sw h o s ec r o s s i n gi l u m b e r sh a b e e nd e t e r m i n e da r e v e r ys c a r c e ，a n dt h e r ea r 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 gn u 血b e r sa r e k n o w n e v e ni ns o m ec a s e s ，i ti sv e r yd i 伍c u l tt of i n dt h eu p p e ro rl 帆，e rb o u n d so f t h ec r o s s i n g 肌l b e r 8o fg r a p h s i nt h i 8p a p e r ，w es t u d yt h ec r o s s i n gn u n l b e r so ft h e c a r t e 8 i a np r o d u c t so fs t a r sw i t hs o m e 口v e r t e xg r 印l l s ，a n dw ed i s c u s st h ec r o s s i n g 肌n l b e r so ft h ej o i n 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 n d sa n do r i g i 璐o ft h ec r o s s - i n gn 1 】i i l b e ra n d i 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 i l dt h ew o r l d ，a i n dp r e s e n t t h em e a i l i n 9 8o ft h er e s e a r c ha n dt h ep r o b l e n l sw h i c hw ew i l ls 0 1 v e i nc h 印t e rt w o ，w eg i v es o m ec o n c e p t i o 璐a n dp r o p e r t i e so ft h ec r o s s i n g 姗h 卜 b e 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 ew h i l er e a d i n gt h i sp a p e r i nc h 印t e rt h r e e ，w ed e t e r 】n i n et h ec r o s s i n g 肌n l 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 r s w i t hs e 、，e r a l6 v e r t e ) ( g r a p h s i nc h a p t e rf o u r ，w ed i s c u s st h ec r o s s i n g 肌m b e ro ft h ej o i n w bg e tt h ec r o s s i n g 肌i n b e ro ft h ej o i no fp a t l l srw i t hs o m e6 一v e r t e xg r 印h s i nt h el a s tc h a p t e r ，w ei n t r o d u c et h ed i r e c t i o 璐o fo u rr 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 mg oa h e a d k e y 、0 r d s ：g r 印h ，d r a w i n g ，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 ，j o i n ，h o m e o m o r - p h i s m i i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果除文中已经注明引用的内容外，本论文不含任何其它个人或集体已 经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体，均已在文 中以明确方式标明本人完全意识到本声明的法律结果由本人承担 学位论文作者签名：诰翻多 9 7 年r 月万日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅本人 授权湖南师范大学可以将本学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密囵i ( 请在以上相应方框内抒) 作者签名：和荔黟日期：口了年，月印 导师签每碴矽阢日期：j 年r 月万日 关于一些图类的交叉数的研究 1 引言 图论( 【1 】 3 】) 是一个内容非常丰富而且应用十分广泛的数学分支，起 源于著名的哥尼斯堡七桥问题在哥尼斯堡的普莱格尔河中有两个岛，七 座桥将河岸与岛以及岛与岛联接起来问题在于能否从四块陆地中任何 一块出发，在通过每座桥恰好一次后回到起点人们经过数次尝试后都没 有成功欧拉在1 7 3 6 年解决了这个问题，他将陆地看成点，桥看成边，构造 了一个图，再用与图有关的方法证明了这个问题没有解因此，欧拉成为 了图论的创始人如今图论已经发展出很多分支，并且和实际应用联系非 常紧密图的交叉数正是在近代图论中发展起来的一个重要概念，简单说 来，主要研究如何把图画在一个平面上，使其交叉的数目最少 自从上个世纪七十年代初匈牙利数学家p a lt u r 五n 根据其在一个砖厂 碰到的实际难题( m 磊n sb r i c kf a c t o 珂p r o b l e m ) ( 见文献 4 】) ，从而提出了交叉 数的概念以来，图的交叉数逐渐成为国际上一个非常活跃的分支，很多图 论专家对这方面进行了深入研究 事实上，研究图的交叉数不仅具有重要的理论意义，而且具有较强的 现实意义，在许多领域有着非常广泛的应用，例如： ( 1 ) 超大规模集成电路y 己s ，中的圈布局问题； ( 2 ) 草图的识别与重画问题，使之具有比手写汉字识别应用更为广泛 的应用领域； ( 3 ) 工业上电子线路板设计中的布线问题； ( 4 ) 生物工程d a 的图示； ( 5 ) 软件开发过程中文档部分的e r 图( 实体联系图) 等的自动生成； ( 6 ) 在几何学、堆垒数论与测度论等理论中的应用 硕士学位论文 然而，一般说来要确定图的交叉数是十分困难的，g a r e y 和j o h n s o n 在 文献 5 】证明了确定图的交叉数问题属于n p 完全问题由于其具备一定 难度，目前国际上对交叉数的研究进展十分缓慢，范围也受到了局限，能确 定交叉数的图类型较少也正因此，使得这项研究更具有挑战性随着对图 的交叉数问题研究的深入，我们发现值得研究的内容也日益丰富一方面 希望确定具体图类的交叉数，另一方面希望得到与图的交叉数有关的其 它性质，研制有关确定图的交叉数的算法等目前看来，主要集中在以下几 个方面： 1 一些特殊图类的交叉数 这些图主要包括结构特殊，规律性较强的图类一部分已经确定了交 叉数的精确值，还有一部分只给出了交叉数的上下界或猜想具体结果如 下： ( 1 ) 平面图 平面图的交叉数为o 从图论知识中我们已经知道一个图是平面图的充分必要条件是： k u r a t o w s l 【i 定理 6 ，7 】图g 是平面图当且仅当它没有同胚于图蚝或 3 的子图 ( 2 ) 完全图 完全图结构特殊，任意两个顶点之间都有且只有一条边相连关于完 全图的交叉数有一个重要的猜想，即g u y 猜想： c r ( ) = 心l 孚儿孚儿字j ， 这里用c r ( g ) 表示图g 的交叉数；对任意实数n ，用【几j 表示不大于凡 的最大整数 一2 关于一些图类的交叉数的研究 当我们将完全图k 的顶点映射到同构于单位球的圆柱体的顶部和底 部的圆盘面上时，在圆盘的顶部和底部相连的点形成两个同构于2 的 完全图，在顶部和底部的点间，考虑圆柱体上最短的螺旋状的路，就可以得 到g u y 猜想中的交叉数 目前，已经知道当完全图的顶点数分别为n = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 时，其交叉数分别为o ，o ，o ，o ，1 ，3 ，9 ，1 8 ，3 6 ，6 0 最新的结果证明了上述猜想对 于n 1 0 成立( 见文献 8 】- 1 0 】) ( 3 ) 完全2 一部图 实际上，n r a n 的“砖厂问题”等价于确定完全2 一部图m 的交叉 数1 9 5 4 年，z a r a n l ( i e 奶c z 在文献f l l 】中“证明 了 c r ( _ = 倒【- 孚旭儿孚j ( m 纠 ( 习惯上称之为励m 扎舰e 叫i c 名猜想) 为方便起见，将上述结果用z ( m ，n ) 表 示然而在1 9 6 9 年，m n g e l 1 2 】和k a i n e n 各自独立发现z a r a l l l 【i e 、) l r i c z 在文献 【1 1 】中的证明有错误，同时指出z a r a n l 【i e w i c z 猜想至少是某个精确值的上 界1 9 7 0 年d j k l e i t m a n 证明了等号对于m 讥( m ，n ) 6 成立 1 3 】，1 9 9 3 年 w b o d a l l 证明了仇= 7 且礼1 0 时z a r a n l ( i e w i c z 猜想成立 1 4 】 ( 4 ) 完全3 部图 上世纪八十年代，k a s a m o 证明了c r ( k 。，3 ，n ) = z ( 4 ，n ) + 吲， c r ( ，3 ，n ) = z ( 5 ，扎) + n ( 见文献 1 5 】) 最近黄元秋教授证明了盯( 硒，4 n ) = 礼( 礼一1 ) = z ( 5 ，礼) + 2 【詈j ( 见文献 1 6 】) ，后又与梅汉飞教授合作证明了c r ( 虬，5 ，n ) = z ( 6 ，礼) + 4 吲( 见文献( 17 】) ，2 0 0 5 年又与赵霆雷合作证明了，4 ，n 的交叉数( 见文献 【1 8 】) 这些结果都是建立在z a r a n k i e w i c z 猜想对于m z n ( 仇，n ) 6 成立的基 础上黄元秋和他的学生又在假设z a r a n k i e w i c z 猜想对于仇7 成立的前 提下，讨论了凹( k ，m ，n ) 的交叉数( 见文献 1 9 】， 2 0 】， 2 1 】i 【2 2 】) ( 5 ) 笛卡尔积图 3 一 硕士学位论文 对于长度分别为m ，几的圈的笛卡尔积图，f h a r a r y 等在1 9 7 3 年提出 了著名的猜想 2 3 ： c 7 ( c 之g ) = ( m 一2 ) n ，( 3 m 礼) n a d i n ec m y e r s 在文献 6 】中对这个猜想的起源，发展过程以及现状等都做 了较为详尽的介绍 r i n g e i s e n 和b e i n e k e 在1 9 7 8 年证明了盯( g g ) = 佗 2 4 】，在1 9 8 0 年证 明了凹( a g ) = 2 礼【2 5 】，1 9 9 6 年k l e 琵和d l t e r 证明盯( g g ) = 3 n 【2 6 】，2 0 0 1 年r i c h t e r 证明c r ( 侥繇) = 4 铊【2 7 】，2 0 0 4 年a d a 瑚s o n 和r i c h t e r 证明了c r ( 岛g ) = 5 钆 2 8 】另外，一些阶数确定的圈与圈的笛卡尔积图 的交叉数，如c r ( a a ) = 8 2 9 】，c r ( g g ) = 1 5 3 0 】，c r ( g g ) = 2 4 3 1 】，c r ( 岛岛) = 3 5 3 2 】等都已经得到证明，其他与圈的笛卡尔积有关的 结论参考【3 3 】_ 3 5 】 上世纪八十年代初，b e i n e k e 和硒n g e i s e n 及j e n d r o i 和弘e r b o v 矗等人确定 了所有4 阶图与圈的笛卡尔积图的交叉数【2 5 ，3 6 】 路是图论中最基本最简单的研究对象之一，很多文献都对路与其它图 的笛卡尔积图的交叉数进行了讨论捷克数学家k l e 酌等研究了一些路与 星的笛卡尔积图的交叉数【3 7 ，3 8 】，1 9 9 4 年确定了所有4 阶连通图与路的笛 卡尔积图的交叉数，之后他又陆续给出了所有5 阶连通图与路的笛卡尔积 图的交叉数【3 9 卜 4 5 】在黄元秋教授的带领下，他的学生们也先后做出了很 多新的结果，参见 4 6 】- 【5 5 】 ( 6 ) 联图 目前就联图的交叉数的讨论还很不充分，仅有b o g d a no p o r o w s k 等在 【5 6 】中证明了c r ( 岛v 瓯) = 6 ，和黄元秋及他的学生得出了圈和路之间的联 图的交叉数( 5 7 】) 2 有某种特点的图的交叉数的一些性质 关于一些图类的交叉数的研究 因为具体确定某个图的交叉数比较难，所以换个角度从交叉数的性质 如临界交叉数，正则图的交叉数，交叉数的奇偶性等着手研究 5 8 】- 【6 0 】，希 望能得出一些有关图的交叉数方面比较好的结果。 3 线图的交叉数 图g 的线图l ( g ) 是指顶点集为e ( g ) 的图，其中两个顶点相连的充要 条件是它们在g 中为相邻的边一般来说，图g 和它的线图l ( g ) 的交叉 数满足：盯( g ) 盯( l ( g ) ) 上世纪六十年代初，s e d l 茂芒e k 【6 4 】得到一个平面图g 的线图( g ) 是平 面图的充分必要条件。1 9 7 9 年，k u l l i ，a k l 【a | 和b e i n e k e 【6 1 】获得了一个平面图 的线图的交叉数为1 的充分必要条件1 9 9 7 年，a k k a ，j e n d r o i ，k 1 e 琵等研究 了平面图的线图的交叉数为2 的情形 6 5 】 1 9 9 9 年j e n d r o i 和k l e 酌已经证明了图g 和线图的交叉数都是1 的充分 必要条件【6 2 】2 0 0 1 年，j e n d r o i 和k 1 e 酌【6 2 】研究了非平面图的线图的交叉 数情形，确定了非平面图的线图的交叉数为1 的充分必要条件2 0 0 5 年黄 元秋和赵霆雷给出了图及其线图的交叉数都是忌的充分必要条件 6 3 】 正是在这些文献的启发下，同时在已有结果的基础上应用并创新相关 方法，我们推广了笛卡尔积图的交叉数和联图的交叉数 一5 一 关于一些图类的交叉数的研究 2 相关概念的解析 本文涉及到的基本概念和性质，未作特别说明均同文献【1 】，且无特别 说明时文中所涉及的图均指简单连通图 图g 是指一个有序三元组( y ( g ) ，e ( g ) ，矽g ) ，其中y ( g ) 是非空的顶点 集，e ( g ) 是不与v ( g ) 相交的边集，而妒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 1 图g 的好画法中不允许出现的四种情况 前三个条件( 1 ) ，( 2 ) ，( 3 ) 是最优画法中必然满足的因为如果不满足，我 们可以对画法进行改进，从而得到一个具有更小交叉数的画法，这与最优 画法的定义矛盾( 见图2 2 ) 叉) 与 口1 ，忱，蚀，) 的完全二部图甄，仃 中，若把顶点集 耽，蚴，) 中联入8 条边使得这六个点的导出子图 同构于g 。，联入1 0 条边使得这六个点的导出子图同构于g 2 ，由此得到两 个新图记为玩，巩在图玩，玩中，用矸( 江1 ，2 ，n ) ，砰0 = 1 ，2 ，扎) 分 别表示与顶点t i ，磅关联的边集，用日，易表示g 。，g 2 的边集，于是易得 n e ( a n ) = 易u ( 【j 巧) ，= 1 ，2 ) ，( a = b ，日) 图3 2 玩和巩 硕士学位论文 用g f 表示把图f 的6 个顶点与2 一边连通图g 的其中6 个顶点分别 相连所得到的图用g 表示收缩g f 中的所有边到一点，后所得到的图 本章的主要结果是如下定理： 定理3 1 ：设g ，g 2 为上述所示的图，& 是甄则有 ( 1 ) c 7 ( 玩) = z ( 6 ，礼) + n ，礼1 ； ( 2 ) c ，( 巩) = z ( 6 ，礼) + 2 n ，礼1 ； ( 3 ) c r ( g 1 ) = z ( 6 ，n ) + 2 扎； ( 4 ) c 7 ( g 2 & ) = z ( 6 ，礼) + 4 n 3 1g 1 & 的交叉数 引理3 1 1 盯( b 1 ) = 1 ，c r ( b 2 ) = 2 证明由图3 1 1 知，存在一种好画法。使得c r ( b ) 1 ，c r ( b 2 ) 2 成立 b 的一个最优画法图3 1 1 b 2 的一个最优画法 而b 。包含一个子图同胚于蚝，所以c r ( b ，) 1 下面证明盯( 岛) 2 设c r ( b 2 ) = o ，那么从b 2 中删掉某口条边后将得到一个平面图，根据 欧拉公式可得： 8 一( 2 0 n ) + 厂= 2 ，= 1 4 一o 4 0 2 n = 2 e 3 厂= 4 2 3 n 19 关于一些图类的交叉数的研究 所以c r ( 岛) 2 引理得证 o 2 引理3 1 2 令为b 2 的一个好画法若c r 咖( 矸，砑) = o ，则有哪( 局，矸u 砑1 2 证明令b = ( 砰，u 死) 为b 2 的边导出子图b 同构于由点划分为 t ；，亡! ) 和 口1 ，可2 ，地，地， 的完全二部图鲍，6 因为c r 毋( 硭，砑) = o ，所以b 的由 导出的子画法必同构于图3 1 2 设 0 1 ，口2 ，口3 ，凸4 ，0 5 ，0 6 ) = 口1 ，忱，蚴，) 则两对3 度点n 1 ，0 5 及0 2 ，口4议 0 1 ，口2 ，口3 ，凸4 ，0 5 ，0 6 _ = 口1 ，忱，蚴，j 贝u 网反点n 1 ，0 5 及0 2 ，口4 关联的边口t 口5 ，0 2 口4 分别与( 砰u 露) 产生至少一个交叉所以凹咖( 毋，矸u 砑) 2 引理得证 口 鲍，6 的西翕零优画法图3 1 3 引理3 1 3 盯( g 苔，) 盯( g g 。) 一1 证明令咖为g g 。的一个好画法若把图g 。的6 个顶点与某一点1 都相 连，则将得到一个同构于b 。的图，由引理3 ，1 1 知盯( b ，) = 1 ，于是在下 图g ，的边上至少有一个交叉又知图g 。包含一个子图同构于图3 1 3 中 的图f 7 ，且g 1 e ) 兰又因为c r ( g + f ，) c r ( g f ，) 一1 ( 4 7 】) ，因此，假设e 边 上产生的交叉数为不论z ，为何值，g ，均可按照f 7 的收缩方式收缩，即 一】3 一 硕士学位论文 在g 。的任意画法咖和f 7 的子画法下有凹币( 9 g ，) = 盯咖，( 口f ，) 所以有 c r ( g g l ) = c r ( g f ，) + z 1 c r ( g f ，) + 1 + z 1 c 7 - ( g + f ) 十1 所以c r ( g 各，) c r ( g g ，) 一1 定理3 1 ( 1 ) 仃( 鼠) = z ( 6 ，扎) + n ，n 1 证明下面先构造反一个好画法口：在平面直角坐标系上，把风的顶点集 u 1 ，耽，忱，地，) 放在可轴上，其中口1 ，耽，地放在秒轴的正半轴上， 放在可轴的负半轴上把顶点集 ，t 5 ，：) 放在z 轴上，其中詈1 个放 在负半轴上，【詈j 个放在正半轴上然后把各边用适当的直线或曲线表示出 来，见图3 2 显然在图3 2 中，鼠毋同构于玩且在9 下的子画法也正好就是风，n 的一个最优画法所以： c r 口( 风e 1 ) = c r ( 甄，n ) = z ( 6 ，礼) 而凹日( 岛，砑) = 1 ，且咖( 局) = o ，所以 盯口( 岛) = c r 一( 鼠毋) + 盯日( 毋，u 砑) + 盯口( 局) i = 1 = z ( 6 ，n ) + 盯口( 日，砑) + c r 一( 日) t = 1 = z ( 6 ，仡) + 佗 根据交叉数的定义知盯( 鼠) c r 一( 既) = z ( 6 ，n ) + n ，n 1 下面我们用归纳 法来证明结论成立 由引理3 1 1 知c 7 _ ( b 1 ) = z ( 1 ，6 ) + 1 = 1 ，c r ( b 2 ) = z ( 2 ，6 ) + 2 = 2 即当 n = 1 ，2 时定理结论成立现假设n 3 且2 礼时有c 7 ( 岛) z ( 6 ，2 ) + 2 只 需证对图鼠的任意一个好画法，有凹毋( 鼠) z ( 6 ，礼) + 礼用反证法证明： 若存在玩的一个好画法使得：凹咖( 鼠) z ( 6 ，扎) + n 1 4 关于一些图类的交叉数的研究 下面分两种情况分别讨论。 情况1 若存在两个砰，碍( 1 t ，歹n ，i 歹) ，使得c ( 砑，碍) = o 不失一般性，不妨假设有霹，霹一。使得c ( 霹，露一，) = o ，他2 又因为 ( 露u 露一。u 碍) 同构于完全二部图，6 而 c r 咖( 砭u 砭_ 1 砰) = 盯妒( 尥，6 ) 一仃咖( 露u 露一1 ) 一c r 毋( 碍) 6 一o o = 6 所以 n 一2 盯咖( 鼠) = 盯毋( 易u 砭u 露一1uu 砑) t = 1 n 一2 n 一2 = 甜西( 露u 露巾u 砑) + 盯妒( u 露巾且) + c ( 局uu 霉) 讧= 1i = 1 死一2 佗一2 = 凹咖( 露u 砭巾砑) + 凹西( 露u 露巾日) + 哪( 局uu 碍) 6 ( 愿一2 ) + 2 + z ( 6 ，弦一2 ) + ( 弛一2 ) z ( 6 ，n ) + 佗 情况2 若对任意两个碍，写( 1 i ，歹礼，i 歹) ，都有c ( 砑，霉) 1 因为 c r ( 鼠) =c r 咖( 局u 砰u 砑u u 砭) = c ( 甄，n ) + e ( 置) + 哪( 置，矸u 霹u u 露) z ( 6 ，n ) + o + 盯毋( 日，矸u 霹u u 砭) 由反设，有c ( 目，矸u 霹u u 露) n 这说明在玩的好画法咖中，至少 存在某个霹，不妨设为砰，使得盯咖( 局，矸) = o 因为顶点 与g 。的每一 个顶点都关联，易知，( 毋u 矸) 的画法必如下： 存在平面上的一个圆盘c 使得g ，的各顶点都位于c 的边界上，g 。 的各边都位于c 的内部以及顶点；和边集矸都位于c 的外部再根据 g 1 的对称结构，知( e 1 u 矸) 的画法必同构于以下1 9 种画法( 见图3 1 4 ) 1 5 硕士学位论文 96 6 6 够6 6 6 6 6 ( 8 ) 6 6 6 6 ( 1 0 )( 1 1 )( 1 2 ) 6 6 6 ( 1 3 )( 1 4 ) ( 1 5 )( 1 6 ) 6 6 6 ( 1 7 )( 1 8 ) ( 1 9 ) ( 毋u 乃) 的所有好画法 图3 1 4 6 而从图3 1 4 知，a 所指区域最多有g ，中的4 个顶点在其边界上，而空 白区域最多只有g ，中3 个点在其边界上，b 所指的区域最多只有g ，中的 两个顶点在其边界上若将i 画入图中各区域，有 ( 1 ) z i 位于区域6 时，盯妒( 置u 矸，砰) 5 ；且仅当盯西( 且，露) 1 时，有 盯咖( 日u 矸，霹) = 5 ； ( 2 ) ；位于区域n 时，盯妒( 局u 矸，霹) 2 ；且仅当凹西( 矸，砑) = o 时，有 一1 6 关于一些图类的交叉数的研究 仃西( 毋u 矸，砑) = 2 ，又因为盯妒( 霹，霉) 1 ，所以c r 咖( 局u ，碍) 3 ； ( 3 ) i 位于空白区域时，c ( 且u 矸，砑) c r 西( 日u 矸，砑) = 3 ， z2 又因为 3 ；且仅当凹( 砰，碍) = 盯西( 霉，碍) 1 ，所以盯毋( 毋u 矸，砰) 4 位于图3 1 4 中b 所指区域的顶点个数 y = 位于图3 1 4 中a 所指区域和空白区域的顶点个数 易知，可= 礼一1 一z ，对于图3 1 4 ( 1 ) 法，有凹毋( 且) = 1 c ( 鼠) = o 时， 是图3 1 4 中唯一一个含有a 区域的画 仃咖( 蜀u 矸u 露u 霹u u 砭) = 仃毋( 且u 砰) + 盯毋( 砑u 露u u 露) + 盯咖( 毋u 矸，磅u 露u u 露) 21 + z ( 6 ，礼一1 ) + 3 ( n 一1 一z ) + 5 z 又由反设有 即 所以 与假设矛盾 1 + 3 ( n 一1 一z ) + 5 z + z ( 6 ，几一1 ) z ( 6 ，n ) + 他 c r 毋( 鼠) = z 1 1 9 硕士学位论文 令e 是h l 中的任一条边，得到的子图阢 e ) 中总有与风同胚的子 图，因此c r ( 玩) 2 同上不妨设盯( 巩) = 6 ，若删掉凰中的6 条边也得到一个平面图由 e u l e r 定理 8 一( 2 2 6 ) + ，= 2 ，= 1 6 6 4 4 2 6 = 2 e 3 ，= 4 8 3 6 6 4 引理得证 f 】 引理3 2 2c r ( g + g ：) c r ( g g 。) 一2 证明令d 是图g g ：的一个好画法若把图g ：的6 个顶点于某一点。都 相连则将得到一个同构于研的图由盯( 研) = 2 ，则在画法d 中至少有 2 个交叉令盯( 皿) = 2 中1 0 条边岛( 江1 ，2 ，1 0 ) 上产生的交叉分别为 戤( i = 1 ，2 ，1 0 ) ，则至少存在一条边e i 使得以1 令g 2 k ) = n ，由 于ru 砰包含一个子图与蚝同胚，因此在g f l 中至少还有一个交叉下 面证明c r ( g f 1 ) 凹( g f l ) 一1 由f 的对称性易知r 有两种可能情况( 见 图3 2 2 ) 显然f 1 1 和f 2 l 均包含一个子图同胚于p ( 见图3 1 3 ) 竺f 1 1 e 7 ，e 9 ) 兰f 2 l e l o ，e 5 ) 怂恐 e 4e 4 f 1 1f 2 1 图3 2 2 只的2 种可能情况 2 0 关于一些图类的交叉数的研究 又因为盯( g ，) 玎( g f ，) 一1 ( ( 4 7 ) 。因此我们可以按照f 的边收缩方 式来收缩f 1 。和f 2 。的边，则在任意好画法d 下都有c r d ( g ；。) = c r d ( g 釜，) ， 所以 盯d ( g f l l )= c ? - d ( g f ，) + z 7 + z 9 c r d ( g ；，) + 1 + z 7 + z 9 盯d ( g ； - 。) + 1 同理可证c r ( g ；。) c r ( g f ：。) 一1 ，再结合甄1 与歹= 1 ，2 ，有 凹d ( g g 2 )= 盯d ( g 剐1 ) + 墨 凹d ( g 知。) + 1 + 兢 盯d ( g + g 。) + 2 引理证毕 定理3 1 ( 2 ) c r ( 凰) = z ( 6 ，几) + 2 n ，( 礼1 ) 证明同定理3 1 ( 1 ) ，在图3 2 中的好画法咖下，有c r 毋( ) = z ( 6 ，竹) + 2 n ， 由此c r ( ) z ( 6 ，n ) + 2 n 下面对佗用归纳法来证明凹( 巩) z ( 6 ，n ) + 2 佗 由引理知几= 1 和礼= 2 时定理成立不妨设当几3 时且z 礼时有 c r ( 凰) z ( 6 ，j ) + 22 现反设存在巩的某一好画法d 使得 盯d ( 只_ ) z ( 6 ，礼) + 2 几 矛盾 子情况3 若对每个碍均有仃d ( 易，砰) 2 此时，有 n c r d ( ) = 盯d ( 岛uu 砰) t = 1 nn = 盯d ( 易) + c r d ( u 砰) + 盯d ( 易，u 砰) i = 1 = 1 z ( 6 ，佗) + 2 佗 一2 6 关于一些图类的交叉数的研究 同样与假设盾 综合情况1 ，2 有c r d ( 巩) z ( 6 ，n ) + 2 n 即有盯( 巩) = z ( 6 ，n ) + 2 n ，( 礼1 ) 定理证毕 口 定理3 1 ( 4 ) c r ( g 2 & ) = z ( 6 ，n ) + 4 礼 证明当礼1 时g 2 岛有6 ( 佗+ 1 ) 个点，n + 1 个q ， = o ，1 ，2 ，n ) 拷贝 和6 个& 拷贝( 见图3 2 7 ) 同定理3 1 ( 3 ) ，图3 2 7 的画法说明c r ( g 2 & ) z ( 6 ，礼) + 4 佗假设存在一个g 2 & 的最优画法d 的交叉少于z ( 6 ，n ) + 4 几分 别收缩每个哦( i = 1 ，2 ，n ) 拷贝至一个点得到一个图与巩同构由引 理3 2 2 得凹d ( 风) z ( 6 ，几) + 2 佗，与定理矛盾因此，盯( f & ) = z ( 6 ，n ) + 4 礼 口 图3 2 7c r ( g 2 叉) 的一个好画法 2 7 关于一些图类的交叉数的研究 4 与r 的联图有关的图的交叉数 目前关于两个图的联图的交叉数的讨论还不充分，我将在本章详细讨 论两个六阶图g ( 如图3 1 ) g 3 ( 如图4 1 ) 与有几个顶点的路r 的联图的交 叉数，得到以下定理： 定理4 1 ：设g 。g 3 为上述所示的图，p n 是有礼个顶点的路，则有 ( 1 ) 凹( g 3vr ) = z ( 6 ，n ) + n + 1 ，礼l ； ( 2 ) c 7 ( g 1vr ) = z ( 6 ，礼) + n + 1 ，佗1 图4 1g 3 图4 2g 3vr 的一个好画法 4 1g 3vr 的交叉数 令g 3 的六个顶点y ( g 3 ) = 箩1 ，沈，珧，弘，蜘，蜘) ，y ( r ) = z 1 ，z 2 ，z n ) 令边集驴= _ 毛协i j = 1 ，2 ，6 ) ，驴= u ：1 ，螈= 矿ue ( g 3 ) ，e ( r ) = 戤z 件1 k = 1 ，2 ，礼一1 ) 由此g 3vr = ue ( r ) ( 如图4 2 ) 弓l 理4 1 1 凹( ) = z ( 6 ，礼) + 礼( 【4 7 】)口 引理4 1 2 凹( g 3vp 1 ) = 1 ，c r ( g 3v 忍) = 3 证明由图4 2 知c r ( g 3vr ) 1 ，c r ( g 3vr ) 3 ( 1 ) 易知g 3vp 1 包含一个 子图与完全二部图蚝，3 同胚，因此c r ( g 3vp 1 ) 1 ( 2 ) 设盯( g 3v 岛) 2 ，则 一2 9 硕士学位论文 若删去g 3v 岛中的某两条边将的到一个平面图但由g 3v 最中的8 个顶 点的度数均大于等于4 ，因此删去g 3v 最中的任意两条边所得到的子图 均至少有5 个度数大于等于4 的顶点，即子图中均包含一个更小的子图同 胚于风由此c r ( g 3v 恳) 3 口 定理4 1 ( 1 )盯( g 3vr ) = z ( 6 ，礼) + 亿+ 1 ，n 1 证明用归纳法证明： ( 1 ) 当n = 1 ，2 时，由引理4 1 2 ，定理结论成立 ( 2 ) 设定理结论