（计算机应用技术专业论文）循环图c（n1k）的交叉数.pdf

摘要 图的交叉数是衡量图的非平词性的一个重要概念。b h a t t 和l e i g h t o n 指出一个网络 ( 图) 的交叉数是与这个图v l s i 电路设计需要的最小版图面积是密切相关的。然而计 算任意图的交叉数是非常棘手的，g a r e y 和j o h n s o n 证明了交叉数问题是n p 完全的。 迄今为止，只有很少图族的交叉数是已知的。完全图的交叉数，完全二分图的交叉数都 是拓扑图论中公jr 的难题。 近年来，广义p e t e r s e n 图，圈的交图，循环图等具有良好互连特性的图族成为交叉 数问题中活跃的研究对象。e x o o 等给出了p ( n ，2 ) 的交叉数，f i o r i n i 给出了部分小阶广义 p e t e r s e n 图的交叉数。s a r a _ i n 证明了p ( i o ，4 ) 的交叉数足4 。刈同印与刘彦佩给出了 c ( 月；( 1 ，2 ) ) v j 交叉数。郝荣霞与刘彦佩给出了关于q n ； l ，女 ) 交叉数的新上界。r i c h t e r 和s a l a z a r 给出了p ( n ；3 ) 的交叉数。杨元生和赵承业给出了c ( h ； 1 ，l ”2 j 的交叉数。 s a l a z a r 给出了关于c ( n ； l ， ) 和p ( n ，曲通用的界。 本文首先研究了循环图c ( n ；0 ，3 ) ) 的交叉数，证明了 c r ( c ( n ； 1 ，3 ) ) ) = ln 3i - i - n m o d3 扣rn 8 这个结沦证明了r i c h t e r ，s a l a z a r ，郝荣霞，刘彦佩等关于循环图c ( ；( 1 ，3 ) ) 的交叉数的 猜想是成立的。 进一步，本文研究了循环| 莩| q h i 1 ，l 1 2 j l ) 的交叉数，给出了n 为偶数时交叉数的 值和1 7 为奇数时交叉数的上界。 月2 f o re v e n l 7 8 4 + 2 ，f o rn = 8 h + 1 ，h 2 4 + 2 ，f o rh = 8 h + 3 ，h 2 4 + 3 ，f o r ”= 8 h + 5 ，h 1 4 + 5 ，f o rn = 8 h + 7 ，h 1 本文还研究了循环图c ( m k ； 1 ，砖) 和广义p e t e r s e n 图p ( m k ，的交叉数。给“_ ；了 q i n k ； 1 ， ) 交叉数的个上界和c ( 3 k ； 1 ， ) 交叉数的值， e r ( c ( 3 k ； 1 ，t ) ) = kf o ，k 3 ； c r ( c ( 4 k ； l ，t ) ) 2 k + 1 加，k 3 ； c r ( c ( m k ； 1 ，) ) ) m i n ( m 一2 ) ( 女+ 1 ) 一1 ，( t 2 ) 扣r k 3 ，m 5 同时给mrp ( m k ，的交叉数的一个上界和p ( 3 k ，硒的交叉数的值， c r ( p ( 3 k ，t ) ) = k 加rk 4 ； c r ( p ( 4 k ，女) ) 曼2 k + 1 i rk 4 ； c r ( p ( m k ，) ) m i n 2 m k + m 一6 k 一5 ，m ( 2 k 一5 ) f o ，k 4 ，m 5 关键谰：交叉数；循环图；广义p e t e r s e n 图 a b s t r a c t c r o s s s i i l gn u m b e ri s a ni m p o r t a n tc o n c e p tm e a s u r i n gt h en o n p l a n a r i t yo fg r a p h s b h a t t a n dl e i g h t o ns h o w e dt h ec o r s s i n gn u m b e ro fan e t w o r k ( g r a p h ) i sc l o s e l yr e l a t e dt ot i r e m i n i n m ml a y o u ta r e ar e q u i r e df o rt h ei m p l e m e n t a t i o no fav l s ic i r c u i tt b rt h a tn e t w o r k h o w e v e r ，i ti si n t r a c t a b l et oc a l c u l a t et h ec r o s s i n gn u m b e ro fa na r b i t r a r yg r a p h g a r e ya n d , j o l m s o nh a v es h o w e dc r o s s i n gn u m b e ri s n p - c o m p l e t e t h e r ea r e o n l y af e wi n f i n i t e f a m i l i e so f g r a p h sw h o s e c r o s s i n gn u l n b e i s a r ek n o w n t h e c r o s s i n gn u m b e r so f t h ec o m p l e t e b i p a r t i t eg r a p ha n d t h ec o m p l e t eg r a p ha r eo p e n p r o b l e m si nt o p o l o g i c a lg r a p ht h e o r y r e c e n t l y , m a n y m a t h e m a t i c i a n sf o c u so ns o m eg r a p h sw i t hg o o d p r o p e r i t i e s s u c ha st h e g e n e r a l i z e dp e t e r s e ng r a p h ，c | 1 t x ( ：na n dt h ec i r c u l a n tg r a p h e x o oe ta 1 s h o w e dt h ec r o s s i n g n u m b e ro f p ( n ，2 ) f i o r i n is h o w e dc r o s s i n gn u m b e r s o fs o l n eg e n e r a l i z e dp e t e r s e ng r a p h sw i t h s m a l l0 1 d e r s a r a g i np r o v e dt h a tt h ec r o s s i n gl l t l n l h e ro f 珂t 0 ，4 ) i sf o u rl i ut o n g y i na n dl i u y a u p e is h o w e dt h ec r o s s i n gn u m b e ro fc ( h | ，1 ，2 ) ) i l a or o n g x i aa n dl i uy a n p e is h o w e da n e wb o u n df o rc r o s s i n gn u m b e r so fc ( ”：f 1 ，日) r i c h t e ra n t is a l a z a rs h o w e dt h ec r o s s i n g n u m b e r o f ，j ( ，1 ；3 ) v a n gy u a n s h e n g a n dz h a oc h e n g y es h o w e dc r o s s i n gu u t n b e r so f c ( n ； 1 , l n 2 j ) s a l a z a rs h o w e d t i g h tb o u n d s f o r c r o s s i n g l l u m b e r s o f c t ( 月； 1 ，) ) a n d p ( n ， f i r s t l y i tj sp r o v e d t h a tt h ec r o s s i n gn u m b e r o f a ， 1 ，3 ) i s e r ( c ( n ； l ，3 ) ) ) = lr 3 l + n m o d 3f o ，n 8 i tv e r i t i e st h ec o a j e c t u r ep t o p o s e db yr i c h t e r , s a l a z a r , h a or o n g x i aa n dl i uy a n p e i s e c o n d l y ，t h i sp a p e rf o c u s e so nt i r ec r o s s i n gn u m b e ro fc ( n ；( 1 ，l n t 2 j 。1 ) ) l h e v a l u eo f c r o s s i n gn u n l b e r sf o re v e n ha n dt h eu p p e rb o u n df o rc r o s s i n gn u m b e r sf o ro d d1 1a r es h o w e d c r ( c ( n ； 1 ，h 2 1 ) ) = 2f o re v e n n 8 f 4 矗+ 2 ，门= 8 + l ，矗2 ； 州驯，l n 2 胚 笔：篙：漾孝 4 h + 5 ，托：8 矗+ 7 ，矗 f i n a l l y ，c r o s s i n gn u m b e r so fc ( m k ； 1 ，q ) a n dp ( m k , k ) a r es t u d i e di nt i f f sp a p e r s o m e c l o s eu p p e rb o u n d sa n ds o m ee x a c ! v a l u e sa r es h o w e d c l ( c ( 3 ； l ，a ) ) = k 弘，3 ； c l 4 ( c ( 4 ； l ，) ) 2 k + 1f o r 3 ； c r ( c 0 7 ； l ，t ) ) r a i n ( m 一2 ) ( + 1 ) 一1 ，m ( k 一2 ) f o , k2 3 ，j 7 i2 5 c ，。( f ( 3 k ，) ) = k 如rk 4 ； c ，( e ( 4 k ，女) ) 2 女+ l i r 4 ； c ，( p ( m k ，女) ) m i n 2 m k + m 一6 k 一5 ，m ( 2 k 一5 ) ) f o ，k 4 ，”t 5 k e y w o r d s ：c f o s s in gn u m b e r ：e jr c u j a n tg r a p h ：g e n e r a iiz e dp e t e r s e ng r a p h 循环图c ( ； i ，t ) ) 的交叉数 o 前言 冈论的研究对象是图，即顶点以及它们的邻接关系；而拓扑图论关注的不是抽象的 图，而是如何在表面上表示图。例如，如果一个图可以“嵌入”到平面( 球面) 上，边 与边之间没有交叉，那么这个图就是可平面的；反之，这个图就是不可平面的。 面法是一个比嵌入更为广泛的概念。与图的嵌入不同的是，它允许表面上的边交叉。 画法中两条边的交点称为一个交叉点。画法中交叉点的数目称为这个画法的交叉数，而 一个图的所有画法中最小的交叉数称为图的交叉数。图的交叉数是图的一个拓扑不变 量，它给 虹了图的非平面性的一个量度。 交叉数的概念来源于t u r g n 的砖j 一问题。在二战期间的一个劳动营中，有若干个砖 窑和若十个仓库。每座砖窑都与每一个仓库用铁轨相连。运输砖块的列车沿着铁轨从 砖窑了1 往仓库。在铁轨的交叉点处列车容易出轨，这导致许多麻烦。t u r i n 想到如果铁 轨的交叉点数目最小，那么带来的损失也就能够最小。t u r g n 砖厂问题，用术语来讲， 也就是完全二分图的交叉数。 1 9 5 4 年，z a r a n k i e w i c z l 2 1 试图给出了关于完全二分图五。交叉数的交叉数。 c 皑。) = 引掣掣i ( o 1 ) l 二j l 二 j l i l 二j 1 9 6 9 年，g u y 叫指出在z a r a n k i e w i c z 的证明中存在错误，并且给出了关于完全图 交叉数的猜想。 c ，1 _ 三l 到兰兰旦二兰0 ! ! ! j( o 2 1 “4 l 2 j l2j l 2 j l 2 j k l e i t m a n l 4 1 给h 对于m 6 式子( o 1 ) 成立，并且证明了关于z a r a n k i e w i c z 猜想的最小 反例必然出现在州和”为奇数的情况。w o o d a l l l 5 1 利用计算机搜索给出了对于玛7 和嵇9 式子( 0 1 ) 成立。g u y l 3 给出了对于月1 0 式子( 0 2 ) 成立。迄今为止，没有人能够对这两 个猜想的币确性给出完全的证明，也没有人能够给出反例。完全二分图的交叉数和完全 图的交叉数是拓扑图论领域公开的难题。 1 9 8 3 年，g a r e y 和j o h n s o n 6 】证明了计算任意图的交叉数是n p 完全的。n p 完全问 题被认为是难以得到有效算法的，任意图的交叉数问题被认为是难以处理的。近年来， 广义p e t e r s e n 图，圈的交图，循环图等具有良好互连特性的图族成为交叉数问题中活跃 的研究对象。e x 0 0 1 7 1 等给出了，眠2 ) 的交叉数，f i o r i n i 8 给出了部分小阶广义p e t e r s e n 图的交叉数。s a r a t i n l 9 l 证明了p o o ，4 ) 的交叉数是4 。刘同印与刘彦佩l l o l 给出了c ( ”；f 1 ，2 ) ) 的交义数。郝荣霞与刘彦佩 给出了关于c ( 珥 1 ，嬲) 交叉数的新上界。r i c h t e r 和s a l a z a r 【1 2 给出了p ( n ；3 ) ( t t j 交叉数。杨元生和赵承业0 3 1 给出c ( ”； 1 ，l n 2 j ) ) 的交叉数。s a l a z a r 1 4 1 给 出了关于c ( n ； l ，k ) ) 和p ( n ，功通用的界。 本文选择了循环图c ( ； 1 , k i ) n , t 及广义p e t e r s e n 图p ( n ，妁) 的交叉数做为研究范围， 塑塑：鬯g 曼! ! ：! ! ! 塑壅墨塑 其中循环图c ( h ；( 1 ，3 ) ) ，c ( n ； 1 ，l n 2 j - 1 ) ，( i n k ； 1 ，q ) 以及广义p e i e r s e l l 图，( 卅k ，酬r 拘交叉 数是本文主要的研究对象。 循环图c ( h ； 1 ，q ) 的交叉数 1 交叉数概念及其进展 1 1 交叉数相关概念 图 一个图g 定义为一个二元组( k 毋，记作g 兰( k 目。其中怍坎g ) 表示顶点的非空集 合。庐e ( g ) 是由妖g ) 中元素的无序对组成的集合，e 中的元素称为边。边( “，v ) 简记为 “v 。一般称“和v 是相邻的顶点。称一条边的顶点和这条边相关联。 图g 中顶点的数目，称为图g 的阶；图g 中边的数目，称为图g 的大小。 关联同一个顶点的边称为自环。关联同一对顶点的两条或两条以上的边称为多重 边。无自环，无多重边的图称为简单图。仅有一个点的简单图称为平凡图。 本文涉及到的图均为无向的，非平凡的简单图。 路径与圈 一个图g 的一条通道是顶点和边的一个交替序列v o ，e 】，vj 1 p n - l ，e 。，h 。有时也可记作 r o y l v n 。v n 。这时称它是从v o 到v 。的长为 的通道。若它的所有边都不同，称之为一 条迹。若它的所有顶点都不同，称之为一条路径。若路径的起点和终点相同，即v o = v n 且它的前n 个点都不同，n 3 ，则称它为一个圈或回路，记作r o y l o n - l v n 。一个圈中 边的个数称为这个圈的长度。 图g 的围长是指在图g 中最短的圈( 假如g 中有圈) 的长度。 子图 ， 对于图g 和n 若有h 劢h g ) 且以顾回，则称h 是g 的一个子图。若h 功ch g ) 或觑邱c 日6 3 ，则称图h 是g 的一个真予图。若h 功= h 6 3 ，则称日是g 的生成子 图。设w e “g ) 是g 的任意顶点集，则由矽及那些两个端点都在中的边构成的子图 称为g 的顶点导出子图。设f 是g 的任意边集合，并且f c _ e ( g ) ，由这些边以及那些与 这些边关联的顶点组成的子图称为g 的边导出子图。 嵌入与平面图 如果一个图g 可以画在一个表面s 上且任何两条边都不相交，则称g 可以嵌在表 面s 卜。相应的画法称为一种嵌入。 一个图如果可以嵌入平面，则称之为可平面的，或称之为平面图。如果一个图不能 被嵌入到一个平面上，则称之为非平面图。对于一个非平面图g ，若存在它的一个生成 子图乜日是平面图且对任意一条属于g 但不属于h 的边e ，册8 是非平面图，则把图 h 称为图g 的极大平面子图。一个非平面图可能有不止一个极大平面子图。 画法与交叉数 图g 在表面上的画法是指图g 在表面上的一个同胚映射，使得图g 的顶点表示为 不同的结点，图g 的边表示为连接对应顶点对的简单连续弧，并且不包含结点。一个 画法是好的画法倘若它满足下列条件：( i ) 关联于同个结点的两条弧没有公共点；( i i ) 循环图c ( 噬( 1 ， ) 的交叉数 没有两条弧有两个或者两个以上的公共点：0 i i ) 没有弧自己相交；( i v ) 没有三条弧有一 个公共点。 画法中两条弧的一个公共点称为一个交叉点。图g 在给定表面上的最优画法是指 图g 的所有画法中具有最少数目交叉点的画法，这个数目称为图g 对于该表面的交叉 数。画法d 中交叉点的数目记为”( d ) ，图g 在平面( 或球面) 上的交叉数简称为图的 交叉数，记为c r ( g ) 。 在不引起歧义的情况下，方便起见，也称结点为顶点，称弧为边，直接利用抽象图 的元素来指代它们的平面表示。 除了特别指出，本文中所提到的所有画法都是好的画法。 交叉数是衡量图的非平面性的一个概念。平面图的交叉数为0 ，非平面图的交叉数 至少为1 。 亏格、厚度、糙度 亏格是指为了把g 嵌入球面所需要的环柄的数目；厚度是指构成g 所需要的可平 面图的数目；糙度是指边不相交的不可平面子图的最多数目。 亏格、厚度、糙度和交叉数都是图的拓扑不变量。 映射和象 设x 和y 是任意两个集合，雨，是x 到y 的一个关系，如果对于每一个x e x 都有 唯一的y y ，是的q f 则称厂为函数，记做： f ：x - y 假如，y e f , 则x 称为白变元，y 称为在厂作用下x 的象。从x 到y 的函数往往也叫 做从到r 的映射。 如果x 和y 的元素数目相同，并且x 中没有两个元素有相同的象，则称这个映射 为一一映射。 正则 图g 中与一个顶点v ，相关联的边的数目叫做顶点v ，的度，记作西或d e gv i 。图g 中所有顶点中最小的度记作巧( 6 3 = m i n d e g g ，最大的度记作d ( 6 3 = m a x d e g g ) 。如果 j ( g ) = a ( g ) = r ，则g 中所有点的度都相等，这时g 称为是r 正则的。 同构 若在两个图g 和h 的顶点集合之间存在一个保持邻接性的一一对应，则称它们是 同构的。即存在一个一一对应的映射使得对任意u e 坎g ) 。有y ( u ) 坎功，同时满足： ( b ，v ) e ( g ) 当且仅当暇功，贝v ) ) 耳，记作g 丝日。 同胚 若x = “v 是g 的一条边，又w 不是g 的一个顶点，则当用边甜w 和w v 来代替x 时 称x 被细分。两个图是同胚的，若它们都可以从同一个图通过一系列边的细分得到。 同胚的图的可平面性是一样的。 连通 若一个图的每一对顶点都有一条路径联结，这个图称为是连通的。g 的一个最大的 连通子图称为g 的一个连通分支。一个图的一个割点是这样一个顶点；移去它后使剩 下的图的连通分支的数目比原来的图有所增加。一条割边也是具有类似性质的一条边。 连通的，非平凡的而且没有割点的图称为不可分图。图g 的一个极大的不可分子图称 2 j ! ! 型旦曼! ! ：! ! ! 堕奎墨塑 为图( ；的一个块。 收缩 图g 中有边e = “v ，从图g 中删除p ，合并顶点“v 使得无论原来关联于u 的边还是 芙联于v 的边都关联于新的顶点v ，这个操作称为收缩边e 。 广义p e t e r s e n 图 ”义p e t e r s e n 图j p 阮矽是由如下顶点集哪，( n 问) 和边集e ( e ( n ，旬) 构成的具有2 n 个顶 点的图，其中顶点集v ( p ( n ，) = v o ，v i ，v ，l 山v o ，v l ，v 川) ，边集e ( 尸以妁) = v i v ，bv 。v ，i p i + k ：i = o ，l ，n 一1 ) 。 通常把边v i l p ，称为广义p e t e r s e n 图p ( n ，功的连杆，圈v o ”l v n _ 1v o 称为p ( ”，k ) n 主n 。 循环图 循环图c ( ；两也称为分布式环网络。它有顶点集合 y ( c ( n ；s ) ) = ( v ，：0 i n 1 ) 利边集合 e ( c ( ；s ) ) = v ，v ，：0 i 玎一l ，0 j 行一i ，f f 一i m o d n s ， s = 1 , 2 ，i 2 交图 交图g l x g 2 是满足以下条件所构成的图类： ( 1 ) g 的顶点集矿= ( ，v ) i 对于任意i , l g l ，v g 2 ： ( 2 ) 对于任意“= ( 札u 2 ) ，v = ( v l ， 9 2 ) n 当3 1 = v i 且u 2 和v 2 在g l 中相邻或u 2 = v 2 且 h i 和v i 在g 2 中相邻时，“和v 在g l g 2 中相邻。 完全图与完全二分图 简单图g 中，若每一对顶点问都有边相连，则称该图为完全图。 完全二分图k 。是满足以下条件所构成的图类： ( 1 ) 顶点分为二个集合n ，比，其中l y ll = 州，l 如i 嘲； ( 2 ) 列j 二任意“k ，v 巧，若f ；呵，则m v 相邻( 巧= 1 ，2 ) 。 k u r a t o w s k i 定理，e u l e r 定理和w h i t n e y 定理【1 5 】 k u r a t o w s k i 定理一个图是平面图，当且仅当它不包含与坞3 或瞄同胚的予图。 e u l e r 定理设有一个连通的平面图g ，共有v 个顶点e 条边和，个面，则欧拉公式 v p + 7 一= 2 ，成立：。 w h i t n e y 定理三连通图在球面上的嵌入是唯一的。 1 2 交叉数问题的研究现状 交叉数的研究起源于t u r i n 的砖厂问题。最古老的交叉数问题t u r i n 砖厂问题至今 仍然是图论中公开的难题，没有人能够给出完全的证明，也没有人给出任何反例。尽管 如此，人们对交叉数研究依然有浓厚的兴趣。完全二分图，完全图，圈的交图，循环图， 广义p e t e r s e n 图等图族都是人们关注的研究对象。 循环图c ( n ；( j ，k 1 ) t i q 交叉数 完全二分图肠。 z a r a n k i e w i c z 2 1 曾经试图给出了完全二分图的交叉数： 州k ，= l 纠降埘孚j ， 但是g u y 3 1 指出它的证明存在错误。于是z a r a n k i e w i e z 猜想成为了公开的谜题。 若把l n 2 j 个顶点放在x 轴的负半部分，f 2 1 个顶点放在y 轴的难半部分，l 州2 j 个 顶点放在y 轴的负部分，lm 21 个顶点在y 轴的正半部分，并且用线段画出对应的脚n 条边就可以得到凰。的一个画法，这就是目前人们猜想的最优画法。尽管z a r a n k i e w i c z 的证明有误，但是这样的上界仍然是成立的。 州h j h 降脚孚j k l e i t m a n l 4 对m i n ( m ，n ) 6 的完全二分图k 。，验证了式子( 1 1 ) 成立，并且证明了关 于z a r a n k i e w i c z 猜想的最小反例必然出现在 和m 为奇数的情况。w o o d a l l 5 1 验证了对 于m = 7 月n 1 0 的完全二分图蜀。式子( 1 1 ) 成立。、 完全图岛 r k g u y 在1 9 6 0 年就提出了下面的关于完全图k ，的交叉数的猜想： 嘏，= 划旧j l 孚且字j ：， b l a z e k 和k o m a n 等人在6 0 年代中期的研究表明上述公式给出的是完全图k ，的交 叉数的一个上界。1 9 7 1 年g u y l 3 】对式子( 1 2 ) 关于”1 0 的情形进行了验证。 这里给山月为偶数的时候的画法：拿一个肥皂盒，它是同胚于球体的，把n ，2 个顶 点等距离地方在顶面的圆周上，把”2 个顶点等距离地放在底面的圆周上。在顶面和底 面上分别用直线段画出k 以。从地面上的一个顶点，向顶面上的各个顶点画出最短的螺 旋形曲线。在底面上对n 2 个顶点重复这个操作，就可以得到一个猜想的最优画法。 根据k l e i t m a n 4 1 的关于完全二分图的交叉数的结果，对足够大的n 有如下的公式成 立： c r ( e ) n ( n o ( n 一2 ) ( ”一3 ) 8 0 。 完全三分图肠。 完全三分图髓。是满足以下条件所构成的图类： ( 1 ) 顶点分为三个集合，圪，以，其中i n p ，l n 户肌，l v 3 i 刊； ( 2 ) 刑于任意“k ，v 巧，若f i 芎，则“，v 相邻( i j 2 1 , 2 ，3 ) 。 关于完全三分图的研究成果比较少，k o u h e ia s a n o i 给出了完全三分图k j ，3 ，。和 - 3 。的交叉数 循环图q h ； 1 ，埘) 的交叉数 c r ( k ”。) = z ( 4 ，n ) + l n 2 _ 1 , c r ( k 23 。) = z ( 5 ，n ) + n 其中z ( m ，n ) = l m 2 j e ( m o 2 j l n 2 i l ( 一1 ) 2 j 。 交图c r 。x c n 关于g ，g ，h a r a r y ，k a i n e n 和s c h w e n k 17 】有一个长期的猜想，那就是，对于n 1 1 1 1 3 ，两个圈的笛卡尔乘积的交叉数为 c r ( c 。，c 。) = n ( m 一2 ) r i n g c i s c n 平b e i n e k e d8 1 证明了该式予对于c 3 x g 成立。d e a n 和r i c h t e r 1 9 1 证明了该式子 划于c 4 g 成立。r i n g e i s e n 和b e i n e k e l 2 0 1 证明了该式子对于c 4 x g 成立。k l e s c ，r i c h t e r 和s t o b e r t 2 ”证明了该式子对于c 5 xc j ，成立。r i c h t e r 和s a l a z a r 2 z i i d 蝈了该式子对于c 6 g ，成立。g l e s k y 和s a l a z a r 2 3 1 证明了如果n + 1 ) 并且m 3 ，该式子成立。 表1 1f i o r i n i 的n 1 4 的广义p e t e r s e n 图p 的交叉数 ! 鲨堕! ：! 旦! 盟堕! ! ! ! ! ! ! ! 坚型! 翌! ! 堡! ! ! f ! ! 盟丝! ! 茎! 1 12345 67891 01 11 2 1 31 4 厂义p e t e r s e n 图p ( n ， f i o “n i l 8 1 对广义p e t e r s e n 图的交叉数进行了研究。它给出了部分小阶广义p e t e r s e n 图的交叉数，结果如表1 ，1 。但是在这张表中存在一些错误，如表中星号所示；还有一 些没有给出结果，在表中用问号表示。 进一步，他试图给出了广义p e t e r s e n 图p ( n ，3 ) 的交叉数： ( 1 ) c r ( p ( 9 ，3 ) ) = 2 ，c y 妒( 3 h ，3 ) 2 h ( 4 ) ； f 2 1 女+ 1 c r ( p ( 3 h + l ， ) ) a + 3 ( h 3 ) ； ( 3 ) c ，( p ( 3 h + 2 ， ) ) = + 2 ( h 2 ) 。 o 3 5 p ? 3 3 7 p p 3 0 0 0 4，1 7 + 4 0 0 o 3 5 5驴驴5 5 3 o 0 o舻?铲0 o 0 3 2 扩3 2 3 0 0 0 4 4 0 o 0 o o 0 0 5 6 7 8 9 m 他 循环图c ( n ； i , k ) f j o 交叉数 p i o r i n i 还给出了，( 垃，f ) 交叉数的上界 州鹏，) ) 懒k n f o r ) 暑= m c q u i l l a n 和r i c h t e r z 4 1 证明了o r ( p ( 1 0 ，3 ) ) 5 。 s a r a i n 9 1 证明了c r ( p ( 1 0 ，4 ) ) = c ，妒( 1 0 ，6 ) ) = 4 。 w a t k i n s 2 5 1 则给出了关于广义p e t e r s e n 图的同构定理： ( 1 ) p ( n ，丝尸，h 一妁； ( 2 ) 女t t 果l ，月2 一1 并且幻霄；1 ( r o o d ”) ，p ( n ，m ) 竺p ( 蚪，妨。 表1 2 杨元生的月1 4 的广义p e t e r s e n 图p 幻的交叉数 t a b l e1 2y a n g y u a n s h e n g sc r o s s i n gn u m b e r so f p ( n ，幻f o r n 1 4 k , n 1234567891 01 11 21 31 4 000 o20 杨元生等2 6 埽0 用计算机搜索重瓤计算了阶数不大于1 4 的广义p e t e r s e n 图的交叉数， 纠征了f i o r i n i 给出7 8 个值中的9 个错误，并且给出了l o 个未知值。关于阶数不大于 1 4 的广义p e t e r s e n 图的交叉数如表1 2 所示。由于c r ( p ( n ，p ) = c r ( p ( ”，n - 句) ，表2 仅仅给 出了k n 2 的情形。 2 0 0 2 年，r i c h t e r 和s a l a z a r 比1 发现在f i o r i n i 的证明过程中存在错误，从而给出新的 证明与结果： ( 1 ) 吖( p ( 3 h ，3 ) = h ( 4 ) ； ( 2 ) c r ( p ( 3 h + l ， ) ) = h + 3 ( a 3 ) ； ( 3 ) c r ( p ( 3 h + 2 ，) ) = h + 2 ( h 2 ) 。 最近，s a l a z a l t 。4 j 给出了关于广义p e t e r s e n 图p ( n ，通用的界。当5 并且n t 则 有 詈( 一昙) ( 一一t4 ) + ( 4 k2 + 1 - k 3 ) c r c ，c n ，t ，( z 一詈) n + ( t q 2 + k 2 + 1 ) n 方图g ， n 方图g 。是满足以下条件所构成的图类： ( 1 1n 方图g 。有2 ”个顼点，其顶点v 可以表示为t 7 1 1 c t 2 的二进位形式，其中 a i = o 或1 ； ( 2 ) 若两个顶点的二进位表达式中只有一位不同，则它们棚邻接。 0 0 3 o 3 l 墼壁! ! ! 型! ：生! 塑銮墨塑 关于n 方图q ，的交叉数问题，m a d e j l 2 7 】曾经给出的一个如下的界 n 2 2 “ c r ( g ) ”壹 。) 任意的图g 的交叉数也有通用的上界，例如任意两条边都交叉，设m = l 以g ) | 则有 c r ( g ) 这个上界是非常糟糕的，通常人们可以利用经验绘制出比这个更优的画法。如果能够构 造交叉点数目比较少的画法，则可以改进该图交叉数的上界；如果能够证明图在若干个 交叉点的条件下仍不能够画在平面上，则可以改进该图交叉数的下界。 本文的主要思路是利用手工绘制和计算机构造优的画法来得到图的交叉数的上界， 对于下界则采用数学证明的方法。这一章中，首先给出画法的存储方法，然后描述算法 f b d 怎么构造优的画法，最后给出算法f b d 的一些计算结果。 2 1 旋转方案 旋转方案由e d m o n d s 于1 9 6 0 年首先提出，后来y o u n g s 又进行了详细的讨论。 让g 是一个非平凡的连通图，顶点集合h g ) = v l ，v 2 ， 。刘于g 在表面上的一 个任意2 - c e l l 嵌入存在唯一的p t u p l e ( ”1 ，”2 ，p ) ，这里对于f = l ，2 ，口，表示邻接 于顶点v ，的顶点们的下标的循环排列。相反，对于每一个p - t u p l e ( n i ， 2 ，j r 力，在某 表面上存在唯一的2 - c e l l 嵌入，使得邻接于顶点v ，的顶点的下标们以顺时钊顺序排列， 正如”，所捕述。 举例，如图2 1 所示给出了一个图的平面嵌入。从图2 1 可以得到关于每一个顶点 的j 1 唳时管| - 1 f 歹0 。 l = ( 2 ，4 ，6 ，2 )7 2 = ( 3 ，4 ，1 ，3 ) 循环图q 峨( i ，料诸0 交叉数 ”3 ：( 2 ，4 ，2 )y ( 4 = ( 3 ，5 ，1 ，2 ，3 ) ”5 = ( 4 , 6 ，4 )”6 = ( 5 ，1 ，5 ) 反过来，根据这些排列能够得到图的边数目，能够得到图的嵌入的面有哪些边组成。 例如： ( 1 ) 从边( 1 ，2