（基础数学专业论文）关于一些图类的交叉数.pdf

关于一些图类的交叉数 摘要 我们已经知道确定图的交叉数是一个n p 完全问题( 见文献【1 】) ，因 此，到现在为止有关交叉数的结果比较少，在许多情况下，甚至找出图 的一个好的上界或下界也很艰难本文研究路与某些6 阶图的笛卡儿积 交叉数，及在假定z 盯强k i e 丽c z 猜想成立的基础上研究完全3 部图虬 1 0 。n 及完全3 部图硷m 。当m ，n 均为偶数时的交叉数 在第一章：交代了本文的写作背景，交叉数研究在国内外发展的动 态，研究工作的意义以及本文中要解决的问题和创新之处 在第二章：给出一些基本概念和性质，介绍了阅读本文所需要的预备 知识其中主要包括交叉数的概念，并介绍了在后面文章中会出现的一些 相关概念、性质以及常用到的一些定理，而部分使用较少的概念等我们 放到了具体的章节中去交代 在第三章：我们确定了5 个六阶图与路r 的笛卡儿积图的交叉数 在第四章：在假定z a r a n k i e 耐c z 猜想对m = 1 1 成立的基础上，我们得 到了完全3 部图k l 1 0 ，n 的交叉数，并且将结果推广到假定z a r a n k i e w i c z s 猜想对甄+ m ，。( m 为不大于n 的偶数) 成立时得到完全3 部图施，m ，n 当n 也为偶数时的交叉数 在第五章：提出了研究工作在发展中的一些问题以及作者在以后将 致力于前进的方向 关键词：图； 画法； 交叉数；路；笛卡儿积；同胚；平面图 一 关于一些图类的交叉数 a b s t r a c t w | eh a ea l r e a d yl 【n o w nt h a td e t e r m i n gt h ec r i d 豁i n g 肌n l b e r so fg r a p h si sn p - c o l p l e t e ( s e e 【1 】) t h e r ea r eaf 撕e ) 【a c tr 圈u l t 8o nt h ec r o s s i n gn u i n b e r g o fg r 印h sf o r i t 8c o m p l e 五t y e v e ni nm 锄yc 嬲e s ，i ti sv e 珂d i m c u l tt o 丘n du p p e ro rl o 骶rb o u n d s o ft h ec r 0 鹃i n gm 加小e r so fg r 印h s i nt h i sp a p e r ，w es t u d yt h ec r 0 蹈i i l gi m m b e 瑙o f t h ec 盯t 箦i a np r o d u c t so fp a t l l s 丽t hs o m e6 - v e r t e 】【伊a p h s ，a n di ft h ez a r a n l 【i e 丽c z s c o n j e c t u r ei sh o l d ，w eg e tt h ec r o s s i n gi l u i i l _ b e 墙0 ft h ec 0 l p l e t et r i p a r t i t eg r 印h 甄1 0 n ，a n do b t a i nt h ec r o 鹃i n gm l i i i b e ro fj q 。m ，nw h e nm ，na b o t he v e ni n t e g e r s i nd 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 8o ft h ec r o s s i n gn u m b e ra n di t s d e v e l o p m e i l t 踟0 u n dt h ew o r l d ，t h em e a n i n g so ft h er 瞄e a u r d h 舭i dt h ep r o b l e h 塔w e w i l8 0 l v e i nc h a p t e r 怕，w eg i v e8 0 m ec o n i 弛p t i o n sa n dp r o p e r t i 馏，a n di n t r o d u c et h e r e ( 1 u i r e dk n o w l e d g e si n c l u d i n gc r o s s i n gn u h l b e r 8w h e nr e a dt h i sp 却e r i nc h 印t e rt h r e e ，w ed e t e r i n i n et h ec r o 豁i n gn u i i l _ b e r so ft h ec a n e 8 i 蚰p r o d u c t s o f p a t h sp n 诵t hs o m e 昏v e r t 既g r 印l l s i nc l l 印t e rf o u r ，、7 l 陀g e tt h ec r o 鹃i n gn u 】l b e ro ft h ec o m p l e t et r i p a r t i t eg r 印h 虬，l o ，ni ft h ez a r a n h e w i c z sc o n j e c t u r ei sh o l df o rm = 1 1 ，a n dw eo b t a i nt h ec r o 鼹i n g 肌瑚i b e ro fj n 。m ，nw h e nni se v e ni n t e g e r s ，i ft h ez a r a n l 【i e 诵c z sc o 两e c t u r ei st r u e f o rk j + m ，nw h e nr y li se 、，e ni n t e g e r sn om o r et h 锄礼 i nc h 印t e rf i v e ，t h e r ea r es o m eq u e s t i o n sw h e nr e s e a r c h i n gi n t ot h i sp r o b l e m ， a n dt h ed i r e c t i o ni 丽u9 0a h e a d k q r w o r d s ：g r a p h ；d r 鲫订n g ；c r o 鼹i n gn u 】【b e r ；p a t h ；c a n 签i a np r o d u c t ； h o m e o m o r p h i s m ；p l a n a rg r a p h i i i 关于一些图类的交叉数 第一章引言 图的交叉数是近代图论中发展起来的一个重要概念，自从上个世纪 七十年代初匈牙利数学家p 甜| i 、l r 缸根据其在一个砖厂碰到的实际难题 ( m 缸8b r i d 【f 诎。盯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 ( c m g ) ( m 一2 ) n ，( m n ) ，瞰n g e i s e n ，b e i 聃k e ，m k l 磷 和瞰c h t e r ，j a ya d 删等证明等号对m = 3 ，4 ，5 ，6 ，7 成立( 见文献【3 】- 1 0 】) 硕士学位论文 从二十世纪后期起，捷克数学家m k l 盛等人开始对阶数较小的图与 路，星，圈的笛卡儿积图的交叉数的研究( 见文献【1 1 】f 1 8 】) 路是图论中 最基本最简单的图之一，很多文章是路与其它图的笛卡儿积图的交叉数 开始考虑，阶数为3 的连通图或同构于2 路或同构于3 圈，结论显然为 o ，因此系统的研究从阶数是4 的图开始m k l 西芒1 9 9 4 年确定了所有4 阶 连通图与路的积图交叉数，( 见文献【1 3 】) 之后，他又陆续给出了所有5 阶连通图与路的笛卡儿积图的交叉数( 见文献 1 4 】一【1 8 】) ( 2 ) 完全图： 关于完全图的交叉数有一个猜想，即。c r ( 虬) = 扎儿孚儿孚儿孚j ， 目前仅证明了等号对于n 1 0 成立这里，c r ( g ) 表示图g 的交叉数； 对任意实数n ，h 表示不超过n 的最大整数 ( 3 ) 完全二部图： 实际上，n r a n 的誓砖厂问题斗等价于确定完全2 部图。的交叉数 后来，z 舭a n k i 喇c z 在文献【2 】中“证明”了c r ( ，n ) = 【引【警儿量儿孚j ，( m 竹) 不久，n g e l 和k 越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 丽c z 猜想，把上式右端记 为z ( m ，n ) d j k l e i t n 舢在1 9 7 0 年证明了等号对于侧n ( m ，n ) 6 成立( 见 文献【2 0 】) w o o d a u 于1 9 9 3 年证明了对m = 7 且n 1 0 成立( 见文献【2 1 】) ， 直到目前为止还没有关于此方面的新结果 ( 4 ) 完全三部图： 上世纪八十年代，k a 跏n o 证明了c r ( 甄，3 。) = z ( 4 ，i ) + 吲， c r ( 娲，3 t n ) = z ( 5 ，n ) + n ( 见文献【2 2 】) 最近黄元秋教授证明了c r ( 坼，4 ，n ) = n ( n 一1 ) = 2 关于一些图类的交叉数 z ( 5 ，n ) + 2 吲( 见文献【2 3 】) ，后又与梅汉飞教授合作证明了c r ( m 5 t n ) = z ( 6 ，n ) + 4 吲( 见文献【2 4 】) ，2 0 0 5 年又与赵霆雷合作证明了恐，4 ，。的交叉数( 见文献 【2 5 】) 这些结果都是建立在z a u r 锄k i e 诵c z 猜想对于而扎( m ，礼) 6 成立的基 础上黄元秋，赵霆雷又在假设z a r 眦k i e 耐c z 猜想对于m = 7 成立的前 提下，确定了c r ( 虬t 6 ，n ) = z ( 7 ，n ) + 6 削( 见文献【2 6 】) ，其后不久又在假设 z 盯缸k i e 丽c z 猜想对于m = 8 ，m = 9 成立的前提下，确定了托7 n ，甄，8 n 的 交叉数 ( 见文献【2 7 】，【2 8 】) 2 有某种特点的图的交叉数的一些性质 因为具体确定某个图的交叉数比较难，所以换个角度从交叉数的性 质如临界交叉数，正则图的交叉数，交叉数的奇偶性等着手研究，【2 9 】- 【3 5 】 希望能得出一些有关图的交叉数方面比较好的结果 3 线图的交叉数 l ( g ) 表示图g 的线图，已经证明了c r ( l ( g ) ) = 1 的充分必要条件，( 见 文献【3 6 】) 黄元秋教授给出了c r ( l ( g ) ) = 2 的充分必要条件( 见文献【3 7 】) 受到这些文献的启发，在它们的基础上，应用并创新某些方法推广了 关于笛卡儿积图和完全3 部图交叉数方面的结果所给出的定理是关于 路与5 个6 _ 阶图的笛卡儿积图的交叉数及完全3 部图的交叉数 一3 关于一些图类的交叉数 第二章基本概念和性质 本章给出涉及到的基本概念和性质，未说明的概念均同文献【3 8 】，【3 9 】； 且无特别说明所涉及图均指连通简单图 一个图g 是指一个有序三元组( y ( g ) ，e ( g ) ，惦) ，其中y ( g ) 是非空的 顶点集，j 5 7 ( g ) 是不与( y ( g ) 相交的边集，而惦是关联函数，它使g 的 每条边对应于g 的无序顶点对 定义1 图g 在画法d 下的交叉数是指在画法d 下边与边产生的交 叉点的个数，用c r d ( g ) 表示 定义2 图g 的交叉数，用c r ( g ) 表示，是指图g 在平面上的所有画 法下交叉数的最小值，即z 知c r d ( g ) u 定义3 图g 在平面上的一个最优画法是指恰好达到交叉数的画法 定义4 图g 在平面上的一个好画法是指图g 在平面上的画法满足 以下四个条件： 1 ) 连接同一个结点的任意两条边不相交； 2 ) 边不能自身相交； 3 ) 任何两条相交的边最多交叉一次； 4 ) 没有三条边交叉于同一个点 注：定义4 中第四种画法是为了研究而统一规定不允许的前三种 画法1 ) ，2 ) ，3 ) 在最优画法中是不会出现的，因为如果出现这些情况，我们 可以对画法改进，从而可以得到一个具有更小交叉数的画法( 见图2 1 ，图 参2 ) 。5 一 硕士学位论文 叉爻 图2 1 ：图g 的好画法中不允许出现的四种情况 ) ( 图2 2 ：对图2 1 中前三种画法的改进 ，注：定义1 定义4 中的“平面 可改为“曲面? ，且相关定义可推广 到曲面的情况目前国内外大多是对在平面上的交叉数的研究，但也有 讨论环面等曲面上的交叉数( 见文献【4 0 】) 在这里我们仅讨论平面上的情 形 两个图g 。和g 2 的笛卡儿积图用g 。g 2 表示，它是这样的图： 点y ( g 1 g 2 ) = y ( g 1 ) y ( g 2 ) ；边集e ( g l g 2 ) = ( 似，) ，) ) ：t i i = 且 吻，) e ( g 2 ) ，或者 t ，) e ( g 1 ) 且吩= ) 设d 为图g 的好画法，若g 。，g 。和g 3 为g 的边不相交子图，显然 有：c r ( g ) c r ( g ) ，( i = 1 ，2 ，3 ) ， c r d ( g lug 2 ) = 咖( g 1 ) + ( g 2 ) + ( g 1 ，g 2 ) ， c r d ( g 1 ug 2 ，g 3 ) = c r d ( g 1 ，g 3 ) + c r d ( g 2 ，g 3 ) 若对于图f 某些边加入或抹平2 度点( 均可反复多次) ，得到的图与图 日同构，则称f 和日同胚，记为f h 易知有：c r ( f ) = c r ( 日) 一6 一 关于一些图类的交叉数 第三章六阶图q ( 歹= 1 ，2 ，3 ，4 ，5 ) 与路r 的笛卡儿积 交叉数 从2 0 世纪后期起，m k l 耐等人对阶数较小的图与路，星，圈的笛卡儿 积图的交叉数进行研究，见文献( 【1 2 】- 【1 7 】) ，肖文兵等人给出了开始研究6 阶图与路，星的笛卡儿积图的交叉数，( 见文献【4 1 】，【4 2 】) 作者在这些结果 的基础上研究6 - 阶图与路的笛卡儿积图的交叉数 我们假定本章qo = 1 ，2 ，3 ，4 ，5 ) 分别是如下具有6 个点的图： 25 2 g 1 g 2g 3 2 g 4g 5 5 5 图孓1 ：5 个六阶图qo = 1 ，2 ，3 ，4 ，5 ) 本章的主要结果是如下定理： 定理：设g jo = 1 ，2 ，3 ，4 ，5 ) 为上述所示的图，r 是长为n 的路，则有 ( 1 ) c r ( q r ) = 3 n 一1 ， 歹= 1 ，2 ； ( 2 ) c r ( q r ) = 2 n 一2 ，歹= 3 ； ( 3 ) 仃( q r ) = 4 n ， j = 4 ； ( 4 ) c r ( g j r ) = 4 n ，歹= 5 7 硕士学位论文 假设n 1 ，我们以如下的方式考虑g j r ：它有6 ( n + 1 ) 个顶点，边为 ( n + 1 ) 个g ；的拷贝( 用g 表示，i = o ，1 ，2 n ，) 和6 条长为，i 的路r 为了下面证明的方便，我们让每个拷贝佛中的边着红色，每条长为n 的 只中的边着蓝色江1 ，2 n ，我们用霉表示q r 中由六条连接g 1 和q 的蓝边导出的子图，用锈表示q r 中由y ( g 1 ) u y ( g ；) u y ( 尊1 ) 导出的子图，我们定义砺的力量，( 饼) 为下列类型交叉数的总和z ( 1 ) 由霹u 巧“中的蓝边和q 中的边产生的交叉； ( 2 ) 由巧中的蓝边和巧+ 1 的蓝边产生的交叉；和 ( 3 ) 由辞自身的边之间产生的交叉 画法的总力量是所有，( 讲) 的和很容易看到每一个交叉至多在画 法的总力量中计算一次 我们说一个q r 的好画法是凝聚的，如果对每一个q ，江o ，1 ，2 _ n ， ( 不管它是否有内部交叉) 来说，其余所有的点都落在g ；的子画法的同一 个区域中 设日是g 的一个子图，d 是g 的一个好画法，我们称一个交叉为图 日的自身交叉是指：在画法d 中，产生交叉的两条边都属于鼠 c 为图g 的一个圈，如果g y ( c ) 连通，则称c 是图g 的不可分离 圈；如果g 的点导出子图g ( c ) 】是c 本身，则称c 为图g 的诱导圈 圈c 如果既是不可分离圈也是诱导圈，则称为是不可分离诱导圈我们 很容易有： 引理3 1 若c 是图g 的不可分离诱导圈，则在g 的平面嵌入中，c 一 定是某个面的边界 3 1g 1 p n 的交叉数 定理3 1 c r ( g l r ) = 3 n 一1 ， n 1 8 一 关于一些图类的交叉数 证明：g - p n 的一个好画法( 见图3 _ 2 ) 说明c r ( g 1 r ) 3 n 一1 另一方 面，g t 同胚于文献 1 8 】中的图g 。9 ，g 。r 包含一个同胚予g 。r 的 子图，因为c r ( g 1 9 r ) = 3 n l ，所以c r ( g 1 r ) c r ( g 1 9 r ) = 3 t l 1 这就完成了我们的证明 口 须 f 。 ili 7f i g 。r 的一个好画法 图3 - 2 3 2g 2 r 的交叉数 _ i ?f7 | | j g 。r 的一个好画法 图3 - 3 考虑一个由连接g 2 的所有顶点和一个连通图g 所得到的图因为它 包含一个同胚与蚝的子图，所以在这个图的任意好画法下，g 。中的边 上至少会产生1 个交叉 引理3 2 如果d 是g 2 r 的一个好画法，且在d 下每一个岛上最多 有2 个交叉，则c r d ( g 2 r ) 5 n 一3 证明：我们首先证明画法d 是凝聚的如果两个不同的哦和磷之间有交 叉，由于倪是2 - 连通的，则它们至少会交叉2 次根据假设有c 物( g ；，磷) = 2 ，且c r d ( g ；) = o 由e u l e r 公式，u e + ，= 2 ，所以，= 4 又g ；有4 个不 可分离诱导圈： 1 2 - 3 ；参3 一垂5 ；1 2 - 5 - 6 ；1 3 垂5 _ 6 ，由引理3 1 ，这4 个不可分 离诱导圈恰好是g ；的平面嵌入下的4 个面的边界由c r d ( q ，磷) = 2 知 9 硕士学位论文 g ；( 哦) 最多在磷( 磷) 的限制画法下的两个区域内，且最多有q 的5 个 顶点在这些面的边界上，鹂还会和蓝边产生一个交叉，与假设矛盾因 此，对于i 七，c r d ( 晚，g ；) = o 现在假设在画法d 下，子图磷和g ：位 于鹂子画法下的不同区域中不管鹂是否有内部交叉，岛的子画法 把平面分为数个区域，使得任何两个相邻区域的共同边界上至多只有g ； 的3 个顶点所以，在画法d 下，哦会与连接磷和鸹的6 条路有6 个 公共点，其中至多有3 个为哦的顶点，谚上至少有3 个交叉，矛盾 所以画法d 是凝聚的，又g 。是2 连通图，不与啦关联的写中的 蓝边不与晓交叉，否则g ；和写至少交叉两次，且g ；要么有一个自身 交叉，要么与关联它的蓝边交叉一次 考虑由d 导出铫的限制画法在下，不同的雠和砚，( ， f 【i 一1 ，i ， + 1 ) ) 之间的边不会交叉，霹的边不与g 1 的边交叉，曩“ 的边不与g 争1 的边交叉所以在鸥的任何好画法下，交叉类型仅为 ( 1 ) ，( 2 ) 或( 3 ) 那么在画法d 下，对任意的t ，江1 ，2 n 一1 ，( q ；) 5 ( 从 相应的铫的画法中很容易看得出来) ，则画法d 的总力量至少为5 ( n 一1 ) 在这一节的第一段我们已经证明了在凝聚画法d 下至少有1 个交叉 分别发生在g 2 和回的边上它们都没有计算在画法d 的总力量内所 以，c r d ( g 2 r ) ，( q ；) + 2 5 n 一3 凸 1 n 一1 定理3 2 c r ( g 2 r ) = 3 n 一1 ，n 1 证明；g 2 r 的好画法说明c r ( g 2 r ) 3 n l ，礼1 ( 见图3 - 3 ) 我们用数学归纳法证明相反的不等式注意到在g 2 只的任何好画 法中g 2 和g ；的边上分别至少有1 个交叉，结论对n = 1 时成立假设当 n = 七，七1 时结论成立，再假设有g 2 r + 1 的好画法，使c r d ( 岛r + 1 ) 3 ( 七+ 1 ) 一1 由引理3 2 ，必有某个谚上至少有3 个交叉去掉这个哦的 1 0 关于一些图类的交叉数 所有边，我们得到一个图或者同胚于g ：最，或者包含g z r 作为它 的子图，并且交叉数小于3 ( 七十1 ) 一1 3 = 3 七一1 与归纳基础矛盾。口 3 3g 3 r 的交叉数 引理3 3 若d 是g 3 r 的一个好画法，且在d 下每一个磁上至多只 有1 个交叉，则咖( g 3 r ) 4 n 一4 证明：我们证明画法d 是凝聚的首先由于g 3 是2 连通图，不同的岛 与磁之间不会彼此交叉，否则c r d ( 晓，磷) 2 其次假设在画法d 下子图 磷和磷位于岛导出画法的不同区域中，运用引理3 2 中同样的方法， q 的边和连接磷到职的蓝边至少产生2 个交叉，矛盾! 所以画法d 是凝聚的，而且由于g 3 是2 连通图，不与岛关联的碍 中的蓝边不会与磷交叉 q 。g 言 1 图孓4图3 5 ：g 3 r 的一个好画法 现在考虑由d 导出的硪的限制画法d i ，很容易看到在谚的限制画 法下交叉类型只有( 1 ) ，( 2 ) 或( 3 ) 那么在画法下，砚只能是图3 - 4 中的形式( 否则谚的边上至少有2 个交叉，与假设矛盾) ，所以职上的 交叉至少有4 个，即，( 鹂) 4 因此当t 遍历1 ，2 孔一1 时，画法d 至少 1 1 硕士学位论文 有4 m 一1 ) 个交叉口 定理3 3 c r ( g 3 r ) = 2 n 一2 ，l 1 证明：图孓5 说明c r ( g 3 r ) 2 n 一2 ( n 1 ) 我们对n 用数学归纳法来证明相反的不等式g 3 只是一个可平面 图，c r ( g 3 p 1 ) = o ，结论对t l = 1 成立假设结论对n = 七( 七1 ) 成立， 再假设存在g 3 r + 1 的好画法d 使得c r d ( g 3 r + 1 ) 2 ( 七十1 ) 一2 由引 理3 3 ，必存在某个q 上至少有2 个交叉，去掉这个碟的所有边，我们 得到一个图或者同胚与g 3 最或者包含g 3 r 作为它的子图，且交叉 数小于2 ( 七+ 1 ) 一2 2 = 2 七一2 与归纳假设矛盾口 3 4 + g 4 r 的交叉数 将g 4 的6 个顶点都和另一点z 连边，得到的图记为q ，用p 表示6 条和点z 关联的边( 见图孓6 ) ，有q = g 4up q 的一个好画法g 4 r 的一个好画法 图3 6 引理3 4 c r ( q ) = 2 图3 _ 7 证明：q 的一个好画法说明c r ( q ) 2 ( 见图3 7 ) 我们用逐一分析来证 1 2 关于一些图类的交叉数 明相反的不等式在q 的任何好画法d 下，有下列3 种情况：c r d ( g 4 ) = 0 _ ， 咖( g 4 ) = 1 和c r d ( g 4 ) 2 情况( i ) ：c r d ( g 4 ) = o 根据e u l e r 公式，= 6 ，而g 4 恰有6 个不可分 离诱导圈：1 2 3 ，2 3 - 4 ，3 _ 4 - 5 ，缸5 - 6 ，1 2 缸6 ，1 3 1 5 6 ，所以在每个区域的边界 上最多有g 4 的4 个顶点，连接g 4 的6 个顶点和点z ，则g 4 的边至少会 和p 产生2 个交叉，即c r d ( q ) = c r d ( g 4 ) + c r d ( p ) + c 物( g 4 ，p ) 2 情况( 础c r d ( & ) = 1 在g 4 的每个区域的边界上至多有5 个顶点连 接g 4 的6 个顶点和点z ，则g 4 的边上至少会和p 的边产生1 个交叉， 即印( q ) = ( g 4 ) + ( p ) + ( g 4 ，p ) 2 情况( 渊：c ，d ( g 4 ) 2 则( q ) c r d ( g 4 ) 2 上面的分析说明在g 。的边上至少有2 个交叉且c r ( 饿) = 2 口 引理3 5 若d 是g 4 r 的一个好画法，在d 下每一个磺上至多有3 个 交叉，则c r d ( g 4 r ) 7 n 一3 证明：采用和引理3 2 完全相同的方式我们知道画法d 是凝聚的，而且 由于g 4 是3 连通图，不与q 关联的巧中的蓝边不会与g i 相交( 否则 ( q ，巧) = 3 ，c r d ( 欲) = o ，在g j 的边上还会有2 个与关联醴的蓝边产 生的交叉) 下面我们将证明在画法d 下，哦或者有1 个自身交叉或者有3 个自 身交叉 ( t = 1 ，2 n 一1 ) 若c r d ( 岛) = o ，则磺至少会与砭和霹+ 1 中的蓝边分别交叉2 次，矛 盾! 若c r d ( 哦) = 2 ，在哦的限制画法下，边界上最多有硪的5 个顶点， 故q 上还有2 个与霹u 曩+ 1 的蓝边产生的交叉! 所以，c r d ( g i ) = 1 ，或 者c r d ( 暖) = 3 1 3 硕士学位论文 考虑画法d 导出的硪的限制画法我们已经证明交叉类型仅为( 1 ) ， ( 2 ) 或( 3 ) ，而且g i 或者有1 个自身交叉或者有3 个自身交叉在职上还会 有6 个或4 个交叉( 相应于暖的自身交叉) ，即，( 硪) 7a = 1 ，2 n 一1 ) ， 引理3 4 说明在g 2 和四的边上分别至少有2 个交叉，它们都没有计算 在画法d 的总力量内所以，c r d ( g 4 r ) ，( 哦) + 2 + 2 7 n 一3 口 l s i n 一1 定理3 4 c r ( g 4 r ) = 4 n ( n 1 ) 证明：g 4 r 的好画法说明c r ( g 4 r ) 4 n ( 见图3 7 ) 我们对n 用归纳法证明相反的不等式引理3 4 说明，在g 2 和q 的 边上分别会有2 个交叉，所以c r ( g 4 p 1 ) 4 ，结论对n = 1 成立假设结 论对n = 七( 七1 ) 成立，再假设有g 4 r + 。的好画法且在该画法下的交 叉数小于4 ( 七+ 1 ) 由引理3 5 ，必有某个g i 上至少有4 个交叉去掉这个 g ：的所有边，我们得到个图或者同胚于g t 最或者包含g 4 r 作为 它的子图，且该图的交叉数小于4 ( 七+ 1 ) 一4 = 4 七这与我们的归纳假设矛 盾口 3 5g 5 r 的交叉数 电 g 5 即是图妫4 以下我们均用鲍。4 代替g 。来进行讨论考虑由连接 鲍。的6 个顶点和一个连通图g 所得到的图，由于收缩g 的边会得到一 个图包含娲4 作为它的子图，而c r ( 砥，4 ) = 1 ，所以在这个图的任意好画法 下鲍4 的边至少会有2 个交叉 引理3 6 若d 是配，。r 的一个好画法，在d 下每一个鹚4 的边上最多 有3 个交叉，那么( 如，4 r ) 4 n 证明：根据条件，我们有如下4 个断言： 首先，不同的鹚，。和趔4 ( i j ) 之间的边不能交叉否则由于鲍，4 是 1 4 关于一些图类的交叉数 2 连通图，碰，4 ( 硅。) 至少会与琏，4 ( 琏，4 ) 交叉两次，而且这节的第一段 说明每个鹂，4 ( 砭，4 ) 的边上已经至少有2 个交叉，矛盾! 其次，每个鹂 4 ，( 江l ，2 ，n 一1 ) 都有自身交叉否则在琏，4 子画 法的每个区域的边界上恰好有4 个顶点，鹚，4 至少会与连接鹚，4 到砭j 1 和遥。4 到磁1 的蓝边产生4 个交叉0 = l ，2 ，7 l 一1 ) 第三，硅4 和鹚4 在鹚。4 j f ) 子画法的同一区域中因为不管 鹚4 有几个自身交叉，在子画法的任何两个区域的公共边界上至多只有 3 个顶点，所以如果，4 和鹚，4 在砭，4 的不同区域中，那么鹂，4 还会和 6 条连接硪到鹂，4 的路产生至少3 个交叉，矛盾! 第四，从上面的分析很容易得到不和鹚，。关联的蓝边不会与琏4 的 红边交叉 一 用h 幻表示鲍，a r 由鹂- 4 磁1 琏，。构成的点导出子图( l j n ) 考虑由d 导出的日讲+ 1 的限制画法“1o o ，1 ，n 一2 ) ) 砖：1 有 自身交叉，容易证明磁1 的画法只能如图3 8 所示，因为在其他的画法 下磁1 上的交叉都会多于3 个在情况( 口) 下，琏。4 只能落在包含硅：1 的5 个顶点在其边界上的区域中，否则在磁1 上会有至少4 个交叉， 与条件假设矛盾在情况( z ) 下，鹚，4 只能落在包含磁1 的6 个顶点在 其边界上的区域中0 = 6 ，c ) 在情况( z ) 中，在限制画法d t 下，最多只有磁1 的2 个顶点在区 域魄( z = o ，6 ，c ) 的边界上( 见图3 - 9 ) 现在考虑由d 导出的日邙+ 2 的限制画法d 讲+ 2i o ，l ，n 一2 ) 由假 设知，尉的所有顶点都必落在区域魄中扛= 口，6 ，c ) ，在每种情况下， 酽+ 1 m 的蓝边上至少会与日i + 1 蓝边和磁1 的红边交叉4 次当i 遍历 o ，1 ，礼一2 时，画法d 至少有4 ( n 一1 ) + 2 + 2 = 4 n 个交叉口 1 5 硕士学位论文 磷 硪1 ( b ) 图孓8 磁1尉 ：一一一一一： 一一 ( b )( c ) 图孓9 定理3 5 c r ( 鲍，4 r ) = 4 n n 1 证明：图孓1 0 说明c r ( 鲍。4 r ) 4 n 我们对亿用数学归纳法证明相反的不等式我们注意到每个4 的 拷贝上至少会有2 个交叉，所以结论对n = 1 成立假设结论对n = 七 ( 七1 ) 成立，再假设有鲍4 r + 。的一个好画法且在此画法下的交叉 数小于4 ( 七+ 1 ) 由引理3 6 ，必存在某个鹂4 至少被交叉4 次，去掉这个 鹚。4 的所有边，我们得到一个图或者同胚于尥4 只或者包含尬，4 r 作为它的子图，且交叉数小于4 七与归纳假设矛盾 口 1 6 关于一些图类的交叉数 图孓1 0 ：鲍4 r 的一个好画法 1 7 关于一些图类的交叉数 第四章 尬，1 0 ，礼与匝，仇，n 的交叉数 关于完全3 - 部图的交叉数最早的结果是1 9 8 6 年k 触给出了 完全3 部图尬，3 ，n 和娲，3 n 的交叉数，由于研究受到完全偶图，n 当 z a r a n l 【i e w i c z s 猜想对于武n m ，礼) 6 时成立的限制，此后一直没有新结 果，直到最近我的导师黄元秋教授和梅汉飞，赵霆雷合作给出了完全孓部 图坼4 ，n ，施5 n ，鲍4 n 的交叉数，( 文献【2 3 】一【2 5 】) 后来又假设z 盯a n l c i e 耐s 猜想成立给出了完全3 - 部图甄6 n ，噩，7 n ，坼8 ，n 的交叉数，( 文献【2 6 】- 【2 8 】) 我们从这些文章中可以看到，随着考虑对象的不同，研究方法也不能一 概而全，甚至有些很类似的图也不能采用相同的方法，这就要求我们在 研究中必须发现新方法 本文是在假定z 盯a n k i 赫c z s 猜想成立的基础上，得出了如下定理： 定理4 1 ：若z a r a j l k i e 耐c z s 猜想对尬1 n 成立，则 c r k l ，1 0 。n ) = z ( 1 1 ，n ) + 2 0 【芸j 在研究过程中发现完全3 部图施m n 的交叉数可以用一个通式表达 出来： 定理4 2 ：m 为偶数，若z a r a n l 【i e w i c z s 猜想对虬+ m 。n 成立，当n 也为偶数 时，则有 c r ( 一= 砷+ m ，卅业【争 4 1 定理4 1 的证明 证明：k ，1 0 ，n 的三个划分点集为x = z ) ，y = 玑1 1 t l o ) ， z = 巧1 1 j n ) 我们构造虬 1 0 n 的一个好画法d 0 使得( 尬- 1 0 ，n ) = z ( 1 1 ，n ) + 2 0 吲，所需的画法d 0 构造如下：在平面直角坐标系中， ( 1 ) 把z 画在点( ，) 上，这里是很小的正数，( 2 ) 把玑( 1 i 1 0 ) 画在点 一1 9 硕士学位论文 ( o ，( 一1 ) i ) ) 上，( 3 ) 把匀( 1 歹礼) 画在点( ( 一1 ) j ，o ) 上，( 4 ) 用直线段连 接所有该连的点，从而形成图中所有的边如图4 1 所示所以由交叉数 的定义有， c r ( 1 0 。) c r d o ( 甄1 0 ，n ) = z ( 1 1 ，7 i ) + 2 0 【卧现在只需证对任意 的画法d ，均有c r d ( 尬，1 0 ，n ) z ( 1 1 ，n ) + 2 0 吲，即可完成定理的证明 图4 - 1 ：髓1 0 ，。的一个好画法仇 下面用反证法反设存在甄，- 卟的一个好画法d ，有c r d ( 虬，- o ，n ) z ( 1 1 ，n ) + 2 0 吲记凰，1 0 ，n 的边集忍= 【z 执1 1 i 1 0 ) ，局= e ( 凰，l o ，n ) 忍， 因为尬1 0 ，n 关于目的边导出子图同构于完全二部图甄- n ，由于我们假 设z 脚m k i e 丽c z s 猜想对甄l ，n 成立，所以c r d ( 毋) z ( 1 1 ，n ) ，则有 c r d ( 虬，l o 。n ) = c r d ( 目ub ) = c r d ( 日) + c r d ( 尾) + c r d ( 而，尾) z ( 1 1 ，7 1 ) + c r d ( 目，e ) 2 0 关于一些图类的交叉数 又c r d ( 施，1 0 ，n ) l n 一，即v 1 t 1 0 ，蚍l n 一设u 1 u l o 中有s 个咄l 孔+ ；，其余的( 1 0 s ) 个蚍等于；n 由 ( 1 0 s ) ( 量n 一壶) + s ( 兰n + 丢) ， 得s 5 假如s 4 ，则u o 中至少有6 个的值等于；n 一；，那么一 定有两个相邻的咄= 蚍+ l ，l l 9 ，不妨设为u 1 = 忱，而 o = u 1 一忱= l a l i l a 2 l l a 3 i i a 4 i l a 5 i l a 6 i + i a 7 i + i a 8 i + i a 9 i + i a l o l ， 所以有l a l i + l a 7 i + i 也i + i a 9 l + i a l o i = i a 2 i + i a 3 i + i 山i + l a 5 i + l a i ，故 1 0 n = i = 2 ( i a ，i + l a 7 i + l a 8 i + i a 9 l + i a l 0 1 ) ，与礼为奇数矛盾! = 1 2 2 一 4 3 2 1 0 1 2 3 4 5 3 2 1 o 1 2 3 4 5 4 2 1 0 l 2 3 4 5 4 3 1 0 l 2 3 4 5 4 3 2 0 1 2 3 4 5 4 3 2 1 l 2 3 4 5 4 3 2 1 0 2 3 4 5 4 3 2 1 o 1 3 4 5 4 3 2 1 0 1 2 4 5 4 3 2 1 0 1 2 3 5 4 3 2 1 0 1 2 3 4 蛾 m 汹 = n52 关于一些图类的交叉数 因此可以得到不能有相邻的咄= 姚+ l ，l 9 ，所以s = 5 ，即 u 。u - o 中有5 个蚍l n + ；，其余的5 个岫等于；n 一；再设u - o 中有z 个姚i n + i ，剩下的( 5 一z ) 个岫= ；n + ， 2 5 礼：苎蛇5 ( 争扣( 5 - f ) ( 兰n + 扣z ( 扣2 5 礼= 蛇5 ( 扣三) + ( 5 一f ) ( 兰n + 去) + z ( 争+ 量) ， 得z o ，所以f = o ，即u u o 中另外5 个的值等于；n + ； 又任意两个相邻的坝蚍+ 1 ，1 i 9 ，所以u 。u 。o 的值只有两种 情况： ( i ) u 1 = 蛐= 眺= = 岫= ；n 一 ，忱= 蛾= 蛐= 蛐= u l o = l n + ； 或者是 ( i i ) u 1 = 蛐= 姚= u 7 = 蛐= 2 n + ，忱= 地= = 。u 8 = u l o = n 一； 我们分别将u 。的两组值代回原方程，用m a t l a b 软件计算可得 方程的两组解分别为 ( ) ： ( 1 a 1 i ，i a 2 l ，l a 9 i ，i a l 。i ) = ( 一2 ，3 + 三，一2 ，2 ，一2 ，o ，1 + 兰，o ，o ，o ) 或 ( 既) ： ( i a l i ，i a 2 l ，l a 9 i ，i a l 。i ) = ( 2 ，一3 + 兰，2 ，一2 ，2 ，o ，一1 + 三，o ，o ，o ) 显然，这两组解都与限i 为大于或等于。的整数矛盾! 故我们可以肯定 一定存在某个咄l n l ，所以u k n i 不妨设七= 1 ，即u l 礼，当n 为奇数时，u - l n 一；同【2 9 】，由 于b 为循环矩阵，图4 - 2 所示的结构也有循环性，因此对u ，的假定性不 影响我们的证明下面对n 分奇偶两种情形给予分别证明 情形( 1 ) ：当n 为偶数时，首先，我们适当的修改画法d ，得到一个 完全二部图k 。肘。及其对应的画法其中西，n + ，和d 的构造方法如 下： 硕士学位论文 设是平面舻上以d ( z ) 为圆心， 为半径的圆， 第一步：增加一个新点磊+ 。，把+ 1 画在原来d ( e 。) 与的相交处， 这里相当于剖分边e 。，因而自然的形成两条新边+ 。g 和+ 。! ，如图 垂3 ； 第二步：对于每条边瓯( 2 t 1 0 ) ，去掉位于圆内部的片段( 不 去掉点z ) ； 第三步：按如图垂3 所示的方式，画连接磊+ l 和鼽( 2 i l o ) 的边， 即，这些边是由位于圆外部的边色的片段和位于圆内部的一段组 成，见图厶3 e 1 图缸3 ： 虬1 1 及对应的画法d 这样我们得到了完全二部图冠，卅- 及对应的画法d ，现在我们要来 确定图虬- 斛- 在画法d 下的交叉数由于在我们的构造过程中，第一 步和第二步不改变交叉数，交叉数的改变主要是由第三步引起由图垂3 可知，在画边磊+ 。耽时，增加了i a 。1 个交叉数；在画边磊件。的时，增加了 ( 1 a 1 i 十i a 2 1 ) 个交叉；在画边+ 1 弧时，增加了( 1 a l i + i a 2 l + i a 3 1 ) 个交叉； 一2 4 关于一些图类的交叉数 在画边+ 1 蜘时，增加了( i a l i 十i a 2 i + 1 4 3 i + i 也i ) 个交叉；在画边+ 1 舶 时，增加了( i a - i + i a 2 i + i 如i + i 山l + i a l ) 个交叉；等等，因此我们有 c r d ，( j q l ，n + 1 ) = c r d ( k