（基础数学专业论文）线图与若干典型图类的交叉数研究.pdf

线图与若干典型图类的交叉数研究 摘要 图的交叉数是近代图论中发展起来的一个重要概念，自从上个世纪五十 年代初匈牙利数学家p a u ln r 缸根据其在一个砖厂碰到的实际难题( ，i 、u r 缸s b r i c kf a c t o r yp r o b l e m ) ，从而提出了交叉数的概念以来，图的交叉数逐渐成为国 际上一个非常活跃的分支，使得很多图论专家对这方面进行了深入研究 研究图的交叉数不仅具有重要理论意义，而且有较强的现实意义，如超大 规模集成电路v l s t 中的圈布局问题、电子线路板设计中的布线问题等1 9 8 3 年计算机科学家c a r e y 和j o h n s o n 证明了确定图的交叉数是n p 一完全问题， 由于其难度，目前只知道一些特殊图类的交叉数，如完全图，完全2 一部图， 完全3 一部图，圈与圈以及路与点数较少的图的笛卡尔积图，循环图，p e t e r s e n 图以及线图等关于非平面图，k u l l i 与b e i n e k e 等在1 9 7 9 年给出了使得它的 线图的交叉数为1 的条件； j e n d r o l 7 与k l 西芒于2 0 0 1 年研究了平面图的线图 的交叉数为1 的条件关于完全2 一部图目前只能确定当m 6 时， z a r a n k i e w i c z 猜想为真，而确定完全图k 。的交叉数目前也是一个公开问题 上世纪八十年代，a s a n o 确定了完全3 一部图k l 3 n 和恐1 3 i n 的交叉数此后， 关于完全3 一部图一直没有新结果 本文在第一章较为详细地介绍了目前图的交叉数研究的历史与现状，并 简要介绍一些与本文有关的交叉数的概念 在第二章，着重研究图及其线图的交叉数，给出了图与其线图的交叉数的 有关性质，并得到了一个图与其线图的交叉数为都为忌的充分必要条件： 设g 为图， c r ( g ) = 七( 忌1 ) ，其线图为l ( g ) 若凹( l ( g ) ) = 忌，则当且仅 当下列条件成立： ( 1 ) ( g ) 4 ，且g 中每个4 度点都是割点； ( 2 ) 存在g 的一个恰有后个交叉数的最优画法使得每条交叉的边关联g 中的一个2 度点 该结果实质性地推广了s t a n i s l a vj e n d r o l 7 和m a r i a nk 1 醛芒的关于非平面图 和它的线图的交叉数都是1 结果 博士学位论文 然后在第三章、第四章以及第五章中，与已有文献中使用的方法不同，用 “局部点度修改法”，并结合组合方法和归纳原理，研究了完全3 一部图甄4 几， 鲍，6 ，n ，甄，7 k ，8 ，n 和恐，4 ，仡的交叉数问题，分别确定它们各自的交叉数： 1 c r ( k 1 ，4 ，仡) = 礼( 仡一1 ) 2 若z a r a n k i e w i c z 猜想对m = 7 的情形成立，则有 凹( _ = 9 引l 孚j + 6 卧 3 若z a r a n k i e w i c z 猜想对m = 8 的情形成立，则有 州扣1 2 引【孚j + 9 斟 4 若z a r a n k i e w i c z 猜想对m 9 的情形成立，则有 凹( 扣1 6 引l 孚j + 1 2 斟 5 设g 是完全3 一部图鲍，4 则凹( g ) = z ( 6 ，礼) + 2 n 上述研究结果充实和发展了图的交叉数的研究成果，推广了k l e s c 关于星 与5 阶图的积图的交叉数结果，并提供了新的研究图的交叉数的方法 本文最后简要介绍了作者今后研究的方向，同时指出了一些亟待解决的 问题 关键词：图；线图；交叉数；平面图；非平面图；画法 ， _ 一 f 线图与若干典型图类的交叉数研究 i i i a b s t r a c t t h ec r o s s i n gn u m b e ro fg r a p h si sav e r yi m p o r t a n tc o n c e p ti nm o r d e ng r a p h t h e o r y s c i n c ee a r l yi nt h e1 9 5 0 s ) t h eh u n g a r i a nm a t h e m a t i c i a np a u l7 i 、u r 螽nw h o s u g g e s tt h ea u c t u a lp r o b l e m ，w h i c hn a m e d“n r 缸sb r i c kf a c t o r yp r o b l e m ” b y z a r a n k i e w i c z ，g r a d u a l l yb e i n gav e r ya c t i v e 矗e l di nt h e 、o r l d i ta t t r a u c t sm a n y g r a p ht h e o r ye x p e r tt o w o r k t h er e s e a r c h 、o r ki nt h ec r o s s i n gr 【u r i f b e ro fg r a p hi sn o ta ，ni m p o r t a n ti n t h e o r y ，b u ta l s om o r ep r a c t i c a l ，e g t h ec i r c u i tp l a y o u tp r o b l e m si nv l s ia n dp l a y o u t p r o b l e m si ne l e c t r i cc i r c u i td e s i g n ，e t c i n1 9 8 3 ，c a r e ya n dj o h n s o np r o v e dt h a t i ng e n e r a ld e t e r m i n i n gt h ec r o s s i n gn u 1 b e ro fg r 印h si sn p c o m p l e t e b e c a u s eo f i t sd i 伍c u l t y ，a tp r e s e n tt h ec l a s s e so fg r 印h sw h o s ec r o s s i n gn u 1 b e r sh a eb e e n d e t e r m i n e da r ev 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 g i m i l l _ b e r sa r ek n a w n f b re x a m p l e ，t h e s ei n c l u d et h ec o m p l e t eg r 印hj 厶f o rs m a l ln ， t h ec o m p l e t eb i p a r t i t eg r 印h nf o rs m a u 竹la n da 1 1 yn ，t h ec o m p l e t et r i p a r t i t e 铲a p hk 1 ，m ，竹，s o m ec a r t e s i a np r o d u c to ft w oc i r c u i t s ，o fp a t ha n ds t a u r s ，c e r t a i n p e t e r s e ng r a p h s ，l i n eg r 印h s i fgb ean o n p l a n a r ，k u l l ia n db e i n e k ep r o v e dt h e n e c e s s a r yc o n d i t i o nf o rw h i c hl i n eg r 印hh a sc r o s s i n gn u l b e r1i n1 9 7 9 ，a n d ，j e n d r o l 7 a n dk l e 莒芒h a ep r o 、r e dt h en e c e s s a r ya n ds u 伍c i e n tc o n d i t i o n sf o rw h i c hb o t ht h el i n e 口印ha n di t sp r i m a lp l a n a rg r 印hh a v et h es 锄ec r o s s i n gn u m b e r1 t h ec r o s s i n g n u i i 【b e ro ft h ec o m p l e t eb i p a r t i t eg r a p h s 卵( ，n ) ，i st r u ef o rt h ec a l s em 6 i ti sa no p e np r o b l e mt od e t e r m i n et h ec r o s s i n gn u m b e r so ft h eg r a p h 矗麓i nt h e 1 9 8 0 s ，a s a n oh a v sp r o v e dt h ec r o s s i n gn u m b e r so fk 1 ，3 ，他a n d 尬，3 ，几js i n c et h e nn o n e wr e s u l t sh a v eb e e ng o t f i r s t l y ，陀i n t r o d u c et h eh i s t o r i c a lb a c k g r o u n da n dr e c e n tw d r ko nt h ec r o s s i n g r m i n _ b e r so ft h eg r a p h si ns o m es u r f a c e ja n ds o m er e l a t i o n a lc o n c e p t so fc r o s s i n g n u m b e r s s e c o n d l y ，i nc h a p t e r2 ，w eh a ep r e s e n t e ds o m ep r o p e r t i e so f t h el i n eg r 印ha n d i t sp r i m mp l a n a r 伊印h ，a n dp r o v e dt h en e c e s s a r ya n ds u m c i e i l tc o n d i t i o n sf o rw h i c h b o t ht h el i n eg r a p ha n di t sp r i m a lg r 印hh a v et h es a m ec r o s s i n gn u i n b e r 尼( 凫1 ) ： l e 芒g6 ea9 唧危t d i 亡危芒 ec 丁 d s s i n 夕n u z 6 e r 忌1 ，n n dl ( g ) 6 ei 亡sf i n e9 7 1 哆p 危 ，i-i l-iiev ii-i眵r r i v 博士学位论文 j 陬e 他c r ( l ( g ) ) = 后矿。咒do 礼f 可t 厂 e 如f f d 叫i 7 姆c d 几d i 扰o n s 危d f d ? ( 1 ) ( g ) 4 ，n n de e 阿 e n e z 吖d 叼他e4i soc u 一u e n e zd ，g j ( 2 ) z h e 7 ee 疵s t sod 7 u 叫i n 9o ，gi 礼沈ep f 口n et 盯i t 危e z n c t f 剪忌c r d s s i 7 姆st n 伽忍i c 危 e o c c 7 d 5 s e de d 9 ei si 礼c i d e 礼t 叫i t 危ou e n e z 吖d 弓9 r e2 t h er e s u l te x t e n d se s s e n t i 出1 yt 1 1 ew o r ko fs t a n i s l 打j e n d r o l 7 狐dm 缸i a l lk l e 吾芒 w h i c ht h en e c e s s a r ya n ds u m c i e n tc o n d i t i o n sf o rw h i c hb o t ht h el i n eg r 印ha j l di t s p r i m a jg r a p hh a j v et h es a m ec r o s s i n gn u i n b e r1 i nc h 印t e r s3 ，4a n d5 ，w bu s et h e“1 0 c a l lv e r t e x sd e g r e em o d m e d ” a n d s o m ec o m b i n a t o r ym e h t o d s ，w h i c hd i 髓rt ot h ek n o w nm e t h o d s ，t od i s c u s st h eg r 印h s k 1 ，4 ，n ，k 1 ，6 ，n ，k 1 ，7 ，几，k 1 ，8 ，礼a n d 鲍，4 ，nw h i c hc r o s s i n gi m m b e r sa r ef o l l o w i n g ： 1 c r ( k 1 ，4 ，礼) = 礼( 礼一1 ) 2 i fz a r a n k i e w i c z sc o n j e c t u r ei st r u ef o rm = 7 ，t h e n 凹( 扣9 引【孚j + 6 卧 3 i fz a r a n k i e w i c z sc o n j e c t u r ei st r u ef o rm = 8 ，t h e n 凹( 扣1 2 引l 孚j + 9 卧 4 i fz a r a n k i e w i c z sc o n j e c t u r ei st r u ef o rm 9 ，t h e n c r ( 扣1 6 引【孚j + ，2 斟 5 l e tgb eac o m p l e t et r i p a t t i t eg r a p h 鲍，4 ，n ，t h e nc r ( g ) = z ( 6 ，礼) + 2 n f i n a u y ，r ei n t r u d u c et h ed i r e c t i o n so fo u rr e s e a r c h 、7 l ，o r ka n dp u tf o r w a r ds o m e p r o b l e m sw h i c hw i l lb es 0 1 v e dr e c e n t l y k e yw b r d s ：g r a p h s ；l i n eg r a p h s ； c r o s s i n g n u i n b e r s ；p l a n a tg r a p h s ；n o n p l a n a r g r 印h ；d r a w i n g j111 ，jlj1 i_1l，；i-fl l，1 j ji】1，_1 l，e l_ilqi ji d、，ijl、-_j、 博士学位论文 1 第一章绪论 1 1交叉数的历史背景与研究现状 图论是一门应用十分广泛且其内容非常丰富的数学分支，起源于1 7 3 6 年 欧拉解决哥尼斯城堡七桥问题 1 3 】图的交叉数是近代图论中发展起来的一 个重要概念，自从上个世纪五十年代初匈牙利数学家p a u lr i 、u r 缸根据其在一 个砖厂碰到的实际难题( r i 、u r 缸sb r i c kf a c t o r yp r o b l e m ) ( 见文献 2 ，4 ，5 】) ，从而提 出了交叉数的概念以来，图的交叉数逐渐成为国际上一个非常活跃的分支， 使得很多图论专家对这方面进行了深入研究 1 9 7 7 年匈牙利数学家p a u lt u r 缸在图论杂志创刊时撰文“an o t eo f w b l c o m e ”【6 】，提到他于2 0 世纪4 0 年代在布达佩斯工作时提出的“n r 缸s b r i c kf a c t o r yp r o b l e m ”即平面上图的交叉数问题他写道： “i nj u l y1 9 4 4t h ed a n g e ro fd e p o r t a t i o nw a sr e a li ab u d a p e s t ，舡l dar e a l i t y o u t s i d eb u d 印e s t w 色、o r k e dn e a rb u d 印e s ti nab r i c kf a c t o r y t h e r ea r es o m e k i l n sw h e r et h eb r i c k k sw e r em a d ea n ds o m eo p e ns t o r a g ey a r d sw h e r et h eb r i c k s 、e r es t o r e d a ut h ek i l n s 、e r ec o n n e c t e db yr a i lw i t h 出lt h es t o r a g ey a u r d s t h e b r i c k sw e r ec a r r i e do ns m a l lw h e e l e dt r u c k st ot h es t o r a g ey 甜d sa l lw eh a dt od o w a st op u tt h ek i l n so nt h et r u c k sa tt h ek i l n s ，p u s ht h et r u c k st ot h es t o r a g ey a l r d s ， a n du n l o a dt h e mt h e r e w 色h a dar e a s o n a l b l ep i e c er a t ef o rt h et r u c k s ，a n dt h ew o r k i t s e l fw a sn o td i m c u l t ；t h et r o u b l ew a so n l ya tt h ec r o s s i n g s t h et r u c k sg e n e r a l l y j u m p e dt h er a i l st h e r e ，a n dt h eb r i c k sf e uo u to ft h e m ；i ns h o r tt h i sc a u s e dal o to f t r o u b l ea n dl o s so ft i m ew h i c hw a sr a t h e rp r e c i o u st oa l lo fu s w 宅w e r ea 1 1s w e a t i n g a n dc u r s i n ga ts u c ho c c a s i o n s ，it o o ； b u tn 0 1 e n s v o l e n st h ei d e ao c c u r r e dt om e t h a tt h i sl o s s o ft i m ec o u l dh a 、r eb e e nm i n i m i z e di ft h en u m b e ro fc r o s s i n g so ft h e r 越l sh a db e e nm i n i m i z e d b u tw h a ti st h em i n i m u mm l m b e ro fc r o s s i n g s ? i r e a l i z e da f t e rs e v e r a ld a y st h a tt h ea c t u a ls i t u a t i o nc o u l dh a eb e e ni m p r o v e d ，b u t t h ee x a c ts o l u t i o no ft h eg e n e r a lp r o b l e mw i t hm k i l n sa n dns t o r a g ey a r d ss e e m e d i-，11。i，卜一lpiirkrl|flr，l，iliirrr-r l l 1 i l 博士学位论文 t ob ev e r yd i 伍c u l ta n da g a i nip o s t p o n e d l ys t u d yo fi tt ot i m e sw h e ni n yf e a r s f o rr i l yf 锄i l y 、o u l de n d ( b u tt h ep r o b l e mo c c u r r e dt om ea g a i nn o te a r l i e rt h a n 1 9 5 2 ，a ti n y 矗r s tv i s i tt op o l a n dw h e r eim e e tz a t a n k i e w i c z im e n t i o n e dt oh i mh 1 y b r i c l ( - f a c t o r y - p r o b l e m ；) ” n t t e 【7 】、e r d 6 s 和g u y 【8 及m y e r s 【4 】等对图的交叉数历史做了较为详 细的介绍，p a c h 和t 6 t h 【9 1 1 】对交叉数的概念及成果也作了较多的介绍国 际一些计算机科学家，如l e i g h t o n 【1 2 】，g 盯e yj o h n s o n 【1 4 】等，也对图的交叉 数进行了研究研究图的交叉数不仅具有重要的理论意义，而且有较强的现实 意义，在许多领域有着非常广泛的应用，例如： 1 超大规模集成电路y l s t 中的圈布局问题等【1 2 ，1 3 ，1 6 】； 2 草图的识别与重画问题，具有比手写汉字识别应用更为广泛的应用领 域； 3 软件开发过程中文档部分的e r 图( 实体联系图) 等的自动生成； 4 生物工程d a 的图示； 5 几何学、堆垒数论与测度论等中的应用【1 0 2 然而，一般地，确定图的交叉数又是十分困难的， g a r e y 和j o h n s o n 【1 4 】 证明了确定图的交叉数问题属于p 一完全问题由于其难度，已确定的交叉 数的图类较少随着对图的交叉数问题研究的深入，对它的研究内容日益丰 富一方面希望确定具体图类的交叉数，另一方面希望得到与图的交叉数有关 的其它性质，如确定图类交叉数的较好上界、研究图的交叉数与图的结构、图 的其它参数之间的关系、研制有关确定图的交叉数的算法等 1 5 ，8 3 ，8 4 ，1 0 5 】目 前确定图类的交叉数主要集中在以下几个方面： 1 一些较特殊的具体图类的交叉数 这些特殊图类的交叉数中，部分给出了交叉数上下界或猜想，但是具体结 果甚微，主要有 ( 1 ) 平面图g 对于平面图g ，其交叉数等于o ，一-j一r_1，_ 线图与若干典型图类的交叉数研究 例如，对于完全图，当n 1 危 1 郝荣霞，刘彦佩等也研究了一类循环图c ( n ，m ) ，给出了其交叉数的上界f 8 3 ，8 4 】 如 州c 3 胚 端篙：曼：罴 ； c r ( c ( 2 m ，m ) ) ( o 考1 ) + ( o 零1 ) ， 凹( c ( n ，m ) ) 等+ 1 华东师大任韩、马登举等也获得了部分循环图的新的结果【8 6 】 2 与图的交叉数有关的其它参数与性质 ( 1 ) 直线交叉数 直线交叉数万( g ) 是指图g 的边都是直线的交叉数【9 】 一般地， 凹( g ) 万( g ) 线图与若干典型图类的交叉数研究 1 9 9 3 年，b i e n s t o c k 和d e a n 【5 0 研究了图的直线交叉数，得到 a 对任意m 南4 ，存在图g ，使得c 7 ( g ) = 南，但是万( g ) 七 b 若c 7 ( g ) 3 ，则石f ( g ) = c r ( g ) c 若用多个直线段代替直线边，并记此时图的交叉数为甜2 ( g ) ，则 c r 2 ( g ) ( 凹( g ) ) 2 他们并介绍了一些有4 个交叉数的图，其直线交叉数可以任意大 任给图g 和整数南，确定图g 的直线交叉数万( g ) 尼是p 一完全 问题【9 9 】目前我们能确定直线交叉数的图类很少当图g 的顶点数n = 4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，1 1 ，1 2 时，已确定图g 的相应的完全图直线交叉数分别为 0 ，1 ，3 ，9 ，1 9 ，3 6 ，6 2 ，1 0 2 ，1 5 3 【8 5 ( 2 ) 奇交叉数 图g 的奇交叉数o 砌一c r ( g ) 是g 的边e 和e 7 相交奇数次使得图g 有最 小交叉数的边对 e ，e 7 ) 的数目一般地， o d d c r ( g ) p o i r c r ( g ) c r ( g ) 西；( g ) ， 其中p n 打一c r ( g ) 是指图g 有最小交叉数的边对( e ，e 7 ) 的数目 j 磊n o sp a c h 等【9 提出：对任意图g ，是否有 0 d d c 7 ( g ) = p o i r c 7 ( g ) = c r ( g ) ? 图g 的任意一对边如果相交偶数次，则一定可以得到它的交叉数为o 也就 是说，如果o 捌一c 7 1 ( g ) = o ，则c r ( g ) = o ，即万( g ) = o p e l s m a j e r 等人对 环面上图的映射的奇交叉数做了较为详细的研究 1 1 1 ，即对任意图g ，都有 c r ( g ) 2 ( 0 d d c r ( g ) ) 2 【9 ，1 3 】 ( 3 ) 正则图交叉数 正则图交叉数的研究也是一个较热的研究方向r i c h t e r 等研究了3 一正则 图的交叉数 7 0 】，杨元生等利用计算机编程，给出了礼1 2 的所有四正则图的 交叉数和n 1 6 的随机四正则图的交叉数，并猜想四正则图的交叉数的平均 交叉数为0 ( n 2 ) 【1 5 】 博士学位论文 ( 4 ) 临界交叉数 m a u r t i nk o c h o l 研究了临界图的结构，得到了具有n ( n 2 ) 个交叉数的3 一 连通临界简单图的结构f 6 6 】r b r u c er i c h t e r ，c a r s t e nt h o m a s s e n 等人也对该 图做了大量的研究工作【6 0 】在【6 0 中， r i c h t e r 证明了：若图g 上具有交叉 数最少为南的最小的图，则c r ( g ) 博士学位论文 第二章图与其线图的交叉数 2 1引 言 本章中未说明的概念和术语均同文献【1 】，且无特别说明时，所涉及的图均 指非定向的连通简单图，用y ( g ) 和e ( g ) 分别表示一个图g 的点集和边集， 且用( g ) 表示g 的最大度 设g 为图，对于任意集合a y ( g ) ue ( g ) ，g a 表示从g 中去掉a 中 的所有元素所得到的图( 去掉一个点必须同时去掉与该点关联的所有边) 若a 包含一个元素z ，则用g z 表示g a 图g 中一个度为忌的点，我们称为七一 度点，而且若该点不是g 的割点，我们称为g 的忌一度非割点设u 为一个图 g 的割点，若g 中与u 关联的某条边e 与g 【u ) 中的某个分支f 中的点关 联，我们说e 连接g u 】的分支f 图的画法是指用弧来表示平面上的图的边弧可以交叉，但是不能通过 点( 端点除外) 交叉，且没有三条以上的弧具有同一个内点交叉是指两条弧 公共的内点图g 的一个画法妒的交叉数凹西( g ) 是指g 在该画法中两两不 相邻的边相交的数目这里的边是画法中的不自相交的约当曲线一个图g 的交叉数凹( g ) 是指图g 在平面上的所有画法中的最小的交叉数目显然， 图g 的交叉数凹( g ) ，是指图g 在平面上的所有”好画法”中边与边之间的 最小交叉数，其中“好画法”与“最优”画法见第一章中的定义 对于图的交叉数的进一步了解，读者可阅文献【2 1 若为图g 的一个好 画法，对于g 的任意子图f ，由定义，f 在西的限制画法也是f 的一个好画 法无特别说明，本文以下所指涉及到的“画法”均指“好画法” 显然，一个图g 是平面图，当且仅当有c r ( g ) = o 从6 0 年起，人们就开 始对图的交叉数问题进行研究从计算难度上，文献【1 4 】证明了，一般地，确 定图的交叉数问题是一个n p 一完全问题正因为如此，目前能够确定交叉数 的图类非常少，我们只知道一些特殊图类的交叉数，如点数较少的完全图， 1 2 博士学位论文 完全2 一部图，完全3 一部图，圈与圈以及路与点数较少的图的笛卡尔积图( 见 文献【3 弘4 8 】等) ，循环图【8 3 ，8 4 ，8 6 ，1 0 5 ，1 0 6 】以及p e t e r s e n 图 1 0 7 ，1 0 8 】等特别 地，近几年来，对于线图与原图的交叉数问题，引起了人们的注意一个较早 的结果( 见文献【5 5 】) 证明了： 定理2 ：1 1 一个平面图g 的线图三( g ) 是平面图，当且仅当( g ) s4 且 g 中每个4 一度点是g 的割点 用图的“交叉数”术语，上述定理可以表述为如下形式： 定理2 1 1 7 设g 为平面图则凹( l ( g ) ) = o ，当且仅当( g ) 4 且g 中 每个4 度点是g 的割点 自然地，人们会研究平面图或非平面图的交叉数，对于它的线图的交叉数 为1 的研究有如下结果j e n d r o l ，和k l e 琵【6 8 】于2 0 0 1 年研究了非平面图的线 图的交叉数情形： 定理2 1 2设g 为非平面图 l ( g ) 为它的线图则盯( l ( g ) ) = 1 ，当且 仅当下列三个条件成立： ( 1 ) 卯( g ) = 1 ； ( 2 ) ( g ) 4 ，且g 中每个垂度点是g 的割点； ( 3 ) 存在g 的一个恰有一个交叉数的最优画法使得每条交叉的边关联g 中的一个2 度点 对于平面图的情形，文献【1 0 3 】证明了： 定理2 1 3 设g 为平面图若c r ( l ( g ) ) = 1 ，当且仅当如下条件( 1 ) 或 ( 2 ) 满足 ( 1 ) ( g ) = 4 ，且g 中恰好存在一个垂度非割点；或者 ( 2 ) ( g ) = 5 ，g 中没有4 - 度非割点，而且g 恰好存在一个5 一度点，且仳 是割点，不是而且在与u 关联的边中，最多有3 条边连接g u 的同一个分 支 线图与若干典型图类的交叉数研究 1 3 d g l ( g ) 图2 1 ：非平面图与线图的交叉数都为l 在许多情形下，线图的交叉数要比原图的交叉数多例如，星图k 1 ，礼具 有n + 1 个顶点且其交叉数为o ，然而其线图是完全图k 。，其交叉数为q ( ) ( n 8 ) 3 】 事实上，定理2 1 2 给出了线图和原图的交叉数都是1 的充分必要条件 自然地，我们可以考虑相似的问题，即对任意整数七1 ，什么条件下线图与 原图具有相同的交叉数后? 特别地，我们得到如下的主要结果： 定理2 1 4 设g 为图，凹( g ) = 后( 七1 ) ，其线图为三( g ) 若凹( l ( g ) ) = 庇， 则当且仅当下列条件成立： ( 1 ) ( g ) 4 ，且g 中每个4 一度点都是割点； ( 2 ) 存在g 的一个恰有尼个交叉数的最优画法使得每条交叉的边关联g 中的一个2 度点 定理2 1 4 是定理2 1 2 的推广但本文的研究方法与j e n d r 0 1 和k l 西亡在 文献【6 8 】中使用方法不同 设g 为图，l ( g ) 为它的线图，e 和u 分别表示g 的一条边和一个顶点 由线图的定义可知，e 对应于l ( g ) 的顶点，并用- e 表示与e 相应的l ( g ) 的 顶点又，如果u y ( g ) ，且d ( u ) = m ，设e t ( 1 i m ) 为所有与 关联的 1 4 博士学位论文 边，则l ( g ) 的点导出子图= l ( g ) 【 可。；1 1 i m ) 】同构于完全图有 时，我们称为对应u 的线图l ( g ) 的子图对g 中任意两个不同的顶点u 和札，和或者是点不交的，或者是恰有一个公共端点- e ( 后者只发生在 u 和u 是相邻的情形) 设是图g 的一个好画法如果a 和b 足g 的两个边了集，那么用记 号c ( a ，b ) 表示由a 的边和b 的边产生的交叉数 2 2 线图的特殊子图 定义2 2 1 设g 是图， l ( g ) 是其线图，丌：y ( g ) _ y ( l ( g ) ) 是y ( g ) 到 y ( l ( g ) ) 的映射称为从g 到l ( g ) ) 的诱导同胚映射，如果满足如下两个 条件： 1 对每一个顶点u y ( g ) ，丌( 札) = _ e ，其中e 是g 中与u 相关联的边 2 对任意两个顶点u ，u ，若u u ，则丌( 乱) 丌( ) l ( g ) 中的顶点z 被称为在丌下是主要的，如果它在g 中有原像，即存在 u y ( g ) ，使得丌( “) = z ；否则，z 被称为次要的 定义2 2 2 设丌是图g 到其线图三( g ) 的诱导同胚映射对任意e = 让口 e ( g ) 丌( e ) 可定义为： i7 r ( u ) 丌( u ) ，女疆果7 r ( u ) = _ e 或7 r ( u ) = ：_ e ( 7 r ( e ) l ( g ) ) ； 丌( e ) 全 i 丌( u ) 西。丌( u ) ，否则( 丌( e ) 是三( g ) 中长度为2 的路) 由丌的定义我们可以得到7 r e 同时，如果丌( e ) = 丌( u ) _ e 丌( u ) ，则可。是l ( g ) 的两个子集| c u 和的公共端点 设e + = u 所有丌( e ) ) 则e + 是l ( g ) 的边子集下面考虑l ( g ) 的 e e ( g ) 诱导边子集三( g ) 陋+ 】对于给定的丌，三( g ) 刀1 是由e + 唯一确定因为三( g ) 的主要顶点必须关联e + 的一条边，因而l ( g ) 【e 1 包含了l ( g ) 的所有主要顶 线图与若干典型图类的交叉数研究 1 5 点显然，可以说l ( g ) e + 被丌诱导我们可以得到如下结果 6 已2 gi 删 图2 2 ：诱导同胚映射丌：y ( g ) 一y ( l ( g ) ) 、 j 引理2 2 1l ( g ) 旧+ 同胚于g 证明如果l ( g ) 陋+ 】在映射丌下含有l ( g ) 中的次要顶点z ，则z 在在 三( g ) 陋 中的度为2 因为z l ( g ) 陋+ 】，由e + 的定义，存在g 的一条边 e = u u ，使得z 丌( e ) 因为z 是次要的，所以丌( e ) = 丌( u ) z 丌( u ) ，其中丌( e ) 是 l ( g ) 中的长度为2 的路又由丌( e ) 的定义，z = 西。显然，z 在l ( g ) 陋+ 】中 的度至少为2 如果d ( z ) 3 ，z 必须关联于l ( g ) 【e + 】中另一条边q 且q 不属 于7 r ( e ) 由此得到a 为一条属于7 r ( e 7 ) 的边且e 7 g ，e 7 e 设u 7 和u 7 为e 7 的两个端点相似地，由e + 的定义与z 是次要的，可以得到丌( e 7 ) 是一条2 一 路，且丌( e 7 ) = 丌( u 7 ) z 丌( - u ，) 这样，z = - e ，e e 7 因为l ( g ) 的第一个主要的 顶点必须关联于e + 的一条边，因此l ( g ) 陋1 包含了l ( g ) 的所有主要顶点 如果忽略l ( g ) e + 】中的所有次要顶点，那么不难得到映射丌是g 到l ( g ) 陋+ 】 的同构映射这样，l ( g ) e + 】同胚于g 1 引理2 2 2 设g 是树，u 是g 的任意一点则存在映射丌：v ( g ) u ) _ y ( l ( g ) ) 使得定义2 2 1 中的条件( 1 ) 和( 2 ) 都满足 证明将g 变为具有根u 的树存对任意顶点u y ( g ) u ) ，因为具有关 1 6 博士学位论文 联于顶点- u 的唯一一条深度边，所以可以令丌( u ) = 一e 容易验证定义2 2 1 中 的条件( 1 ) 和( 2 ) 都满足 口 j e n d r 0 1 7 和k l 西芒【6 8 】已经证明了至少有一个圈的图g 的线图l ( g ) 有一 个同胚于g 的子图通过引理2 2 2 ，我们可以得到相同的结果 引理2 2 3 设图g 至少有一个圈，则存在一个导出同胚映射丌：g _ l ( g ) ， 且由丌导出的l ( g ) 的子图同胚于g 证明仅证明前部分，后者由引理2 2 1 可以直接得到 对g 的边的数目使用归纳法如果g 是只有一个圈的图，则g 有一条边 e 使得g ，= g e 是树令u 是e 的一个端点由引理2 2 2 ，存在从y ( g ，) u ) 到y ( l ( g ，) ) 的映射丌使得定义2 2 1 的条件( 1 ) 和( 2 ) 都满足延拓映射7 r 7 得 到从y ( g ) 到y ( l ( g ) ) 的映射7 r ：任给t ，y ( g ) ， r 、j7 r 铷) ，i f 口札； 7 h 叫一、- e ， i f = 饥 则定义2 2 1 的条件( 1 ) 和( 2 ) 都满足，因而丌是从g 到l ( g ) 的诱导同胚映 射假设对具有至少一个圈的图g 且边数少于g 的边数归纳成立，于是可假 设图g 至少有两个圈令边，e ( g ) ，使得g = g ，连通显然，g 至少 有一个圈由归纳假设，存在从g ，到l ( g 厂) 的诱导同胚映射丌因为g 和g ，的顶点数相同，且l ( g ，) 是l ( g ) 的子图，由定义容易验证丌同样 是从g 到l ( g ) 诱导同胚映射因此由归纳假设就证明了引理的前半部分口 引理2 2 4 设丌是从图g 到它的线图l ( g ) 的诱导同胚映射，9 + 是由丌 在图l ( g ) 中的导出子图e ，和e 2 是g 中两条相邻的边，e 1ne 2 = u - 如果 一e ，可。9 + ，贝0 丌( u ) 可。，可。) 证明设耽是e i 的端点，i = 1 ，2 由引理2 2 1 前面的叙述可知，9 + 含 有l ( g ) 的所有主要的顶点由9 + 的定义，如果_ e 。玩。是g + 的边，则存在如 下两种情形： 情况( 1 ) ：订。，西。是l ( g ) 中的一条2 一路边丌( ，) ，其中，e ( g ) ； 情况( 2 ) ：面。面。是l ( g ) 中一条边7 r ( h ) ，其中h e ( g ) - _ 1 l l ，血1-】11j_ ，j，1、， 线图与若干典型图类的交叉数研究 1 7 对情况( 1 ) 设z 和可是厂的两个端点，记丌( 厂) = 丌( z ) 万，7 r ( y ) 因为可。- e 。是 7 r ( ，) 的边，有_ e ，= 可，且可。 7 r ( z ) ，丌( y ) ) ，或者可。= 可，且西。， 7 r ( z ) ，丌( 可) 如果是前者，则e 1 = 厂因为g 是简单图，所以 ，u 1 ) = 茁，秒】这样， _ e 。 丌( z ) ，丌( y ) = 丌( 口) ，丌( u 1 ) 类似地，由g 的简单性， 1 珏所 以，- e 。丌( 1 ) ，否则e 2 必须与u 1 关联，这与图g 是简单图矛盾由此可得 可。= 丌( u ) 如果是后者，通过相同讨论，可得e 。= 丌( u ) 情况( 1 ) 即