《关于图的交叉数》由会员分享，可在线阅读，更多相关《关于图的交叉数（27页珍藏版）》请在金锄头文库上搜索。
1、北京交通大学硕士学位论文关于图的交叉数姓名：赵琳申请学位级别：硕士专业：运筹学与控制论指导教师：何卫力20071101北京交通大学硕士学位论文A B s T R A C TA B S T R A C TA 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
2、r ( G ) I ti sw e l lk 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 so 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 ho t h e rm o r et h a no n c e ( 2 ) n oe d g eh a sas
3、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 nt 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 eN P - c
4、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 ng 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 ，
5、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 n8 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
6、 i a nP 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 nt h es e c o n dc h a p t
7、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
8、：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 hC L A S S N o ：0 1 5 7 5学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阕同意学校向国家有关部门或机构送交论文的复印件和磁盘( 保密的学位论文在解密后适用本授权说明)学位论文作者签名导师签名签
9、字日期，年月日签字日期-年月日独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。学位论文作者签名签字日期：年月日在本文即将结束的时候，我要特别向我的导师何卫力副教授表示最衷心的感谢他无论是在科研上，还是在平时的生活中，都给了我无微不至的关怀与鼓励当我在课程学习中遇到难点时。住总能以循循善诱的授课方式使我豁然开朗；当我在科研上遇到困
10、惑时，他给了我很多新的思路和方法，使我受益匪浅他严谨的治学风格，广博的知识，精益求精的科研作风，敏锐的学术思想和忘我的工作精神极大的影响并鞭策了我本论文是在何老师的精心指导和关怀下完成的无论是在研究生课程学习过程中，还是在论文选题、研究、定稿的过程中，何老师自始至终给了我大力的支持和无私的关怀，在此向何老师表示深深的感谢感谢我同门的师姐师妹师兄师弟。三人行，必有我师”，共同的学习生活使我收获多多我还要感谢同窗两年多的各位同学我从他们身上学到了很多有益的知识和学习的方法两年多的同窗之谊，离别之际，更显珍贵我为自己两年多来生活在那种坦诚相待，互帮互助的氛围中感到莫大的荣幸!最后，感谢各位专家，学者
11、在百忙中审阅我的论文，并给出批评意见在完成本论文、即将踏入工作岗位之时，我深深地感到：自己每一步的前进，都离不开老师亲朋和同学的支持与教诲，在此表达我对他们最衷心的感谢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
12、 和口称为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 ；如果一个图能画在平面上使
13、得它的边仅在端点相交，则称这个图为可嵌入平面的，或称为甲面图。有时，我们必须将一个图画在乎面上，即使它不是一个可平面图比如，布局在芯片上的电路就对应一个图的甲面作图由于线路交叉会 降低性能并引起潜在的问题，因此必须最小化交叉次数图G 的交叉数是将G画在甲| 面上时交叉次数的最小值，记为o - ( G ) 其中画法满足c ( 1 ) 任何两条边相交叉的边最多交叉一次；( 2 ) 边不能自身交叉( 3 ) 有相同端点的两条边不交叉；( 4 ) 没有3 条边交叉于同一点称含最小交叉敦的画法为最优画法一般而言，确定图的交叉数是一个完全N P 一问题，目前能确定交叉数的图很少对交叉致的研究主要集中在对完
14、全图，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 为星图，记为岛一-
15、 循环图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 小于
16、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 一6+n “Q“ m 一R叨北京交通大学硕士学位论文第二章关于交叉数的进一步探讨：勤旬x R田2 1 1 ：( i ) 妒l 毋- 1 ( 毋(
