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

湖南师范大学硕士学位论文 o 1中文摘要 已经证明确定图的交叉数是一个n p 完全问题( 见文献 1 】) 因为 其难度，我们能够确定交叉数的图类非常少，在许多情况下，即使 找出图的交叉数的一个好的上界也是非常困难大多的努力是在探 求完全图，完全二部图及笛卡尔积图的交叉数本文研究一类笛卡 尔积图的交叉数 在第二章，我们确定了5 个六阶图与路r 的笛卡尔交叉数； 在第三章，我们证明了星图鼠及5 个六阶图与r 的笛卡尔积交 叉数； 在第四章，我们求出了一个六阶图与品的笛卡尔交叉数 这里，魂与分别表示边为5 及n 的星，r 表示边长为n 的 路 关键词：图；画法；交叉数； 路；笛卡尔积；同构 平面图 湖南师范大学硕士学位论文 i i 0 2 a b s t r a c t ， d e t e r 黧gt h e c r 。s 8 i n g n u m b e r s 。fg r a p h sh a s 纱p r o v e dt o b e 阻c o m p l e t e t h e r ea r eaf e we x a c tr e s u k so i lt h ec r o s s i n gn u m b e r so fg r a p 蟪c l a s sb e c a u s eo f i t sc o m p l e x i t y i nm a n y c 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 f t h e c r o s s i n gn u m b e r s o fg r a p h ym u c he f f o r th a sb e e ns p e n to i li n v e s t i g a t i n gt h e c 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 sa n d c a r t e s i a n p r o d u c t sg r a p h s i nt h i sp a p e r ，w es t u d yt h ec r o s s i n gn u i a b e r so ft h ec a r t e s i a n p r o d u c tg r a p h i nd l a p 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 m b e ro ft h e c a r t e s i a np r o d u c to 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 e d 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 a n d5g r a p h s o n6 - v e r t e xw i t hp a t hr 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 n l b e r o fa6 - v e r t e xg r a p hw i t ht h es t a rk ln ，w h e r es 5a n dr a r et h es t a rw i t hf i v e e d g e sa r i 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 ；p a t h ；c a l 【- t e s i a np r o d n e t ；i s o m o r p h i c ；p l a n eg r a p h 湖南师范大学硕士学位论文i i i o 3前言 拓扑图论是目前国际上一个非常活跃的图论分支，其中对图的 拓扑参数一一交叉数的研究又是一个重要的课题之一，自从上个世 纪七十年代初匈牙利数学家p a lt u r h n 根据其在一个砖厂碰到的实际 难题( t u r 缸1 1 sb r i c kf a c t o r yp r o b l e m ) | 见文献【2 , 3 ，4 1 1 ，从而提出了交叉数 的概念以来，因其在c a d ( 计算机辅助设计) 领域有着非常广泛的应 用，如： ( 1 ) 工业上电子线路板设计中的布线问题； ( 2 ) 草图的识别与重画问题，具有比手写汉字识别应用更为广泛 的应用领域； ( 3 ) 软件开发过程中文档部分的e r 图( 实体联系图) 等的自动 生成； ( 4 ) 生物工程d n a 的图示 使得很多图论专家对这方面进行了深入研究，但因为图的交叉 数问题属于n p 困难问题，目前仅有有限的图的交叉数得到了精确 值，主要有： ( 1 ) 完全图： c r ( k n ) 1 - - 1 警 孚 字 ， t 萨蒂( s a a t y ) 证明了等号对于n 1 0 成立【见文献【5 ( 注h 表示 不超过n 的最大整数，以下类同) ( 2 ) 完全二部图： c r ( k m ，n ) “5 - 】 ! 孚 ；】 孚 ， 克莱曼( k l a i m a n ) 证明了等号对于m i n ( m ，n ) 6 成立阮文献( 6 j 】， w o o d a l l 证明了对m = 7 且n 1 0 成立 见文献【7 】 ( 3 ) 三部图： c r ( k 1 。) = z ( 4 ，n ) + ； ，c r ( k = ，3 m ) = z ( 5 ，n ) + n 日本的k a s a m o 证明了上面的等式成立 见文献 8 黄元秋证明了c r ( k l | a 。) = z ( 5 ，n ) + 2 吲【见文献 9 - 7 1 1 ， 湖南师范大学硕士学位论文 i v ( 4 ) 笛卡尔积图 c r ( c k g 。) s ( m 一2 ) n ，( 竹15 佗) 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 等证明等号对m = 3 ，4 ，5 ，6 成立( 见文献 【9 - 1 5 1 ) m k l e e 等确定了许多对于阶数不超过5 的图与路，星，圈的笛 卡尔积图的交叉数( 见文献 1 6 2 6 ) 本文受到f 1 6 2 6 的启发，发展和 运用他们的某些方法确定一类6 阶图的笛卡尔积交叉数推广了有 关方面的结果 湖南师范大学硕士学位论文 第一章引言 本文未说明的概念均同文献 2 , 3 ，4 ，5 ：且无特别说明所涉及图均 指连通简单图图g = ( ve ) 均是由顶点集v ( a ) 与顶点上的无序对 的子集s ( c ) 组成的集合，e ( o ) 中的元素称之为边另外r 表示边 长为n 路，s 札有n 条边的星k 。，g 表示边长为n 的圈，图g 的交 叉数是指把图g 画在平面上时出现的最小交叉数下面给出相关交 叉数的定义14 1 及笛卡尔积的定义 定义1 图g 在表面上的一个画法是指把图的顶点画在表面上的 结点，把图的边画为表面的弧 定义2 图g 在表面上的一个好的画法是指图g 在表面上的画 法满足以下四个条件： 1 ) 连接同一个结点的任意两条边不相交； 2 ) 边不能自身相交； 3 ) 任何两条相交的边最多交叉一次； 4 ) 没有三条边交叉于同一个点 根据定义2 图( 1 ) 中的前三种画法是不会出现的，第四种画 法是不允许的 图l 定义3 图g 在表面上的一个最优画法是指图g 在表面上的具有 最少交叉数的好的画法，这个最少交叉数目即为图g 在该表面上的 湖南师范大学硕士学位论文 2 交叉数 定义4 图g 在平面( 或球面) 上的交叉数称为图g 的交叉数， 记为o r ( g ) 定义5 两个图g 。和g 。的笛卡尔积图用g 。g 。表示，它是这样的 图：点v ( c 1 g 2 ) = v ( c 1 ) v ( c 2 ) ；边集e ( c 1 g 2 ) = ( 啦，) ，( u 。) ) “；= “。且 ，v m ) e ( e ：) 或者( u ；，“。) e ( g 1 ) 且= 。) 若g ，和g 。是两个边不相交的图，那么g 。u 岛表示点集为v ( g ，) u v ( a 。) 和边集为e ( g ，) u e ( g 。) 的图设d 为一个图g 的好画法，我 们用”d ( g ) 表示图g 在画法d 下的一个交叉数，若g ，和g 。为图 g 的两个子图，我们用”d ( g 。，g 。) 表示g - 与g 2 在画法d 下的交叉 数，易得到如下公式：( 见文献 6 ) c r 。( g 1ug 2 ) = 。”。( g 1 ) + c r d ( g 2 ) + c r s ( o l , g 2 ) 门1 c r d ( g 3 ，g 1ug 2 ) = c r o ( g 3 ，g 1 ) 十c 7 v ( g 3 ，g 2 ) 这里g 。，g 。，g 。是边互不相交的g 的子图 在两个图f 和h 中，对于某些边的加入或抹平2 度点( 均可反复 多次) 这样的过程使得这两个图同构，则称f 和h 同胚，记为f h 易知同胚的两个图同具有如下的性质： 性质1 若f h ，贝0c r ( f ) = c r ( h ) 性质2 若h 为图g 的子图，则c 1 、) c r ( g ) 证：设曲是图g 的一个好画法，使c t l 。( g ) = c 7 ( g ) ，则妒自然诱导 它的子图i 的一个画法记为西i ，c r l h ) c t 口( g ) = ”( g ) 、由交叉数 的定义， c t ( h ) c r ( g ) 湖南师范大学硕士学位论文 4 ( 即每条长为n 的路拷贝r ) 着蓝色 2 1当j = 1 ，2 时，定理的证明 定理2 1c 7 、( gxr ) = 2 ( n 一1 ) 0 = 1 ，2 ) 7 22 1 跫壤：簿掰激煺。练赢蜡d ；浠送c i d 。l 冀；i 笋i 一 一i 整普 磊疆擐鬻蛙输谢斟孥i 麓3 甬珏：常黑令意蕈肯二舞黔罢，月；露ix 移i 萝；鬻一i ；j 商错：g i 餮x 昙高黠望g j 爵坚晶；冒徐g i -含有同构于g ，r 的子 图，所以由性质2 ；得到c r ( g 1xr ) 墨c r ( g 。r ) s2 一1 ) 又因为g ： 和g：均含有星图岛，所以g 。r 以及g 。r 均含有同构于s 4 只。 的子图由文献【6 ，c r ( s 4 r ) 一2 ( n 1 ) 再结合性质2 ，我们得到 一(g 。r ) = c r ( g 2 瑞) = 2 ( n 一1 ) 这就得到当，= 1 ，2 情形时定理中 的(1 ) 2 2 当j = 3 时，定理的证明 设日是图g 的一个子图，d 是g 的一个好画法，我们说“是 h 的一个交叉点是指：在画法d 中，产生交叉点“的两条边中，至 少有一条边属于日 我们 湖南师范大学硕士学位论文 7 2 3当j = 4 时，定理的证明 定理2 3c r ( g 4 p 札) = 2 nn l 证明：由图6 的画法知，c r ( g 。r ) 墨2 n ，n 1 ，由于g t r 包 含一个子图同构于k 2 。r ，而由文献【7 和 8 知c r ( k 2 ，。r ) = 2 n ， 由性质( 2 ) 知c r ( g 。r ) 2 n ，因 而c r ( g 4 xr ) = 2 n 图6 2 4当j = 5 时，定理的证明 定理2 5c r ( g 5 r ) 一4 n ，n21 湖南师范大学硕士学位论文8 图7 g 7 设g 是图，c 为g 的一个圈，若g v ( c ) 是连通的，则称c 是不 可分离圈若g 的点导出子图o i v ( c ) ) = c ，则称c 是一个诱导圈 引理2 2 设c 为平面图g 的不可分离诱导圈，则在g 的任何一 个平面嵌入中，c f 必定是这个嵌入的某个面的边界 证：由定义，容易证明 引理2 3 在图g 。的任何平面嵌入中，每一个面的边界上至多包 含g 的4 个顶点 证：我们假设有一个面的边界上包含g s 的5 个顶点，由引理2 知，图g 。的平面嵌入中，必有2 个3 度面和2 个4 度面，根据欧拉 公式有： 2 923 + 3 + 4 + 4 + 5 ，矛盾，因而在g 5 的平面嵌入中， 每个面的边界上至多有g 。的4 个顶点n 引理2 4c r ( g 6 ) _ 2 ，c r ( g 7 ) = 4 ( g 。表示由g 。xp i 收缩g 2 成点z 而碍到的图，g t 表示由g s xp 2 分别收缩g 2 ，g ；成点z ，y 而得到的图) 证：由图6 的画法可知c r ( g 6 ) 2 ，c r ( c ，) s 4 下面我们分三种情况，证明相反的不等式。让t 2 ，p 分别表示关 联于z ，y 的边 情况( i ) ：c r 。( g 。) = 0 ，由引理3 知g 5 导出的平面的每一个区域 湖南师范大学硕士学位论文- 9 边界上至多只有g 5 的4 个顶点，不管z ，位于瓯导出的哪一个区 域内，都有c r d ( g 5 ，t z ) 2 ，c f d ( g 5 ，7 1 9 ) 2 由式( 2 ) 有：c = r d ( g 6 ) 一c r v ( g 5 u t 。) = c r d ( g 5 ) + c r d ( 1 。) + d ( g 5 ，t 2 ) 2 c t d ( g 7 ) = c r d ( t 2 u g 5 u t ”) c r d ( g 5 ，t 。) + c r d ( g 5 ，t y ) 4 情况( i i ) ：c r 上，( g 5 ) = l ，则g 。在d 导出的画法中，至多有一个区 域的边界上包含砩的5 个顶点( 不可能有6 个顶点) ，因而，必有 c r d ( g 5 ，1 ”) l ； 如果c r d ( g 5 ，t 。) = 1 ，则c r j ) ( g 5 u t 。，t ”) 2 ： 如果c r ，) ( g ，疋) 2 ，则c r d ( g 5 u t ，p ) 2l ； 无论哪一种情况，根据式( 2 ) 有：c r d ( g o ) 2c f d ( g t ) = e r d ( t 。u g 5 u t ”) 芝4 情况( i i i ) ：c r d ( g 。) 2 ，此时g 导出的画法中，至多有一个区 域的边界上包含g 的顶点不少于5 个若c r d ( g 。，t 。) = 0 ，则必有 口_ 】) ( g 5 u t 。，t y ) 2 若c r d ( g 5 ，t 。) = l ，则必有c t j ) ( 姥u p ，t 。) 1 若c 1 d ( g 5 ，t 。) 2 ，必有c t v ( g 5 u t 。，p ) 0 因而，根据式( 2 ) 也有：c t 。( g e ) 2 2 c r d ( g ，) 4( 引理2 5 设d 是岛r 的一个好画法，如果在画法d 中，每个 g 至多有3 个交叉点，那么d 至少有4 n 个交叉点 证：断言( i ) 任何两个不同的三连通图瞵与g i 不能彼此交叉 如果g 与g i 交叉，则c r d ( 嚷，g ；) 3 ( 因为g s 是三连通) ，假设 c 仞( 晓，侥) 一3 ，由假设知印( 嚷) = c m ( g ) = o ，因而嚷( 嚷) 分平面成 两个三角形区域和三个四边形区域。又由c r o ( 嚷，嚷) = 3 知岛( 哦) 至 多位于g ：( 嚷) 的两个区域中，且每一个至多有g ；( 瞬) 的四个顶点， 因而g j ( g ) 至少被g f l 到g 鼍或g ：到g 纩1 ( 瞑_ 1 到g j 或g j 到g r l ) 的两条蓝色边交叉，这与引理假设矛盾。 断言( i i ) 嚷，g j ，g l - 1 ，g 纩1 ，g ；都位于侥导出的同一个区 域中 湖南师范大学硕士学位论文 l o 我们假设有两个不同的罐与g 位于g ；导出的两个不同区域 中，因为侥的画法d 分串面成这样的区域，使得任何两个区域的 共同边界上最多有g ；的两个顶点( 不管g j 是否交叉) ，而在画法d 中g ；与g 到g 2 的蓝色边至少有6 个共同点，且至多两个为嚷的 顶点，因而g ；的边上至少有4 个交叉点，这也与引理的假设矛盾 断言( i i i )没有不关联嚷的蓝色边交叉嚷的红色边 假设有不关联于g ；的蓝色边交叉g 的红色边，则g ；至少被 r ( p 表示g ；。到g ；：的蓝色边) 的边交叉3 次( 因为g ；是3 一连通 的图) ，而且皖的边有两个内部交叉点或者g ；的边被关联于g ：的 蓝色边交叉两次或者晚的边有一个内部交叉点且g ；的边至少被关 联于g 的蓝色边交叉一次，这再一次与引理假设矛盾 对于i = l ，2 ，n 一1 ，我们用日”“表示由y ( g 1 ) u y ( g ；) u v ( g 寸1 ) 导出的g 。b 的子图，让娥一h ，表示从h 。- l , i “中删除g r l 的四条 边与g 1 的四条边使得h a - 1 , i “有一个子图同构于g ，而”( g t ) = 4 在g 。x 只的好画法当中，我们定义日r l ”1 的如下类型交叉数为 f ( h i - 1 , i + i ) ( 皿。一”如下类型的交叉数为，( h ! - 1 , 1 + 1 ) ) ( 见文献 1 ) 】) ： ( 1 ) t 。u5 、“的蓝色边与眯的红色边的交叉点； ( 2 ) t 。的蓝色边与t 州的蓝色边的交叉点； ( 3 ) 的自身交叉点 容易看到，整个画法的交叉数就是f ( h i - l , i + 1 ) ，i = 1 ，2 ，- ，n 1 的 和，而且每一个交叉点在整个交叉数中最多只计数了一次，由断言 ( n ( i i ) ，( i i i ) 知，噬- 1 , i + 1 的最优画法的交叉数只有( 1 ) ，( 2 ) ，( 3 ) 三种情 况；因而对每一个i = l ，2 ，n 一1 ，f ( h ”1 ，”1 ) ，( 峨。- ”1 ) c r ( 0 7 ) 一 4 ，而且当i 取遍1 ，2 ，n 一1 时，画法d 的交叉数，( 舅”1 对1 ) 4 ( n 一1 ) ，由前引理4 知g 2 与g ；都至少有两个交叉点，且没有计算 到ef ( h ”1 ，”1 ) 当中 t = i n 一1 因此，画法d 至少有f ( h ”1 斗1 ) + 4 4 n 个交叉点 】 湖南师范大学硕士学位论文 1 l 图8 ( b ) 箕 引理2 6o r ( g 5 p 1 ) 一4 证：如果g 2 与砩彼此交叉，由引理5 的证明知。( g 5 p 1 ) 4 ， 当砩与g i 不交叉时，由引理4 知c r ( g s p 1 ) 4 又由图7 ( a ) 可知 c 7 1 ( g 5xp 1 ) s4 因而有c r ( g 5 p 1 ) = 4 】 定理2 ：4c r ( g 5 r ) 一4 n ，n 1 证：由图8 ( b ) 的画法可知”( g s xr ) 4 n ，n l 现在我们用数学归纳法来证明相反的不等式，当n = l 时，g s r 为平面图，c t ( g 。p 1 ) = o ，命题成立，假设当n = 时，命题成立 即有c r ( g 。xr ) = 4 k 我们再假设n = + 1 时，有一个g s p k + - 的好 画法，使c , r ( g 。xr + ，) 4 k ，由引理2 3 和2 4 知，必有某个i 使g ；有 四个交叉点，那么我们删除g ；的所有边得到一个图同构于g s 饩 或拥有一个子图同构于g 。xr ，而且这个图有少于4 个交叉点的 画法，这与我们的归纳假设矛盾，因而c r ( g s r ) = 4 n 湖南师范大学硕士学位论文 第三章星图5 5 及5 个六阶图g 。( i = 1 ，2 ，3 ，4 ，5 ) 与 路r 的笛卡尔积交叉数 本章我们假定s 5 ，g ；0 = 1 ，2 ，3 ，4 ，5 ) ，l zs5 ，分别是具有6 个点 的如下： g 4 图9 3 1星图s 5 与路r 的笛卡尔积交叉数 为了讨论的方便，我们把品的5 度点标记为0 ，而岛的其它5 个1 度点依次标为1 ，2 ，3 ，4 ，5r 的n + 1 个顶点也依次标为0 ，1 ，2 ，使 湖南师范大学硕士学位论文 1 5 由日”+ 。的画法口”+ 。导出的子图，那么在画法d 计2 中，也容易 得到h 升2 一s 一的边上至少有2 个交叉点因而也有h 卅1 的画 法时2 至少有4 个交叉点 镩翟孚汀 l 岸l 藩 影 霸 荦 霪 霸 霄 ( d ) 图1 3 断言( i i ) ：由画法d 导出的画法d ”- 2 的交叉数比由d ”8 导出 的画法d t 肘n ，的最少交叉数至少多四个 现在我们来考虑由d 导出的子图日埘的画法d t 升。，也有如下 四种情况： 情况( 1 ，) ：如果在画法d 卅* 导出的画法升“1 中，酽拙1 的 边没有交叉由类似断言( i ) 的情况( 1 ) 的分析知在画法。舢中， 妒+ - ”p + t 的边至少有四个交叉点 情况( 2 ，) 在画法_ d ”导出的画法d 珏+ 一1 中，s m 。的边与 d n 肘一一酽+ 一的边有一个交叉点由类似断言( i ) 的情况( 2 ) 分析知，日m 吐卅一p + 一边上至少有三个交叉点而且此时画法 驴m 一的交叉数比画法d t 一一的最少交叉数至少多一个从而也 娶器 x 湖南师范大学硕士学位论文1 8 有画法d ”+ * 比画法口- m 一的最少交叉数至少多四个 情况( 3 ，) 在画法d 卅。导出的画法d ”+ 一1 中，9 + “的边与 口批1 卅一p + 一的边有两个交叉点由类似断言( i ) 的情况( 3 ) 分析知，d m m p + n - 边上至少有两个交叉点而且此时画法 ，”“1 的交叉数比画法d 卅扛- 的最少交叉数至少多2 个从而也 有画法，m 比画法d 卅n ，的最少交叉数至少多4 个 情况( 4 兮在画法h e 导出的画法d ”廿- 1 中，s * “1 的边与 d 一“。，m 一“。的边有3 个交叉点由类似断言( i ) 的情况( 4 ) 分析知，d m 吐m 一+ n 边上至少有3 个交叉点而且此时画法 d 卅n t 的交叉数比画法驴一m 一的最少交叉数至少多一个从而也 有画法d ”+ * 比画法d ”+ “，的最少交叉数至少多4 个 又因为由d 导出的d i 。有至少4 交叉点，而且在画法d = d m “中 还有n 2 星，由断言( i ) 和( i i ) 知画法d 至少有4 + 4 一2 ) = 4 ( n 一1 ) 交叉点 习。 鳄 图1 4 定理3 1c r ( j f 。聂巧) = 4 ( n 一1 ) n 1 证：由图1 4 的画法知c r ( 两f 巧) 4 一1 ) ，n 1 现在我们用数 学归纳法来证明相反的不等式，当n l 时，爵丽：为平面图， ”( 两i 耳) = o ，命题成立，当n = 2 时，巧i 了：同胚于飓，s 而由 ( 1 ) 知”( 凰；) = 4 ，命题成立假设当n = k 时，命题成立，即有 湖南师范大学硕士学位论文 2 1 ( d ) 图1 6 定理4 3c r ( g 。r ) = 4 ( n 一1 ) n21 ( i = l ，2 ，3 ，4 ，5 ) 。 证明：由图1 6 ( a ) ，( b ) ，( c ) ，( d ) ，( e ) 知 ( g 。r ) 4 ( 礼一1 ) ，n 1 ( i 2 1 ，2 ，3 ，4 ，5 ) 又因为g 。r 包含一个子图同构于瓯r 由性质2 和 定理2 的证明知( g 。r ) 4 ( n 一1 ) ，n l0 = 1 ，2 ，3 ，4 ，5 ) 从而也有 c r ( g l 气) ：4 ( n 1 ) ，n 1 ( i = l ，2 ，3 ，4 ，5 ) 一。塑童堑堇叁兰丝圭兰竺丝圭：丝： 第四章 一个六阶图与星& 的笛卡尔积交叉数 2 ( a )f b ) 图1 7 定理4 1c r ( g 4 r ) = 6 吲 4 + 2 nn2l 为了证明定理4 i ，我们先证明引理4 1 ，引理42 ，为了表达方便， 我们将强g - 图1 7 ( a ) 标记为如图1 7 ( b ) ，假定a 为图g 的点集v 或边 集e 的子图，用 表示由a 导出的g 的子图，耳7 ) 表示关联 于点集v 的边集取y ，取z ，与勖z 分别表示 ， 与 的边集，z ( 6 ，n ) 表示6 翌笋】 弓j 理4 1c ，( g l ，他) = z ( 6 ，n ) + n ，帆1 i v 湖南9 f 范大学硕士学位论文2 4 如果多( 五) 在i ，i i ，v i 区域，则口女( 只g ( 五) ) 26 ( 5 ) 如果妒( 五) 在i i i ，v 区域，( a ) 当c ( e x y ，e ( 五) ) = o ，则。( 只e ( 五) ) 6 ( b ) 当。( 2 玟r ，e ( 五) ) 1 ，贝有。( fe ( 五) ) 5 ( 6 ) 如果( z 。) 在v i i ，v i i i 区域，”$ ( ee ( 互) ) 4 ( 7 如果( 互) 在区域，c ( e e ( 互) ) 2 f 8 ) 我们假定有h 个五位于i x ，2 个五位于v i i 和v i i i 和乜个五 位于i i i 和v ，其余的点位于其它区域，那么根据( 6 ) 式又有以下两种 情况： 情况( a ) ，c q ( k y ，f ( 五) ) = o ，c ( fe ( 五) ) 6 有 n ”( 厮y ，e ( 毛) ) 2 噩+ 4 k 2 t = 2 c r 4 ( f e ( 五) ) 2 1 + 4 玛+ 6 m 一l 一也一1 ) ， ：= 2 由( 3 ) ，( g ) 和。( e x y ) = 1 ，有： ( 9 ) ( 1 0 1 c q ( g 1 ，n ) 2z ( 6 ，n ) + 2 也+ 4 克2 + l ( 1 1 ) 由( 1 1 ) 和( 2 ) 有：2 l + 4 乜 n l ( 1 2 ) 由( 1 0 ) ，”( g l ，n ) = ”( u _ e ( 五) ) + c r ( f ) + ( e e ( z ：i ) ) 和”d ( f ) = 1 ， = 2i = 2 有： c ( g l ，n ) z ( 6 ，n 1 ) + 6 n 一4 岛一2 也一5 ( 1 3 ) 由( 1 2 ) 有一4 h 一8 2 一2 n + 2 代入( 1 3 ) 有： c 7 ( g 1 ，礼) z ( 6 ，( n 一1 ) ) + 4 n 一3 + 6 如z ( 6 ，n ) + n 这与假设( 2 ) 矛盾 情况( b ) ，( 最x r ，e ( 五) ) l ，c ( 只e ( 互) ) 5 有： n 。( ! k y ，e ( 五) ) 2 女i + 4 如+ 如一( 1 4 ) l = 2 n c r 币( f e ( z 1 ) ) 2 岛l + 4 惫2 + 5 危3 + 6 ( 札角l 一乜一k 3 1 ) ( 1 5 ) 由( 3 ) ，( 1 4 ) 和c ( e x y ) = l ，有： c r 母( g 1 ，n ) z ( 6 ，扎) + 2 而1 + 4 如+ 5 b + l 由( 1 6 ) 和( 2 ) 有：2 l + 4 如+ 5 n 一1 ( 1 6 ) ( 1 7 ) 湖南师范大学硕士学位论文 2 5 由( 1 5 ) 和c q ( g ，n ) 一”4 ( ue ( 互) ) + c q ( f ) + ( f ) e ( 五) ) 和( f ) = 1 ， = 2f 5 z 有： c 舌( g l ，他) z ( 6 ，n 1 ) + 6 扎一4 盘1 2 七2 一蚝一5 ( 1 8 ) 由( 1 7 ) 有一4 k 1 8 一1 0 一2 + 2 代入( 1 8 ) 有： 盯o ( g l ，n ) 之z ( 6 ，一1 ) ) + 4 n 一3 + 6 后2 + 如z 6 ，礼) + n 这与假设( 2 ) 矛盾 情况i i ：假定西( ) = d 2 如图1 8 ( b ) 所示，那d 。分平面成区 域i i x ， 如果( 五) 在i ，i i ，区域，则口。( 取y ，e ( 五) ) 3 ( 1 9 ) 如果毋( 五) 在i i i _ i x 区域，则c r ( fe ( 磊) ) 5 ( 2 0 ) 我们假定有个五位于i 或i i 区域，其余的点位于其它区域， 则有： n 。q ( 取y ，e ( 最) ) 3 t = 2 n c ( f 1 e ( 五) ) 3 k + 5 ( n 一女一1 ) t = 2 由( 3 ) ，( 2 1