（运筹学与控制论专业论文）关于图的笛卡尔积交叉数的研究.pdf

摘要 图的交叉数是在近代图论中发展起来的一个重要概念，主要研究 如何把图画在一个平面上，使其交叉的数目最少通常这项研究都采 用纯数学方法证明然而，确定一般图的交叉数是一个n p 一完全问题， 因此，到目前为止有关交叉数的结果比较少，仅限于一些特殊图和简 单图的交叉数甚至于在许多情况下，试图找出图的交叉数的一个好 的上界或下界也很困难 近年来，笛卡尔积交叉数越来越受到国内外有关学者的重视和关 注本文运用组合方法和归纳思想以及反证法，主要研究了六阶图 g ( i _ 1 ，2 ，3 ，4 ) 与路的笛卡尔积交叉数，五阶图g l ，与星图最的笛卡尔 积交叉数，轮岷与星图最的笛卡尔积交叉数全文由五个章节构成 第一章：较为详细地交代了交叉数的起源，理论和实际意义，国内 外发展的动态，本文的写作背景，将要解决的问题和文章的创新之处 同时对与交叉数有关的一些基本概念和性质进行了解释 第二章：主要确定四个六阶图q ( i = 1 ，2 ，3 ，4 ) 与路只的笛卡尔积交 叉数 第三章：主要研究了五阶图g 1 ，与星图最的笛卡尔积交叉数 第四章：主要得到了轮联与星图鼠的笛卡尔积交叉数 第五章：提出了研究工作在发展中的一些问题以及作者在以后将 致力于前进的方向 关键词：交叉数：轮：路：星图：笛卡尔积：好画法 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 印h si sav i t a lc o n c 印ti nm o r d e ng r 印h t h e o i t s 印p l i c a t i o ni si m p o n a n tn o to n l yi nm e o b u ta l s oi np r a c t i c e t h e ni th a sa t t r a c t t e dm a n y 伊印hm e o 哆e x p e r t st o s m d yw eh a v e a l r e a d yl m o 、mt h a t t od e t e n l l i n et h ec r o s s m gn u n l b e r so fg r a p h si s n p - c o m p l e t e b e c a u s eo fi t sd i 伍c u l 咄a tp r e s e n tt h ec l a s s e so fg r a p h s w h o s ec r o s s i n gn u n l b e r sh a v eb e e nd e t e l l n i n e da r ev e r ys c a r c e ，a n dt h e r e o n l y s o m e s p e c i a l伊印h s w h o s e c r o s s i n g n 啪b e r sa r e k n 筛m e v e ni ns o m ec a s e s ，i ti sv e 拶d i 衢c u l tt of i n dt h eu p p e ro r1 0 w 钉 b o u n d so ft h ec r o s s i n gn u m b e r so f 伊a p h s i 沁c e n u y ；m ec r o s s i n gn u n l b e r so ft h ec a 九e s i a np r o d u c t sb e c o n l e m o r ei n t e r e s t e d h 1t h i sp 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 叭e s i a n p r o d u c t so fg ( i = 1 ，2 ，3 ，4 )a n d ， d e t e n n i n et h e c r o s s i n g n u m b e r so ft h ec a n e s i a np r o d u c t so fa $ 5 $ 一v e n i c e sg r 印h s g 1 3 w i t h 鼠，a n d 呢w i t h 最 c h 印t e ro n e ，i n t l c i d u c i n gt h eb a c k g r o u n d so ft h ec r o s s i n g n um _ b e r so f 鲫h s ，i t sd e v e l o p m e n ta r o u n dm ew o r l d ，t h em e a n i n g so ft h e r e s e a r c h ，t h ep r o b l e m sw ew i l ls o l v e ，a n dg i v i n gs o n l ec o n c 印t i o n sa n d p r o p e r t i e s c h a p t e rt w o ，d e t e l l l 血n i n gm ec r o s s i n gn u i t i b e r so fm ec a r t e s i a n i i i p r o d u c t so fg f ( i = l ，2 ，3 ，4 ) w i t h 只 c h 印t e rt h r e e ，d e t e m i n i n gt h ec r o s s i n gn uh 1 _ b e r so ft h ec a n e s i a n p r o d u c t so fa5 - v e n i c e s 鲫h sg 1 3w i t h 最 c h a p t e rf o u r ，d e t e m l i n i n gt h ec r o s s m gn u m b e r so ft h ec a r t e s i a n p r o d u c t so f 呢w i t h 最 c h 印t e rf i v e ，d e s c m i n gs o m eq u e s t i o n sw r h e nr e s e a r c h i n gi n t ot h i s p 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 ；w 1 1 e e l ；p a m ；s t a r ( 计印h ；c a r t e s i a n p r o d u c t ；g o o dd r a w i n g i v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的研究成果除了文中特别加以标注引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完全 意识到本声明的法律后果由本人承担 学位论文作者签名：笏、挖耸凶。净玉月沾日 。 。 l 7 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，研究 生在校攻读学位期间论文工作的知识产权单位属湖南师范大学同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分内 容编人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密 ( 请在以上相应方框内打“、嚣) 作者签名： 导师签名： 獬 交别处 日 日巧【 月 月 j b 年 年 、j， ，1 期 期 关于图的笛卡尔积交叉数的研究 1 绪论 1 1 研究背景 图论( 【1 】- 【3 ) 是一个内容非常丰富而且应用十分广泛的数学分支，起 源于著名的哥尼斯堡七桥问题 在哥尼斯堡的普莱格尔河中有两个岛，七座桥将河岸与岛以及岛与 岛联接起来问题在于能否从四块陆地中任何一块出发，在通过每座桥 恰好一次后回到起点人们经过数次尝试后都没有成功欧拉在1 7 3 6 年 解决了这个问题，他将陆地看成点，桥看成边，构造了一个图，再用与图 有关的方法证明了这个问题没有解因此，欧拉成为了图论的创始人 如今图论已经发展出很多分支，并且和实际应用联系非常紧密 图的交叉数是图论中的一个重要概念，从上个世纪七十年代初匈牙 利数学家p a lt u r 缸根据其在一个砖厂碰到的实际难题( t u r 缸sb r i c k f a c t o r yp r o b l e m ) ( 见文献【4 5 】) ，从而提出了交叉数的概念以来，图的交 叉数问题逐渐成为国际上一个非常活跃的图论分支，很多图论专家对这 方面进行了深入研究研究图的交叉数不仅具有重要的理论意义，而且 有较强的现实意义，在许多领域有着非常广泛的应用，例如： ( 1 ) v l s t 中的圈布局问题； ( 2 ) 草图的识别与重画问题，具有比手写汉字识别更为广泛的应用领域； ( 3 ) 工业上电子线路板设计中的布线问题； ( 4 ) 生物工程d n a 的图示； ( 5 ) 软件开发过程中文档部分的e r 图( 实体联系图) 等的自动生成 ( 6 ) 在几何学、堆垒数论与测度论等理论中的应用 然而，文献 6 】证明了确定图的交叉数问题属于n p 完全问题由于 其难度，目前国际上对交叉数的研究主要集中在以下几个方面： 1 特殊图类的交叉数 硕士学位论文 这些图主要包括结构特殊，规律性较强的图类，一部分已经确定了交 叉数的精确值，还有一部分只给出了交叉数的上下界或猜想但具体结 果较少，主要有： ( 1 ) 笛卡尔积图交叉数： 对于猜想凹( g ) ( 仇一2 ) 钆，n ) ，r i n g e i s e n ，b e i n e k e ，m k l e 吾芒和r i c h t e r ，j a ya d 锄s s o n 等证明等号对仇= 3 ，4 ，5 ，6 ，7 成立( 见文 献 7 】- 1 4 】) 从二十世纪后期起，捷克数学家m k l e 豆芒等人开始研究阶数较小的 图与路r ，星图& ，圈g 的笛卡尔积的交叉数( 见文献【1 5 】- 【2 2 】) 由于阶 数为3 的连通图或同构于2 路或同构于3 圈，它与路r ，星图& 的笛卡 尔积的交叉数显然为o 因此系统的研究从4 阶连通图开始的m k l e 酌 1 9 9 4 年确定了所有4 阶连通图与路r ，星图& 的笛卡尔积的交叉数( 见 文献【17 ) ，之后，他又陆续给出了所有5 阶连通图与路r 的笛卡尔积的 交叉数( 见文献 1 8 - 2 2 】) ，以及给出了部分五阶连通图与星图& ，圈g 的笛卡尔积的交叉数 ( 2 ) 完全图的交叉数： 关于完全图的交叉数的猜想： c r ( ) = 翘【孚j 字儿字j 目前仅证明了等号对于n 1 0 成立盯( g ) 表示图g 的交叉数；h 表 示不超过礼的最大整数 ( 3 ) 完全二部图的交叉数： t u r 锄的“砖厂问题”实际上等价于确定完全2 部图，靠的交叉 数z a r a u l k i e w i c z 在文献【5 】中“证明 了 c r ( ，n ) = 目【字峥【孚m 他) 一9 一 关于图的笛卡尔积交叉数的研究 但r i n g e l 和k 撕n e n 不久各自独立发现z a r a n k i e w i c z 在文献【5 】中的证 明有误( 参见文献 2 3 】) ，因而确定完全2 一部图，几的交叉数问题目前 仍然是一个公开问题习惯上把上式称之为z a r a n k i e w i c z 猜想，把上式 右端记为z ( m ，n ) d j k l e i t m a n 在1 9 7 0 年证明了等号对于仇i 凡( m ，n ) 6 时成立( 见文献 2 4 】) w o o d a l l 于1 9 9 3 年证明了当m = 7 且礼1 0 时等 号也成立( 见文献【2 5 】) 到目前为止还没有关于此方面的新结果 ( 4 ) 完全三部图的交叉数： 上世纪八十年代，k a s 锄。证明了仃( ，3 ，n ) = z ( 4 ，n ) + 【詈j ， c r ( 鲍，3 ，n ) = z ( 5 ，佗) + 礼( 见文献 2 6 】) 最近黄元秋教授证明了c r ( k - ，4 ，n ) = 钆( 礼一1 ) = z ( 5 ，亿) + 2 【墨j ( 见文献【2 7 ) ；后梅汉飞教授又与黄元秋教授合作证明了 盯( 尬，5 ，n ) = z ( 6 ，竹) + 4 【墨j ( 见文献【2 8 ) ；2 0 0 5 年黄元秋教授又与赵霆雷合 作证明了，4 n = z ( 6 ，n ) + 2 礼( 见文献【2 9 】) ；同时在假设z a u r a n k i e w i c z 猜想 对于m = 7 成立的前提下，黄元秋教授与赵霆雷确定了c r ( k ，6 ，n ) = z ( 7 ，n ) + 6 吲( 见文献【3 0 ) ；其后不久又在假设z a r a n k i e w i c z 猜想对于m = 8 ，m = 9 成立的前提下，确定了虬，7 礼，甄，8 ，n 的交叉数( 见文献 3 1 】 3 2 】) ( 5 ) 联图的交叉数 与笛卡尔积图相比，两个图的联图是另一种图运算，目前就联图的 交叉数的讨论还很不充分，仅有b o g d a no p o r o w s l ( i 等在 3 3 】中证明了 凹( 岛vg ) = 6 2 有某种特点的图的交叉数的一些性质 因为具体确定某个图的交叉数比较困难，所以换个角度从交叉数的 性质如临界交叉数，正则图的交叉数，交叉数的奇偶性等着手研究( 文 献【3 4 】- 4 0 】) ，希望能得到图的交叉数的一些比较好的性质 3 线图的交叉数 l ( g ) 表示图g 的线图，已经证明了凹( l ( g ) ) = 1 与c r ( l ( g ) ) = 2 的充分 必要条件( 见文献【4 1 】， 4 2 】) 一3 一 硕士学位论文 受到这些文献的启发，应用并创新某些方法，在m k l e 吾芒等人研究 阶数较小的图与路r ，星图晶，圈g 的笛卡尔积的交叉数的基础上，本 文给出了六阶图g i 0 = 1 ，2 ，3 ，4 ) 与路r 的笛卡尔积交叉数，五阶图g 。3 与星图& 的笛卡尔积交叉数，轮比与星图& 的笛卡尔积交叉数 1 2 相关概念及性质 本文涉及到的基本概念和性质，未作特别说明均同文献【2 】，且无特 别说明时文中所涉及的图均指简单连通图 图g 是指一个有序三元组( y ( g ) ，e ( g ) ，妒g ) ，其中y ( g ) 是非空的顶点 集，e ( g ) 是不与y ( g ) 相交的边集，而惦是关联函数，它使g 的每条 边对应于g 的无序顶点对 定义1 图g 在平面上的一个画法d ，是指把图的顶点画为平面上的结 点，把图的边画为平面的弧 定义2 图g 在画法d 下的交叉数，是指在画法d 下边与边产生的交叉 点的个数，用c r d ( g ) 表示 定义3 图g 的交叉数，用c r ( g ) 表示，是指图g 在平面上所有画法的交 叉数中的最小值，即盯( g ) = 蝉n c r d ( g ) ) 定义4 图g 在平面上的一个最优画法，是指产生的交叉数目恰好等于 图g 的交叉数的画法 定义5 图g 在平面上的一个好画法，是指图g 在平面上同时满足以下 四个条件的画法： ( 1 ) 连接同一个结点的任意两条边不相交； ( 2 ) 边不能自身相交； ( 3 ) 任何两条相交的边最多交叉一次； 关于图的笛卡尔积交叉数的研究 ( 4 ) 没有三条边交叉于同一个点( 见图1 - 1 ) 图1 1 图g 的好画法中不允许出现的四种情况 注1 定义5 中的条件( 4 ) 是为了研究而统一规定的 前三个条件( 1 ) ，( 2 ) ，( 3 ) 是最优画法中必然满足的因为如果不满足， 我们可以对画法进行改进，从而得到一个具有更小交叉数的画法，这与 最优画法的定义矛盾( 见图1 2 ) ) ( 图1 2 对图1 1 中前三种画法的改进 注2 定义1 定义4 中的“平面 可改为“曲面 ，且相关定义也可推 广到曲面的情况目前国内外大多是研究平面上的交叉数，但也有研究 环面等曲面上的交叉数的( 见文献 4 3 】) 在本文中作者仅讨论平面上的 交叉数 定义6 两个图g ，和g 2 的笛卡尔积用g ，g 2 表示，它是这样的图：点 集y ( g 1 g 2 ) = y ( g 1 ) y ( g 2 ) ；边集e ( g 1 g 2 ) = ( u i ，) ，( 让n ，) ) ：缸i = u n 且 ，) e ( g z ) ，或者 u i ，乱n ) e ( g ) 且= 钉m ) 用星图岛表示完 全二部图k 。在笛卡尔积g 品中，可以方便的用g o ，g 1 伊表示 图g 的n + 1 个拷贝 一5 一 硕士学位论文 定义7 对一个图g ，我们删除g 的若干m 条边后可以得到一个平面图， 其中m 是非负整数，我们定义所有满足上述条件的m 的最小值为r ( g ) ( 见 文献 4 4 】) 易见，对g 的任意好画法，有凹( g ) r ( g ) 定义8 设g 是图，c 是g 的一个圈，若g y ( c ) 是连通的，则称c 是 不可分离圈若g 的点导出子图g ( c ) 】一c ，则称c 是一个诱导圈 性质1 设c 是平面图g 的不可诱导分离圈，则在g 的任何一个平面嵌 入中，c 必定是这个嵌入的某个面的边界( 见文献【4 4 】) 性质2 令咖是图g 的一个好画法且且，易和马是图g 的彼此互不相交 的边集，则有 ( 1 ) 盯毋( 日u 易) = 凹( 目) + c ( 晶，易) + 盯( 易) j ( 2 ) 仃( 日u 易，琶) = 盯多( 日，马) + 凹牵( 易，岛) 若在图f 的某些边上加入或抹平2 度点( 均可反复多次) ，得到的图 与图日同构，则称图f 和图日同胚，记为f 一日 性质3 若f 日，则有： c r ( f ) = 盯( 日) 性质4 若日是图g 的子图，则有：盯( 日) 盯( g ) 一6 一 关于图的笛卡尔积交叉数的研究 2 六阶图q0 = 1 ，2 ，3 ，4 ) 与路r 的笛卡尔积交叉数 从2 0 世纪后期起，m k l e 誊迂等人对阶数较小的图与路，星，圈的笛 卡尔积图的交叉数进行了研究，见文献( 1 5 2 2 】) 肖文兵等人开始研究 昏阶图与路，星的笛卡尔积图的交叉数( 见文献 4 5 卜 4 9 ) 作者在这些 结果的基础上运用和发展了他们的某些方法，确定了一类六阶图与路的 笛卡尔积交叉数，从而推广了相关结果 本文我们总是假定g j 0 = 1 ，2 ，3 ，4 ) 分别是图2 1 所示的6 阶图 g 1g 2g 3 g 4 图2 1 四个六阶图q0 = 1 ，2 ，3 ，4 ) 本章的主要结果如下： 定理：设g j 为上述所示的图，r 是长为几的路，则有 c 7 ( g 1 r ) = 2 ( 礼一1 ) ； c r ( g 2 r ) = 4 ( 几一1 ) ； 盯( g 3 r ) = 3 ( 他一1 ) ； 凹( g 4 r ) = 5 n 一1 注意到在笛卡尔积图q r 中，它有6 ( 佗+ 1 ) 个顶点，钆+ 1 个拷贝 q ( o i n ) ，以及6 个拷贝r 为了方便起见，我们让每个拷贝嘭中的 边着红色，其余的边( 即每条长为n 的路拷贝p n ) 着蓝色 7 时时时时 1 2 3 4 = = = = 当当当当 、j、j、，、 1 2 3 4 硕士学位论文 2 1g 1 r 与g 2 r 的交叉数 定理2 1c 7 ( g 1 r ) = 2 ( n 一1 ) ，几1 证明：由图2 2 ，我们有c r ( g 。r ) 2 ( n 一1 ) 又因为g 。包含两个同胚于 星图s 的子图，所以g 。r 包含两个同胚于岛r 的子图而由文献 【1 7 】知，盯( & r ) = n 一1 ，由性质3 和性质4 ，得到c r ( g 1 r ) 2 ( n 一1 ) 因而c r ( g r ) = 2 ( n 一1 ) ，定理得证口 定理2 2c 7 ( g 2 r ) = 4 ( 亿一1 ) ，礼1 证明：由图2 3 ，我们有盯( g 。r ) 4 ( n 一1 ) 又因为g 2 包含一个同胚于 星图鼠的子图，所以g 2 r 包含一个同胚于琵r 的子图而由文献 【17 】知，c r ( 昆r ) = 4 ( 扎一1 ) ，由性质3 和性质4 ，得到c r ( g 2 r ) 4 ( 礼一1 ) 因而c r ( g 2 r ) = 4 ( 礼一1 ) ，定理得证 图2 2g 1xr 的一个好画法 图2 3g 2 r 的一个好画法 2 2g 3 r 的交叉数 引理2 1 设d 是g 3 r ，嚣2 的一个好画法，如果在画法d 下每个g 至多有2 个交叉点，则d 至少有4 ( 礼一1 ) 个交叉点 证明：由引理的假设知，任何两个不同的岛与岛彼此不交叉否则， 职至少有3 个交叉因为岛为2 一连通图，内部红色边产生两个交叉， 还有当连接岛和尊1 或g 纩1 时与蓝色边产生至少1 个交叉与引理假 设矛盾在画法d 下，锑，瞵，g 1 ，甜1 ，g 雪都位于q 导出的同 一个区域中否则，假设有两个不同的岛和g ；位于戗导出的两个不 一8 一 关于图的笛卡尔积交叉数的研究 同区域因为g ；的画法d 分平面成这样的区域，使得任何两个不同的 区域的共同边界上至多有g ；的3 个顶点( 不管g ；是否交叉) ，而画法d 中g ；与q 到雠的蓝色边至少有6 个共同点，且至多3 个为g ；的顶 点，因而磷的边上至少有3 个交叉点，与引理的假设矛盾 让，j 表示g 3 r 的由g ：，g 尹1 ，q ( o i j 礼) 的顶点导出子 图现在我们来考虑由d 导出子图日讲十1 的画法d q + l ，i o ，1 ，2 ，n 一2 ) ， 有如下三种情况( 见图2 4 ) ： ( o )( 6 )( c ) 图2 4 由d 导出子图日印+ 1 的三种可能画法 情况1 ：在画法，州中，g 扩1 的边没有交叉点由引理的假设知画法 如图2 4 ( a ) 所示，因为g 2 与g j 只能位于g 纩1 的同一区域( g 纩1 的外 部区域) ，所以在由d 的导出子图日巧+ 2 的画法，m ，i o ，1 ，2 ，n 一2 】 中，日州，m g 尹1 的边与日钳+ 1 的边至少有4 个交叉点 情况2 ：在画法，中，g 扩1 的边有1 个交叉点由引理的假设知画法 如图2 4 ( b ) 所示，因为g 纩2 与q 只能位于甜1 的同一区域( 甜1 的外 部区域) ，所以在由d 的导出子图印 l + 2 的画法砂m ，i o ，1 ，2 ，n 一2 】 中，日州，t + 2 一g 扩1 的边与所，件的边至少有4 个交叉点 情况3 ：在画法，州中，g 扩1 的边有2 个交叉点由引理的假设知画法 如图2 4 ( c ) 所示，因为g 纩2 与暖只能位于g 尹1 的同一区域，所以甜2 的蓝色边与g 1 至少交叉2 次，则g 争1 共交叉4 次，与引理假设矛盾 因此，当i 遍历o ，1 ，2 ，n 一2 时，画法d 至少有4 ( 礼一1 ) 个交叉点口 9 一 硕士学位论文 定理2 3c 7 _ ( g 3 r ) = 3 ( 几一1 ) ，扎1 证明：由图2 5 ，知c r ( g 3 r ) 3 ( 佗一1 ) 用数学归纳法证明相反的不等 式当n = 1 时，g 3 p 1 为可平面图，c r ( g 3 p 1 ) = o ，结论成立假设 当n = 尼时，盯( g 3 r ) 3 ( 七一1 ) ，现假设n = 七+ 1 时，有一个g 3 r + 1 的好画法，使g 3 最+ 。 3 克由引理2 1 知，必有某个i ，使得g ；有3 个 交叉点，那么我们删除佛的所有边得到一个同胚于g 3 r 或含有同胚 于g 3 最的子图，则c r ( g 3 r ) = 3 ( 一1 ) ，而仃( g 3 最) 3 ( 忌一1 ) ，与 定理的归纳假设矛盾因而c r ( g 3 r ) = 3 ( 礼一1 ) 定理证毕口 图2 5g 3 r 的一个好画法 2 3g 4 r 的交叉数 引理2 2 ：r ( 蚝) l o 证明：记r = r ( 飓) ，砭为凰的有2 8 一r 条边的平面图则砭为的 连通生成子图，由平面图的欧拉公式，在任意的平面画法中有2 2 一r 个区域，因为每个区域至少由3 条边围成，所以有3 ( 2 2 一r ) 2 ( 2 8 一r ) ， 所以7 l 1 0 口 推论2 1 ：f 是e ( 凰) 的子集，则c r ( 尥一f ) 1 0 f 将g 4 的6 个顶点都和另一个点z 连边，得到的图记为q ，用p 表示六条与点z 关联的边( 见图2 6 ) ，有q = g 4up 同理，令萌= p u g 4u t ( 见图2 7 ) 关于图的笛卡尔积交叉数的研究 爪瓜 图2 6g ：的一个好画法图2 7g ：的一个好画法 引理2 3 盯( g ：) = 2 证明：g ：的一个好画法说明c r ( g ：) 2 ( 见图2 6 ) 我们用逐一分析法 来证明相反的不等式在c r ( g ；) = 2 的任何好画法d 下，有以下三种情 况： 情况1 ：凹( g 4 ) = o 根据e u z e r 公式，= 7 ，而g 4 恰有7 个不可分的诱 导圈：1 2 3 ，2 3 4 ，3 4 5 ，1 2 6 ，4 5 6 ，2 4 6 ，1 3 5 6 ， 所以每个区域的边界上最多有g 4 的4 个顶点连接g 4 的6 个顶点和点 z ，则g 4 的边上至少会和产生2 个交叉，即盯( q ) 2 情况2 盯( g 4 ) = 1 在g 4 的每个区域的边界上至多有4 个顶点，连接 g 4 的6 个顶点和点z ，则g 。的边上至少会和p 产生2 个交叉，即 凹( g ：) = c 7 ( g 4 ) + c r ( p ) + c r ( g 4 ，t z ) 3 情况3c r ( g 4 ) 2 ，贝4c 7 _ ( g ：) c r ( g 4 ) 2 上面的分析说明g 4 的边上至少有2 个交叉，且c r ( q ) c r ( ) 2 口 引理2 4 ：盯( 暖) = 5 证明：暖如图2 7 所示，由图中画法可知凹( g ：1 ) 5 把暖看作是尥的 有2 3 条边的连通子图，由推论2 1 得c r ( q ) 5 引理得证 凸 引理2 5 ：若d 是g 4 r 的一个好画法，在d 下每一个g i 上至多有4 个交叉，则c r ( g 4 r ) 5 n 一1 证明：我们有以下三个断言： 断言1 ：任何两个不同的q 与鸹彼此不交叉 ，11 硕士学位论文 否则，由于g i 为3 连通图，g i ( 暖) 至少与暖( q ) 产生3 个交叉，而 且由引理4 每个g i 边上至少还有2 个交叉与引理假设矛盾 断言2 ：础，g j ，g 耄- 1 ，甜1 ，q 都位于g i 导出的同一个区域中 否则，假设有两个不同的暖和g 耋位于g i 导出的两个不同区域不 管g i 是否交叉，g ：的画法d 分平面成这样的区域，使得任何两个不 同的区域的共同边界上至多有q 的2 个顶点，而画法d 中g i 与q 到g 的蓝色边至少有6 个共同点，且至多2 个为q 的顶点，因而g i 的边上至少有4 个交叉点不妨设l 七一i i j 歹一i i ，且不妨设七i ，选 取y ( g i ) ，y ( g 1 ) ，y ( g 勃的导出子图，此子图同构于g 4 r - 由引理 2 3 ，q 还至少有两个交叉，显然这2 个交叉与上4 个交叉不重复与引 理假设矛盾 断言3 ：没有不关联g ：的蓝边与戗的红边交叉 否则，因为俄是3 - 连通图，则g ：至少被墨的边交叉3 次，删除巧的 6 条边，所剩导出子图含有俄的一段同构于g 4 ，m 1 ( 因为巧不关 联g ) ，因此g j 边上至少还有2 个交叉再一次与引理假设矛盾 对i = 1 ，2 ，他一1 ，我们用_ 1 ，i + 1 表示由顶点y ( g 1 ) uy ( g i ) uy ( g 1 ) 导出的g 4 r 子图，让麟_ 1 ，t + ，表示从胃扣1 i + 1 中删除簖1 的6 条边与 甜1 的6 条边使得碰。h t 有一个子图同构于q ，而c r ( 暖) 3 在g 4 r 的好画法中，我们定义酽- 1 ，件1 的如下类型交叉数为，( 序- 1 升1 ) ( 碰。，i + 1 如 下类型的交叉数为，( 碰- 1 州) ) ( 见文献 9 】) ：( 1 ) 矿up 的蓝色边与戗的红 色边的交叉点：( 2 ) ，的蓝色边与于+ 1 的蓝色边的交叉点；( 3 ) 暖的自 身交叉点 容易看到，整个画法的交叉数就是，( 酽- 1 ，件1 ) ，i = 1 ，2 ，佗一1 的 和，而且每个交叉点在整个交叉数中最多只计算了一次，由断言1 ，2 ，3 知噬。，m 的最优画法的交叉数只有( 1 ) ，( 2 ) ，( 3 ) 三种情况；因而对每一 个i = 1 ，2 ，n 一1 ，( 驴1 ，州) 厂( 琏。，件1 ) 凹( 暖) 5 ，而且当t 取 遍1 ，2 ，佗一1 时，画法d 的交叉数蓦，( 1 ，件1 ) 5 ( n 一1 ) 又 一1 2 关于图的笛卡尔积交叉数的研究 由引理2 3 ，我们知g 0 与g 孑都至少有2 个交叉，因此c r d ( g 4 r ) 身，( 日一1 ) + 2 + 2 = 5 ( 几一1 ) 引理证毕 口 定理2 4 ：c r ( g 4 r ) = 5 礼一1 ，几1 证明：由图2 8 ，知盯( g 4 r ) 5 礼一1 ，礼1 用数学归纳法证明相反的不 等式由引理2 3 ，在础与g 2 的边上分别有2 个交叉，所以盯( g 4 只) = 4 ， 结论对n = 1 时成立假设结论对n = 尼( 七1 ) 时成立，再假设几= 七+ 1 时， 有一个g 4 r + 1 的好画法，使c r ( g 4 r + 1 ) 5 ( 后+ 1 ) 一1 由引理2 4 知，必有 某个t ，使得g i 有4 个交叉点，那么我们删除g i 的所有边得到一个同胚于 g 4 r 或含有同胚于g 4 r 的子图，而c r ( g 4 r ) 5 ( 尼+ 1 ) 一1 4 = 鼽一1 ， 与定理的归纳假设矛盾因而仃( g 4 r ) = 5 佗一1 定理证毕口 图2 8g 4 r 的一个好画法 1 3 硕士学位论文 3 五阶图g 。3 与星图& 的笛卡尔积交叉数 在文献【2 2 】中m k l e 资列出了所有五阶图的画法以及与路r ，星& ， 圈g 的笛卡尔积交叉数的已知和未知的结果本章证明了五阶图g ，3 ( 见 图3 - 1 ) 与星图品的笛卡尔积的交叉数从而填补了m k l e ；芒给出的五 阶图与星图的笛卡尔积交叉数列表中的一个空白 图g 的顶点个数用y ( g ) 表示，如果y ( g ) = n ，那么我们就称图g 为礼阶图r 表示长为n 的路，岛表示星，即硒为了证明方便， 我们先构造一个新图巩：风由g ，3 与蚝n 合成，蚝n 中的五个顶点与 g 。3 的顶点的构边方式相同，蚝n 中的另一部分的n 个顶点与g ，a 相连 边把正记作如( 江1 ，2 ，礼) 与g 。3 五个点连边构成的图巩的一个 好画法如图3 3 所示，显然有 n = g 1 3u 蚝m = g 1 3u ( u 丁i ) i = 1 图3 1g 1 3图3 2g 1 3 下面是本章的两个主要定理： 定理3 1 c r ( 巩) = z ( 5 ，竹) + 【墨j ，礼1 ； 定理3 2 c r ( g 1 3 & ) = z ( 5 ，礼) + 【詈j ，n 1 3 1 巩的交叉数 关于图的笛卡尔积交叉数的研究 定理3 1 c 7 ( 巩) = z ( 5 ，n ) + 【号j ，n 1 ； 证明：由图3 3 可知：c r ( 巩) z ( 5 ，n ) + l 詈j ，n 1 我们对n 用归纳法证 明相反的不等式当亿= 1 时，日。为可平面图，显然盯( h 。) = o ，当n = 2 时，玩有一个子图同构于 3 所以c r ( 凰) = 1 所以当礼= 1 ，2 时，结 论成立现在假设当n 3 时：c r ( 巩一2 ) z ( 5 ，几一2 ) + 【孚j 现在考虑巩的一个好画法d 使得，c r d ( 巩) z ( 5 ，n ) + 吲下面分 两种情况考虑： 曩 粪 慧爱 图3 - 3 巩的一个好画法 情形1 ：若存在两个正，乃( 1 i 歹仡) 使得c r d ( 互，乃) = o 不失一般性，不妨设为死乩瓦使得c r d ( 瓦乩死) = o 由于对于 每一个i = 1 ，2 ，n 一2 ，lu 死一1u 正同构于恐，5 ，而且凹( ，5 ) = 4 ， 且c 7 d ( 已乩冗) = o ，所以有： c 7 d ( ru 已- 1 j 正) = 凹d ( 虬，5 ) 一凹d ( 死u 已一1 ) 一c r d 限) 4 0 0 = 4 因为兀u 死一。u g 。3 包含一个子图同构于，3 ，且c r d ( 瓦乩瓦) = o ，所以 盯d ( 死u 瓦乩g 1 3 ) = 1 又g 1 3u ( 正u 疋u u 瓦一2 ) 同构于巩一2 ， 盯d ( 巩) = c r d ( 瓦u 死一1u ( g 1 3u 丑u 死u 矗一2 ) ) = 凹d ( 死u 死- 1 ，乃u 乃u u 瓦一2 ) + 盯d ( 瓦u 瓦一1 ，g 1 3 ) + c r d ( g 1 3u 乃u 正u u 死一2 ) 4 ( 几一2 ) + 1 + c 7 d ( 巩2 ) z ( 5 ，佗) + 【j 一15 硕士学位论文 情形2 ：若对任意两个正，乃( 1 冬i j n ) 都有c r d ( 正，弓) 1 根据前面的假设，凹d ( 巩) z l + z 2 ，则可得到瓢 o ，显然交叉数目不能为o ， 所以假设不成立，引理得证 3 6 日的嫩缩 图3 7 日的e 收缩 定理3 2 c r ( g 1 3 & ) = z ( 5 ，n ) + l 若j ，竹1 证明：由图3 8 可知存在一种好画法d 使得凹( g 1 3 岛) z ( 5 ，礼) + 【鸶j ，( n 1 ) 由引理3 1 ，把g i 3 ( i = 1 ，2 ，几) 收缩到赴，则得到的图同构于玩，再 根据定理3 1 有c r ( g 1 3 & ) z ( 5 ，n ) + l - 鸶j ，因此盯( g 1 3 & ) = z ( 5 ，n ) + 【鸶j ( 佗1 ) ，证毕口 一1 8 关于图的笛卡尔积交叉数的研究 图3 8g 1 3 r 的一个好画法 1 9 硕士学位论文 4 轮溉与星图& 的笛卡尔积交叉数 轮比是这样一个图：顶点集为 伽，口1 ，晚，忱，吼，口5 ) ，其中伽与忱( 1 i 5 ) 都有边相连，御1 一忱一蚴一一 5 一u 1 构成一个5 圈把睨的六个 顶点 咖，可。，也，) 与另外礼个顶点如 = 1 ，2 n ) 分别相连我们得到 一个新图( 见图垂1 ) ，记为巩在图巩中，用正( i = 1 ，2 死) 表示与顶 点屯关联的边集( 见图垂2 ) ；用岛表示中与顶点咖相关联的边集， 用尻表示中圈可1 一t j 2 一铂一m 一一u 1 中的边集于是易得 n e ( 砜) = 岛u 忍u ( 【j 互) ( 4 1 ) 如一 图4 1 巩的一个好画法图垂2 图正 下面是本章的两个主要定理： 定理4 1 c 7 ( ) = z ( 6 ，礼) + 佗+ 3 l 詈j ，礼l 定理4 2 c r ( 眠) = z ( 6 ，扎) + 2 n + 3 【墨j ，仃1 4 1 日n 的交叉数 引理4 1 凹( 凰) = 1 ，c r ( 凰) = 5 证明：凰的一个好画法如图垂3 ( a ) 有盯西( 巩) = 1 ，则凹( 研) 1 又因 为风包含一个同构于托，3 的子图，而c r ( 尥，3 ) = 1 ，则甜毋( 皿) 1 因此 仃( 矾) = 1 由图4 3 ( b ) ，同理可证c r ( 凰) = 5 口 一2 n 一 关于图的笛卡尔积交叉数的研究 引理4 2 令为图凰的一个好画法，若c ( 死，正) = o ，则有c ( 岛u 忍，乃u 乃) 5 ，且c r 毋( 码，五u 乃) 6 证明：令日= 乃u 易为风的边导出子图显然日同构于具有二部划分 t 1 ，2 ) 和 如，u 1 ，忱，耽，啦，u 5 ) 的完全二部图鲍，6 因为c ( n ，疋) =