（运筹学与控制论专业论文）五阶图与星图的笛卡尔积图的交叉数.pdf

摘要 图的交叉数是近代图论中发展起来的一个重要概念，自从上个世纪 五十年代初匈牙利数学家p a u lt u r & n 根据其在一个砖厂碰到的实际难题 ( t u r i n sb r i c kf a c t o r yp r o b l e m ) ，从而提出了交叉数的概念以来，图的交叉数 逐渐成为国际上一个非常活跃的图论分支，使得很多图论专家对这方面 进行了深入研究 研究图的交叉数不仅具有重要理论意义，而且有较强的现实意义，如 超大规模集成电路v l s t 中的圈布局问题、电子线路板设计中的布线问 题等1 9 8 3 年计算机科学家g a r e y 和j o h n s o n 证明了确定图的交叉数是 一个n p 完全问题，由于其难度，我们能够确定交叉数的图类非常少，在 许多情况下，即使找出图的交叉数的一个好的上界或下界也非常困难 目前，很多文献在研究一些特殊图类的交叉数，例如：完全图，完全2 一 部图，完全3 一部图及笛卡尔积图等本文研究几个连通五阶图与星图& 的笛卡尔积图的交叉数 第一章：交代了本文的写作背景，交叉数研究在国内外发展的动态， 研究工作的意义以及本文中要解决的问题和创新之处 第二章：给出一些基本概念和性质，介绍了阅读本文所需要的预备知 识，并介绍了在后面章节中会出现的一些相关概念、性质以及常用到的 一些引理，而部分使用较少的概念则放到了具体的章节中去交代 第三章：着重研究了三个五阶图g 。2 、g 。s 、g - 8 与星图晶的笛卡尔 积图的交叉数问题，分别确定它们各自的交叉数为： 1 c r ( g 1 2x 晶) = n ( n 一1 ) ，n 1 2 c r ( a 1 5x 晶) = z ( 5 ，n ) + 2 n + 【詈j ，n 1 3 o r ( g 1 8 晶) = z ( 5 ，n ) + 2 n + 【詈j ，礼1 第四章：提出了研究工作在发展中的一些问题以及作者在以后将致 力于前进的方向 关键词：交叉数；完全图；完全4 一部图；星图；笛卡尔积； 好画法 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 lt u r & uw h o s u g g e s tt h ea c t u a lp r o b l o m w h i c hn a m e d “n l 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 ef i e l d i nt h ew o r l d i ta t t r a c t sm a n y g r a p ht h e o r ye x p e r tt ow o r k t h er e s e a r c hw o r ki nt h ec r o s s i n gn u m 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 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 ta n d p l a y o u tp r o b l e m si ne l e c t r i cd e s i g n ，e t c i n1 9 8 3 ，g a r e ya n dj o h n s o np r o v e dt h a ti n g 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 m b e ro fg r a p h si sn p c o m p l e t e t h e r ea r eaf e w e x a c tr e s u l t so nt h ec r o s s i n gn u m b e r so fg r a p h sc l a s sb e c a u s eo fi t sc o m p l e x i t y i n m a n yc a s e s ，e v e ni ti sv e r yd i f f i c u l tt of i n do u tg o o db o u n d so ft h ec r o s s i n gn u m b e r s o fg r a p h s n o w ，m a n ya r t i c l e sa r ef o c u so ni n v e s t i g a t i n gt h ec r o s s i n gn u m b e r so f s o m es p e c i a lg r a p h s ，f o re x e 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 a p h f o rs m a l l n , t h ec o m p l e t eb i p a r t i t eg r a p hk m 住f o rs m a l lma n da n yn , t h ec o m p l e t et r i p a r t i t e g r a p h 风，m m s o m ec a r t i s i a np r o d u c tg r a p he t c i nt h i sp a p e r ，w es t u d yt h ec r o s s i n g n u m b e r so fc a r t e s i a np r o d u c t so fs t a r s 晶w i t hs e v e r a l5 - v e r t e xg r a p h s i nc h a p t e ro n e ，w ei n t r o d u c et h eb a c k g r o u n d so ft h ec r o s s i n gn u m b e r so fa n d i t sd e v e l o p m e n ta r o u n dt h ew o r l d ，t h em e a n i n g so ft h er e s e a r c ha n dt h ep r o b l e m s w ew i l ls o l v e i nc h a p t e rt w o ，w eg i v es o m ec o n c e p t i o n sa n dp r o p e r t i e s ，a n di n t r o d u c et h e r e q u i r e dk n o w l e d g e sa b o u tc r o s s i n gn u m b e r sw h e nr e a dt h i sp a p e r i nc h a p t e r t h r e e ，w ed i s c u s st h ec r o s s i n gn u m b e r so fg r a p h sg 1 2 岛、g 1 5 & a n dg 1 8 岛，w h i c hc r o s s i n gn u m b e r sa r ef o l l o w i n g ： 1 c r ( g 1 2 晶) = n ( n 一1 ) ，n 1 i i i 2 c r ( g 1 5 & ) = z ( s ，n ) + 2 n + 【詈j ，n 1 3 c r ( ( ? 1 8 s k ) = z ( 5 ，t t ) + 2 n + 【剖，扎l 。 i nc h a p t e rf o u r ，t h e r ea r es o m eq u e s t i o n sw h e nr e s e a r c h i n gi n t ot h i sp r o b l e m ， a n dt h ed i r e c t i o n1w i l lg oa h e a d k e y w o r d s ：c r o s s i n gn u m b e r s ；c o m p l e t eg r a p h ；c o m p l e t eq u a d r u p l eg r a p h ；s t a r g r a p h ；c a r t e s i a np r o d u c t ；g o o dd r a w i n g i v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的研究成果除了文中特别加以标注引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完全 意识到本声明的法律后果由本人承担 学位论文作者签名年月日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，研究 生在校攻读学位期间论文工作的知识产权单位属湖南师范大学同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论交 被查阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分内 容编人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存和汇编本学位论文 本学位论文属于 l 、保密口，在年解密后适用本授权书 2 、不保密口 ( 请在以上相应方框内打“ ”) 篡霪筻 导师签名：纱主胱 4 1 日期：獬6 月乒日 日期：年月日 五阶图与星图的笛卡尔积图的交叉数 1 引言 图论是一门应用十分广泛且其内容非常丰富的数学分支，起源于1 7 3 6 年欧拉解决哥尼斯城堡七桥问题【1 - 3 图的交叉数是近代图论中发展起 来的个重要概念，自从上个世纪七十年代初匈牙利数学家p a u lt u r f i n 根 据其在一个砖厂碰到的实际难题( t u r i n sb r i c kf a c t o r yp r o b l e m ) 4 ，从而提 出了交叉数的概念以来，图的交叉数问题逐渐成为国际上一个非常活跃 的图论分支，很多图论专家对这方面进行了深入研究 研究图的交叉数不仅具有重要的理论意义，而且有较强的现实意义， 在许多领域有着非常广泛的应用，例如： ( 1 ) 生物工程d n a 的图示； ( 2 ) 工业上电子线路板设计中的布线问题； ( 3 ) 超大规模集成电路v l s t 中的圈布局问题等【5 - 7 ； ( 4 ) 软件开发过程中文档部分的e r 图( 实体联系图) 等的自动生成； ( 5 ) 草图的识别与重画问题，具有比手写汉字识别更为广泛的应用领 域 然而，一般地，确定图的交叉数又是十分困难的，g a r e y 和j o h n s o n 证明了确定图的交叉数问题属于n p 一完全问题f 8 】由于其难度，已确定 交叉数的图类较少目前确定图类的交叉数主要集中在以下几个方面： 1 一些较特殊的具体图类的交叉数 这些特殊图类的交叉数中，部分给出了交叉数上下界或猜想，但具 体结果甚微，主要有 ( 1 ) 平面图g ： 对于平面图g ，其交叉数等于0 例如，对于完全图，当礼 5 时是平面图；对于完全2 一部图n ，当m i m m ，礼) 3 时也是平面图 硕士学位论文 特别地，确定一个图是平面图有下面的定理： k u r a t o w s k i 定理【9 】：图g 是平面图当且仅当它没有同胚于玩或配。3 的子图 ( 2 ) 完全图： 关于完全图的交叉数有一个重要的猜想，即g u y 猜想： c r ( ) 勺j 【字j 【字j 【字j 目前仅证明了等号对于n 1 0 成立这里，c r ( g ) 表示图g 的交叉数； 对任意实数1 2 ，l n j 表示不超过n 的最大整数 ( 3 ) 完全2 一部图： 实际上，t u r a n 的“砖厂问题”等价于确定完全2 一部图。的交叉 数1 9 5 4 年，z a r a n k i e w i c z 在文献【1 0 】中“证明”了 c r ( ( m ，n ) _ 【i m 儿丁m ：- ljn 【虿j - 【字j ，( 仇n ) 1 9 6 9 年，r i n g e l 1 l 】和k a i n e n 各自独立发现z a r a n k i e w i c z 在文献 1 0 】 中的证明有错误，同时指出z a r a n k i e w i c z 猜想至少是某个精确值的上界， 因而确定完全2 一部图。n 的交叉数问题目前仍然是一个公开问题习 惯上把上式称之为z a r a n k i e w i c z 猜想，把上式右端记为z ( m ，咒) 1 9 7 0 年，k l e i t m a n 证明了等号对于m i n ( m ，n ) 6 时成立【1 2 1 9 9 3 年，w o o d a l l 证明了当m = 7 且几1 0 时z a r a n k i e w i c z 猜想成立【1 3 】到目 前为止还没有关于此方面的新结果 ( 4 ) 完全3 一部图： 目前，确定完全3 一部图交叉数的文献很少，且证明基本上建立在 已知的完全2 一部图交叉数的基础上上个世纪八十年代，k a s a m o 证 明了c r ( k , ，3 ，。) = z ( 4 ，孔) + 【詈j ，c r ( 9 2 ，3 ，。) = z ( 5 ，n ) + n 【1 4 此后，关于完全 3 一部图一直没有新结果直到2 0 0 4 年，赵霆雷博士和黄元秋教授证明了 2 五阶图与星图的笛卡尔积图的交叉数 c r ( k 。，4 ，n ) = n ( n - 1 ) = z ( s ，n ) + 2 吲 1 5 】；后来梅汉飞教授与黄元秋教授合作 又证明了盯( k i ，5 ，n ) = z ( 6 ，n ) + 4 吲【1 6 1 ；2 0 0 5 年，黄元秋教授与赵霆雷博士 合作证明了c r ( 鲍 4 n ) = z ( 6 ，几) + 2 n 【1 7 这些结果都是建立在z a r a n k i e w i c z 猜想对于m i n ( m ，n ) 6 成立的前提下2 0 0 5 年初，黄元秋教授和赵霆雷博 士在假设z a r a n k i e w i c z 猜想对于m = 7 成立的前提下，证明了c r ( 硒 6 。) = z ( 7 ，几) + 6 【三j 【1 8 】；其后不久又在假设z a r a n k i e w i c z 猜想对于m = 8 成立的 前提下，证明了汀( k ，7 。) = 1 2 【詈儿孚j + 9 【号j 【1 9 ，假设z a r a n k i e w i c z 猜想 对于仇= 9 成立的前提下，证明了c r ( k 1 ，s ，n ) = 1 6 引【孚j + 1 2 【詈j 【2 0 在假 设z a r a n k i e w i c z 猜想对于冠。住成立的前提下，王晶，黄元秋教授证明了 c r ( k z ，呐) = z ( 1 l ，n ) + 2 0 吲f 2 1 何小年，王晶，黄元秋教授讨论m ，n 的奇 偶性，确定了部分硷，m ，n 的交叉数【2 2 】 ( 5 ) 笛卡尔积图： 对于长度为m ，n 的圈的笛卡尔积图，f h a r a r y 等在1 9 7 3 年猜想c r ( g ) ( m 一2 ) n ，( 3 m n ) 【2 3 n a d i n ec m y e r s 在文献【2 4 】中对这个猜想 的起源，发展过程以及现状等都做了较为详尽地介绍 1 9 7 8 年，r i n g e i s e n 和b e i n e k e 证明了c r ( c 3xg ) = n 【2 5 1 ，1 9 8 0 年证明 了凹( qxq ) = 2 n 【2 6 1 9 9 6 年m k l e 誊6 和r i c h t e r 证明了凹( g g ) = 3 n 2 7 】2 0 0 1 年r i c h t e r 证明了c r ( g g ) = 4 n 【2 8 2 0 0 4 年a d a m s s o n 和r i c h t e r 证明c r ( g g ) = 5 n 2 9 一些具体的圈与圈的笛卡尔积图的交叉数，如 c r ( q 戗) = 8 【3 0 ，c r ( c 5 c 5 ) = 1 5 【3 l 】 c r ( c 8 g ) = 2 4 【3 2 ，o r ( c 7x 岛) = 3 5 f 3 3 等都已经得到证明 从二十世纪后期起，捷克数学家m k l e 豆6 等人开始研究阶数较小的图 与路r ，星图& ，圈g 的笛卡尔积图的交叉数 2 6 3 4 】- 【4 l 】由于阶数为3 的图或同构于2 路或同构于3 圈，它们与路r ，星图& 的笛卡尔积图的 交叉数显然为0 因此系统地研究从4 阶连通图开始 m k l e 吾61 9 9 4 年确 定了所有4 阶图与路r 的笛卡尔积图的交叉数【3 5 】之后，他又陆续给 3 硕士学位论文 出了所有5 阶图与路r 的笛卡尔积图的交叉数【3 6 【4 1 】，以及给出了部分 五阶图与圈g ，星图晶的笛卡尔积图的交叉数【2 7 ，【3 7 】，【4 1 】，但是还有部 分五阶图与星图晶的笛卡尔积图的交叉数却一直没有结果 2 原图g 与线图l ( g ) 之间的交叉数 一般来说，平面图g 与它的线图l ( g ) 的交叉数有：盯( g ) 盯( ( g ) ) 上世纪六七十年代初，s e d l 鸵e k 得到一个平面图g 的线图l ( g ) 是平面图 的充分必要条件f 4 2 1 1 9 7 9 年，k u l l i ，a k k a 和b e i n e k e 获得了一个平面图的 线图的交叉数为1 的充分必要条件【4 3 1 9 9 7 年，a k k a ，j e n d r o l ，k l 战等研 究了平面图的线图的交叉数为2 的情形 4 4 2 0 0 1 年，j e n d r o l 和k l 西芒已 经证明了非平面图g 和线图的的交叉数都是1 的充分必要条件f 4 5 2 0 0 5 年，黄元秋教授和赵霆雷博士合作给出了非平面图g 和线图的交叉数都 为k 的充分必要条件【4 6 】 、3 有某种特点的图的交叉数的一些性质 因为具体确定某个图的交叉数比较难，所以换个角度从交叉数的性 质如临界交叉数、正则图的交叉数、交叉数的奇偶性 4 7 1 1 5 3 l 等着手研究， 希望得出一些有关图的交叉数方面比较好的结果 受到这些文献的启发，应用并创新某些方法，在m k l e g 芒等人研究阶 数较小的图与路r ，星图& ，圈瓯的笛卡尔积图的交叉数的基础上，本 文给出了几个五阶图与星图晶的笛卡尔积图的交叉数 4 五阶图与星图的笛卡尔积图的交叉数 2 基本概念和性质 本章给出以后各章节涉及到的基本概念和性质，凡未说明的概念均 同文献【5 4 5 5 】；且无特别说明所涉及的图均指连通简单图 个图g 是指一个有序三元组( y ( g ) ，e ( g ) ，惦) ，其中v ( c ) 是非空的 顶点集，e ( g ) 是不与v ( c ) 相交的边集，而惦是关联函数，它使g 的 每条边对应于g 的无序顶点对对任何边子集e ( g ) ，用 表示 由边集导出的子图；特别地，令e 为图g 的一条边，用g e ) 表示从 g 中删除边e 后所得到的图图g 中一个度为k 的顶点，称之为k 一度 点d 如( ) = d ，表示子图 中顶点u 的度为d 定义1 图g 在画法下的交叉数是指在画法下边与边产生的交 叉点的个数，用c r , ( a ) 表示 定义2 图g 的交叉数，用c r ( g ) 表示，是指图g 在平面上的所有画 法下的交叉数的最小值，即m i nc r 咖( g ) ，妒取遍图g 在平面上的所有好画 口 法 定义3 图g 在平面上的一个最优画法是指恰好达到图g 的交叉数 的画法 定义4 图g 在平面上的一个好画法是指图g 在平面上的画法满足 以下四个条件： 1 ) 连接同一个结点的任意两条边不相交； 2 ) 边不能自身相交； 3 ) 任何两条相交的边最多交叉一次； 4 ) 没有三条边交叉于同一个点 注：定义4 中第四种画法是为了研究而统一规定不允许的前三种 5 硕士学位论文 画法1 ) ，2 ) ，3 ) 在最优画法中是不会出现的，因为如果出现这些情况，我们 可以对画法改进，从而可以得到一个具有更小交叉数的画法( 见图2 - 1 ，图 2 - 2 ) 叉爻 图2 1 ：图g 的好画法中不允许出现的四种情况 厂 ，、j 图2 2 ：对图2 1 中前三种画法的改进 注：定义1 一定义4 中的“平面”可改为“曲面”，且相关定义也可推 广到曲面的情况目前国内外大多是研究平面上的交叉数，但也有研究 环面等曲面上的交叉数的【5 6 】在本文中作者仅讨论平面上的交叉数 两个图g ，和g ：的笛卡尔积用g 。g 2 表示，它是这样的图：点 集v ( a l g 2 ) = v ( a 1 ) v ( e 2 ) ；边集e ( g 1 g 2 ) = ( 仳i ，) ，( u n ，) ) ：牡t = u n 且 ，】e ( g z ) ，或者 u i ，u n ) e ( g ，) 且= ) 用星图& 表示完全 2 一部图西”在笛卡尔积g 晶中，可以方便的用g o ，g - g n 表示图g 的他+ 1 个拷贝 令为图g 的好画法，若g 。和g ：为g 的边不相交子图用c r 西( e ( g ) ) 表示在好画法砂下发生在g 的边上的交叉的数目；用c r 曲( e ( g 。) ，e ( g 。) ) 表 示发生在g 。的边与g 。的边之间的交叉数显然有t 引理2 1 令是图g 的一个好画法且g l ，g 2 和g 3 是图g 的彼此边 互不相交的子图，则有 6 五阶图与星图的笛卡尔积图的交叉数 ( 1 ) c ( e ( g 1 ) ue ( g 2 ) ) = ( e ( g 1 ) ) + c r 西( e ( g 1 ) ，e ( g 2 ) ) + c r 4 , ( e ( g 2 ) ) ( 2 ) c r 妒( e ( g 1 ) ue c g 2 ) ，e ( g 3 ) ) = c ( e ( g 1 ) ，e ( g 3 ) ) + ( e ( g 2 ) ，e c g a ) ) ( 3 ) c r ( g , ) c r ( g ) 0 = 1 ，2 ，3 ) 若在图f 的某些边上加入或抹平2 一度点( 均可反复多次) ，得到的图 日与图f 同构，则称图f 和图日同胚，记为f 日由同胚的定义易知： c r c f ) = c r c h ) 7 五阶图与星图的笛卡尔积图的交叉数 3 三个五阶图与星图& 的笛卡尔积图的交叉数 在文献【4 0 】中m k l 醇己列出了五阶图g - 一g 2 与路p n ，圈g 和星图 岛的笛卡尔积图的部分交叉数结果，其中上述五阶图与路r 的笛卡尔 积图的交叉数结果都已经给出，然而大部分五阶图与圈g 和星图岛的 笛卡尔积图的交叉数结果却一直未能得到证明在本章中作者将证明文 献【4 0 】中g 。：，g 。5 及g 。s 与星图岛的笛卡尔积图的交叉数结果 凤囟 g 1 2g 1 5g 1 8 3 1g 1 2 & 的交叉数 为了证明g 。与星图& 的笛卡尔积图的交叉数结果，先构造图风： 在顶点集划分为 t 。，t 2 ，“) 和v 1 ，l 2 ，啦，v 4 ，地) 的完全2 一部图拖，n 中，增 加六条边 u 1 u 2 ， 1 3 2 7 3 3 ，v 2 v 5 ，t 3 u 4 ，v a v 5 ，魄，则可得到一个新图，记为巩，其 中玩包含n 个5 一度点、1 个( 几+ 1 ) 一度点、1 个( n + 2 ) 一度点、3 个( n + 3 ) - 度点和5 n + 6 条边( 见图3 1 ) 在图风中，用正( = 1 ，2 ，7 1 , ) 表示与顶点 t i 关联的边集( 见图3 2 ) ，用晶表示边集 口l v 2 ，v 2 v 3 ，v 2 v 5 ，u 3 u 4 ，v 3 v 5 ，v 4 v s ， 于是易得 n e ( 风) = 风u ( u 正) ( 3 1 ) i = 1 9 硕士学位论文 7 忿i + 么丢钐笙 闷影 图3 1图3 2图3 3 3 1 1 预备定理：玩的交叉数 引理3 1 1 令妒为图仍的一个好画法，若凹西( 丑，死) = 0 ，则c r , ( e o ，丑u 7 2 ) 2 证明令t = 为飓的边导出子图显然丁同构于由顶点集 划分为 l ，t 2 和 1 ，忱，v 3 ，魄，奶) 的完全2 一部图恐，5 因为c r ( 五，死) = q ， 所以子图t 的由导出的子画法必同构于图3 3 在图3 3 中 未标明的五个顶点代表v 2 ，v 3 ，v 4 ，v 5 ，显然在图3 3 中每个面都仅含有 l ，忱，v 3 ，v 4 ，中的两个点，又因为d ( 地) = 3 ，从而子图 中与点v 3 关联的三条边中至少有一条边与丑u 乃中的边交叉一次同样d ( u s ) = 3 ，从而子图 中与点v 5 关联的三条边中至少有一条边与丑u 乃中的 边交叉一次如果此两个交叉不相同，则显然有( e o ，7 1u t 2 ) 2 ；如果此 两个交叉相同，此时与边集正u 死中的边交叉的边只能是v 3 v 5 ( 因为要同 时与点v 3 和点关联) ，再考虑点v 2 ，因为d ( 忱) = 3 ，同样子图 中与点v 2 关联的三条边中至少有一条边与乃u 乃中的边交叉一次且此时 与丑u 正中的边交叉的边不可能是边v 3 u 。( 因为要与点v 2 关联) ，故这个交 叉与前面产生的交叉是不相同的两个交叉，从而也有c r 西( e o ，噩u 忍) 2 综上所述，若c r 垂( n ，t 2 ) = 0 ，则有凹毋( 岛，丑ut 2 ) 2 证毕 口 定理3 1 1c r ( 风) = n ( n 一1 ) ，礼1 1 0 五阶图与星图的笛卡尔积图的交叉数 证明先构造风的一个好画法p ：在平面直角坐标系上，把以的顶 点子集 v 2 ，v 3 ，v 4 ，v s 放在y 轴上，其中v 3 放在原点，t 3 1 ，忱放在y 轴 的正半轴上，讥，地放在y 轴的负半轴上；把顶点子集 t 。，t 2 ，t n ) 放在 x 轴上，其中引个点放在x 轴的负半轴上，f 詈 个点放在x 轴的正半轴 上，然后把各边用适当的直线或者曲线表示出来，见图3 1 显然在图 3 1 中，风岛同构于蚝，n 且在0 下的子画法也正好就是蚝，n 的一个最 优画法，所以c r p ( 巩昂) = c r ( 蚝，。) = z ( 5 ，n ) ；而c r o ( e o ，正) = 2 ( t t 位于x 轴 的负半轴) 于是结合式( 3 1 ) 及引理2 1 得 c r 口( 玩) = 印( 风岛) + c 7 o ( e o ，u 正) + 咖( e 0 ) i = 1 = z ( 5 ，凡) + c r o ( e o ，互) + c r o ( e o ) ：z ( 5 ，佗) + 2 【昙j = 4 l 2 jl - - r n - 1j + 2 目 = 几( n 一1 ) 由交叉数的定义知盯( ) 礼m 一1 ) 下面对n 用归纳法来证明反向不等式成立，即证明c r ( y n ) 礼( n 一1 ) 当绍= 1 时，c r ( y x ) 1 ( 1 0 ) = 0 ，结论显然成立 当n = 2 时，要证明盯( 玩) 2 ( 2 1 ) = 2 ，只需证明对于凰的任意好画 法d ，均有c r d ( 日2 ) 2 用反证法：假设有某个好画法妒，使得c r 妒( 吼) 1 若( 飓) = 0 ，则说明也是一个平面图，矛盾( 因为也中含有虬，a 子 图) ；若哪( 凰) = 1 ，设这个交叉为q ，则q 肯定是由某两条边e 。和e 。产生 的，去掉e 。和e ：中任意一条边得到新图吼e 。和凰e 2 ，同时得到凰e 和凰e 2 的好画法咖l 和2 ，显然有c r 毋1 ( 玩e 1 ) = 0 和c ( 凰e z ) = 0 ，说明 玩e 。和矾e ：是平面图，矛盾( 因为凰中去掉任意一条边仍含有配，。子 1 】 硕士学位论文 图) 从而盯( 飓) 2 当礼之3 时，设 c r ( 风一2 ) ( 亿一2 ) ( n 一3 ) 要证明c r ( 风) n ( 扎一1 ) ，只需证明对于风的任意好画法d ，均有 c r o ( n ) n ( n 一1 ) 反设存在风的好画法使得 甜西( 月) n ( n 一1 ) 下面我们根据画法咖中互和t j ( 1 i ，j 佗，i 歹) 是否交叉分情况 讨论： 情况1 ：至少存在两点t i 和岛( 1 i ，歹强，i j ) ，使得c r 毋( 正，乃) = 0 不失一般性，假设点t n 一1 和t 。满足c ( 兀- 1 ，瓦) = 0 因为 ( 1 ，茎i ，倚一2 ) 同构于完全2 一部图恐5 7 且( 瓦- l ，死) = 0 ，所以 有c r 咖( 霉，b 一1ur ) = 钟咖( ，5 ) 一哪( 孔一lur ) 一c r c , ( t , ) 4 0 0 = 4 又 同构于以- 2 ，结合式( 3 1 ) ，引理2 1 及引理3 1 1 得 凹毋( 风) = c r , ( e o u ( u 正) ) i = 1 n - 2 = c r , ( e o u ( u 互) u t 一lu 瓦) i = 1 = c r 西( t t 一2u 矗一1u 已) = 哪( 风一2 ) + 哪( i i 一2 ，露一1u 死) + ( 咒一1ur ) n - 2 = c q ( 风一2 ) + 哪( 岛，瓦一1u 瓦) + c r 毋( u 互，瓦一lu 瓦) + c r 咖( 瓦一1u 死) i = 1 ( 咒一2 ) ( 冗一3 ) + 2 + 4 ( 死一2 ) = n ( n 一1 ) 情况2 ： 对任意两点t i 和t j ( 1 i ，j 礼，i 歹) ，都有盯母，弓) 1 1 2 五阶图与星图的笛卡尔积图的交叉数 结合式( 3 1 ) 及引理2 1 得 哪( 风) = 哪( e o u ( u 正) ) i - - - - i = 盯咖( 岛) + c r a e o ，u 正) + c ( u 正) 因为盯币( 风) 礼( 佗一1 ) = 4 吲【孚j - i - 2 引，c r 曲( 虬，n ) 仃( 蚝，。) = z ( 5 ，佗) = 4 【詈儿孚j ，所以( 岛) + 哪( 岛，u 正) = c r 咖( 岛) + ec ( 品，正) x 4 + z 5 ， z 5 z 2 + z 3 ， 成立当且仅当x 3 + x 4 0 这是不可能的，因为x 4 都是非负整数 证毕 定理3 1 。2c r ( c 1 2 & ) = 礼( 乱一1 ) ，礼1 图3 1 9 证明这里用g i ：( 江0 ，1 ，n ) 表示笛卡尔积图g - 2 & 中g ：的第i 个拷贝图3 1 9 表明，存在好画法庐使得c r , ( g ，z 黑) = c r ( k 5 ，n ) + 2 吲= n ( 几一1 ) ，由交叉数的定义知c r ( c ，：x 瓯) c r , ( c t 2x & ) = n ( n - 1 ) 假设存在 g 。：x 晶的最优画法使得其交叉数小于n ( 住一1 ) 在画法下，将每个 g i 2 ( i = 1 ，2 ，钆) 的边收缩到点t i ，则得到一个同构于玩的图于是可得 c r ( 风) 礼( n 一1 ) 这是不可能的，因为定理3 1 1 中已证明c r ( 玩) = 佗( 几一1 ) ， 从而c r ( g 1 2 & ) n ( n 一1 ) ，佗1 证毕n 3 2 g 1 5xr 的交叉数 为了证明g 。与星图r 的笛卡尔积图的交叉数结果，先证明完全4 一 部图虬 1 3 ，。的交叉数结果把完全3 一部图k 1 , 1 , 3 的五个点v 2 ，v 3 ，v 4 ，与 1 6 五阶图与星图的笛卡尔积图的交叉数 另外1 , 个点如0 = l ，2 ，竹) 分别连边得到完全4 一部图跹，1 ，。，n ( 见图3 2 0 ) 在完全4 一部图虬1 ，s ，n 中，用正g = 1 ，2 ，n ) 表示与顶点t t 关联的边集 ( 见图3 - 2 ) ；用岛表示完全3 一部图甄，1 3 中边集 v f u 2 ，j 2 v 3 ，晚魄，v 2 v s ；用e 表示完全3 一部图硷1 ，s 中边集【u - 1 3 5 ， u 3 v 5 ，v 4 v s 于是易得 e ( 硒1 3 ，n ) = e o o e 。o ( u 互) ( 3 2 ) i = 1 佻 图3 2 0 3 2 1 预备定理： 硒1 3 ，n 的交叉数 为了书写方便，下文中将完全4 一部图尬l ，3 ，。记为舻 引理3 2 1 令为图3 的一个好画法，若盯西( 丑，乃) = 0 ，则c - t , # ( 岛u 邑，丑u 死) 3 ，且c ( 忍，噩u 是) 4 证明证明哪( 玩ue ，正u 死) 3 因为c ( 乃，乃) = 0 ，所以由画法 妒导出的 的子画法必同构于图3 2 1 不妨设完全3 一部图 局1 。的两个4 一度点分别为v 2 和v 5 ( 1 ) 假设点忱与点v 5 是邻接的且边 v 2 v 5 上有交叉从图3 2 1 可知，每个面最多包含五个点忱，v 3 ，v 4 ，v 5 ( 图 中未标明的五个点) 中的两个点，且4 一度点v 2 只能包含于图3 2 1 中两 个相邻的面中，从而4 一度点v 2 与三个2 一度点连边至少要与乃u 乃中的 边产生一个交叉同理，4 一度点v 5 与三个2 一度点连边至少要与死u 正 中的边产生一个交叉由假设知边v 2 v 5 上有交叉，故当点v 2 和点佻邻 接且边v 2 1 ) 5 上有交叉时，可得c ( 岛u 包，丑u t 2 ) 3 ( 2 ) 假设点口z 与点 17 硕士学位论文 忱邻接但边v 2 v 5 上没有交叉从图3 2 1 可知，每个面最多包含五个点 v l ，v 2 ，明，啦，v 5 中的两个点，且4 一度点v 2 只能包含于图3 2 1 中两个相邻 的面中，又点忱与点坞邻接且边v 2 v 5 上没有交叉，从而4 一度点v 2 与三 个2 一度点连边至少要与死u 乃中的边产生两个交叉同理，4 一度点v 5 与三个2 一度点连边至少要与噩u 正中的边产生两个交叉故当点v 2 与 点v 5 邻接且边v 2 v 5 上没有交叉时，可得c r 西( 晶ue ，乃ut 2 ) 4 综上所 述，可以得到( 玩u 忍，t 1ut 2 ) 3 图3 2 1图3 2 2图3 2 3 证明c r 西( 死，丑ut 2 ) 4 因为 的导出子图同构于完全 2 一部图虬，5 且盯曲( 丑，t 2 ) = 0 ，则c r y ( t 3 ，7 1u t 2 ) c r ( 娲，5 ) 4 证毕口 引理3 2 2c r ( k 1 ) = 1 ，盯( 2 ) = 3 证明证明c r ( k 1 ) = 1 。图3 - 2 2 表明，存在一个好画法咖使得c r 咖( k 1 ) = 1 ，根据交叉数的定义知c r ( k 1 ) c r 曲( k 1 ) = 1 下面证明盯( k 1 ) 1 因为 k 1 中包含子图虬 3 根据引理2 1 ( 3 ) 知c r ( k 1 ) 仃( ，3 ) = 1 1 8 五阶图与星图的笛卡尔积图的交叉数 图3 2 5 图3 2 8图3 2 9 证明c r ( 舻) = 3 图3 2 3 表明，存在一个好画法砂使得凹西( 舻) = 3 ，根 据交叉数的定义知c r ( k 2 ) ( k 2 ) = 3 下面证明c r ( k 2 3 ) ，即证明：对 于2 的任意好画法h ，均有c r ( 2 ) 3 ( 1 ) 若c r ( 五，t 2 ) = 0 由引理3 2 1 可得凹毋( 玩u & ，噩ut 2 ) 3 ，显然有c r h ( k 2 ) 3 ( 2 ) 若盯，l ( 五，死) = 1 此 时在同构意义下h 的画法是唯一的，见图3 2 4 ( 图3 - 2 4 以及下文中的图 孓2 5 ，3 - 2 6 ，3 - 2 7 ，3 - 2 8 ，3 2 9 中点x l ，x 2 ，z 3 ，z 4 ，z 5 代表图k 2 中点 l ，v 2 ，v s ，v 4 ，佻) 在 图3 2 4 中，若点z 。，z ：，x 4 ，x 5 中某个点是子图 中的4 一度点， 1 9 硕士学位论文 它与点x