（基础数学专业论文）一类笛卡尔积图的交叉数.pdf

湖南师范大学硕士学位论文 摘要 m r g a r e ya n dd s j o h n s o n 已经证明确定图的交叉数是一个n p 完全问题( 见文献【1 1 ) ，因为其难度，我们能够确定交叉数的图类非常 少，在许多情况下，即使找出图的交叉数的一个好的上界或下界也 是非常困难目前，很多文献都是在研究一些特殊图类的交叉数， 例如：完全图、完全二部图、完全三部图、循环图及一些特殊图类的 笛卡尔积图等本文研究路与某些图类的笛卡尔积图的交叉数 第一章：交代了本文的写作背景，交叉数研究在国内外发展动 态，研究工作的意义以及本文中要解决的问题和创新之处 第二章：基本概念和性质介绍了阅读本文所需要的预备知识其 中主要包括交叉数的概念，并介绍了在后面文章中会出现的一些相 关概念，性质以及常用到的一些定理 第三章：我们寻求了一种好画法，从而给出了路与轮w 名的 笛卡尔积交叉数的一个上界即 讹删i = ( f f l 二瓣涮； 并且证明了当m = 1 ，2 ，3 时的交叉数与此上界是符合的这里，r 表示边长为n 的路，u 名表示由一点到一个n 圈g 的悬挂，也即从 独点k 。向g 的所有n 个点分别连一条边所得图 第四章：我们确定了5 个六阶图与路r 的笛卡尔积图的交叉 数除了每个定理都寻求到一个好画法外，定理1 , 2 的完成是通过交 叉数的一个重要性质得到，定理3 ，4 ，5 的证明是各自独立完成，整个 证明思路看似相同，但实际上在各种细节问题上各有独特之处 第五章：提出了研究工作在发展中的几个问题以及作者在以后 将致力于前进的方向 关键词：图；画法；交叉数；路；笛卡尔积；同胚； 平面图 置鱼三崆 i i湖南师范大学硕士学位论文 a bs t r a c t d e t e r m i n g t h ec r o s s i n gi m m b e r so fg r 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 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 h l 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 f f i c u l tt of i n do u tg o o db o u n d s o ft h e c 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 i li n v e s t i g a t i n g t h ec r o s s i n gn u m b e r so fc o m p l e t eg r a p h s ，c o m p l e t eb i p a r t i t eg r a p h s ，c o m p l e t e t r i p a r t i t eg r a p h s ，c y c l i c o r d e rg r a g h sa n d s o m es p e c i a lg r a p h sc 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 s p a p 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 to fac l a s so fg 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 do ft h ec r o s s i n gn u n i b e ra 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 i nc h a p t e rt w o ，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 m b e r ，s o l n 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 m b e r i nc h a p t e rt h r e e ，w eg i v ea nu p p e rb o u n do nt h ee r o a s i n gn u m b e r so f w ，。t h a t i s 州怯二瓣渊澄 a n d d e t e r m i n e d t h ec r o s s i n g n u m b e r o fp l 眠，尸2 眠a n d b x w ，r e s p e c t i v e l y h e r e ，ri st h ep a t ho fl e , 唱, - t hn 眠i sas u s p e n s i o nt og a n dgi st h ec i r c l e o f l e n g t hn i nc h a p t e rf o u r ，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 fs o m eg r a p h so n6 - v e r t e xw i t hp a t hr k e yw 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 ；p a t h ；c a r t e s i a np r o c p u c t ；h o m e o m o l p h i s m ；p l a n eg r a p h 湖南师范大学硕士学位论文 第一章引言 图的交叉数是近代图论中发展起来的一个重要概念，自从上个 世纪七十年代初匈牙利数学家p a lt u r i n 根据其在一个砖厂碰到的实 际难题( t u r 矗n l sb r i c kf a c t o r yp r o b l e m ) ( 见文献( 2 , 3 ，4 】) ，从而提出了交叉 数的概念以来，图的交叉数逐渐成为国际上一个非常活跃的分支， 使得很多图论专家对这方面进行了深入研究 研究图的交叉数不仅具有重要的理论意义，而且有较强的现实 意义，在许多领域有着非常广泛的应用，例如： ( 1 ) 工业上电子线路板设计中的布线问题； ( 2 ) 草图的识别与重画问题，具有比手写汉字识别应用更为广泛 的应用领域； ( 3 ) 软件开发过程中文档部分的e r 图( 实体联系图) 等的自动 生成； ( 4 ) 生物工程d n a 的图示； ( 5 ) v l s t 中的圈布局问题等 然而，一般地，确定图的交叉数又是十分困难的，文献【1 证明 了确定图的交叉数问题属于n p - 完全问题由于其难度，目前国际 上对交叉数的研究比较局限，主要集中在以下几个方面： 1 一些较特殊的具体图类的交叉数，其中一些给出了交叉数上 下界或猜想，但是具体结果甚微，主要有 ( 1 ) 完全图： 国际上关于完全图的交叉数有一个重要的猜想，即： c r ( 纸) = 【号儿学儿t n - 2 j n - 。3 j ，最新的结果是s a a t y 证明了等号对于 n s1 0 成立( 见文献【5 】) 这里，c r ( g ) 表示图g 的交叉数；对任意实 数佗，h 表示不超过几的最大整数 ( 2 ) 完全二部图： 实际上，t u r a n 的“砖厂问题”等价于确定完全二部图，。的 2 湖南师范大学硕士学位论文 交叉数后来，z a r a n k i e w i c z 在文献 3 4 中“证明”了c i ，( 。) = l 引m 【学儿g 儿警j ，( m n ) 不久， r i n g e l 和k a i n e n 各自独立发现 z a r a n k i e w i c z 在文献 3 4 中的证明有误( 见文献【3 5 】) ，因而确定完全2 _ 部图。的交叉数问题目前仍然是一个公开问题习惯上把上式称 之为z a r a n k i e w i c z 猜想，把上式右端记为z ( m ，n ) k l a i m a n 在1 9 7 0 年 证明了等号对于m i n ( m ，九) 6 成立( 见文献f 6 】) w o o d a l l 于1 9 9 3 年证 明了对m = 7 且ns1 0 成立( 见文献，直到目前为止还未看到关 于此方面的新结果 ( 3 ) 完全三部图： 目前国内外对完全三部图交叉数的证明都还建立在完全二部图 交叉数的基础之上，因此此方面的结果也较少 上世纪八十年代， k a s a m o 证明了c r ( k 1 3 。) = z ( 4 ，n ) 十引， 盯( 尬。) = z ( 5 ，扎) 4 - n ( 见文献【8 ) 直到2 0 0 4 年黄元秋教授才独立证 明了c r ( k t a 。) = n ( n 一1 ) = z ( 5 ，祝) 4 - 2 j ( 见文献【2 7 ) ，后又与梅汉飞教 授合作确定了”( 蜀 。) = z ( 6 ， 2 ) 4 - 4l ；j ( 见文献f 3 0 】) 这些结果都是建 立在z a r a n k i e w i c z 猜想对于m i n ( m ，札) 6 成立的事实基础上 2 0 0 5 年初黄元秋教授又在假设z a r a n k i e w i c z 猜想对于m = 7 成立的前提 下，确定了甜( k - 。) = z ( 7 ，n ) + 6 【j ( 见文献【1 8 1 ) ，在这些文献中都采 用了新的证明方法 ( 4 ) 笛卡尔积图： 对于猜想：c ( c k g ) = ( m 一2 ) n ，( m 佗) ，r i n g e i s e n ，b e i n e k e ，k l e s c 和r i c h t e r ，j a ya d a m s s o n 等人证明等号对m = 3 ，4 ，5 ，6 ，7 成立( 见文献 【9 - 1 5 ，3 2 1 ) ，n a d i n ec m y e r s 在文献 4 】中对这个猜想的起源，发展过程 以及现状等都做了较为详尽的介绍从二十世纪后期起，m k l e 酌等 人开始对阶数较小的图与路、星、圈的笛卡尔积图的交叉数的研究 ( 见文献 1 6 2 6 ，3 3 ) 其中所有不大于5 阶的简单图与路的笛卡尔积图 的交叉数都已经被确定 2 有某种特点的图的交叉数的一些性质 如临界交叉数，线图的交叉数，3 一正则图的交叉数，交叉数的 奇偶性等 湖南师范大学硕士学位论文 3 3 交叉数与图的其他参数的关系 如c r ( g ) 与( 己( g ) ) 的关系，其中l ( g ) 表示图g 的线图； 已经证明了图g 的线图的交叉数是1 的充分必要条件，黄元秋 给出了图g 的线图的交叉数是2 的充分必要条件( 见文献 2 9 1 ) ； 图的交叉数与图的亏格的关系，以及同一类图在不同亏格的曲 面上的交叉数； 图的交叉数与图的树宽的关系等 大部分的研究主要集中在1 ：确定交叉数上，证明方法和技巧也 是越来越多本文受到文献【1 6 2 6 ，3 3 】等的启发，运用并发展他们的 某些方法推广了关于笛卡尔积图交叉数方面的结果所给出的一些 定理等都是关于路与一些图类的笛卡尔积图的交叉数，在此我们对 这方面的发展势态做一简单介绍 路是图论中最基本最简单的一类图之一，活跃在图论的各种研 究当中，在交叉数研究中也不例外国内外公开发表的涉及到路的文 献也已经有一些( 见文献1 9 ，2 0 ，2 0 - 2 6 ，3 3 1 ) ，并且新的文章不断出现，人 们试图从中发现一般的规律和性质如果仅仅考虑路在平面上的交 叉数的话，显而易见，交叉数为0 ，更进一步的话，路在任何曲面上 的交叉数都是0 因此国内外只是研究了路与某些图类的笛卡尔积图 在平面上的交叉数 两条任意长度的路的笛卡儿积圈以及路与圈的笛卡尔积图也都 是平面图，读者可以很容易构建一个他们在平面上的画法使得他们 的交叉数为0 1 9 8 2 年s j e n d r o ia n dm s 6 e r b o v a 发表了名为“o n t h e c r o s s i n gn u m b e r o f 只a n d 晶g ”的文章，这是首篇研究路与其他图类笛卡尔积 图交叉数的文章在这篇文章中，他们给出了关于s m r 和xg 交叉数的一个上界，并且确定了岛xr 和岛c n 的交叉数，但是 很遗憾的是这篇文章发表在c a s o p i sp r op a s t o v 蕊m a t e m a t i k y 上，我们 在国内终于没有找到这篇文献经过我们的演算，xr 交叉数 的上界应该是( 礼一1 ) 【虹 ，而且后来在m k l e 9 5 的文献【1 9 】中也确 定了当m = 4 时的结果与此上界是吻合的关于此方面的文献在后 来却一直没有出现，本文作者在此基础上，把星推广到了轮，并且 湖南师范大学硕士学位论文 第一次把轮的概念引入到了笛卡尔积图的交叉数研究中，在第三章 中给出了一个路尸m 与轮的笛卡尔积交叉数的上界，并且确定了 m = 1 ，2 ，3 时的交叉数 其他的文章基本是集中在关于一些阶数较低的图与路的笛卡尔 积图交叉数上，阶数为3 的连通图或同构于2 路或同构于3 圈，结 论显然为0 ，因此系统的研究从阶数是4 的图开始 m k l e 6 在此方面做了大量工作，1 9 9 4 年他在( ( j o u r n a lo fg r a p h t h e o r y 上发表了题为“t h ec r o s s i n gn u m b e r so fp r o d u c t so fp a t h sa n d s t a r sw i t h4 - v e r t e xg r a p h s ”的文章( 见文献 2 0 0 ，确定了所有4 阶连通 图与路的积图交叉数，其中”( 4 p n ) = 2 n ，最初的证明在计算和 证明上都是较简洁的在之后的几篇文章中他又陆续给出了所有阶 数是5 的连通图与路的积图的交叉数( 见文献 2 0 - 2 5 ，3 3 1 ) 在这些文章 中，虽然不断的出现一些新的技巧，但是整个的证明难度越来越加 大，值得一提的是m k l e g e 在2 0 0 1 年发表在cd i s c r e t em a t h e m a t i c s 上的“t h ec r o s s i n gn u m b e r so fc a r 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 x g r a p h s ”( 见文献【3 3 】) 用列表的形式列出了所有的2 1 个5 阶连通图 与路的积图的交叉数，从中我们可以看出结果都是关于路的长度的 线性式 近几年来这方面的结果继续推广到了阶数是6 的图，本文在第 四章中确定了5 个6 阶图与路的积图的交叉数，读者将会看到这5 个图在结构上似乎有某种共性，这一点在他们的交叉数上的结果上 也得到体现 湖南师范大学硕士学位论文 - 5 第二章基本概念和性质 做为阅读的必备知识，本章我们介绍交叉数等一些本文中的常 用概念、性质，未说明的概念均同文献2 , 3 ，4 ，5 ，1 5 1 一个图g 是指一个有序三元组( v ( g ) ，e ( g ) ，惦) ，其中y ( a ) 是非 空的顶点集，e ( a ) 是不与v ( g ) 相交的边集，而妒g 是关联函数， 它使g 的每条边对应于g 的无序顶点对图g 的交叉数是指把图g 画在平面上时出现的最小交叉数 下面给出相关交叉数的定义及笛卡尔积图的定义 定义2 1 图g 在平面上的一个画法是指把图的顶点画为平面 上的结点，把图的边画为平面的弧 定义2 2 图g 的一个交叉点是指图的边在非结点处的相交点 定义2 3 图g 的交叉数，用”( g ) 表示，是指图g 在平面上的所 有画法中边与边的交叉点的最小数 定义2 4 图g 在平面上的一个最优画法是指图g 在平面上的 恰好具有最小交叉数的画法 而我们已经发现这种最优画法中的最小交叉数必然是在一种我 们称做是好画法的画法中实现： 定义2 5 图g 在平面上的一个好画法是指图g 在平面上的画 法满足以下四个条件： ( 1 ) 连接同一个结点的任意两条边不相交； ( 2 ) 边不能自身相交； ( 3 ) 任何两条相交的边最多交叉一次； ( 4 ) 没有三条边交叉于同一个点 注：定义2 5 中条件( 4 ) 是为了研究而统一规定的前三个条件 ( 1 ) ，( 2 ) ，( 3 ) 是最优画法中必然满足的因为假设不然，我们可以对画 法改进，进而得到一个具有更小交叉数的画法从而与最优画法的定 义矛盾( 见图2 1 ，2 2 ) 6 湖南师范大学硕士学位论文 父又爻 图2 1 ：图g 的好画法中不允许出现的4 种情况 图2 2 ，对图2 1 中前三种画法的改进 注：定义2 1 2 5 中的“平面”可改为“曲面”，且相关定义可推广 到曲面的情况鉴于本文中研究的交叉数都是在平面上的交叉数， 因此作者采用了这样形式目前国内外也大多是对在平面上的交叉 数的研究，但也有少数文章讨论了一些图在环面等曲面上的交叉数 ( 见文献1 3 6 t ) 目前国内外在确定图的交叉数问题上，对“= ”的证明都是采 用“s ”且“”的手法，其中对“s ”就是通过寻找一个具体的 好画法来给出而对于“”的证明正是各位研究者们致力于解决 的问题，用的方法和技巧很多，但在定理的总体证明上采用的都是 传统的数学归纳法，本文给出的几个定理也不例外的采用了这样的 手段 定义2 6 两个图g 。和g 。的笛卡尔积图用g 1 g 。表示，它 是这样的图：点v ( g 1 g 2 ) = v ( a 1 ) xv ( a 2 ) ；边集e ( g l g 2 ) = ( “，吩) ，( “。，) ) ：u = 札。且协，) e ( g 2 ) 或者似，) e ( g x ) 且码= ) 另外，本文中无特别说明所涉及图均指连通简单图r 表示长 为n 的路，叉表示有礼条边的星所。g 表示长为n 的圈，u 名表示由 一点到一个圈的悬挂，也即从独点k 。向g 的所有n 个点分别连一 条边，看起来就象一个车轮，因此起名叫n 轮 与我们的研究特别有关的拓扑学成果是j o r d a n 曲线的一些内 一、i 、厂v_八 湖南师范大学硕士学位论文 7 容一条j o r d a n 曲线是指一条连续的，自身不相交的，起点和终 点相重合的曲线设j 是平面上的一条j o r d a n 曲线平面的剩下部 分被分成两个不相交的开集，称为。，的内部和外部j o r d a n 曲线定 理指出连接内部的点和外部的点的任何连线必在某点和l ，相交( 见 文献 1 5 】) 这个定理在直观上是很明显的，也是贯穿于交叉数的证 明中的一条基本定理 如果一个图g 存在一种画法币使得它在平面上的交叉数是0 ，则 称这个图为平面图，且称这样的画法为平面图g 的一个平面嵌 人平面图g 的一个平面嵌入把平面划分成若干个连通区域，这些 区域的闭包称为g 的面在本文的证明中也用到了连通平面图中的 e u l e r 公式：在连通平面图g 的平面嵌入中，口一e + ，= 2 ，其中，v 、 e 、，分别是图g 在平面嵌入中的顶点数、边数、面数 若g 1 和g ：是两个边不相交的图，那么g 1 u g 2 表示点集为v ( g 1 ) u v ( g 2 ) 和边集为e ( g ，) u e ( g 。) 的图设d 为一个图g 的好画法，我 们用c r d ( g ) 表示图g 在画法d 下的交叉数若g ，和g 。为图g 的 两个子图，我们用盯d ( g 。，g 2 ) 表示g 。与g 2 在画法d 下的交叉数 假设g 。，g 2 ，g 。是边互不相交的g 的子图，易得到如下公式：( 见 文献1 6 1 ) c r v ( g lug 2 ) = c r v ( g 1 ) + c r d ( g 2 ) + e r d ( g 1 ，g 2 ) c r o ( g 3 ，g 1ug 2 ) = o r b ( g 3 ，g 1 ) + c r d ( g a ，g 2 ) ( 2 1 ) ( 2 2 ) 在两个图f 和h 中，对于某些边的加入或抹平2 度点( 均可反复 多次) 这样的过程使得这两个图同构，则称f 和驯司胚，记为f 日 易知同胚的两个图同具有如下的性质： 性质2 1 若f 一日，则c r ( f ) = ”( 日) 对图g 和它的任意子图日的交叉数之间的关系，有如下： 性质2 2 若日为图g 的子图，则c r ( h ) ”( g ) 证明：设咖是图g 的一个好画法，使c r o ( g ) = c r ( g ) ，则曲自然 诱导它的子图日的一个画法记为西kc r o l h ( 日) c r o ( g ) = c r ( g ) ，由交 叉数的定义，c r ( h ) c r ( g ) 口 8 湖南师范大学硕士学位论文 第三章路f ) m 与轮w 的笛卡尔积交叉数 1 9 8 2 年s j e n d r o ia n dm s e e r b o v a 发表了名为“o nt h ec r o s s i n gn u m b e r o f r a n ds m g ”的文章，这是首篇研究路与其他图类笛卡尔 积图交叉数的文章在这篇文章中，他们给出了关于s m p n 交叉 数的一个上界，并且确定了岛r 的交叉数( 见文献 2 5 1 ) 后来在 m k l e g e 的文献 1 9 中确定了s 4 r 的交叉数关于此方面的文献在 后来却一直没有出现本文作者在此基础上，把星推广到了轮，并 且第一次把轮的概念引入到了笛卡尔积图的交叉数研究中，在本章 中共给出4 个定理，首先给出了路p m 与轮眠的笛卡尔积交叉数的 一个上界，并且分别确定了p 1 w 名，p 2xu 名和p 3 w 厶的交叉数 一般地，我们记p m 眠的点为( i ，j ) ，边为咒+ 1 个路径焉，m 个 轮n 名，其中( i ，0 ) 为w 2 的n 度点，i = 0 1 n l ；j = 0 1 ，n 3 1c 7 ( w 名) 的上界 本节的结果是定理3 1 ，给出了路p m 与轮u ，n 的笛卡尔积交叉数 的一个上界 礼 5 证明：当礼2 时，易得p 仇为平面图 当礼23 时，图3 1 中( 见下页) ，我们给出了一个p 2x 的好画 法，其交叉数为( 2 1 ) l 华j + ( 2 + 1 ) 一7 类似地，我们得到一个 p m w ，n 的好画法，其中任意磁( 峨) 自身无交叉，任意两个磁( 峨) 之间无交叉，当i = 1 ，2 ，m 一1 时，w ：与所有磁之间的交叉数为 i 妊辈i + 1 ，当i = 0 ，m 时，峨与所有碟之间的交叉数为1 ，因此， 我们可得c r ( p m 眠) s ( m 一1 ) l 与坐j + ( m + 1 ) 特别地，当n ；3 ，4 时，定理1 中的等号详情请参阅文献4 和文献5 + + m m + + 0 羔 显牵 一 一 仇 m l | 一 ， r 黝 州 理定 湖南师范大学硕士学位论文9 图3 1 ：p 2xw 5 的一个好画法 3 2p 1 瞩的情形 本节的结果是定理3 2 ，确定了p i h 名的交叉数 定理3 2c r ( p , ) = 2 ，这里n 3 证明：由定理3 1 ，有c r ( p l w n ) s 2 又当n 3 时，p 1 含有同胚于尬xk 2 的子图，而”( 硒( 2 ) = 2 ( 见文献【2 1 ) ，由性质2 1 ，2 2 ，有c t ( p , w n ) 2 定理得证【】 3 3p 2x 眠的情形 本节的结果是定理3 3 ，确定了b w 名的交叉数为了证明定理 3 3 ，我们首先来看一些记号和引理3 3 1 为讨论方便，我们记r 眠的点为x ；，z = a ，b ，c ，i = 0 ，1 ，n ，边 为n + 1 个路径舅，3 个轮w z ，其中z o 为孵的n 度点( 即中心点) 设 t 2 ，i = 1 ，2 ，n ，为由点a o ，b o ，c o ，a i ，b i ，c i 及边( a o ，a i ) ，( b o ，6 ) ，( c 0 ，c i ) ，( a 。，6 1 ) ， ( b i ，c i ) 构成的子图( 见下页图3 2 ) 引理3 3 1 设d 为p 2 i 的一个好画法，若在好画法d 中， c t d ( 丁一1 p ) = 0 ，则c f d ( 丁4 ，p _ 1 u t ”) 1 ，这里i = 1 ，2 ，n 一2 l o 湖南师范大学硕士学位论文 证明：设驴为d 导出的丁”1u p 的子图，由题设，则在d + 中，任意一个区域的边界上最多只包含a 。，b o ，c o 中的2 个点现在考 虑由p 。u p u p ，i = 1 ，2 n 一2 导出的子图d ”，若把点a b ，c i 全 放在d 的同一个区域中，至少会有一个p 与7 1 n _ - u 丁n 之间的交 叉，若放在两个以上的区域，也至少会有一个丁2 与? 一，u 丁n 之间 的交叉，综上，c f d ( 丁2 ，p - 1u t ”) 1 ，这里 = 1 ，2 ，n 一2 口 图3 2 ：，示意图 定理3 3 胛( 马) 一【与譬j + 3 ，这里n 3 证明：由定理3 1 ，有”( 尸2 ) 曼【与竖j + 3 我们对礼归纳来证明”( r 眠) 【也+ 3 由定理3 1 ，当n = 3 ，4 时定理3 3 已经成立假设当n 5 时， ”( p 2 一2 ) 纠气坚j + 3 ( 3 1 ) 下面考虑b 眠的任意一个好画法d ，分两种情况考虑： ( 1 ) ：任意两个不同的p 与t ，的子图，都有盯d ( p ，t j ) 1 ，则 c r d ( p 2 讳乞) c 尝【垒亏坐j + 3 ( 3 2 ) ( 2 ) ：存在i 、j ，不妨设为札一1 、n ，使”d ( p 一1u r “) = 0 ，则由引 理3 3 1 ，得c r 。( n u - 2 p ，p t u p ) 礼一2 ，在p 2 中去掉p 一1 u t n = 1 的所有边，得到一个同胚于p 2 ，n 一。的图，设为g ，由归纳假设( 3 1 ) 湖南师范大学硕士学位论文 1 1 式和性质2 1 ，我们得c r d ( g ) l 坦萍j + 3 ，又由性质2 2 ，得 c r 口( p 2 ) c r 。( g ) + c r 。( ，竖t 4 ，丁“_ 1 u p ( 33 1 l 垃孚星j + 3 + ( 礼一2 ) l 生亏坐j + 3 综合情况( 1 ) ，( 2 ) ，都有。- ( p 2 u 名) 2l 垃竽j + 3 定理得证d 3 4p 3 的情形 本节的结果是定理3 4 ，确定了尸3xw 名的交叉数同样，为了证 明定理3 4 ，我们首先来看一些记号和引理3 4 1 同样，我们记p 3 t 的点为x 。，z = o ，b ，c ，d ，i = 0 ，1 ，。n ，边为礼+ 1 个路径p g ，4 个轮n 公，其中。o 为i 增的n 度点( 即中心点) 设t 2 ，江1 ，2 ，为由点a o ，b o c 0 ，d o ，a t bc ；、d i 及边( a o ，啦) ，( 6 0 ，b d ， ( c 0 1c i ) ，( 岛，d 1 ) ，( o 。b i ) ，( b “。) ，( c i ，d i ) 构成的子图 引理3 4 1 设d 为只眠的一个好画法，若在好画法d 中， c t d ( t ”1 ，p ) ) = 0 ，则c r d ( t 4 ，p _ 1u t “) 2 ，这里i = 1 ，2 ，佗 证明：此引理与引理3 3 1 的证明方法相当类似，只需注意到此 时由p 。u t n 导出的子图中，任意一个区域最多只包含b o ，c o ，d o 中的2 个点，且任意两个相邻的区域中最多只包含a o ，6 0 ，c o ，d o 中的3 个点 口 定理3 4c r ( p 3 u ，n ) = 2 l 屿垡j 十4 ，这里 3 证明：由定理3 1 ，有o ( p 3 w a ) 2l i 学j + 4 相反不等式的证明我们采用对n 归纳假设o ( p 3 u 名) 2 【与坐j + 4 对小于n 的自然数都已成立 下面我们考虑p 3 的任意一个好画法d 我们讨论p 是否与其他，有交叉，分两种情况： ( 1 ) 若c r d ( p ，p ) 21 ，对任意扛1 ，2 ，n 一1 成立，则 c t d ( ut 。，t “) n 一1 ，我们移去丁m 中的所有边，得到同胚于p 3 眠一， 1 2 ， 湖南师范大学硕士学位论文 的图，利用归纳假设同理定理3 3 中证明得 c r d ( b 眠) 2 坦芋里j + 4 + ( n 一1 ) 2 【生i 芝j + 4 ( 3 4 ) ( 2 ) 若存在i ，不妨设为n l ，使盯d ( p ，p ) = 0 ，则由引理3 4 1 同理于定理3 3 证明中的情况( 2 ) 即得证明完成口 湖南师范大学硕士学位论文 1 3 第四章5 个六阶图与路r 的笛卡尔积交叉数 从二十世纪后期起，m k l e i n ：等人开始对阶数较小的图与路、 星、圈的笛卡尔积图的交叉数的研究( 见文献f 1 6 2 6 ，3 3 ) 其中所有不 大于5 阶的简单图与路的笛卡尔积图的交叉数都已经被确定近几 年来这方面的结果继续推广到了阶数是6 的图，本章确定了5 个6 阶图与路的积图的交叉数 本章我们总是假定g j ，j = 1 ，2 ，3 ，4 ，6 ，分别是具有6 个点的如下： 2 2 343434 g lg 2 g 3 形 34 g 4 52 g 6 5 图4 1 ：本章中的5 个六阶图 注：考虑到本章中5 个图的特点，我们的变量跳过了j = 5 的情 本章的主要结果是如下定理： 定理：设g j 为上述所示的图，r 是长为礼的路，则有 ( 1 ) 当j = 1 ，3 时，c r ( g j p n ) = j 礼一1 ； ( 2 ) 当j = 2 ，4 ，6 时，c r ( q r ) = j n 圆 1 4 湖南师范大学硕士学位论文 注意到在笛卡尔积图q p n 中，它有6 ( n + 1 ) 个顶点，n + 1 个 拷贝岛，( 用g ；表示，0si 礼) ，以及6 个拷贝r 为了下面证明的 方便，在q r 中，我们让每个拷贝q 中的边着红色，其余的边 ( 即每条长为n 的路拷贝p 。) 着蓝色 4 1 一些定义和引理 为证明这些定理，我们首先给出下面一些本章中用到的定义， 性质和引理 定义4 1 1 设g 是图，c 为g 的一个圈，若a v ( c ) 是连通的， 则称c 是不可分离圈若g 的点导出子图g ( g ) 】_ c ，则称c 是一 个诱导圈 引理4 1 2 设c 为平面图g 的不可分离诱导圈，则在g 的任何 一个平面嵌入中，c 必定是这个嵌入的某个面的边界 证明：首先因为是图g 的平面嵌入，所以圈c 的边上没有交 叉再由圈c 的不可分离性，所以不在圈c 上的图g 的其他所有点 将全部落在圈c 的内部或全落在圈c 的外部，不妨设为外部最后 因为圈c 为诱导圈，可以得到圈c 内部没有图g 的边否则圈c 上 有弦引理得证口 引理4 1 3 在平面图g 的任何平面嵌入中，3 边区域个数少于 图g 的3 阶完全子图尥的个数 定义4 1 4 对一个图g ，我们删除g 的若干m 条边后可以得到 一个平面图，其中m 是非负整数，我们定义所有满足上述条件的m 的最小值为r ( g ) ( 【见文献3 a 1 ) 易见，对g 的任意好画法，有c r ( g ) r ( g ) ( 【见文献3 3 1 ) 引理4 1 5r ( k s ) 1 0 证明：记r = r ( 蜗) ，磁为的有2 8 一r 条边的平面子图则 为玩的连通生成子图，由平面图的欧拉公式，在任意磁的平面 画法中有2 2 一r 个区域，因为每个区域至少由3 条边围成，所以有 3 ( 2 2 一r ) 2 ( 2 8 一r ) ，所以r 1 0 湖南师范大学硕士学位论文 1 5 推论4 1 6f 是e ( k s ) 的子集， 引理4 1 7r u g ) 6 证明同理引理4 1 5 ，略 推论4 1 8f 是e ( k r ) 的子集， 贝4c r ( 蚝一f ) 1 0 一i f 贝4c r ( 1 g f ) 6 一i f 4 2 当j = 1 ，2 时，定理的证明 本节的结果是定理4 1 和定理4 2 ，分别确定了g 。、g 。与路的笛 卡儿积图的交叉数 f t ( a ) g ，xp n 的一个好 必 f l i? ； ( 6 ) g 。r 的一个好画法 图4 2 ：g l r 与g 2 r 的一个好画法 定理4 1c r ( g 1 p n ) = n l ，这里礼1 邗型醚勒 1 6 -湖南师范大学硕士学位论文 证明：由图4 2 ( o ) ，我们得c t ( g ，p 丌) s 忆一1 又因为g t 含有子 图岛，所以g 。p n 含与s 3 r 同胚的子图，而盯( 昆r ) = n 一1 ( 见 文献 2 5 】) ，由性质2 2 又得到c r ( g ，尸n ) n 一1 定理4 1 得证口 定理4 2 ( g 2 r ) = 2 n ，这里n 1 证明：由图4 2 ( 6 ) ，我们得c r ( g 2 p n ) 2 ( n 一1 ) + 1 + 1 = 2 n 又因为g 。同胚于风，所以g 。r 含与k 4 r 同胚的子图，而 c r ( k ax 尸n ) = 2 n ，礼l ( 见文献 2 0 】) ，由性质2 2 又得到c 1 ( g 2 r ) 2 n 定理4 2 得证 】 4 3 当j = 3 时，定理的证明 本节的主要结果是定理4 3 ，确定了g 。与路的笛卡儿积图的交叉 数为证明定理4 3 ，首先来看下面的一些引理 引理4 3 1 在平面图g 。的任何平面嵌入中，每一个面的边界上 至多包含g 3 的5 个顶点 证明：根据欧拉公式计算出图g 。的任何平面嵌入分平面为9 + 2 6 = 5 个区域，由引理1 ，其中有3 个3 边区域，再根据平图中， 所有面的次数之和等于边的两倍，计算得到其他两区域的次数和为 9 ，因为g 。为简单图，所以没有1 边和2 边区域，再由引理4 1 3 ，最 多有3 个3 边区域，所以其他两区域的次数分别为4 和5 ，因此面的 边界上分别包含了g 。的4 个和5 个顶点 】 引理4 3 2 在任何g 3 只( 他1 ) 的好唾法中，哦的边上至少有 一个交叉，这里i = 0 ，1 ，2 ，佗 证：若砩自身有一个交叉点，则引理得证若c r d i ：岛，g ；) = 0 ， 由引理4 3 1 ，每个面的边界上至多包含锈的5 个顶点，因此q 至少 被其他q ( j i ) 交叉一次或被连接岛的蓝色边交叉一次 f 】 引理4 3 3c r ( g ：) = 3 证明：g ：如图4 3 ( o ) 所示，由图中画法可得c r ( 岛) 3 把g ：看 做是凰的有2 1 条边的连通子图，则利用推论4 1 6 ，得盯( g ：) 3 ，即 得证明 湖南师范大学硕士学位论文7 ( a ) 岛示意图( 6 ) g 。p n 的一个好画法 图4 3 ：g ：示意图与g 3xr 的一个好画法 引理4 3 4 设d 是g 。r ，札2 的一个好画法，如果在画法d 中，每个g ；至多有2 个交叉点，那么d 至少有3 咒一1 个交叉点 证明：首先我们有如下3 个断言： 断言( i ) 任何两个不同的g ；与鸹不能彼此交叉 假设q 与g j 交叉，则c r d ( 岛，岛) 2 ( 因为g ；是2 连通图) 若 删除g 3 的所有边，所得图或者同胚于g 。毋n 一1 ) 或者包含一个同 胚于g 3 p ( n 一1 ) 的子图，由引理4 3 2 ，q 还会至少有1 个交叉，与 引理假设矛盾 断言( i i ) g o ，四，g 言_ 1 ，g 纩1 ，g ；都位于g 导出的同一个区 域中 我们假设有两个不同的磁与碍位于q 导出的两个不同区域 中，因为晓的画法d 分平面成这样的区域，使得任何两个区域的 共同边界上最多有g ；的3 个顶点( 不管g ；是否交叉) ，而在画法d 中岛与g ；到g 5 的蓝色边至少有6 个共同点，且至多3 个为g i 的 顶点，因而g ；的边上至少有3 个交叉点，这也与引理的假设矛盾 断言( i i i )没有不关联g ；的蓝色边交叉g 的红色边 假设有不关联于g ；的蓝色边交叉q 的红色边，则q 至少被 t ( t r 表示吗“到g ；的蓝色边) 的边交叉2 次( 因为g ；是2 连通图) ， 而且g 5 的边有2 个内部交叉点或者g 的边被关联于岛的蓝色边 1 8 湖南师范大学硕士学位论文 交叉2 次或者g ；的边有1 个内部交叉点且g ；的边至少被关联于g ； 的蓝色边交叉1 次，这再一次与引理假设矛盾 对i = 1 ，2 ，n 一1 ，我们用h 卜1 一”1 表示由矿( g ；q ) u v ( g ) u v ( q + 1 ) 导出的g 3xr 的子图，让砩- l , i + - 表示从h i - 1 , i + t 中删除g r l 的4 条边与g 扩1 的4 条边使得蛾- l , i + 1 有一个子图同构于g 未而g ：三3 在g sxr 的好画法当中，我们定义h i - l , i 斗1 的如下类型交叉数为 f ( h ”1 ”1 ) ( 峨- 1 一“如下类型的交叉数为，( 碰- 1 , i + 1 ) ) ( 见文献 9 ) ： ( 1 ) pu r 件1 的蓝色边与g 的红色边的交叉点； ( 2 ) p 的蓝色边与p + ，的蓝色边的交叉点； ( 3 ) g ；的自身交叉点 容易看到，整个画法的交叉数就是y ( h i - - l , i + ) ， _ 1 ，2 ，n 一1 的 和，而且每一个交叉点在整个交叉数中最多只计数了一次，由断言 ( n ( i i ) ，( i i i ) 知，碰。，* 1 的最优画法的交叉数只有( 1 ) ，( 2 ) ，( 3 ) 三种情 况；因而对每一个i = 1 ，2 ，n 一1 ，f ( h i - l , i 十1 ) ，( h - l , + 1 ) c r ( 岛) 3 ， 而且当i 取遍1 ，2 ，几一1 时，画法d 的交叉数f ( h 1 h 1 ) 3 ( n 1 ) ，由前引理4 3 2 知g 2 与g ；都至少有1 个交叉点，且没有计 算到f ( h k 件1 ) 当中 f = 1 n 一1 因此，唾法d 至少有f ( h 。1 n 1 ) + 1 + l 3 n 一1 个交叉点口 l = l 引理4 3 5c r ( a 3 只) = 2 证明：g 。含有与尬同胚的子图，而k 4 p l 一2 ( 见文献 1 6 】) ，所 以o - ( a s r ) 2 ，又由图4 3 ( b ) 的画法即得证明【l 定理4 3c r ( g 3x r ) = 3 n 一1 ，这里n 1 证明：由图4 3 ( 6 ) 的画法可知c r ( a 3 r ) 3 n 一1 ，这里n 1 相反不等式的证明我们采用数学归纳法 n = 1 时，引理4 3 5 已经说明 假设当n = k 时，有c r ( g 3 r ) 3 k 一1 湖南师范大学硕士学位论文 当扎= k + 1 时，反设存在g 3 p k + 1 的好画法d ，使c r ( g 3 r + 1 ) 3 ( k + 1 ) 一1 ，由引理4 3 4 知，毖然存在某个i 使g ；至少有三个交叉 点，从g 。p k + 。中删除q 的所有边得到一个图同胚于g 。r 或含 有同胚于g 3 xp k 的子图，而c r d ( g 3 p k ) 3 ( k + 1 ) 一l 一33 k 1 ， 这与我们的归纳假设矛盾，因而c r