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

北京交通大学硕士学位论文中文摘要 中文摘要 摘要t 图g 的交叉数是将g 画在平面上时交叉次数的最小值，记为c r ( g ) 其 中画法满足：( 1 ) 任何两条边相交叉的边最多交叉一次；( 2 ) 边不能自身交 叉( 3 ) 有相同端点的两条边不交叉；( 4 ) 没有3 条边交叉于同一点称含最 小交叉数的画法为最优画法一般而言，确定图的交叉数是一个完全n p 问题， 给出给定图的交叉数的具体值是项非常困难的工作对交叉数的研究主要集中在 对完全图，n 部图，广义p e t e r s e n 图，循环图，笛卡尔积图的交叉数的计算上 目前知道交叉数的图类很少，其中知道交叉数的图类主要集中在简单图的特殊图 与路，与星图，与圈，简单的特殊图之间的笛卡尔积图等 本文共分两章 第一章中综述了本篇文章主要要用的基本概念，以及前人给出的关于交叉数 的已有结果 第二章中给出了一些新的结果： 循环图c ( 1 1 ，4 ) 和c ( 1 3 ，4 ) 的交叉致 两个笛卡尔积图的交叉效。 个三部图的交叉数 关键词：交叉数；循环图；笛卡尔积图；三部图 分类号： 0 1 5 7 5 北京交通大学硕士学位论文 a b s t r a c t a b s t r a c t a b s t a c t ：t h ec r o s s i n gn u m b e ro fag r a p hi st h em i n i m u mn u m b e ro fp a i r - w i s ei n t e r s e c t i o no fe d g e si nad r a w i n go fi nt h ep l a n e ，d e n o t e dc r ( g ) i ti sw e l l k n o w nt h a tt h ec r o s s i n gn u m b e ro fag r a p hi sa t t a i n e do n l yi ng o o dd r a w i n g s o ft h eg r a p h w h i c ha r et h o s ed r a w i n g sw h e r e ：( 1 ) n ot w oe d g e si n t e r s e c te a c h o t h e rm o r et h a no n c e ( 2 ) n oe d g eh a sas e l f - i n t e r s e c t i o n ( 3 ) n ot w oa d j a c e n te d g e si n t e r s e c t ( 4 ) e a c hi n t e r s e c t i o no fe d g e si sac r o s s i n gr a t h e rt h a n t a n g e n t i a l c o m p u t i n gt h ec r o s s i n gn u m b e ro fag i v e ng r a p hh a sb e e np r o v e dt ob e n p - c o m p l e t e i ti sv e r yd i f f i c u l tt od e t e r m i n et h ec x a c tc r o s s i n gn u m b e ro fag i v e n g r a p hf o ri t sc o m p l i c i t y t h ec r o s s i n gn u m b e rp r o b l e mh a sb e e ns t u d i e df o rc o r n - p l e t eg r a p h ，c o m p l e t en p a r t i t eg r a p h ，c i r c u l a rg r a p h ，g e n e r a l i z e dp e t e r s e ng r a p h a n dc a r t e s i a ng r a p h ，t h ec r o s s i n gn u m b e xo ff e wf a m i l i e so fg r a p h sa r ek n o w n 8 0f a r ，m o s to fw h i c ha r ec a r t e s i a np r o d u c t so fs p e c i a lg r 印h 8 ，s u c ha sc a r t e s i a n p r o d u c t so fp a t h s ，c y c l e so rs t a r sw i t h ”s m a l l ”v e r t e xf a p h s t h e r ea r et w oc h a p t e r si nt h et h e s i s ： 。 t h ef i r s tc h a p t e ri n t r o d u c e st h eb a s i cd e f i n i t i o n ，a n ds o m ek n o w nr e s u l t 8 i n t h es e c o n dc h a p t e r ，w ew i l lp r e s e n ts o m en e wr e s u l t s ： t h ec r o s s i n gn u m b e ro ft w oc i r c u l a rg r 印h 8c ( i i ，4 ) a n dc ( 1 3 ，4 ) t h ec r o s s i n gn u m b e ro ft w oc a r t e s i a np r o d u c t s t h ec r o s s i n gn u m b e ro fat r i p a r t i t eg r a p h k e y w o r d s ：c r o s s i n gn u m b e r ；c i r c u l a rg r a p h ；c a r t e s i a ng r a p h ；t r i p a r t i t eg r a p h c l a s s n o ：0 1 5 7 5 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阕同意学校向国 家有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名导师签名 签字日期，年月 日 签字日期-年月日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 学位论文作者签名签字日期：年月 日 在本文即将结束的时候，我要特别向我的导师何卫力副教授表示最衷心的感 谢他无论是在科研上，还是在平时的生活中，都给了我无微不至的关怀与鼓励 当我在课程学习中遇到难点时。住总能以循循善诱的授课方式使我豁然开朗；当 我在科研上遇到困惑时，他给了我很多新的思路和方法，使我受益匪浅他严谨 的治学风格，广博的知识，精益求精的科研作风，敏锐的学术思想和忘我的工作 精神极大的影响并鞭策了我本论文是在何老师的精心指导和关怀下完成的无 论是在研究生课程学习过程中，还是在论文选题、研究、定稿的过程中，何老师 自始至终给了我大力的支持和无私的关怀，在此向何老师表示深深的感谢 感谢我同门的师姐师妹师兄师弟。三人行，必有我师”，共同的学习生活使 我收获多多 我还要感谢同窗两年多的各位同学我从他们身上学到了很多有益的知识和 学习的方法两年多的同窗之谊，离别之际，更显珍贵我为自己两年多来生活 在那种坦诚相待，互帮互助的氛围中感到莫大的荣幸! 最后，感谢各位专家，学者在百忙中审阅我的论文，并给出批评意见在完 成本论文、即将踏入工作岗位之时，我深深地感到：自己每一步的前进，都离不 开老师亲朋和同学的支持与教诲，在此表达我对他们最衷心的感谢l 赵琳 2 0 0 7 年1 1 月 于北京交通大学理学院 北京交通大学顼士学位论文第一章绪论 1 基本概念 第一章绪论 一个图g 是指个有序三元组( y ( g ) ，f ( g ) ，忱) ，其中v ( c ) 是非空的顶点 集，e ( v ) 是不与v ( c ) 相交的边集，而妒g 是关联函数它使g 的每条边对应 于g 的无序定点对( 不必相异) 若e 是一条边，而u 和u 是使得此( e ) = 的 顶点，则称e 连接u 和”；顶点u 和口称为e 的端点一个图称为简单图， 如果它既没有环也没有两条连杆连接同一对顶点图g 的一条途径( 或通道) 是 指一个有限非空序列w = r o e l 口l e 2 v 2 e 3 e k ，它的项交替地为顶点和边，使得 对1 i k ，g i 的端点是2 一l 和地，称是从如到v k 的一条途径；若途 径的边e i ，e 2 ，e k 互不相同，则w 称为迹；又若途径的顶点u o ，1 ) 1 ，一，地 互不相同，则称为路；称一条途径是闭的，如果它由正的长且起点和终点相 同；若一条闭迹的起点和内部顶点互不相同，则它称为圈含有n 个顶点的路记 为r ，含有个顶点的圈记为c ； 如果一个图能画在平面上使得它的边仅在端点相交，则称这个图为可嵌入平 面的，或称为甲面图。有时，我们必须将一个图画在乎面上，即使它不是一个可 平面图比如，布局在芯片上的电路就对应一个图的甲面作图由于线路交叉会 降低性能并引起潜在的问题，因此必须最小化交叉次数图g 的交叉数是将g 画在甲| 面上时交叉次数的最小值，记为o - ( g ) 其中画法满足c ( 1 ) 任何两条 边相交叉的边最多交叉一次；( 2 ) 边不能自身交叉( 3 ) 有相同端点的两条边 不交叉；( 4 ) 没有3 条边交叉于同一点称含最小交叉敦的画法为最优画法 一般而言，确定图的交叉数是一个完全n p 一问题，目前能确定交叉数的图很少 对交叉致的研究主要集中在对完全图，n 部图，广义p e t e r s e n 图，循环图，笛卡 尔积图的交叉数的计算上 每一对不同的顶点都有一条边相连的简单图称为完全图在同构意义下， 个顶点的完全图只有一个，记为亿 所谓偶图( 或二部图) 是指一个图，它的顶点集可以分解为两个( 非空) 子 集x 和y ，使得每条边都有一个端点在x 中，另一个端点在1 7 中；这样的一种 分类( x ，y ) 称为图的一个二分类完全偶图是具有二分类( x ，y ) 的简单偶图， 其中x 的每个顶点都与y 的每个顶点相连；若】x l = m 而l y l = n ，则这样的 图记为。n 都图和完全n 部图可类似定义称l ，1 为星图，记为岛一- 循环图g = c ( m ，f ) 是这样的图一它的顶点集是 咖，”1 ，一1 ，边集 是 h ，饥+ i ) ，m ，地“冲( o ，1 ，一，m 1 ) ) ，这里m ，l 都是正整数，且f 小 于m 2 ，同时下标是在模m 的意义下循环图是一种重要的图，其交叉数问题 多年来一直被人研究 广义p e t e r s e n 图g ( n ，m ) 是这样的图：它的顶点集是 伽，l ，牡”l ，v o ，0 1 ， 北京交通大学硕士学位论文 第一章绪论 ，一1 ) ，边集是 嘶饥，u i u i + 1 ，v i v i + 。l i o ，1 ，n 一1 ) ，这里n ，m 都是正 整数，且m 小于n 2 ，同时下标是在模n 的意义下 设g - 和g k 是两个点不交的图，它们的笛卡尔积g 1x g z 是这样的图：它的顶 点集是v ( a t x g 2 ) = y ( g i ) y ( g 2 ) ，边集是e ( g l g 2 ) = “( 毗，码) ，( u h ，“) ) i ( 锄= u h 且啮仇e ( g 2 ) ) 或( v j = 饥且u ；u h e ( g 1 ) ) ， 2 已知结果 1 2 1 关于完全图的交叉数的已知结果 d r w o o d a u ( 参考文献【2 】) 证明了关于完全图的交叉效如下结果 c r ( 巧) = i 1 p 。p - 21 j 【字j 【字j ，l p l o 1 2 2 关于n 部圈的交叉数的已知结果 d j k l e i t m a n 证明了m 6 时完全二部图尬。的交叉数，即有： e r ( j 。) = h 2 】f ( 仇一1 ) 2 1 n 2 1 ( n 2 ) 1 ，i ，m 6 ( 1 2 1 ) 关于完全三部图的交叉数的结果更少， k o u h e ia s a n o ( 参考文献【1 5 】) 证 明了以下结果： c r ( 硒3 m ) = z ( 4 ，n ) + k 2 】，c r ( k 2 蛳) = z ( 6 ，n ) + 其中z ( m ，n ) = f m 2 】【一1 ) 2 1 n 2 l ( n 2 ) 黄元秋证明了 c r ( k 1 4 。) = n ( n 一1 ) l 2 3 关于循环图的交叉数已知结果 关于循环图的交叉数的结果比完全图和n 部图多，循环图也是交叉数被研究 比较多的一类图，关于循环图的交叉数的结果( 参考文献【2 6 卜 2 9 】) 主要有 c r ( g ( 礼，3 ) ) = 【n 3 j + f lt n0 l 匠3 ( r28 ) c r ( g ，h 2 j ) ) = 1 m26 ) e r ( o ( n ，n 2 一1 ) ) = n 2 m 8 ) c r ( o ( 3 k ，e ) ) = k ( k 3 ) c r ( c ( 3 k + 1 ，) ) = k + 1 忙23 ) 北京交通大学硕士学位论文 第一章绪论 1 2 4 关于广义p e t e r s e n 围的交叉敷的已知结果 关于广义p e t e r s e n 图的交叉数的已知结果很少，杨元盛和他的学生对广义p e - t e r s e n 图的交叉数作了较为系统的研究( 参考文献1 2 5 】) ，计算出了p ( n ，女) 当n 1 6 时的全部交叉数，并给出了以下猜想； ( 1 ) ：c r ( p ( 4 h + 2 ，2 h ) ) = 2 h + 1 ，h 3 ( 2 ) ：c r ( p ( 4 h + 2 ，4 ) ) = 2 h + 2 ，h 23 ( 3 ) ：c r ( p ( 3 h ，3 ) ) = h ，h 4 ( 4 ) ：c r ( p ( 3 h + 1 ，3 ) ) = h + 3 ，h 3 ( 5 ) ：c r ( p ( 3 h + 2 ，3 ) ) = h + 2 ，h 23 任韩和他的学生利用去边的方式证明了广义p e t e r s e n 图g ( 2 m + 1 ，m ) 的交 叉数的下界是3 ，然后证明了它的交叉数就是3 ( 参考文献2 4 1 ) 1 2 5 关于笛卡尔积图的交叉数的已知结果 近年来对交叉数的研究主要集中在对笛卡尔积图的交叉数的探讨上，包括简 单图的特殊图与路，与星图，与圈，简单的特殊图之间的笛卡尔积图等，故关于笛 卡尔积图的交叉数的结果相对来说比较多m k l e s c 确定了所有4 阶以及部分5 阶连通图与路的笛卡尔积图的交叉数( 参考文献【9 】和【1 0 ) ，近年来研究人员 将结果推广到了6 阶图关于笛卡尔积图的交叉数的具体结果主要包括以下几个 ( 参考文献【1 1 】、【1 2 】、【1 3 】、f 1 8 】、【1 9 、【2 l 】- 2 4 】h c r ( 岛岛) = 3 ，h a r a r y e t a l 口( 岛c k ) = n ，r i n g e i s e n a n d b e i n e k e c r ( g 4 c 4 ) = 8 ，d e a n a n d r i c h t e r 口( c 4xg ) = 2 n ，口( k 4 g ) = 3 n ，b e i n e k e a n d r i n g e i s e n c r ( & r ) = 2 ( n 一2 ) ，c r ( 蜀i ) = 2 ( n 一1 ) ，k l e s c c r ( k 2 ，3 晶) = 2 n ，c r ( x r ) = 6 n ，k l e s c 口( b i r ) = 4 国一1 ，y t p e n g a n d y c y i e w c r ( k 3 3 p n ) = 7 n 一1 黄元秋 3 ! ! 星至重盔堂堡主兰丝丝塞笙三至羞量銮墨墼塑堂二生堡塑 第二章关于交叉数的进一步探讨 下面给出本文作者在阅读已有相关文献的基础上所得到新结果 1 循环图c ( 1 l ，4 ) 和c ( 1 3 ，4 ) 的交叉数 2 1 1 主要引理 首先有以下三个事实： 事实1 ：对于图g 的任意画法，c r ( g ) 2 ( g ) 事实2 ：h ( c ( m ，4 ) ) 24 ，m 1 0 证明：设h = h ( c ( m ，4 ) ) ，c + ( m ，4 ) 是c ( m ，4 ) 的含有2 m h 条边的可平面子 图，易见c ( m ，4 ) 是c ( m ，4 ) 的一个连通生成子图由欧拉公式，在c + ，4 ) 的 任意平面画法中，m 一( 2 m h ) + 圣= 2 ，所以有西= ( m - - 2 ) 一h 个面设9 为矿( m ，4 ) 的围长，由( m + 2 一h ) g 2 ( 2 m h ) 和g 4 ，我们可得出结论 事实3 ：由上图1 ，2 知c r ( c ( 1 l ，4 ) ) s5 ，c r ( g ( 1 3 ，4 ) ) 5 由上述事实我们可得出： 引理2 1 1 由事实1 ，2 ，3 知：4 ( c r ( c ( 1 l ，4 ) ) ) s5 ，4 ( c r ( c ( 1 3 ，4 ) ) ) 5 2 1 2 主要结果 在上述引理的基础上本文主要有以下结果： 定理2 1 2去掉循环图c ( 1 l ，4 ) 中任意4 条边后得到的子图都至少含有一 个5 圈 证明：设g = c ( 1 l ，4 ) ，将g 中顶点 仉j i = 0 ，1 ，1 0 简记为 i l i = 0 ，1 ，1 0 ) ，将g 的边子集局= “i 十1 l i = 1 ，2 ，l o 着蓝色，边子集e 2 = 托i + 4 l i = 1 ，2 ，t o 着红色，任取e ( a ) 中4 条边，设为s = e 1 ，e 2 ，e 3 ，e 4 ) ， 并设g = g s 情形1 ：s 中边全为红边，则肯定存在e = i ，i + 4 ) ( e ( a + ) ) ，那么c = ( ，i + 1 ，i + 2 ，i + 3 ，i + 4 g 情形2 ：s 中边全为蓝边，且e l ，e 2 ，e 3 ，e 4 在圈 o ，1 ，l o 上按顺时针方向 排列， 情形2 1 ：e l = i ，i + 1 ) ，e 2 = t + 1 ，i + 2 ，e 3 = a + 2 ，i + 3 ，若e 4 工j + x l j = i + 3 ，i + 4 ，i + 5 ，t + 6 ) ，贝0 圈c = j + 1 ，j + 2 ，j + 3 ，j + 4 ，j + 5 ) g 。； 若龟f j ，j + l l j = i + 7 ，i + 8 ，i + 9 ) ，则圈c = i + 3 ，i + 4 ，i + 5 ，i + 6 ，i + 7 ) g 情形2 2 ：e 1 = ( t ，i + 1 ) ，e 2 = “+ 1 ，i + 2 ， 情形2 2 1 ：e 3 = a + 3 ，i + 4 ) ，若e 4 “j ，j + 1 l j = i + 4 ，i + 5 ，i + 6 ) ，则 圈c = d + 1 ，j + 2 ，j + 3 ，j + 4 ，j + 5 ) g ；若e 4 d ，j + x l j = t + 7 ，i + 8 ， + 9 ， 则圈g = j 一1 ，j 一2 ，j 一3 ，j 一7 ) g ； 情形2 2 2 ：e 3 = f l + 4 ，i + 5 ) ，若e 4 j ，j + 1 l j = i + 5 ，i + 6 ) ，则 圈c = j + 1 ，j + 2 ，j + 3 ，j + 4 ，j + 5 ) g ；若e 4 = f + 7 ，i + 8 ) ，则圈c = 0 + 8 ，i + 9 ，i + 1 0 ，i ，i + 4 g ；若e 4 “j ，j + x l j = i + 8 ，i + 9 ) ，则 圈c = u ，j 一1 ，j 一2 ，j 一3 ，j 一7 ) g ； 情形2 2 3 ：e 3 = t + 5 ，i + 6 ) ，e 4 j ，j + x l j = i + 6 ，i + 7 ，i + 8 ，i + 9 ，则 圈c = i + 2 ，i + 3 ，i + 4 ，i + 5 ，t + 9 ) g 。； 情形2 2 4 ：e 3 “j ，j + 1 ) d = i 十6 ，i + 7 ，i + 8 ，i + 9 ) ，无论e 4 取哪条边， 都有圈c = i + 2 ，i + 3 ，i + 4 ，i + 5 ，i + 6 ) g ； 情形2 3 ：e 1 = i ，i + 1 ) ，e 2 = a + 2 ，i + 3 ) ， 情形2 3 1 ：e 3 = t + 4 ，i + 5 ，若e 4 = t + 6 ，i + 7 ) ，则圈c = 0 + 7 ，i + 8 ，i + 9 ，t + 1 0 ， ，g + ；若e 4 = + 7 ，i + 8 ) ，则圈c = t + 8 ，i + 9 ，i + 1 0 ，i ，t + 4 ) g ； 若e 4 = i + 8 ，i + 9 ，则圈c = 0 + 8 ，i + 1 ，i + 5 ，i + 6 ，i + 7 ) g ； 情形2 3 2 ：e 3 = t + 5 ，i + 6 ) ，e 4 d ，j + x l j = i + 7 ，i + 8 ) ，则圈c = “+ 9 ，i + 1 0 ，i + 3 ，i + 4 ，i + 5 ) g ； 情形2 3 3 ：e 3 j ，j + 1 ) l j = i + 6 ，i + 7 ) ，无论e 4 取哪条边，都有圈c = 矗+ 3 ，i + 4 ，i + 5 ，i + 6 ，l + l o g ； 情形3 ：s 中1 条红边，3 条蓝边，且设3 条蓝边e 1 ，e 2 ，e 3 在圈 o ，1 ，x o 上按顺时针方向排列，设e l = ( i ，t + 1 ) ，e 2 = 工j + 1 ) ，e 3 = ，k + 1 ) ，且按 顺时针方向设e l 与e 2 之问有z 1 条边。e 2 与e 3 之问有z 2 条边，e 3 与e l 之 间有z 3 条边，若 4 ，n = 1 ，2 ，3 ，则 z 1 ，z 2 ，。3 ) 中至少有两个等于3 ，不失 一般性，设z 1 = z 2 = 3 ，则圈c = a + 1 ，i + 2 ，i + 3 ，i + 4 ，i + 8 ) 与c = 5 北京交通大学硕士学位论文第二章关于交叉数的进一步探讨 d + 1 ，j + 2 , 3 + 3 ，j + 4 ，j + 8 ) 至少有一个属于g ；若 z 1 ，z 2 ，) 中存在不妨 设：r i 4 ，则豳g = t + 1 ，i + 2 ，+ 3 ，i + 4 ，抖5 ) 与c = 0 + i ，i + 2 ，i + 3 ，i + 4 ，计8 中至少有一个属于g ； 情形4 ：s 中3 条红边，1 条蓝边，设蓝边为e l = 托i4 - 1 ) ，则圈集“工j + l ，j + 2 ，j + 3 ，j + 4 l j = i + 2 ，i + 3 i + 4 ，i + 5 ) 中至少有一个属于g ； 情形5 ：s 中2 条红边，2 条蓝边，且设2 条蓝边e 1 ，e 2 在圈 0 ，1 ，l o 上按 顺时针方向排列，设e l = “i + 1 ) ，e 2 = d ，j + 1 ，e l 在圈 o ，1 ，l o 上经过z l 条边到。2 ，。2 又经过z 2 条边到e 1 ，则z 1 与z 2 至少有一个，不妨设。125 ，则圈 集 i + 1 ，i + 2 ，i + 3 i + 4 ， + 5 ) ，( i + 2 ，i + 3 ，i + 4 ，i + 5 ，i + 6 ) ，( i + l ，i + 2 ，i + 3 ，i + 4 ，t + 8 ) 中至少有一个属于口，命厨得证 定理2 1 3去掉循环图c ( 1 3 ，4 ) 中任意4 条边后得到的子图g + 满足下列 条件之一；( 1 ) 含有5 圈，( 2 ) 含有3 的剖分图，( 3 ) 是可平面图；且当口 含有5 固时，g 为非可平面图 证明：设g c ( 1 3 ，4 ) ，将g 中顶点 让k = 0 ，1 ，1 3 ) 简记为 i l i = 0 ，1 ，1 3 ，将g 的边子集& = “i ，z + l 批= 1 ，2 ，a 3 着蓝色，边子集b = 0 ，件4 ) i f = 1 ，2 ，l a 着红色，任取e ( a ) 中4 条边，设为s = e l ，e 2 ，3 ，e 4 ) ， 并设g + = g s 情形1 ：s 中边全为红边，则肯定存在e = “，i + 4 ) ( s ( c ) ) ，那么c = ，i + 1 ，i + 2 ，i + 3 ，i + 4 g 情形2 ：s 中边全为蓝边。且e l ，e 2 ，e 3 ，e 4 在圈 o ，1 ，l o 上按顺时针方向 排列， 情形2 1 ：e 1 = ( 1 ，i + 1 ) ，e 2 = 0 + 1 ，i + 2 ) ，e 3 = i + 2 ，i + 3 ) ，若e 4 d ，j + 1 l j = i + 3 ，i + 4 ，i + 5 ，i + 6 ，i + 7 ，i + 8 ) ，则圈c = d + 1 ，j + 2 ，j + 3 ，j + 4 ，j + 5 ) g ； 若e 4 d ，j + l l j = i + 9 ，i + 1 0 ，i + 1 1 ，则圈c = i + 3 ，i + 4 ，i + 5 ，i + 6 ，t + 7 ) g i 情形2 2 ：e l = t ，i + 1 ) ，e 2 = 0 + l ，t + 2 ， 情形2 2 1 ：e 3 = i + 3 ，i + 4 ) ，若e 4 “_ j + l l j = i + 4 ，i + 5 ，i + 6 ，i + 7 ，f + 8 ) ， 则圈c = d + 1 ，+ 2 ，j + 3 ，j + 4 ，j + 5 ) g ；若e 4 j j + x l j = i + 9 ，i + l o ，i + 1 1 ，则圈c = 工j 一1 ，j 一2 ，j 一3 ，j 一4 ) g ； 情形2 2 2 ：e 3 = t + 4 ，t + 5 ) ，若e 4 o ，j + 1 l j = i + 5 ，i + 6 ，i + 7 ，i + 8 ，则 圈c = j + l ，j + 2 ，j + 3 ，j + 4 ，j + 5 ) g ；若e 4 “ j + l l j = i + 9 ，i + 1 0 ，i + 1 1 ， 则圈c = i + 5 ，i + 6 ，i + 7 ，i + 8 ，i + 9 g ； 情形2 2 。3 ：e a ；矗+ 5 ，l + 6 ，若缸 幺j + l l j = i + 6 ，i + 7 ，i + 8 ) ，则圈c = d + 1 ，j + 2 ，j + 3 ，j + 4 ，j + 5 ) g ；若e 4 = i + 9 ，i + l o ，则下图中，3 属于g ； 若e 4 = i + 1 0 ，i + 1 1 ，u i + l x ，件1 2 ) ，贝4 圈c = i + 6 ，i + 7 ，i + 8 ，i + 9 ，t + 1 0 ) g ； 6 北京交通大学硬士学位论文第二章差于变更教的堂二生堡讨 圈22 ： 情形2 2 4 ：e 3 t j ，j + 1 l j = i + 6 ，f + 7 ，i + 8 ，i + 9 ，i + 1 0 ，i + 1 1 ，无论e 4 取哪条边，都有圈c = a + 2 ，i + 3 ，i + 4 ，i + 5 ，i + 6 ) g ； 情形2 3 ：e l = i ，i + 1 ，e 2 = t + 2 ，i + 3 ) ， 情形2 3 1 ：e 3 = 0 + 4 ，i + 5 ，着白【d ，j + l b = i + 6 ，i + 7 ，i + 8 ，则 圈c = d + 1 ，j + 2 ，j + 3 ，j + 4 ，j + 5 ) g ；若e 4 “j ，j + t l j = i + 9 ，i + 1 0 ，件1 1 ) ， 则圈c = i + 5 ，i + 6 ，i + 7 ，i + 8 ，i + 9 g ； 情形2 3 2 ：e 3 = + 5 ，i + 6 ) ，若e 4 = 0 + 7 ，i + 8 ) u i + 8 ，i + 9 ) ，则 圈c = i + 9 ，i + 1 0 ，i + 1 1 ，i + 1 0 ，磅g ；若e 4 = t t + 9 ，i + 1 0 ) ，则下面 第一个图中蚝，3 属于g ；若e 4 = f + 1 0 ，i + 1 1 ) u i + 1 1 ，i + 1 2 ，则圈c = 0 + 6 ，i + 7 ，i + 8 ，i + 9 ， + l o g l ； 情形2 3 3 ：e 3 = + 6 ，f + 7 ) ，若e 4 = d + 8 ， + 9 ，则圈c = 0 + 9 ，i + 1 0 ，i + 1 1 ，i + 1 2 ，i g ；若e 4 = t + 9 ，i + x o u i + 1 0 ， + 1 1 ，则下面第二个图中k 3 ，3 属于g ；若e 4 = 0 + 1 1 ，i + 1 2 ，贝0 圈c = t + 7 ，i + 8 ，i + 9 ，i + l o ，i + 1 1 ) g ； 圈2 3 ： 情形2 3 4 ：e 3 “j ，j + a l j = i + 7 ，i + 8 ，i + 9 ，无论e 4 取哪条边。都有 圈c = 0 + 3 ，i + 4 ，i + 5 ，i + 6 ，i + 7 ，g i 情形2 4 ：e l = i ，i + 1 ) ，e 2 = z + 3 ，i + 4 ) ，e 3 = t + 6 ，i + 7 ) ，若e 4 = 0 + 9 ，i + l o ，则下面第个图中，3 属于g ；若e 4 = t + 1 0 ，i + 1 1 ，则下面 第二个图中中确3 属于g ； 情形3 ：s 中1 条红边，3 条蓝边，且设这条红边为e 4 = f ，i + 4 ) ， 情形3 1 ： i ，i + 1 ，囊+ 1 ，i + 2 ，a + 2 ，+ 3 ， i + 3 ，i + 4 ，中有3 条边属 于s ，则c = z + 4 ，i + 5 ，i + 6 ，i + 7 ，i + 8 ) g ； 情形3 2 ：“t ，t + 1 ) ，( i + 1 ，i + 2 ) ， i + 2 ，i + 3 】，( i + 3 ，t + 4 ) ) 中有2 条边属 7 北京交通大学硬士学位论文第二章关于交叉歙的进一步探讨 田2 4 ： 于s ，贝0 c = 0 + 4 ，i + 5 ，i + 6 ，i + 7 ，i + 8 ) 与c = ( i + 8 ，l + 9 ， + l o ，t + 1 1 ，i + 1 2 至少有一个属于g ； 情形3 3 ：“i ，i + 1 ， i + 1 ，i + 2 ， i + 2 ，i + 3 ) ， i + 3 ，i + 4 ) ) 中有1 条边属 于s ，不是一般性，设 i ，i + 1 ) 属于s ，则 i + 1 ，i + 2 ，i + 3 ，i + 4 ，i + 5 ) ， f + 5 ，i + 6 ，i + 7 ，i + 8 ，i + 9 ) ，0 + 9 ，i + 1 0 ，i + 1 1 ，i + 1 2 ，i 中至少有一个属于g ； 情形3 4 ：t “i + 1 ) ，a + l ，i + 2 ) ， t + 2 ，i + 3 ，0 十3 ，t + 4 ) 中没有边属 于s ， 情形3 4 1 ： l ，i 一1 ) ， l + 4 ，i + 5 都属于s ，若e 3 t 一1 ，i 一2 ) ， i 一 2 ，i 一3 ) ，( i 一3 ，i 一4 ，贝0c = 0 + 5 ，i + 6 ， + 7 ，i + 8 ，i + 9 ) g ，若e 3 “f + 5 ，i + 6 ) ， t + 6 ，t + 7 ) ，( f + 7 ， + 8 ) ) ，则c = 件8 ，i + 9 ，i + 1 0 ，i + 1 1 ，i + a 2 g + ， 若e 3 = i + 8 ，i + 9 ) ，则g ，为如下可平面图； 图2 5 ： 情形3 4 2 ：“e ，t 1 ) ，0 + 4 ，i + 5 ) 中至少有一个不属于s ，不失一般性， 设f i ，i 1 ) 岳s ，则c = i 一1 ，i ，i + l ，i + 2 ，i + 3 ) g ； 情形4 ：s 中3 条红边，1 条蓝边，不妨设这条蓝边为 i , i + 1 ) ，则 t i + 1 ， + 2 ，i + 3 i + 4 ，i + 5 ) ， l + 2 ，i + 3 ，i + 4 ，i + 5 ，。+ 6 ) ， i + 3 ，t + 4 ，i + 5 ，i + 6 ，i + 7 ) ，0 + 4 ，i + 5 ，i + 6 ，i + 7 ，i + 8 中至少有一个属于g ； 8 北京交通大学磺士学位论文第二章关于交叉敬的进一步探讨 情形5 ：s 中2 条红边，2 条蓝边，且设2 条蓝边e l ，e 2 在圈 o ，1 ，1 3 上按 顺时针方向排列，设e 1 = “i + 1 ) ，e z = j ，j + 1 ) ，e l 在圈 o ，1 ，l a 上经过z l 条边到e 2 。2 又经过z 2 条边到e l ，则z l 与x 2 至少有个不妨设z 126 ，则豳 集 ；+ 1 i + 2 ，i + 3 ，i + 4 ，i + 5 ，扛十2 ，i + 3 ，i + 4 ，i + 5 ， + 6 ， + 3 ，i + 4 ，i + 5 ，i + 6 ，2 + 7 中至少有一个属于g ； 且当口含有5 圈时，假设为可平面图，则根据欧拉公式p g + r = 2 得r = 2 + q p = 2 + 2 2 一1 3 = 1 1 ，即口的甲面画法中有1 1 个面，故 有4 4 = 4 1 1 = 4 r 一 r 叨 北京交通大学硕士学位论文第二章关于交叉数的进一步探讨 ：勤 旬x r 田2 1 1 ： ( i ) 妒l 毋- 1 ( 毋( y ) ) 和西l e 是一一映射，其中e 是一条边 ( i i ) 对于砰内的任意一点p ，妒1 p ) 至多包含两个点 ( n i ) 对于两条不同的边e i 和e j ，( 岛) n ( 勺) 包含至多一个点 对于两条相邻的边白和勺，我们有咖( 由) r 3 庐( 白) = 0 ，其中a 为e e 的 内部点设a 和b 为e 的两个子集，我们把 曲( j ) n ( 6 ) i a a ，b 日) 中点的 个数记为c r , ( a ，b ) 特殊的，c r ( a ，a ) 记为c r ( a ) 在图g 中，设a 是顶点集合y 或者边集合e 的非空子集，则由j 4 诱导生 成的子图记为( a ) ，与点u 相邻的边的集合记为e ( v ) 点集划分为( x ，y ，z ) 边集为e 的完全三部图记为硒。，其中x = ( z 1 ，丑) y = l ，) ，z = 。) ；( x u y ) ，( y u z ) ( x u z ) 的边集分 别记为e w ，e i z 和e k z 显然有以下结论 【, 2 c r ( aub ) = c r ( a ) + c r , ( b ) + c r , ( a ，b ) c r a a ，b u c ) = c r ( a ，b ) + c r ( a ，c ) ( 2 3 1 ) 其中a ，b ，c 为e 的互不相交的子集 定理2 3 1c r ( 扔 。) = z ( 6 ，n ) + 2 n 证明，考虑到平面上的一个好的映射有以下性质， ( i ) 妒( z - ) = ( 0 ，2 ) 和妒( z 2 ) = ( 0 ，一2 ) ( i i ) 咖( 1 ) = ( 0 ，1 ) ，毋( 耽) = ( 0 ，一1 ) ，( 蛐) = ( 0 ，3 ) 和( z “) = ( 0 ，一3 ) ( i i i ) ( 毛) = o ，0 ) ，( 1sf ) ；( ) = ( - i + 一，0 ) ，7 , t ts 仃；其中= 1 6 北京交通大学斫士学位论文 第二章关于交叉散的进一步探讨 ( 删除了庐( z l y 4 ) ，( z 1 z ) ，西( z 2 y 1 ) 和妒( 。2 蛐) ，边的像是一条直线段 ( v ) 砂( z l y 4 ) 连接毋扛1 ) 和西( 舰) ，且与除曲( 加蔬) ，1 i 以外的边不相 交；毋( z 1 址) 连接咖( z 1 ) 和妒( 址) ，且与除( 玑乏) ，1 is 以外的边不相交； 妒( x 2 m ) 连接( z 2 ) 和妒( p 1 ) 。且与除( 抛毛) ，i n 以外的边不相交；( z 2 舶) 连接( 却) 和妒( 蜘) ，且与除驴( 玑) ，n ，isn 以外的边不相交 当n = 5 时，如图2 1 2 所示 圉2 1 2 ： 则有c r 6 ( e ) = z ( 6 ，n ) + 2 n ，所以我们有 口( 鲍j ) sz ( 6 ，”) + 2 n 下面我们对n 进行数学归纳，证明c r ( 4 。) 2z ( 6 ，n ) + 2 n 因为z ( 6 ，1 ) 十2 = 2 且配，4 1 包含 4 ，3