（运筹学与控制论专业论文）笛卡儿积图交叉数的若干结果.pdf

笛卡儿积图交夏敬的若干结皋 摘要 我们已经知道确定图的交叉数是一个n p 完全闯题( 见文献f 2 j ) ，正是 因为其计算复杂性，目前为止有关交叉数的结果比较少，甚至在许多情况 下，找出图的一个好的上界或下界也很艰难对具体图类的研究方法和图 自身的结构特征紧密相连，相同的方法甚至不能用在结构相近的两类图 上本文具体研究了路，圈与某些6 _ 阶图的笛卡儿积图交叉数 首先，交代了本文的写作背景，交叉数研究在国内外发展的动态，研 究工作的意义以及本文中要解决的问题和创新之处 然后。给出了一些基本概念和性质，介绍了阅读本文所需要的预备知 识其中主要包括交叉数的概念，并介绍了在后面文章中会出现的一些相 关概念、性质以及常用到的一些定理，而部分使用较少的概念等我们放 到了具体的章节中去交代 再接下来，在第三章，对图飓。xr 在一个已知上界的限制下的结 构做了具体细分，同时运用归纳法，确定了飓。xr 的交叉数在第四 章，先确定一个子图的交叉数，通过母图的交叉数大于等于子图的交叉 数，从而确定了笛卡尔积图岛xg 及岛x 晶的交叉数 最后指出了研究工作中遇到的一些问题以及作者以后研究的主攻方 向 关键词：图；画法；交叉数；路；笛卡儿积；同胚；平面图 笛卡儿积图交叉效的若干结果 a b s t r a c t g a r e ya n dj o h n s o n ( 1 9 8 3 ) s h o w e dt h a td e t e r m i n i n gt h ec r o s s i n gn u m b e ri sa n n p c o m p l e t ep r o b l e m b e c a u s eo fi t sc o m p l e x i t y , t h e r ea r eaf e we x a c tr e s u l t so i l t h ec r o s s i n gn u m b e r so fg r a p h sf o ri t sc o m p l e x i t y e v e ni nm a n yc a s e s ，i ti sv e r y d i f f i c u l tt of i n du p p e ro rl o w e rb o u n d so ft h ec r o s s i n gn u m b e r so fg r a p h s t h ep r o o f m e t h o di sc l o s e dt ot h es t r u c t u r eo ft h eg r a p h s ，e v e l lt h es a m em e t h o di sn o ts u i t t h e 擎印h 8w h i c hh a v et h es i m i l a rs t r u c t u r e i nt h i sp a p e r ，w es t u d yt h ec r o s s i n g n u m b e r so ft h ec a r t e s i a np r o d u c t so fp a t ha n dc y c l ew i t hs o m e6 - v e r t e “g r a p h s a tf i r s t ，w ei n t r o d u c et h eb a c k g r o u n do ft h ec r o s s i n gn u m b e ra n di t sd e v e l - o p m e n ta r o u n dt h ew o r l d ，t h em e t h o d so ft h er e s e a r c ha n dt h ep r o b l e m sw ew i l l s o l v e s e c o n 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 s ，a n di n t r o d u c et h er e q u i r e d k n o w l e d g ei n c h i d m gc r o s s i n gn u m b e r sw h e nr e a dt h i sp a p e r 。 t h i r d ，i nc h a p t e rt h r e e ，w ed e t e r m i n ea nu p p e rb o u n d so ft h ec r o s s i n gn u m b e r s o f 硒3 r ，t h e na n a l y z ei t ss t r u c t u r ei nd e t a i l ，w i t ht h ei n d u c t i o n ，w ed e t e r m i n e t h ec r o s s i n gn u m b e r so fk s 3 r i nc h a p t e rf o u r ，w ef i r s td e t e r m i n et h ee r o d i n g n u m b e ro fas u b g r a p ho fs 5 c k ，b e c a u s et h ec r o s s i n gn u m b e ro ft h es u p e r g r a p h i sn o tl e s st h a nt h es u b g m p h ，t h e nd e t e r m i n et h ee r o s s i n gn u m b e r so r s 5 ga n d 岛岛 a tl a s t ，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 e d i r e c t i o n1w i l lg oa h e a d k e y w o r d s ：g r a p h ；d r a w i n g ；c r o s s i n gn u m b e r ；p a t h ；c a r t e s i a np r o d u c t ； h o m c o m o r p h i s m ；p l a n a rg r a p h i i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果除文中已经注明引用的内容外，本论文不含任何其他个人或集体已 经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体，均已在文 中以明确方式标观本人完全意识到本声明的法律结果由本人承担 学位论文作者签名 9 钌月j 。日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅本人 授权湖南师范大学可以将本学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 ，不保密口 ( 请在以上相应方框内打” ”) 作者签名嗣劳 导师签碰泓 日期：7 年，膨。日 日期：。、) 年岁月j 日日 笛卡扎积图交叉教的若干结果 第一章基本概念和性质 本章介绍有关的一些基本概念和术语，未说明的概念均同文献1 1 】且 无特别说明所涉及图均指连通简单图 一个图g 是指一个二元组( k e ) ，记为g = ( e e ) ，其中v ( a ) 是非空 的集合( 顶点集) ，e ( a ) 是由( v ( g ) 中元素构成的无序对集合( 边集) ，记为 e ( g ) = ( 也”) i “，”y ( g ) ，简记边( ”，口) 为w 称边删的端点n ，。为相邻 的，称一条边的端点与该边相关联，也称一条边与该边的端点相关联 若v ( h ) y ( g ) ，e ( h ) e ( g ) ，则称h 为g 的子图若y ( 日) = y ( g ) ，e ( h ) e ( g ) ，称日为g 的生成子闰( s p a n m n gs u b g r a p h ) ；若v ( h ) y ( g ) ，删e ( 日) ，当且仅当“v e ( h ) 且玛口y ( ) ，则称h 为g 的导出 子图( i n d u c e ds u b g r a p h ) 记为h ，。2 。 硬士学位论文 ( g ( ； l ，3 ，) n - r n 3 , 3 1 进一步，他们还给出了 ，n = o o r l ( m , x t 3 ) t ，n = 2 ( m o d 3 ) e r ( c ( n ； 1 ，3 ) ) ) n 2 4 + 1 后来郝荣霞与刘彦佩给出了关于c ( n ；t ，女) 交叉数的新上界( 1 ) ，杨 元生等( 【4 6 】) 给出了部分小阶循环图的交叉数 除了上述外，还有对广义p e t e r s e n 图，方图的交叉数的研究，在这里 就不赘述了 2 2 一般图类 对于更一般的情况，我们考虑包含n 个顶点，k 条边的图g ( n ，) 甩 g ( n ，自) 表示所有图g ( n ，) 交叉数的最小值e r d o s 和g u y ( 3 c 献1 3 1 1 ) 给出 了一个猜想t c d p n 2 g ( n ，k ) ? |。 j i 1 k k bk 孙 图1 娲jxr 的一个具体的好画法 设丌为图g 的一个好画法，g t 和g 2 为g 的两个边不交的子图，由定 9 硬士学位沦文 义易得，o r ( g 1u g 2 ) = ( g 1 ) + c r ，( g 2 ) + ( g - ，g 2 ) 由一个具体的好画法 p ( 见图1 ) 可以得到硒3 r 的一个上界，c r ( k k 3 r ) sc r d ( 蚝，3 r ) = 饥一l 引理1 若存在k s 。r 的某一个好画法d ，使得对某两个j ( 1s ，js n ，i 焱有( 艇函趔3 ) 0 ，那么c r 口( 聪3 ，瑶，3 ) 3 证明；由于c r d ( 弼3 喇，。) 0 ，琏。和磁。中必有( 设为) 喇j ，其6 个点 落在子图醒。的不同区域中存在由砭。的边构成的一个圈c ，将矿( 弼，s ) 分割为( h ，) ，分别落在圈c 的内外娲，。是3 正则图 ( 1 ) 若l l = 1 关联的3 条边都与圈c 交叉，则“d ( 磁。，皤，3 ) 3 ( 2 ) 若l i = 2 h 至少有4 条关联的边与圈c 交叉，贝! ”d ( 磁，3 ，嘏3 ) 4 ( 3 ) 若l kj = 3 至少有5 条关联的边与圈c 交叉，则c r d ( 聪3 ，琊。s ) 5 综上所述，结论成立 同时当”d ( 磁。魑。) = 3 或4 时的好画法容易确定，图2 给出了 鹚3 ，碹j 自交叉数为1 时的情况 ( b ) 图2 琏3 艇，。自交叉数为1 时的3 种情况 ( c ) 用t t u k s 。表示将岛的6 个悬挂点连边构成飓，3 而得到的新图，其 1 0 笛卡儿积图交叉效的若干结果 同构甄3 3 用p u ，3 u p 表示在，。外添加两个点，y ，并与飓，3 的 点均连边得到的新图，其同构鲍j ，3 ，由文献【17 】可得到下面的引理2 引理2 贯( p u k 3 j ) = 仃( 硒，3 ，3 ) = 3 ，盯( p u 尥 3 u p ) = ( 拖鼬) = 7 引理3 c r ( 7 n 一1 若这3 条边与磁3 交叉， 只能有1 条边，否则磁3 的边至少产生3 + 4 _ 7 个交叉，矛盾! 假设其他 的边都与p 2 交叉，即c r 丌( 醒3 ，p 1 ) 3 ，口_ ( p l ，p 2 ) 2 程3 不与砖3 交 叉，否则g t 3 的边产生至少7 个交叉，矛盾! 收缩磁3 ，磁3 为点岛y 若 ( 砖3 ) = 1 ，( 瑶3 ，p ) 20 c z ，g ) 再加上( 磁3 ，p 1 ) 3 ，贝4 磁3 边 至少产生8 个交叉，矛盾! 若( 耀。) = 3 且f i t ，( 赡。，p ) = 00 = 叠口) ，则 臼_ ( p ，p ) 6 ，得到，( q 2 ) 1 2 当n = 3 时，赡3 与磁3 不交叉，收缩磋3 为一点可知醚3 的边产生至少3 个交叉，那么c r ，( ，3 p 3 ) 7 + 1 2 + 3 2 0 当n 4 时，妒( 日) 9 ，c h ( 地3 r ) 7 ( n 一4 ) + 1 2 + 1 8 = 7 n + 2 7 n 一1 若( 磁3 ) 5 ，那么磁3 边产生至少7 个交叉，矛盾! 情形1 3 当( 礁。) 5 时易知，礁。的边产生至少8 个交叉，矛 盾! 情形2 苦( 醒3 ，础3 ) 4 收缩磺3 为点孔( 霹o u p ) 3 ，则 磁3 的边至少产生7 个交叉，矛盾! 综上所述可得，( 恐。3 r ) 7 n 一1 定理c r ( k 3 1 3 r ) = 7 n 1 证明：由已知画法( 图1 所示) 得到：c r ( 晒3 r ) 7 n 一1 接下来证明逆不等式，对n 用归纳法t 当n = 1 ，2 时，由引理3 ，引理4 可知结论成立! 假设n = k 时定理成立，当n = k + 1 时，对于任意好画法d 1 4 笛卡儿积图交叉效的若于结果 若有某个蟛。的边产生的交叉数大于或等于7 ，那么去掉其边，得列 一个子图同构于飓。r ，显然可以得到： c r d ( 娲3 r + 1 ) c r o ( j 3 p h ) + 7 = 7 k 一1 + 7 = t ( k + 1 ) 一1 否则由引理5 可知： c r d ( k 3 。3 b + 1 ) 7 ( k + 1 ) 一1 综上所述，可以得到结论成立： c r ( 娲3x r ) = 7 n 一1 1 5 笛卡儿积图交夏敷薛若干结果 第四章笛卡尔积图& c y n 及鼠晶的交叉数 m k l 酣在九十年代确定了& g 的交叉数( 文献【1 2 】) ，接下来就再 也没有其他结果了本文用类似的方法确定了s s g ，s 5 的交叉数， 得到如下结果t 定理1 啪蚓= 詈 同时利用文献【19 】的结果我们有 定理2c r ( 岛x & ) = z ( 6 ，n ) + 4 【j 下面我们解释有关的的术语和符号： 兄表示长为n 的路，点用0 1 一表示g 表示长为疗的圈，点用 0 ，1 忭一1 表示星图的5 度点用。表示，其它一度点用b ，c ，d e i ，表示 笛卡儿积图最g 有饥个点( i ，j ) ( i = 口，b ，c ，d ，e ，0sj 竹一1 ) 在图 s 5 g 中，点( o ，j ) 与( i ，j ) 0 = b ，c ，d ，e ，；0 曼，n - 1 ) ，点( t ，j ) 与( i ，j + l ( m o d n ) ) ( i = 口b c d c t f ；j = 0 js1 7 , 一1 ) 是关联的磊而：表示图风g 去 掉边( o ，j ) ( o ，j + l ( m o d 哪) ( o j ，l 一1 ) 得到的子图( i = d b ，c ，d ，e ，) 表示g 点( i ，j ) ( 0 j ”一1 ) 的导出子图，( i = b ，c ，d ，e ，) 表示图 鼠1 名边( n ，j ) ( t ，j ) u = 0 j s7 l 一1 ) ，( 1 ，j ) g ，j + l ( m o d 哟) ( 0 js n 一1 ) 的导出子图s g ( 0 sj sn 一1 ) 表示点( t j ) ( i = 口，b ，c ，d ，e ，f ) 的导出子图另 外在本文中，若g 。是图g 的子图，在具体画法卢下我们用c r 卢( e ( g 。) ) 表 示g 1 的边产生的交叉数，即唧( e ( g 1 ) ) = c r o ( 0 1 ) + 即( g l ，g e ( g 1 ) ) ，其 中c r 口( g 1 ) 称为子图g l 在画法卢下的自交叉数，即子图g 1 在画法卢下自 身的边之间产生的交叉数目另外我们用【割表示不大于的最大整数， 用引表示不小于；的最小整数 1 7 硕士学位论文 4 1 引理 引理1 设图h 是图o 的子图，那么c r ( 日) sc r ( g ) 证明t 由交叉数的定义不难得到 引理2 1 3 6 1 c r ( 酉调= 4 ( n 一1 ) 引理3 ( 均 f 2 ( n - 2 ) 社；3 ，4 c r ( 取一) 2 8 住= 5 【2 n n 6 一耻詈 图4 瓦丽；的一个好画法( 实线部分) 引理4 c r ( 巧丽：) = 4 ( m 一2 ) ，其中m = 3 ，4 证明s 由图4 ，5 所示的具体画法( 实线部分) 可知c r ( 瓦- ；刁口4 m 一2 ) 由于两；刁：包含一个同胚于磊i 丽i 的子图，那么由引理1 和引理2 可 以得到其一个下界t 盯( 民g n ) c r ( x j k 1 ) = 4 ( m 一2 ) 因此，c r ( 磊聂。瓦) = 4 ( m 一2 ) 1 8 笛卡儿积图交叉数的若干结果 蔼 图5 磊玎瓦的一个好画法图6 瓦丐蕊的一个好画法 引理5 c r ( 品) = 4 ( m 一2 ) ，其中m = 3 ，4 证明：由图4 ，5 所示的具体画法( 包括虚线部分) 可知c r ( c k ) 4 ( m 一2 ) 和引理4 的证明类似，风c _ 去掉e ( 伊) 得到的一个子图同胚于s q ic ， 那么由引理1 和引理4 可以得到其一个下界， c r ( 岛x g 。) o r ( & c k ) = 4 ( m 一2 ) 因此c r ( s sx c 矗) = 4 ( m 一2 ) n 亏i 理6 设g 是一个这样的图，其含有3 个n - 圈o = q6 ，c ；礼6 ) ，每个 圈的点都分别标上符号a = a ，b ，c ；0 j s n 一1 ) ，点砭与讲a = b ，c ；0 j 往一1 ) 有边相连如果d 是图g 的一个好画法，且在此画法下，伊没 有自交叉，p ，r 落在俨的同一个区域里，那么”d ( t b ，p ) n 证明t 我们用归纳方法证明，首先当n = 6 时，6 - 圈俨把平面划分为两个 区域，不妨设伊，俨都落在伊的内域，先确定p ，p 把伊的内域划分几个 小区域，且每个区域至多含有俨的2 个点： 情况1 如果伊与俨不交叉有一个圈( 不妨设) 伊包含另一个圈 俨，那么伊必然与边t 嗟产生至少6 个交叉否则伊与g c 互不包含，那 么c 6 的点落在p u 伊的区域里，且区域边界上至多含有2 个c n 的点， 接下来我们考虑秒的6 个点之间的位置关系。 子情况1 1c b 的6 个点落在同一个区域里那么可以通过变形，在 俨的另一个区域添加两个点且用边同伊的点连接起来这样可以构造 1 9 硬士学位论文 出一个新图，且新图含有一个子图同胚于如e ，由对称性可知， c r v ( t b ，p ) ；c r ( 甄o ) = 6 子情况1 2c b 的占个点落在两个区域里现在考虑是否有俨的点位 于这两个区域的公共边界上，如果有也只能是一个，这两个区域的边界 是上至多含有3 个伊的点，剩下的3 个点中有一个点与伊相隔2 个圈， 于是c 6 与另外3 个点关联的边必然会与p 交叉4 次，又由于伊是2 连 通图，那么伊与俨有至少2 个交叉，c r d ( p ，p ) 4 + 2 = 6 如果没有驴的点位于这两个区域的公共边界上，那么由于c a 是2 连通图，伊与p 有至少4 个交叉。又因为这两个区域的边界是上至多含 有4 个c 。的点，伊与另外2 个点关联的边必然会与r 交叉2 次，因此 c r d ( 7 了c ) 4 + 2 = 6 子情况1 3c b 的d 个点落在三个区域里如果其中一个区域与另外 两个区域都相邻，那么这三个区域的边界上至多含有4 个伊的点，与 另外2 个关联的边必然会与p 交叉2 次，而g “是2 连通图，伊与r 有 至少4 个交叉，因此c r d ( p ，p ) 24 + 2 = 6 如果其中一个区域只与一个区域相邻，与另一个不相邻，由于是 2 连通图，那么e - 与p 有至少6 个交叉 如果没有一个区域与另外的区域相邻，由于伊是2 连通图，那么伊 与p 有至少8 个交叉 子情况1 4c b 的艿个点落在四个或四个以上的区域里由于是2 连通图，那么伊与p 有至少8 个交叉 因此在沙与俨不交叉的情况下，c r d ( t b ，p ) 4 + 2 = 6 情况2 如果一与伊交叉设o b ( 或g c ) 包含伊( 或c 6 ) 的c r , 个点，那 么这些点与俨关联的边必然与o h ( 或俨) 交叉。次，剩下6 一z 个点所在 的区域，其边界至多含有伊的2 个点，那么共会产生2 + z + ( 6 一z 一2 ) = 6 个交叉 因此当n = 6 时，结论成立， 现在假设当n = k 时，结论成立 考虑当n = 七+ 1 时 因为l = k + l 的情况包含n = k 的情况，那么p 与 2 0 笛卡儿积图交夏敷的若干结果 p 必然有交叉，如果有交叉是发生在边( d ，f ) ( 6 ，f ) ( 或边( 口，2 ) ( c ，z ) ) ( 0 z k ) 上，那么去掉边( n ，z ) ( 6 ，f ) 和边( n ，f ) ( c ，z ) ，得到的是住= 情况，那么由归纳 基础可以得到p 与p 就有至少k + 1 个交叉如果没有交叉是发生在边 ( o ，f ) ( 6 ，f ) ( 或边( o ，1 ) ( c ，1 ) ) ( 0sl k + 1 ) 上，俨的点必然落在p u 俨的只 含e 。2 个点的区域里，且每个区域只能落2 个俨的点，若不然就会有交 叉发生在边( 。，) 汽z ) 或( a ，移( c ，1 ) 上，所以伊的边只能和伊的边产生交 叉，俨的点共落在期个区域里，每个区域的边界都会与俨的边产生 2 个交叉，那么共有2 f 毕1 k + 1 那么结论成立!d 引理7 c r ( 岛g ) = 1 6 证明：由图6 所示的具体画法可知c r 慨g ) 1 6 那么我们只需要证明 它的下界，即c r ( c 5 ) 1 6 接下来我们运用反证法，假设存在一个好 画法o ，使得c r a ( 风g ) 1 5 ，那么图g 的在此画法下必然满足以下 两个断言： 断言( a ) c ( e ( p ) ) 7 ，a = b ，c ，d ，e ，) 若不然去掉v ( c ) ，由此得到 的子图p 以及相应的一个好画法0 ，面子图p 是同胚于蜀侥，因此有 c r ( s 4 g ) c r o ( p ) 1 5 8 = 7 ，这与引理4 矛盾! 断言( b ) c ( e ( 伊) ) 3 若不然去掉e ( 俨) ，得到的子图p 以及相应 的一个好画法矿，而子图p 同胚于两而i ，那么c r ( 巧丽) c r o ( p ) 1 5 4 = 1 l ，这与引理4 矛盾! 下面对伊的交叉情况分别讨论： 情况1 若俨没有自交叉即俨的边之间没有交叉俨把平面分为 两个区域，且伊至多与一个交叉： 子情况1 1 若伊不与o ( i = b ，c ，d e ，) 交叉俨有一个区域至少包含 3 个醴不妨设伊，伊，落在同一个区域，用引理6 的方法可以知道，俨 与p 至少有4 个交叉，而与p 也至少有4 个交叉，那么一将会产生至少 8 个交叉，与断言( a ) 矛盾! 子情况1 2 若俨与一个f ：妨设为j 伊交又由于5 - 圈是2 - 连通图， 2 1 硕士学位论文 那么c r y ( c c b ) = 2 ，若不然，c ( 俨，c b ) 4 ，与断言( b ) 矛盾! 现在我们考虑子图9 ，g = pup ，g + 的每个区域的边界上至多含有俨2 个点，无论秒的点位于g 的哪个或哪些区域，由引理6 的分析方法可 知，c k ( p ，p u p ) 4 同样的，我们可以得到c r 口( 尹，一u 4 因此有 c r o ( e ( p ) ) c r o ( p ，p u p ) + c ( p ，一u t f ) + c r o ( c 6 ，c 4 ) 4 + 4 + 2 = 1 0 ， 这与断言( a ) 矛盾! 子情况1 3 若俨与两个及两个以上的圈交叉显然，c 4 与每个圈 都至少交叉2 次，那么c r o ( e ( ) ) 4 ，这与断言( b ) 矛盾! 情况2 若驴有个自交叉俨把平面分为3 个区域，且至多与一个 交叉，若不然c 。将产生4 个交叉，与断言( b ) 矛盾! 子情况2 1 若俨不与交叉o = b ，c ，d 一，) 分别落在伊的3 个 区域而且含有驴6 个点的区域至多有2 个，其余的落在另外2 个区域 里，这2 个区域边界上至多含有c n 3 个点，那么c 4 将产生至少7 个交叉， 与断言( b ) 矛盾! 子情况2 2 若俨与一个，不妨设为) c b 交又剩下4 个落在伊的 3 个区域里，同上面分析的一样，可导出俨也将产生至少7 个交叉，与断 言( b ) 矛盾! 情况3 若俨有易个自交叉伊不能与0 = b ，c ，d ，e ，f ) 交叉，否则 俨会有4 个交叉，与断言( b ) 矛盾! 那么0 一b ，g d ，e ，) 分别落在伊的4 个区域里，伊必然产生n 个交叉，与断言( b ) 矛盾! 情况4 若俨有，个自交叉，p 0 = 1 ，5 ) 不与伊交叉，分别落在伊 的区域里，同样能够导出伊必然产生多于3 个交叉，与断言( b ) 矛盾! 综上所论有c r ( s 5 c s ) = 1 6 弓f 理8 c r ( 否f ；_ 瓦) 4 n 一2 ( 6 ) 证明；先设在证明过程当中t l26 ，由于磊面：去掉边( z ，仃一1 ) ( ，o ) a = 1 ，5 ) 得到的子图就是两i 瓦：，由引理2 可得： c r ( s 5 g ) c r ( s 5 r 1 ) = 4 ( - 一2 ) 假设在两奶：的最优画法d 下，去掉边( t ，n 1 ) ( t ，0 ) 0 = b c d e f ) 2 2 笛卡儿积腰交叉数的若干结果 得到子图同胚于酉贯瓦= 用伊表示去掉的5 条边( ，n 1 ) ( i ，0 ) “= b ，c d ，e ，) 用c r d ( 日) 表示耳。而：去掉伊得到的子图在原来d 画法中的 交叉数c r o ( e o ) 表示伊在原来d 画法中的交叉数 在磊i 虿= 去掉s j ，霹- 2 的边和点，考虑由霹和鼋以及霹一1 和男- 3 的 点导出子图，再考虑添加e o 的5 条边会产生的交叉： 1 如果没有g 和雩- 1 的一度点落在同一区域的边界上，那么必然存在 一个圈e 将鼋的端点同霹- 1 的端点分隔开来，那么c , - ( e o ，e ) 5 如果 c r ( e ( ? o ) ) 6 ，有盯( s 5 ( k ) 2c r ( r 1 ) + c r d 但( j 尹) ) 4 n 一8 + 6 = 4 n - 2 现在我们假设c r ( e ( 酽) ) = 5 ，那么”( 伊，口) = 5 ，必然存在一个( 不妨设) 罐， 使得”( 酽，四) = 0 ，再考虑霹位置，砖的中心点a 2 无论位于哪个区 域，n 2 有路和霹的端点关联，那么这些路只能与霹的边产生交叉若不 然，( e ( 驴) ) 26 同前面的情况一样因此仃口( 嚣i 夏- ) 4 n 一7 那么 口d ( 岛c k ) c r 。( 品p - 暑- d + c r d ( e ( e o ) ) 4 n 一7 + 5 = 4 一2 吣赂 瑶霹男- 1 嚣- 3霹霹男1 嚣_ 3 图7 ( 2 ，2 ) 的两种可能的情况 霹霹s 1 霹- 3 罐 s 2 霹。嚣3 图8 ( 2 ，3 ) 的两种可能的情况 2 如果有锷和霹- 1 的一度点都落在同一区域u 的边界上，那么有以下的 情况： 2 3 硬士学位论文 用( 曩f ) 表示霹和霹“各有z 和y 个一度点在u 的边界上，如图7 , 8 所示 对于( 2 ，2 ) ，由霹和霹的点导出子图霹有3 个点不在u 的边界上，那 么添加伊至少会有3 个交叉，同样霹- 1 和嚣- 3 的点导出子图也会有3 个 交叉，那么至少会产生6 个交叉，c r ( h ) 4 n 一8 + 6 = 4 n 一2 图9 ( b ) 对于( 2 ，3 ) ，不妨设霹有3 个点位于u 的边界上，那么霹必有一条边 与冤，( i 一0 ，2 ) 端点关联的边交叉，如图9 ( a ) 所示，设交叉点为u ，首先我 们抹去交叉边关联的2 个霹的点，不妨设为b o 和c o ，然后在点v 处把交 叉的两条边的后半部分交换后连接起来，最后剖分“变形”后的新边，即 在变形后的新边上分别添加一个2 度点b o 和印，如图9 ( b ) 所示“变形” 得到图护以及一个新的画法d ，那么c r o ( h ) 2c r d ( 护) + 124 ( n 一1 ) + 1 而由霹和罐的点导出子图霹有3 个点不在u 的边界上，那么添加酽 后，e o 与。的边界会产生至少会有3 个交叉，同样可知，伊与由嚣4 和 霹- 3 的点导出子图会有至少2 个交叉，所以c r d ( e o ) 3 + 2 = 5 ，那么可以 得到 c r ( 磊两) c r d ( h ) + c v d ( e o ) 4 n 一7 + 5 = 4 n 一2 那么对于其他的情况，当u 的边界上每增加一个点时，相应的，子图日在 画法d 下必然比在最优画法下又多出一个交叉，我们都是用同样的方法 进行分析的下表给出了其他情况下的两个值c r o ( h ) 和c r d ( 伊) 的下界： 2 4 笛卡儿积田交夏致的若干结果 ( 2 , 2 ) ( 2 , 3 )( 2 ，4 )( 2 , 5 )( 3 3 )( 3 ，4 )( 3 , 5 )( 4 ，4 )( 4 , 5 ) ( 5 , 5 ) c r d ( g ) 4 珏- 84 n 74 n 64 n 54 n 64 n - 54 n 一44n 一4 4 n - 3 4 n c r o ( e o ) 654343 2 2 1 o 出于图形的对称性，( 3 ，2 ) 与( 2 ，3 ) ，( 4 ，2 ) 与( 2 ，4 ) ，( 4 ，3 ) 与( 3 ，4 ) ，( 5 ，2 ) 与( 2 ，5 ) ， ( 5 ，3 ) 与( 3 ，5 ) ，( 5 ，4 ) 与( 4 ，5 ) 是一样的得到所有的情况合计在一起， c r d ( s 5 - - 7 - c ) c r d ( j f 爱】j i ) + c r d ( e o ) 4 n 一2 因此结论成立 口 4 2 定理的证明 下面我们先给出本文的第一个主要结果的证明 图l osx g 的个好画法 定理1 的证明；当n = 3 ，4 时，。由引理5 可得当n = 5 时，由引理7 - - 1 得在 接下来的证明过程中，所有情况都在n 6 的前题下，由图1 0 所示的具体 画法可以得到c r ( 岛x g ) 锄，现在要证明的是口( s 5 x g ) 缸我们用反 证法证明，先假设存在个s 5 g 的好画法芦，使得e 即( s 5 g ) 4 n 一1 ， 那么好画法卢都必然满足以下两个断言： 2 5 硬士学位论文 ( 1 ) c 即( e ( p ) ) 2 n 一1 ，o = b ，c ，吐毛，) 若不然，去掉v ( o ) 得到一个 同胚于s 4 g 的子图p 以及相应的一个画法，由此得到 c r 士( f ) = c r y ( & g ) 一c 印( e ( p ) ) 4 n 一1 2 n 2 n 1 ，与引理2 矛盾! ( 2 ) c 即( f ( 俨) ) 1 若不然，去掉e ( c 。) 得到一个同胚于瓦而：的 子图p 以及相应的一个画法由此得到 c r ，( p ) = c r y ( & 倪) 一唧( e ( e 4 ) ) 4 n 一1 2 4 n 3 ，与引理7 矛盾! 现在我们就在这两个断言成立的条件下考虑伊的自交叉数，那么有 两种情况： 情况1 如果伊没有自交叉由断言( 2 ) 可知伊也不会与0 = b ，c i d ，岛，) 交叉，否则o r b ( c ) 2 ，这样就导出了矛盾因此，c 4 把平 面划分为两个区域，那么必然有个区域含有3 个p “= b ，c d ，e ，) 不妨 设为p ，p ，那么有引理5 可得c 即( f ，t b ) 2n , c r 口( t d ，p ) 竹那么 ( e ( ) ) e , z ( t d ，p ) + c r z ( t d ，p ) n + ，l = 2 n ，与断言( 1 ) 矛盾! 情况2 如果伊有自交叉由断言( 2 ) 可知仃d ( 伊) = 1 ，且不能与 o = b ，c ，d ，e ，) 交叉伊把平面分为3 个区域，有一个区域含有n 个点，此 区域至多含有2 个，那么还有3 个落在另外两个区域里，而这两个 区域的边界上至多含有n - 2 个俨的点，因此俨必然会与这3 个p 产生6 个交叉，那么俨上将至少会有7 个交叉，与断言( 2 ) 矛盾! 综上所述，所有情况都与假设矛盾，那么”( 岛g ) 4 n 6 ) 因此结论成立 下面我们给出了本文的另一个结果的证明，首先介绍有关的记号和符号， 在笛卡儿积图岛& 中，共有6 + 1 ) 个点以及5 m + 1 ) + 6 n 条边，其 中包含n + 1 个岛的拷贝( 用踺( 0 i 帕表示) 以及6 个& 的拷贝 2 6 笛卡儿积图交叉敷的若干结果 图l l x & 的一个好画法 定理2 的证明t 昆x & 包含一个同胚于尬，5 。的子图，由文献【1 9 j 可以得 到c r ( & ) ”( 尬加) = z ( 6 ，n ) + 4 1 2 j 又由岛& 的具体好画法( 如图 i i 所示) 可以得到上界，c r 涵x & ) z ( 6 ，n ) + 4 【孙 因此，c r ( 岛晶) = z ( 6 ，n ) + 4 【j n 2 7 笛卡儿积田交叉致的若于结果 第五章结语 由于确定图的交叉数是n p 同题，且两个图在结构上的小差别就能使 得他们的证明方法完全不同，在研究过程中缺乏参照性，连续性，所以长 期以来，研究进展一直很难取得很大的突破一直以来，应用的方法多是 采用纯数学证明方法，如数学归纳法，反证法等等，在证明过程中由于关 系到交叉数的上限或下限，甚至有一些很繁琐的计算，对某些图的证明还 含有很局限的技巧随着研究对象的阶数不断增大，它们的画法急剧增加， 采用原有的方法进行研究将越来越会困难，推广工作也就遇到了很大的 困难而且几十年的结果也主要局限于画在平面上的图的交叉数，对于其 他的曲面上的研究极少，不过我们已经开始在这一方面的研究，也有一 些数据和结果出来从事这些方面的研究，是作者今后一段时间内的主要 工作 2 9 笛卡儿积图交叉致的若干结果 参考文献 【l 】1j a b o n d ya n du s r m u w , g r a p ht h e o r ya n da p p l i c a t i o n s m ，l o n d o n ，1 9 7 6 【2 】m r g a r a r ya n dd s j o h n s o n ，c r o s s i n gn u m b e rj sn p - c o m p l e t e j ，s i a m 正 a l g e b r i cd i s c r e t em e t h 础, 1