交叉数的综述摘要：综述了图的交义数研究诞生6馀年来，国内外的研究进展和若十结 果.包括了以下4个方面：一些具有特殊结构图类的交义数；交义数的下界；与 一些参数相关的交义数性质；以及其他类型的交义数.关键词：图；画法；交义数Survey of the crossing number of K1,12,nAbstract : This paper gave a comprehensive review of the studies of the crossing number in China and in the world during the last 60 years ,from the following 4 aspects : The crossing number of some particular graphs ， the lower bound of crossing numbers parameters related to crossing numbers and crossing numbers of other typesKey words : graph ； drawing ； crossing number图的交义数概念是Pual Turan根据其于1944年在Budapest附近的一个砖厂 所碰到的实际难题提出的，它是图的一个重要参数，研究图的交义数不仅具有重 要理论意义，而且有较强的现实意义，如VLSI中的布线问题，草图的识别与重画 问题等.多年来，国内外许多学者都研究过图的交义数问题.但是到目前为止， 还没有有效的算法能确定任意图的交义数. 事实上，Garey和Johnson已经证明了确定一个图的交义数是NI完全问题.正是由于其难度较大，故国内外在这方面 的研究进展缓慢，研究对象也主要集中在一些具有特殊结构图的交义数的具体数 值或者研究其上界、下界和研究图的交义数的一般性质上. 具体来讲，主要分为以下四个部分.引言：我们在这里所考虑的图G匀指简单连通图，顶点集为V,边集为E. 一个图GM在平 面上，若满足如下条件：(1) 任何两条相交义的边最多交义一次；(2) 边不能自身相交；(3) 有相同端点的两条边不交义；(4) 没有三条边交义于同一个点.则称此画法为G勺一个好画法.若G勺某个好画法用 软表示，则在画法D下，G书 边与边的所有交义数称为在画法D^G勺交义数，用cf(G)表示.一个图G勺交义数，用cf(G)表示，定义为如下一个值： cr(G) min{g(G)}，其中最小值min取遍G勺所有好画法D.若图G&平面上的一个画法D荷足cj(G) crG，则称D为图 G的一个最优画法.图的交义数概念是Pual Turan根据其于1944#在Budapest附近的一个砖厂所碰 到的实际难题提出的，它是图的一个重要参数，研究图的交义数不仅具有重要理 论意义，而且有较强的现实意义，如VLSI中的布线问题，草图的识别与重画问题等.多年来，国内外许多学者都研究过图的交义数问题.但是到目前为止，还没 有有效的算法能确定任意图的交义数. 事实上，Garey和Johnson已经证明了确定一个图的交义数是NI完全问题.正是由丁其难度较大，故国内外在这方面的研 究进展缓慢，研究对象也主要集中在一些具有特殊结构图的交义数的具体数值或 者研究其上界、下界和研究图的交义数的一般性质上 .一、一些具有特殊结构图类的交叉数：A、 完全图Gu处文献中猜想完全图Kn的交义数cr(Kn)为Z(n)=1 n 史 堂2 土 4 2 2 2 2其中，对任意实数，x表示不超过x的最大整数.B、 完全二部图我们知道，P. Turan的砖厂难题事实上等价丁确定完全二部图 Km,n的交义数.Zarankiewicz 断言，他“证明” 了 cr(Kmn) — 虬^ n -~-,当我们2 2 2 2把n个顶点放在Xffl的正半轴上，把个顶点放在尚由的负半轴上，把m个2 2 2顶点放在洛由的正半轴上，把-个顶点放在洛由的负半轴上，用直线连接X5由和Y 2轴上的相应顶点就可以得到 Km,n的一个画法，其交义的数目就等丁 Zarankiewicz猜想中所确定的交义数，并记Z(m,n) cr(Km,n)(其中n表示不小丁 n的最小整 数).在1969年，Gu妙现Zarankiewicz的证明有误.后来，Kleitman证明了上式对丁min{m, n) <6成立，并且得出,如果cr(K m,2s 1) Z(m,2s 1),则能得到cr(K m,2s) Z(m,2s) . Woodall证明了当 m=7 n< 10时上式也成立.C、 完全二部图对丁完全三部图的交义数，早在上世纪八十年代就有所研究， K.Asamo证明了cr(Ki,3,n) Z(4, n)己，沮5) Z(5,n) n ,后乂有黄元秋教授证明了cr(Ki,4,n) n(n 1) Z(5,n) 2 ；，再后来梅汉飞教授与黄元秋教授合作证明了 cr(K1,5,n) Z(6, n) 4 n。
2005年，黄元秋教授与赵霆雷教授合作证明了cr(K2,4,n) Z(6, n) 2n ,并且在假设Zarankiewicz猜想对丁 m 7成立的情况下，黄元秋教授与赵霆雷教授确定了 cr(K16n) Z(7, n) 6 -,其后不久乂在假设2Zarankiewicz猜想对丁 m=8,m=9成立的前提下，确定了心孙，心时的交义数，黄元 秋教授与王晶在假设Zarankiewicz猜想对丁 m=11的情况下，证明了K1,m,n的交义数，并得到了,cr(K110n) Z(11,n) 20 -，何小年、王晶以及P. T. HO虫立研究了完全三部图2 n 1 n cr (K1,2M ,n) M -—如果 Zarankiewicz猜想对丁 m=2M +1成立，贝Un M -2D. 笛卡尔积图两个图Gl和G2勺笛卡尔积图，用G1X G2^示，它的顶点集为V(G1X G2)=V(G1)XV(G2),边集为E(Gi G2)={( U1,U2)(V1,V2)|U1=V1,U2V2 E(G2),huo U2=V2,u〔V1 E(G〔)}.笛卡尔积图是一类重要的图，由丁在结构上具有很特殊的可重复性， 所以该类图交义数的研究一直吸引着国内外广大学者的注意.Harary等给出了的一个Cm Cn画法，使得Cm Cn在此画法下的交义数为(m 2)n，并由此猜想c「(Cm Cn) (m 2)n,( n m),从交义数的定义可以很容易得到，要确定图的交义数，主要在丁确定其下界. 所以Cm CN交义数的下界也是一个重要的研究方向.Salazar证明了当m >3时，Cm Cn的M-交义数满足|imbM(Cm Cn) 1n (m 2)n1998年，Shahrkhi 证明了 c「(Cm Cn) 四，2000年，sa1azar 改进了这一结果,9得到了 cr(Cm Cn) (^—2皿；Salazar 和JUarez、salazar 证明了在一些有限制 3条件的特殊画法下，Cm Cn的交义数至少有(m 2)n ； Salazar Ugalde证明了对丁任意的 ,如果说够大，且当n> m寸，有cr(CM Cn) (0.8 )mn .2004年，Glebsky salazar 证明了 cr(CM CN) (m 2)n,n m(m 1),这证明了当n充分大时，猜想cr(CM Cn) (m 2)n,(n m)是成立的，使得圈与圈的笛卡 尔积图交义数的研究有了极大的进展.除了圈与圈的笛卡尔积图的交义数， 还有其他笛卡尔积图G H的交义数也一直 吸引着人们的关注.具体可分为3个方面：(1)G和静8是阶数比较小的图(2)G是阶 数较小的图，而 出某一类型的图.(3)G和厝8是某一类型的图.这些类型的笛卡 尔积的交义数也取得了很大的效果.二、交叉数的下界对任意的简单图G=( V(G) , E(G)) , V(G)|, |E(G),目前很多学者也致力丁研究用图的点数 和边数 来确定一般图交义数的下界. Euler公式告诉我们，对任意的平■面图有 3 6;在非平■面图中，每增加一条边至少会有一个新的交义产生.因此，可以马上得出 cr(G) 3 6 .1973年，Erdos和Gu0别猜想当 较大时，存在一个正数C,使得：cr(G) C /z 。
Ajtai 和Leighton 分别独立证明了当 4 时，有C — . Pach64等证明了当 15 /2时C .随后，Pach^人乂证明了当 103 /16时，33.75土 1有C 31.08三、与一些参数相关的交叉数性质直接确定某个图的交义数是很困难的，所以人们也常常会依据图的某些参数 来研究图的交义数的性质.A、 临界交义数如果cr(G) k,而e E(G),有cr(G e) k ,则称阈k-交义临界图令k ={G|G是k-交义临界图}B、 正则图的交义数正则图交义数的研究是一个比较热门的方向. Richter证明了，一个交义数> 2的3-正则图含有交义数为2的子图.McQuillan , Richter和Hlineny也都对3- 正则图的交义数进行了研究.杨元生等用计算机编程，给出了阶数 12的所有四正则图的交义数.C、 图与其线图的交义数图G勺线图L(G)是指顶点集为E(G)的图，其中两个顶点相连当且仅当它们在 G 中为相邻的边.因为图G勺线图L(G)包含一个子图同胚丁图G,所以一般地有：cr(G)< cr(L(G)) . 1962年，Sedlacek得到平面图G勺线图L(G)是平面图的充分必要条 件.1979年，Kulli , AkkaO Beineke获得了平面图的线图的交义数为1的充分必 要条件；1997年，Akka, Jendrol , Klesc等研究了平面图的线图的交义数为 2的 情形.对于其他情形的研究一直没有进展.2001年，Jendroi和Klesc确定了非平 面图的线图的交义数为1的充分必要条件，200弭，黄元秋和赵霆雷给出了图及 其线图的交义数都是k的充分必要条件(待发表).四、 其他类型的交叉数其他类型的交义数还包括有直线交义数， 对交义数，奇交义数等，关于交义数的研究远不止这些，需要不断地发现以及探索。
五、 参考文献：【1】TURAN P. A note of welcome[J]. J Graph Theory, 1977(1)： 7-9.【2】GARARY M R , JOHNSON D S. Crossing number is NIcomplete[J]. SIAMJ Algebric Discrete Methods, 1993(4)： 312. 316.【3】GUY R K . Crossing numbers of graphs[M]//Graph Theory andApplications. LNM 303 . Heidelberg： Spring— Verlag, 1972： 111-124.【4】RICHTER R B . THOM ASSEN C . Relations between crossing numbers of complete and com plete bipartite graphs[J] American Mathematical Monthly,1997, 104(2): 137-137.【5】DE KLERK E , M AHARRY J , PASECHNIK D V , et a1. Im proved 。