（基础数学专业论文）关于图的交叉数研究(1).pdf

i v 硕士学位论文 y 中文摘要 m r g a r e ya n dd s j o h n s o n 已经证明确定图的交叉数是一个n p 完 全问题( 见文献 4 ) ，因为其难度，我们能够确定交叉数的图类非常 少，在许多情况下，即使找出图的交叉数的一个好的上界或下界也 是非常困难。目前，很多文献都是在研究一些特殊图类的交叉数， 例如：完全图，完全二部图，完全三部图，循环图及笛卡尔积图等。 本文研究某些简单图与路，星图的笛卡尔积图的交叉数和完全三部 图的交叉数。 第一章：基本概念和性质，介绍了阅读本文所需要的预备知识其 中主要包括交叉数的概念，并介绍了在后面文章中会出现的一些相 关概念、性质、引理以及常用到的一些定理而部分使用较少的概念 等我们放到了具体的章节中去交代。 第二章：我们确定了6 个7 阶图与路的笛卡尔积图的交叉数； 第三章：我们证明了4 个五阶图与星图的笛卡尔积交叉数； 第四章：我们求出了完全三部图k m ，n 的交叉数 这里，& 与& 分别表示边为5 及n 的星，r 表示边长为n 的 路 关键词：图；画法；交叉数；笛卡尔积；完全三部图 关j ：图的交叉数研究 a b s t r a c t d e t e r m i n g t h ec r o s s i n gn u n l b e r so f 萨a p h sh a sp r o v e dt ob en p c o m p l e t e t h e r ea r eaf e we ) ( a u c tr e s u l t so nt h ec r o s s i n gn u m b e r so f 伊a p h sc l a s sb e c a u s e o fi t sc o m p l e x i t y i nm a n yc a s e s ，e v e ni ti sv e r yd i 伍c u l tt of i n do u t9 0 0 db o u n d s o ft h ec r o s s i n gn u m b e r so fg r 印h y n o w ，m a n ya r t i c l sa r ef o c u so ni n v e s t i g a t i n g t h ec r o s s i n g 耻m b e r so fc o m p l e t eg r 印h 8 ，c o m p l e t eb i p 盯t i t eg r 印h s ，c o m p l e t e t r i p 盯t i t eg r a p h s ，c y c l i c o r d e r 留a 曲sa n d s o m es p e c i a l 口印h 8c a r t e s i a np r o d u c t sg r a p h s ，a n ds oo n i nt h i sp 印e r ，w es t u d yt h ec r o s s i n gn u m b e r so ft h e c a r t e s i a np r o d u c 乞g r a p ha n dc o m p l e t et r i p a r t i t eg r a p h j i nc h a p t e ro n e ，w eg i v et h ec o n c e p t i o no fc r o s s i n gn u 血b e r ，s o m ei n t e r r e l a t e dc o n c e p t i o na n ds o m ei n t e r r e l a t e dc h a r a c t e ro nt h ec r o s s i n gn u h l b e r i nc h 印t e rt w o ，w ed e t e r m i n et h ec r o s s i n gn u 1 b e ro ft h ec a r t e s i a np r o d u c t o ff i v eg r a p h so n6 一v e r t e xw i t hp a t h i nc h a p t e rt h r e e ，w ed 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 ec a r t e s i a np r o d u c t so f & a n d5g r a p h so n6 一v e r t e xw i t hp a t h 户k i nc h a p t e rf o u r ，、ed e t e r m i n et h ec r o s s i n gn u m b e ro ft h et h ec o h l 】p l e t e t r i p 盯t i t eg r 印hc r ( 甄，m ，n ) ，w h e r e & ，鼠a n dra r et h es 七缸w i t l ：1 矗v ee d g e s ，n e d g e sa n dt h ep a t hw i t hne d g e s ，r e s p e c t i v e l y k e y w o r d s ：g r a p h ；d r a w i n g ；c r o s s i n gn u m b e r ； c a r t e s i a np r o d u c t ；c o m p l e t e t r i p a u r t i t eg r a p h 心 i j 关于图的交叉数研究 y9 13 二97 前言 图的交叉数是近代图论中发展起来的一个重要概念，自从2 0 世 纪7 0 年代初匈牙利数学家t u r 缸根据其在一个砖厂碰到的实际难题 ( m 舂n sb r i c l 【y a r dp r o b l e m ) ( 见文献 1 】，【2 】 3 ) ，从而提出了交叉数的概 念以来，图的交叉数逐渐成为国际上一个非常活跃的分支，使得很 多图论专家对这方面进行了深入研究 研究图的交叉数不仅具有重要的理论意义，而且有较强的现实 意义，在许多领域有着非常广泛的应用，例如： ( 1 ) 工业上电子线路板设计中的布线问题； ( 2 ) 草图的识别与重画问题，具有比手写汉字识别应用更为广泛 的应用领域； ( 3 ) 软件开发过程中文档部分的e r 图( 实体联系图) 等的自动 生成； ( 4 ) 生物工程d n a 的图示； ( 5 ) v l s t 中的圈布局问题等 然而，一般地，确定图的交叉数又是十分困难的，文献【4 证明 了确定图的交叉数问题属于n p 一完全问题由于其难度，目前国际 上对交叉数的研究比较局限，主要集中在以下几个方面： 1 一些较特殊的具体图类的交叉数，其中一些给出了交叉数上 下界或猜想，但是具体结果甚微，主要有 ( 1 ) 完全图： 国际上关于完全图的交叉数有一个重要的猜想，即： 凹( ) ：l 詈儿孚儿学儿字j ，最新的结果是s a l a z 盯证明了等号对于 n 1 0 成立( 见文献【5 】) 这里，c r ( g ) 表示图g 的交叉数；对任意实 数n ，h 表示不超过n 的最大整数 ( 2 ) 完全二部图： 实际上，t u r 矗n 的”砖厂问题”等价于确定完全2 一部图m 的交叉数后来，z a r a n k i e 谢c z 在文献 6 】中”证明”了c r ( ，。) 硕士学位论文 【詈儿警儿警儿孚j ，( m n ) 不久， m n g e l 和k a i n e n 各自独立发现 z 盯a n k i e 谢c z 在文献 6 】中的证明有误( 参见文献【7 】) ，因而确定完全2 一 部图m 的交叉数问题目前仍然是一个公开问题习惯上把上式称 之为z a r a n k i e 讯c z 猜想，把上式右端记为z ( m ，n ) k 1 e i t m a l l 在1 9 7 1 年 证明了等号对于m 讯( m ，n ) 6 成立( 见文献【8 ) w b o d 础1 于1 9 9 3 年证 明了对m = 7 且n l o 成立( 见文献 9 ) ，直到目前为止还未看到关于。 此方面的新结果 ( 3 ) 完全三部图： 目前国内外对完全三部图交叉数的证明都还建立在完全二部图 交叉数的基础之上，因此，这方面的结果也较少 上世纪八十年代，k a s a n o 证明了c r ( 皿1 3 。) = z ( 4 ，礼) + 吲， 凹( 施3 。) = z ( 5 ，n ) + n ( 见文献【1 0 】) 此后关于完全三部图也是一直没 有新结果最近我的导师黄元秋教授独立证明了c r ( 硷4 i 。) = 他( 佗一1 ) = z ( 5 ，n ) + 2 吲( 见文献 1 1 】) ，后又与梅汉飞教授合作确定了c r ( k 5 ，。) = z ( 6 ，几) + 4 引( 见文献【1 2 】) 这些结果都是建立在z 甜a n k i e 硝c z 猜想 对于m i 礼( m ，礼) s6 成立的事实基础上2 0 0 5 年初黄元秋教授又 在假设z a r a n k i e w i c z 猜想对于m = 7 ，9 ，1 l 成立的前提下，确定了 凹( 所6 。) ，凹( 甄肋) ，盯( 1 0 ，。) ( 见文献 1 3 - 【1 5 ) ，在这些文献中都采用了 新的证明方法 ( 4 ) 笛卡尔积图： 对于猜想：c r ( c m g ) ( m 一2 ) 扎，( m 礼) ，m n g e i s e n ，b e i n e k e ，k l e 吾芒 和r j c h t e r 等人证明等号对m = 3 ，4 ，5 ，6 ，7 成立( 见文献【1 6 】一【2 1 】) n a d i n e c m y e r s 在文献 3 】中对这个猜想的起源，发展过程以及现状等都做 了较为详尽的介绍从二十世纪后期起，m k 1 西芒等人开始对阶数较 小的图与路，星，圈的笛卡尔积图的交叉数的研究( 见文献 2 2 】- 【3 1 ) 其中所有不大于5 阶的简单图与路的笛卡尔积图的交叉数都已经被 确定最近我的导师黄元秋教授与他的学生合作确定了一些阶数大 于5 的简单图与路、星、圈的笛卡尔积图的交叉数( 见文献 3 2 - 【3 5 】) 2 有某种特点的图的交叉数的一些性质 如临界交叉数，线图的交叉数，3 - 正则图的交叉数，交叉数的 一 关于图的交叉数研究 奇偶性等 3 交叉数与图的其他参数的关系 如盯( g ) 与( l ( g ) ) 的关系，其中l ( g ) 表示图g 的线图； 图的交叉数与图的亏格的关系，以及同一类图在不同亏格的曲 面上的交叉数； 图的交叉数与图的树宽的关系等 大部分的研究主要集中在，确定交叉数上，证明方法和技巧也 是越来越多m k l e 芒等确定了许多对于阶数不超过5 的图与路， 星，圈的笛卡尔积图的交叉数( 见文献f 2 2 h 3 1 】) 本文受到( 1 0 】- 【1 5 ， 2 2 _ 3 1 】) 的启发，发展和运用他们的某些方法确定一类笛卡尔积图和 完全三部图的交叉数推广了有关方面的结果 关于图的交叉数研究 第一章引言 一个图g 是指一个有序三元组( y ( g ) ，e ( g ) ，矽g ) ，其中v ( g ) 是非 空的顶点集，e ( g ) 是不与( v ( g ) 相交的边集，而惦是关联函数，它 使g 的每条边对应于g 的无序顶点对另外r 表示边长为n 路， r 有n 条边的星髓g 表示边长为n 的圈，图g 的交叉数是指把 图g 画在平面上时出现的最小交叉数。本文未说明的概念均同文献 ( 2 2 】) 2 3 ， 3 6 】) ；且无特别说明所涉及图均指连通简单图。 下面给出相关交叉数的定义及笛卡尔积的定义。 定义1 图g 在平面上的一个画法是指把图的顶点画在表面上的 结点，把图的边画为表面的弧 定义2 图g 在平面上的一个好的画法是指图g 在表面上的画 法满足以下四个条件： 1 ) 连接同一个结点的任意两条边不相交； 2 ) 边不能自身相交； 3 ) 任何两条相交的边最多交叉一次； 4 ) 没有三条边交叉于同一个点 根据定义2 图1 1 中的前三种画法是不会出现的，第四种画法 是不允许的 图1 1 定义3 图g 在平面上的一个最优画法是指图g 在表面上的具有 最少交叉数的好的画法，这个最少交叉数目即为图g 在该表面上的 交叉数 硕士学位论文 定义4 图g 在平面( 或球面) 上的交叉数称为图g 的交叉数， 记为c r ( g ) 定义5 完全二部图，n ( 仇6 ) 的交叉数在文献( 8 】) 中给出： 凹( ，n ) = 刚孚删孚】 ( 1 1 ) 这里旧指不超过z 的最大整数 定义6 两个图g ，和g 。的笛卡尔积图用g 。g ：表示，它是这样的 图：点y ( g 1 g 2 ) = y ( g 1 ) y ( g 2 ) ；边集e ( g l g 2 ) = e ( g 1 ) 且= ) 下面我们解释相关术语和记号。设g 为图且顶点集为y 和边集 为e 如果a e ( 或a y ) ，我们用g ( a ) 表示由a 导出的g 的子 图。设x 和y 是顶点集y 中两个无关联的子集，我们用取y 表示 所有与x 和y 相关联的边集。对于顶点刀，玩表示所有与顶点口 关联的边。 设图g 且边集为e ，是g 的一个好画法，4 和b 是图g 的 两个边子集，记号盯西( a ，b ) 表示画法矽中由a 中边与b 中边产生的 交叉的个数。若a = b ，凹咖( a ，b ) = 盯咖( a ) 。显然盯咖( g ) 与盯毋( e ) 本质 上是同一个值。 若g 1 和g 。是两个边不相交的图，那么g 。u g ：表示点集为y ( g - ) u y ( g 2 ) 和边集为e ( g 1 ) ue ( g 。) 的图设d 为一个图g 的好画法，我 们用凹d ( g ) 表示图g 在画法d 下的一个交叉数，若g 。和g 2 为图 g 的两个子图，我们用c r d ( g 。，g 。) 表示g ，与g 。在画法d 下的交叉 数，易得到如下公式： ( 见文献 6 】) 凹d ( g lug 2 ) = c 功( g 1 ) + 凹d ( g 2 ) + c r d ( g 1 ，g 2 ) f 1 2 ) 凹d ( g 3 ，瓯ug 2 ) = 凹d ( g 3 ，g 1 ) + c r d ( g 3 ，g 2 ) 、7 这里g 1 ，g 2 ，g 3 是边互不相交的g 的子图 在两个图f 和h 中，对于某些边的加入或抹平2 度点( 均可反复 多次) 这样的过程使得这两个图同构，则称f 和h 同胚，记为f 日 易知同胚的两个图同具有如下的性质： 关于图的交叉数研究 性质1 若f 日，则c r ( f ) = c r ( 日) 性质2 若日为图g 的子图，则c r ( 日) c r ( g ) 证：设咖是图g 的一个好画法，使( g ) = 盯( g ) ，则咖自然诱导 它的子图h 的一个画法记为妒1 日，盯妒1 日( 日) 凹( g ) = 凹( g ) ，由交叉数 的定义， 凹( 日) 凹( g ) 引理1 设画法d 是g 的一个最优画法，若在画法d 中增加若干 条边( 没有增加交叉数) 得到一个新的图g 7 和一个新的画法d ，则 d 7 是g 7 的一个最优画法 证明：设图g 在画法d 下有k 个交叉，则有凹d ( g ) = 七= c r ( g ) ， c 砀，( g ) = 忌，凹( g ) c r ( g 7 ) 尼，所以c 7 ( g 7 ) = 七，即d 7 是g 7 的一个 最优画法 0 关于图的交叉数研究 第二章 七阶图q ( j = 1 ，2 ，3 ，4 ，5 ，6 ，7 ) 与路r 的笛卡 尔积交叉数 m k 1 e 酌等确定了许多对于阶数不超过5 的图与路、星、圈的笛 卡尔积图的交叉数，近段时间，我的导师黄元秋教授与他的学生合 作确定了一此六阶图与路、星，以及星图与轮的笛卡尔积交叉数( 见 文献 3 2 】一 3 5 ) ，本章受到他们的启示，发展和运用他们的某些方法确 定了一类7 阶图与路的笛卡尔积交叉数，推广了有关方法的结果。 我们假定本章g j ，1 j 6 ，分别是具有7 个点的如下图形： 3 2 1 7 3 g 1 4 g 11 2 23 7 g 2 2 67 6 55 7 2 4 g 3 4 6 17 g 5g 6 图2 1 ：6 个基本图 本章的主要结果是如下定理： 定理设g j 为上述所示的图，r 是长为几的路，则有 ( 1 ) 当j = 1 时，盯( g j r ) = 3 ( n 一1 ) ； ( 2 ) 当歹= 2 时，凹( 岛r ) = 4 ( 佗一1 ) ； 6 l 5 6 7 硕士学位论文 ( 3 ) 当歹= 3 时， ( 4 ) 当歹= 4 时， ( 5 ) 当歹窖5 时， ( 6 ) 当歹= 6 时， 凹( q r ) = 2 ( n 一1 ) ； 凹( q r ) = 几一1 ； c 7 - ( 岛r ) = 2 礼； 盯( q r ) = 2 ( n 一1 ) 注意到在笛卡尔积图g j r 中：它有7 ( 佗+ 1 ) 个顶点，佗+ 1 个 拷贝q ，( 用g ；表示，o i 佗) ，以及7 个拷贝r 为了下面证明的 方便，在q r 中，我们让每个拷贝q 中的边着红色，其余的边 ( 即每条长为礼的路拷贝r ) 着蓝色 2 1当歹= 1 时，定理的证明 引理2 1 设d 是g 。r ，n 1 的一个好画法，在画法d 中，对每一 个g i ( o i 礼) ，若g i 最多有二个交叉点，则有c r d ( g ，r ) 3 ( 仡一1 ) ( b ) 图2 2 ：由画法d 导出的子图日谢+ t 的3 种可能画法 证明：由引理的假设知，在画法d 下两个不同的g ；和q 的红 色边不能彼此交叉，否则g ；( 硝) 有至少3 个交叉点( 因为磷( g i ) 内 部红色边至少产生两个交叉，还有当连接q 和q _ 1 或者甜1 ( q 和g j - 1 或者暖“) 时与篮色边产生的) ，与假设矛盾又由引理的假 设知，在画法d 下g 2 ，g ；，g 2 ，q ，q ，g n 位于由q 导出的同一 个区域中，否则我们假设g 和g 5 ( 七z ) 位于由g ；导出的不同区域 关于图的交叉数研究 中( 至多两个区域) ，因为子图g ；导出的平面成数个区域，使得任何 两个相邻区域至多有4 个共同的g ；的顶点，但在这样的画法d 中 g t 与连接g 到g 5 的7 条路至少有7 个共同交点，其中至多有4 个 交点为q 的顶点，则q 的边上至少有3 个交叉点，这也与引理的 假设矛盾。 现在我们来考虑由d 导出子图，州的画法讲州，i _ o ，1 ，2 ，n 一 2 ，有如下三种情形： 情况1 在画法d 钳+ z 中，g “的边没有交叉，又由引理的假设知 画法如图2 2 ( a ) 所示那么法画d 印+ t 导出的平面区域中，每一个区域 边界( 或同一个区域) 至多有o ，k ，q + 1 ) 吨+ 1 ，e 州，“。和吼+ 。( g 1 的顶 点) 中的4 个。现在我们考虑由d 导出的子图一2 的画法讲件2 ，i o ，1 ，2 ，几一2 】- ，在画法莎m 中，日m 一2 一硝“的边与印，州的边 至少有三个交叉点。 情况2 在画法，m 中，g p l 的边有一个交叉，又由引理的假 设知画法如图2 2 ( b ) 所示那么法画斗- 导出的平面区域中，第 一个区域边界( 或同一个区域) 至多有o m ，t ，q + 1 ，“- ，e m ，“- 和 吼+ ，( g ，1 的顶点) 中的5 个。现在我们考虑由d 导出的子图抖2 的 画法，m ，i o ，1 ，2 ，n 一2 ，在画法d i ，啪中，印+ 1 ，m g 卜1 的 边与驴j + 1 的边至少有二个交叉点。 情况3 在画法砂中，g p l 的边有两个交叉，又由引理的假 设知画法如图2 2 ( e ) 所示那么法画，件，导出的平面区域中，每 一个区域边界( 或同一个区域) 至多有n m ，玩+ 1 c m ，如+ ，e 州，五+ 和 仇+ 。( 磷“的顶点) 中的6 个。现在我们考虑由d 导出的子图印，件2 的 画法d i ，啪，i o ，1 ，2 ，n 一2 ，在画法，m 中，印+ 1 ，m g p l 的 边与h t 件的边至少有一个交叉点。 因而当i 遍历o ，1 ，2 ，几一2 时，画法d 至少有3 ( n - 1 ) 个交叉点d 定理2 1c r ( g 1 r ) = 3 ( 佗一1 ) ，仡1 硕士学位论文 首先，我们构造一个画法d 使得盯d ( g 。r ) = 3 ( n 1 ) 需要构 造的画法如图2 3 所示： 八 jf 。 。i ，。 心 。t 一- 图2 3 ：g 。r 的一个所需画法 证明：由交叉数的定义知凹( g 。r ) 3 ( 几一1 ) ，n 1 现在我们用 数学归纳法来证明相反的不等式，当札= l 时，g ，p 竹为平面图， c 7 ( g 1 只) = o ，命题成立，假设当n = 七( 后1 ) 时，命题成立即有 c 7 ( g 1 最) 3 ( 忌一1 ) 我们再假设他= 尼+ 1 时，有一个g 1 r + 1 的 好画法，使盯( g ，r + 1 ) 3 后，由引理2 1 知，必有某个i 使g j 有三 个交叉点，那么我们删除g 的所有边得到一个图同构于g ，最或 拥有一个子图同构于g 。r ，而且这个图有少于3 ( 忌一1 ) 个交叉点 的画法，这与我们的归纳假设矛盾，因而盯( g ，r ) = 3 ( 礼一1 ) 0 2 2当歹= 2 时，定理的证明 定理2 2c r ( g 2 r ) = 4 一1 ) ，礼1 关于图的交叉数研究 亿 。 j ( f 心 多 。f 。 i 图2 4 ：g 。r 的一个所需的画法 证明：由图2 4 的画法知，凹( g 2 r ) 4 ( 佗一1 ) ，礼1 ，由于 g 。包含一个子图同构于星图& ，所以g 。r 包含一个子图同构于 & r ，而由文献 8 】知r = 4 ( 扎一1 ) ，礼1 ，再结合性质2 知 c r ( g 8 r ) 4 ( n 一1 ) ，因而c r ( g 2 r ) = 4 ( 礼一1 ) 0 2 3当歹= 3 时，定理的证明 定理2 3c 7 ( g 3 r ) = 2 ( 佗一1 ) ，礼1 f 。f 。 i l 多 f l 1 图2 5 ：g 3 r 的一个所需画法 证明：由图2 5 的画法知，c r ( g 3 r ) 2 ( n 一1 ) ，礼1 由于g 3 包含一个子图同构于星图& ，所以g 。r 含有同构于r 的子 图由文献 4 】) c r ( & r ) = 2 ( 几一1 ) ，n 1 ，再结合性质2 ，我们得到 凹( g 3 r ) 2 ( 几一1 ) 即可得到c 7 ( g 3 r ) = 2 ( 礼一1 ) 口 1 0 硕士学位论文 2 4当歹= 4 时，定理的证明 定理2 4c 7 ( g 4 r ) = n 一1 ，n 1 。厂、 。 i 图2 6 ：g 4 r 的一个所需的画法 证明：由图2 6 的画法知，盯( g 4 r ) s 佗一1 ，礼1 ，由于g 4 包含一个子图同构于星图岛，所以g 4 r 包含一个子图同构于 岛r ，而由文献 2 9 c r ( & r ) = 礼一1 ，n 1 ，再结合性质2 知 凹( g 4 r ) 礼一1 ，因而盯( g 4 r ) = n 一1 口 2 5当歹= 5 时，定理的证明 定理2 5 凹( g 5 r ) = 2 n ，亿1 图2 。7 ：g 。r 的一个所需画法 关于图的交叉数研究 证明：由图2 7 的画法知，盯( g 5 r ) 2 礼，礼1 ，由于g 5 包 含一个子图同构于二部图鲍。，所以g 。r 包含一个子图同构于 恐，3 r ，而由文献 2 7 】知凹( 飓，3 r ) = 2 n ，礼1 ，再结合性质2 知 盯( g 5 r ) 2 凡，因而c 7 ( g 5 r ) = 2 n 口 2 6当歹= 6 时，定理的证明 定理2 6c r ( g 6 r ) = 2 ( 几一1 ) ，他1 。f 7 。 。q 。 i 。 图2 8 ：g 6 r 的一个所需的画法 证明：由图2 8 的画法知，盯( g 6 r ) 2 ( n 一1 ) ，札1 ，由 于g 6 包含二个子图同构于星图岛，所以g 。r 包含二个子图同 构于& r ，而由文献 2 9 】知岛r = 他一1 ，n 1 由性质2 知 c 7 ( g 6 r ) 2 ( 几一1 ) ，因而c r ( g 6 r ) = 2 ( n 一1 ) 0 关于图的交叉数研究 1 3 第三章五阶图与星图的笛卡尔积交叉数 从2 0 世纪后期开始，m k 1 e 酌等开始对阶数较小的图与路、星、 圈的笛卡尔积交叉数进行研究，其中在文献t h ec r o s s i n gn u m b e ro f c 射t e s i a np r o d u c t so fp a t h sw i t h5 一v e r t e xg r a p l l s 中列出所有五阶图的 画法以及与路、星、圈的笛卡尔积交叉数的已知与未知的结果。本 章确定了4 个5 阶图与星图的笛卡尔积交叉数填充了此文献中列出 的四个空白。 本章我们总是假定g f ，1 歹4 ，分别是具有5 个点的如下图形： g 1g 2 g 3g 4 图3 1 ：4 个基本图 现在我们定义一个新的图风，巩是由蚝，n 加上5 条边( 包含有 礼个5 度点，5 个( n + 2 ) 度点和6 n 条边) 组成的图形( 如图3 2 所示) 我 们现在来考虑图3 1 中的g 。，从图3 2 很容易得知：巩= g 。u 拖，n 。 多 蕙荔 图3 2 ：珥。 1 4 硕士学位论文 定理3 1 凹( 风) = 4 引 孚】，扎1 证明：由图3 - 2 的画法知，仃( 凰) 4 吲 孚】，佗1 又因为含 有一个子图同构于蚝，n ，由文献 8 】知：c r ( 蚝，n ) = 4 吲【孚】，礼1 再 结合性质2 ，我们得到盯( ) 4 嘲 孚】因而c r ( ) = 4 【孚】 0 定理3 2c r ( g 1 & ) = 4 等】 譬】，佗1 证明：由图3 3 的画法知， 凹( g ，& ) 4 詈 【孚】，礼1 又 因为g 。鼠含有一个子图同构于巩，由定义3 1 知：凹( 巩) = 4 豳【孚 ，礼1 再结合性质2 ，我们得到盯( g & ) 4 嘲【孚】，因 而c r ( g & ) = 4 刚孚】 0 图3 3 ：g ，品的一个所需画法 定理3 3 凹( q & ) = 扎( n 一1 ) ，n 1 ，歹= 2 ，3 图3 4 ：g 。& 的一个所需画法 关于图的交叉数研究 1 5 由图3 4 的画法知，c r ( g 2 & ) n ( 扎一1 ) ，他1 又因为g 2 含有 一个子图同构于星图& ，所以g 2 & 含有一个子图同构于& & 由文献 1 1 】知：c r ( & & ) = n ( n 一1 ) ，礼1 再结合性质2 ，我们得到 c r ( g 2 ) 礼( n 一1 ) 因而盯( g 2 & ) = n ( 礼一1 ) 在图3 4 中连接每 一对o ；和玩( i = 1 ，2 ，礼) ，但不增加交叉数，即可得到g 3 鼠，再结 合引理1 得： c r ( g 3 & ) = 礼( 礼一1 ) ，礼1 口 下面我们又定义一个新的图形r ，r 是由风，n 加上6 条边( 包 含有n 个5 度点，3 个( n + 2 ) 度点，2 个( 他+ 3 ) 度点和6 礼+ 1 条边) 组成的图形( 如图3 5 ( a ) 所示) 我们现在来考虑图3 1 中的g 4 ，从 图3 5 ( a ) 很容易得出r = g 4u 蚝设，江1 ，2 ，n 是蚝，他的一个 子图，是由风n 中的5 条边，g 4 中的5 个点和一个o 。( 1 i n ) 点 组成( 如图3 5 ( b ) 所示) 。因此有： 几 r = g 4u 蚝，n = g 4u ( ut ) ( 3 1 ) t = 1 ( a ) ：r 图3 5 ( b ) ：t 。 定理3 4c r ( r ) = 4 嘲 孚】+ 吼n 1 证明：根据图3 5 ( a ) 的画法知凹( r ) 4 嘲 孚 + 嘲，n 1 现在 我们只需证明相反的不等式即可。假设有一个画法咖使 c ( r ) 4 号 孚】+ 吲 ( 3 2 ) 1 6 硕士学位论文 根据( 1 1 ) ，( 1 2 ) ，( 3 1 ) 式得： n，l c ( r ) = c r 咖( g 4 ) + 盯咖( up ) + 盯妒( g 4 ，矿) 诘1 0 - 1( 3 3 ) 4 吲 孚】+ c r 咖( g 4 ) + c r 妒( g 4 ，p ) l = l 根据( 3 - 2 ) ，( 3 3 ) 式得： t i 凹妒( g 4 ) + 盯妒( g 4 ，f ) 号 ( 3 4 ) t = l 由于上述不等式，所以存在一个i 使得盯西( g 4 ，一) = o 不防假设 c ( g 4 ，t 1 ) = 0 ( 3 5 ) g 4 把二维空间分为若干个区域，又要满足条件( 3 5 ) ，使得g 4 的 顶点在某一个区域中，因此在二维空间中有一个圆盘u ，即咖( g 4 ) cu ， 以及西( t 1 ) cr 2 一u 设f = g 4u t l ，则 n r = fu ( ut i ) ( 3 6 ) 扛= 2 我们很容易证明i f 的所有的画法如图3 6 所示 a 1 图3 6 ：f = g 4u t 1 f 把平面分成6 个区域，很容易得出以下结论： c ( g 4 ，p ) 1 ， c r 曲( g 4 ，p ) 2 ， c ( f ，t ) 4 ， ( n i ) 在7 区域中 矽( 啦) 在6 区域中 ( 3 7 ) 驴( n ) 在1 5 区域中 关于图的交叉数研究 1 7 假设有七。个顶点在7 区域中，有忌。个顶点在6 区域中，则有： 佗 c r 曲( g 4 ，丁) 尼1 + 2 后2( 3 8 ) t = 2 量c ( e ) 尼1 + 2 也+ 4 ( n h 一庇2 1 ( 3 9 ) = 4 佗一3 后1 2 尼2 4 由( 3 3 ) ，( 3 8 ) 式得： c ( r ) z ( 5 ，礼) + 尼l + 2 尼2 根据上述不等式和( 3 2 ) 式得： 由( 1 2 ) ，( 3 6 ) ，( 3 9 ) 式得： 忌1 + 2 后2 z ( 5 ，几一1 ) + 4 佗一3 【鸶 + 4 乜一4 4 嘲 孚】+ 鸶】 与假设( 3 2 ) 式矛盾，即c r ( r ) 4 吲 孚】+ 詈】 定理3 5c r ( 岛& ) = 4 嘲【孚 “考 ，n 1 1 8 硕士学位论文 图3 - 7 ：g 4 的一个所需画法 证明：由图孓7 的画法知，凹( g 4 & ) 4 吲 字】+ 吲，礼1 。又 因为g 4 鼠含一个子图同构于r 由定理3 4 ，c r ( r ) = 4 詈】 警 + 吲，扎1 。再结合性质2 ，我们得到c r ( g 4 & ) 4 鸶】 孚】+ 吼因而 仃( g 4 ) = 4 警 孚】+ 阻口 关于图的交叉数研究 1 9 第四章 完全三部图硒，m ，佗的交叉数 早在2 0 世纪5 0 年代，关于完全二部图，馆目前只能确定当 m 6 ，z 甜a 1 1 l 【i e 谢c z 猜想为真( 参见文献 8 】) 。2 0 世纪8 0 年代a s a n o 在文献( 1 0 】) 中确定了完全三部图跹，3 竹和鲍，3 n 的交叉数，此后， 关于完全三部图一直没有新的结果，最近我的导师黄元秋教授和他 的学生合作先后确定了完全三部图k ，4 n ( 【1 1 】) ，k 1 5 ，n ( 【1 2 ) ，k 6 竹( 【1 3 】) ， 髓，8 ，n ( 1 4 ) a n d 硒，1 0 一( 1 5 】) 。我们注意到文献 1 3 】， 1 4 和 1 5 】中结果的 得到都是利用了文献 8 中的结果得到，即z r a n k i e w i c z 猜想为真。本 章的主要结果是如下的定理： 定理若z a r a n k i e w i c z 猜想对任意m 的情形成立，则有： 凹( 西，m ，n ) = z ( m + 1 ，几) + l 等儿孚儿号j ( 当扎为偶数) ； z ( m + 1 ，n ) + l 罟jl 堡尹j 【詈j 一盟c 7 ，( 虬，m ，仡) z ( m + 1 ，n ) + l 詈jl 翌尹j 【鸶j ( 当n 为奇数) 。 这里z ( 仇+ 1 ，n ) = 【盟笋儿筹jl 詈j 【孚j 4 1引理 引理4 - l 设完全二部图m 的边集e 和两个划分的顶点集( y ， z ) ，其中y = ( 可1 一，可m ) ，z = ( z 1 ，一，) 。若矽为，n 的任意好画 法，则 ( 仡2 ) 汀( e ) = c ，( e 玩) i = 1 证明：因为，n 的画法包含n 个扩。，又每一个交叉发生 ( 扎一2 ) 个俨。上。d 2 0 硕士学位论文 _ _ - - - _ 一一_ 引理缸2 设g 为完全三部图纸m n ，它的边e 和三个划分的点 集为( x ，y ，z ) ，这里x = ( z 1 ，) ，y = ( 可1 ，) ，z ：( z 1 ，) 如果矽为g 的任意好画法，则有 ( q ) ：三凹妒( e 忍。) = 2 c q ( 取y ) + 壹盯多( 取y ，色。) + ( n 一2 ) 凹妒( e ) 重1 需1 ( 6 ) 圣卵妒( e ) = 2 c r 咖( 取z ) + 妻凹( 取z ，马。) + ( m 一2 ) 盯妒( e ) 证明：根据( 1 2 ) 式，我们有 凹咖( e ) = 凹妒( 取yu 取zu 毋z ) = 唧( 取y + 唧( 取zu 毋z ) + ( 取y ，取zu 研z ) ( 4 1 ) = 凹毋( 取y + 汀咖( 取zu 毋z ) + 凹毋( 取y ，既) 因为( 取zu 毋z ) 同构于完全二部图虬+ 仇，n ，它们的两个划分顶点 集为伍u z ) ，由引理4 1 得 ( 佗一2 ) 凹妒( 取zu 毋z ) 2 三盯( ( 取zu 毋z ) 乜i ) ( 4 2 ) 另一方面，又根据( 1 2 ) 式则有 c r 妒( e e ；) = 凹( ( 取yu 取zu 毋z ) 巴。) = 凹咖( 取y ) + 凹币( ( 取zu 研z ) e ；) + c q ( 取y ，( 取z u 毋z ) 最i ) ( 4 3 ) = c 唧( 艮y ) + ( ( 取z u 研z ) 圾) + 暑c ( 取y ，) 一c ，( 取y ，) 关于图的交叉数研究 2 1 上述( 4 3 ) 式两边对i 求和，以及使用了( 4 1 ) 和( 4 2 ) 式，我们得到： c ( e 巴；) = n c ( 取y ) + c ( ( 取zu 毋z ) 忍；) 扛= 1 i = 1 nn + ( c ( 取y ，也，) 一凹( 取y ，最；) ) 讧= 1j = 1 几 = 礼c ( 取y ) + c ( ( 取zu 毋z ) ) 佗 扛1 + ( n 一1 ) 凹咖( 取y ，也；) = 1 n = 2 c ( 取y ) + c ( 取y ，忍；) + ( 几一2 ) c ( e ) 同理( b ) 式成立。 引理垂3 设g 为完全三部图k m 竹，它的边集为e 和三个划分 点集为( x ，y ，z ) ，这里x = ( z ”) ，y = ( 可”) ，z = ( z 1 ) ， 假设为g 的任意好画法满足c ( e ) = z ( m + 1 ，咒) + 【警儿警儿詈j n ( 这里m 为奇数) ( a ) 假设佗= 2 七，则凹咖( 取z ，玩) 2 孚尼2 一孚尼+ ( m 一2 ) n ； i = 1 ( b ) 假设佗= 2 七+ 1 ，则c ( 取z ，马i ) 孚七2 一巫+ ( m 一2 ) o 讧= 1 证明： 记边e t = z 犰，l l i m ) ，以及边办= z 名1 1 j 佗) 。 不防假定在画法咖下，这m 条边巳围绕点按逆时针是：e 。_ e 2 一 e 3 _ _ e m ( 如图4 1 所示) 。又我们总可以选取以x 点为圆心， 半径为的领域c ( 这里可适当小) ，使得：( 1 ) 对于每条不与x 关联 的边e ，领域c 内部不含e 的任意片段；( 2 ) 对于第条与x 关联的边 ea ! ，ea ! 落在领域c 内部的片段上没有出现交叉。用a 表示位于 e i 与e 州所形成的角的那些边厶组成的集合。( 如图4 1 所示，用虚 线表示) ，这里下标i 自然理解为在m o d u l ez n 下。显然他i = 礼。 2 2 硕士学位论文 岛 b 懑蕊 i_、。f p m 一 图垂1 ：在画法咖下髓，m ，n 的局部情形 下面，我们对图g 的画法咖作适当的修改，我们构造m 个新的 图以及它的好画法也( 1st m ) 。使得每个也同构于完全二部图 卅。现在我们构造二部图g 。和它的画法，。 ( 1 ) 增加一个新点磊+ ，把磊+ ，画在e r 罟 + ，与c 的交点处，然 后连接点磊+ 1 与点z 以及点磊+ l 和可导 + 1 ； ( 2 ) 从g 中删除一条边e 。以及顶点玑，然后移去圈c 内部的白 弧( i 1 ，罟 + 1 ) ； ( 3 ) 按如图4 - 2 的方式连接磊+ ，和犰的边( i 1 ，署 + 1 ) ，其中 连接点玑和点磊+ 。而形成边位于圈c 内部 关于图的交叉数研究 2 3 钢唧智+ 1 一。 图4 2 ：图g 。以及它的画法。的局部情形 根据图4 2 ，我们不难得到 凹咖，( g 1 ) = c ( e 局。) + l a 2j + 2 1 4 3 i + + ( 1 詈j 一1 ) l a r 罟 一1 i + l 罟jl a 等 i + ( 【詈j 一1 ) 1 4 罟1 + 1 i + + 2j 4 m 2 + i a m 一1 ( 4 4 ) 类似的，删除边e i 和顶点玑，我们很容易得到图g 和它的画法晚( 2 i m ) 一同样的，画法咖2 ，咖3 ，我们可以分别得到如下的等 式： 。 c 7 ：( g 2 ) = c ( e 日。) + j a 3 f + 2 l a 4 i + + ( 【警j 一1 ) j a 罟1 + l 詈j f a f 罟1 + 1 i + ( 【筹j 一1 ) f a f 等1 + 2 f + + 2 f 4 m 一1 l + f a m f ( 4 5 ) c r 咖。一，( g m 一1 ) = c r 咖( e 玩。一，) + l a m i + 2 i a l l + + ( 1 等j 一1 ) i a 号 一3 i + l jf a 等 一2 i + ( 【等j 一1 ) 1 4 罟卜1 l + + 2 i 以。一4 l + i a m 一3 i ( 4 6 ) 2 4 硕士学位论文 c 7 咖。( g m ) = c q ( e 毛。) + i a l i + 2 i a 2 i + + ( 【罟j 一1 ) l a 罟卜2 l + 【罟jl a 予卜1 l + ( 1 罟j 一1 ) i a f 筹 j + + 2 1 4 m 一3 f + i a m 一2 l ( 4 7 ) 因为每一个g i ( 1 i m ) 都同构于完全二部图，n + 1 ，又凹机( g t ) z ( m ，佗+ 1 ) 。所以，由( 4 4 ) 一( 4 7 ) 式相加得到： m z ( m ，n + 1 ) 蚤c r 机( g ) ：曼c r ( 趴玩) + 掣曼= c r ( e 玩) + 半i a i = 凹咖( 趴b 。) + 巫n ：2 c r 咖( 取