（运筹学与控制论专业论文）关于几类图的一些不变量的研究.pdf

r e s e a r c ho ns o m ei n v a r i a n t so fs o m et y p e so fg r a p h s a 吼e s 妇 s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t s ， | o rt h em s 。d e g r e ei nm a t h e m a t i c s b y h o ua i l i n p o s t g r a d u t ep r o g r a m s c h o o lo fm a t h e m a t i c sa n ds t a t i s t i c s c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：l is h u c h a o a c a d e m i ct i t l e ：p r o f e s s o r s i g n a t u r e ： a p p r o v e d m a y , 2 0 1 1 列批1 1 肋4 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明本声明的法律结果由本人承担 作者签名： 日期：知年占月加日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即学校有权保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅 本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进行 7 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文同意华中师 范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容 作者签名：钦凌林 日期：知l f 轱月如日 导师签名：斟旬 日期：乃f 年岁岿弓) e l 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人 的学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中 的规定享受相关权益同意论文提交后滞后：口半年：口一年；口二年发布 作者签名：饮徘 日期：西1 1 年与月幻e t 导师签名： 毒书幺 日期：锄f f 年上月岁日 摘要 图的第一类z a g r e b 指标、第二类z a g r e b 指标、图的邻接谱半径以及无符号拉 普拉斯谱半径均是图的不变量。本论文在前人研究的基础上，进一步研究在极大外 平面图中z a g r e b 指标的极值问题及两类z a g r e b 指标的比较，并研究了单圈图的无 符号拉普拉斯谱半径、c a c t i 的谱半径，主要内容包括： 介绍了本文的研究背景和研究意义，国内外在这方面具有代表性的发展状 况通过对本文研究背景及研究现状的深刻讨论，充分说明了本文的主要研 究工作的必要性和创新性然后，给出了本文涉及到的基本概念、符号及相 关引理 研究了极大外平面图、具有完美匹配的外平面图及极大外平面图中z a g r e b 指标的上下界，并相应地确定了z a g r e b 指标达到上下界的极图 研究了极大外平面图中两类z a g r e b 指标的比较 研究了具有q 匹配的n 阶单圈图中无符号拉普阿斯谱半径的前三大的排序， 并确定了相应的图 研究了具有q 匹配的n 阶c a c t i 中谱半径的前两大的排序，并确定了相应的 图 关键词：z a g r e b 指标；极大外平面图；单圈图：c a c t i ；匹配数 a b s t r a c t t h ef i r s ta n dt h es e c o n dz a g r e bi n d i c e s ，a d j a c e n c ys p e c t r mr a d i u sa n ds i g n l e s s l a p l a c i a ns p e c t r a lr a d i u sa r et h ei n v a r i a n t so fg r a p h s t h i sp a p e rw h i c hs t a n d so n t h eb a s i so fp r e v i o u sr e s u l t s ，d of u r t h e rr e s e a r c ho ns h a r pb o u n d so fz a g r e bi n d i c e s o fu n i c y c l i cg r a p h s ，a n dc o m p a r et h ez a g r e bi n d i c e sf o rm a x i m a lo u t e r p l a n a rg r a p h s ； m o r e o v e r ，d of u r t h e rr e s e a r c ho nt h ei s s u eo ft h es i g n l e s sl a p l a c i a ns p e c t r a lr a d i io f u n i c y c l i cg r a p h sw i t hm a t c h i n gn u m b e rq ，a n do ft h es p e c t r a lr a d i io fn - v e r t e xc a c t i w i t hm a t c h i n gn u m b e rq ，r e s p e c t i v e l y i nt h ef i r s tt w os e c t i o n s ，w ei n t r o d u c et h eb a c k g r o u n da n d s i g n i f i c a n c eo ft h e r e s e a r c h ，i n c l u d i n gt h ed e v e l o p m e n to far e p r e s e n t a t i v ea th o m ea n da b r o a d r e g a r d i n gt h i sa s p e c t b a s e do nt h i sr e s e a r c hb a c k g r o u n da n dp r o f o u n dd i s c u s - s i o no nt h es t a t u sq u o ，i tf u n ys h o w st h em a i nw o r k sn e c e s s i t ya n di n n o v a t i o n i ns e c t i o n3 ，w es t u d yt h es h a r pu p p e ra n dl o w e rb o u n d sf o rt h ez a g r e bi n d i c e s a m o n gt h en - v e r t e xm a x i m a lo u t e r p l a n a rg r a p h s ，a n da m o n gn - v e r t e xo u t e r - p l a n a rg r a p h s ( r e s p m a x i m a lo u t e r p l a n a rg r a p h s ) w i t hp e r f e c tm a t c h i n g s a n dt h ec o r r e s p o n d i n gg r a p h sa r ec h a r a c t e r i z e d i ns e c t i o n4 ，w ec o m p a r et h ez a g r e bi n d i c e sf o rm a x i m a lo u t e r p l a n a rg r a p h s i ns e c t i o n5 ，w ed e t e r m i n et h ef i r s tt h r e el a r g e s ts i g n l e s sl a p l a c i a ns p e c t r a l r a d i it o g e t l e rw i t ht h ec o r r e s p o n d i n gg r a p h sa m o n gu n i c y c l i cg r a p h sw i t hn v e r t i c e sa n dm a t c h i n gn u m b e rq a n dt h ec o r r e s p o n d i n gg r 印h sa r ec h a r a c - t e r i z e d i ns e c t i o n6 ，w ed e t e r m i n et h ef i r s ta n ds e c o n dl a r g e s ts p e c t r a lr a d i it o g e t h e r w i t ht h ec o r r e s p o n d i n gg r a p h sa m o n gc a c t iw i t hnv e r t i c e sa n d m a t c h i n gn u m - b e rq a n dt h ec o r r e s p o n d i n gg r a p h sa r ec h a r a c t e r i z e d k e yw o r d s ：z a g r e bi n d e x ；m a x i m a lo u t e r p l a n a rg r a p h ；u n i c y c l i cg r a p h ；c a c t u s g r a p h ；m a t c h i n gn u m b e r i i 硕士学位论丈 m a s t e r st h e s i s 目录 摘要i a b s t r a c t i i 第一节绪论1 1 1 研究背景及研究意义 1 1 2 本课题国内外的主要研究现状 2 1 3 本文主要解决的问题3 第二节预备知识及符号4 2 1 基本符号与定义 4 第三节极大外平面图、具有完美匹配的外平面图、极大外平面图中z a - g r e b 指标的上下界 7 3 1 引理的证明8 3 2 极大外平面图中m 1 指标的上下界1 0 3 3 极大外平面图中m s 指标的上下界1 2 3 4 具有完美匹配的极大外平面图、外平面图中z a g r e b 指标的上下界1 8 第四节极大外平面图中两类z a g r e b 指标的比较2 1 第五节具有g 匹配的n 阶单圈图中无符号拉普拉斯谱半径的排序2 7 5 1 引理的证明2 9 5 2 主要结论4 0 第六节具有g - 匹配的n 阶c a c t i 中谱半径的排序5 2 6 1 引理的证明5 3 6 2 主要结论5 6 第七节归纳展望6 8 参考文献：6 9 在校期间发表的论文7 4 致谢7 5 第一节绪论 本节首先介绍了本文的研究背景及研究意义与国内外研究现状 1 1 研究背景及研究意义 如果用图中的每个顶点代表分子中的一个原子，每条边代表原子之间形成的 化学键，我们就把这种图称为分子图一般地，我们把在分子图或其矩阵表示中不 依赖于顶点标号方式而改变的量叫做分子图的拓扑不变量它在一定程度上表达 出分子的本性，同时在数学处理上相对于量子化学具有简单性因此，拓扑不变量 在化学、医学、制药等方面具有巨大的应用价值 第一类z a g r e b 指标尬，第二类z a g r e b 指标m s 是由g u t m a n 和t r i n a j s t i 6 在1 9 7 2 年的一次报告中提出的 3 8 】设图g = ( y ( g ) ，e ( g ) ) 是一个简单的连通图， 则 m = m ( g ) = ( d g ( u ) ) 2 ，m 2 = m s ( g ) = d g ( 乱) d g ( 口) u y ( g )u v e e ( g ) 它们主要应用于分子设计、分子复杂性等方面，反映了分子骨架的分支程度，并与 分子的能量密切相关z a g r e b 拓扑指标在分子结构复杂性、能量等方面得到广泛的 应用 图谱理论是代数图论中一个非常重要的研究方向，也是一类重要的不变量为 了研究图的性质人们引入了各种各样的矩阵，例如：图的邻接矩阵，拉普拉斯矩阵， 无符号拉普拉斯矩阵等等这些矩阵与图都有着自然的联系，它们的特征值对应着 图的各种谱图谱理论的一个主要问题就是研究图的结构性质能否以及如何由这些 矩阵的代数性质反映出来( 这里所说的结构性质是指与图的结构有关的量，如顶点 数，边数，匹配数等等而代数性质主要指矩阵的特征值和特征向量) 可喜的是， 近几年来，关于图谱理论方面的研究成果很多，这极大地丰富了图谱的研究内容 图的谱半径指的是其邻接矩阵的最大特征值，它在化学上有很重要的作用一 个分子所对应的图的谱半径可以用来衡量分子的分支结构而人们对谱半径的研 究主要集中在这样的问题：在给定的一类图的集合中，找到谱半径的上界，并刻画 出相应的极图( 这是由a b r u a l d i 、e s s o l h e i d 在【2 中提出的) 近几年来，关于图的无符号拉普拉斯谱半径的研究也很多图的无符号拉普拉 斯谱半径指的是其无符号拉普拉斯矩阵的最大特征值较之图的谱半径，人们发现 1 ： 硕士学位论丈 m a s r e r st h e s i s 图的无符号拉普拉斯谱半径更能反映图的结构性能【2 9 】中指出：在图的各种矩阵 中，无符号拉普拉斯矩阵更便于研究图的性质 1 2本课题国内外的主要研究现状 自z a g r e b 指标被提出以来，研究者们对它的以下三类问题有浓厚的兴趣： ( 1 ) 图g 的结构对尬( g ) 和( g ) 指标所产生的影响 ( 2 ) 给定一类分子图集合够，如何确定舰( g ) 和( g ) 的上、下界，并且刻画 出相应的极图 ( 3 ) 比较同一个图的两类z a g r e b 指标，见 4 9 1 近些年，国内外众多学者围绕着z a g r e b 指标的性质进行了大量研究，并取得 了显著成果当图g 中某种参数( 如：顶点、悬挂点、割边、直径、最大度、围长、 完美匹配、连通度、割点等) 确定时，z a g r e b 指标的极值问题也得到了不同程度的 解决，见【2 4 ，4 1 ，6 9 ，7 1 ，6 0 ，6 1 ，1 1 ，1 2 ，4 6 ，2 8 ，1 5 ，5 7 ，1 6 】 在比较同一个图的两类z a g r e b 指标的研究中，人们注意到尬一指标的数量级 是d ( n 3 ) ( 其中孔是顶点数，数量级为d ( n ) ) ，而一指标的数量级是0 ( 扎4 ) ( 边数 为m = o ( n 2 ) ) 那么，较之直接比较尬和，比较警和警更合理 在【4 9 ，3 1 ，3 2 】中，g c a p o r o s s i 、p h a n s e n 、m a o u c h i c h e 等人给出如下的猜 想： 猜想1 1 设g 是任意的简单连通图，则： 竺坦 i m i ，则称m 是g 的最大匹配 若l m i = m 并且g 中任意其他匹配m 7 都有i m i m ，则称m 是m 匹配 设m 是g 的匹配，g 的m 交错路是指其边在e m 和m 中交错出现的路 m 可扩路是指其起点和终点都是m 非饱和的m 交错路 定义2 3 设u y ( g ) ，若d ( v ) = l ，则称口是g 的悬挂点或叶子 定义2 4 设p = r o y l ( s 1 ) 是g 中的一条路，并且d ( v 1 ) = = d ( 一1 ) = 2 ( s 1 ) 若d ( v o ) ，d ( ) 3 ，则称p 是g 的一条内部路；若d ( v o ) 3 ，d ( v 。) = 1 ，则称p 是g 的一条悬挂路 定义2 5 设g = ( ke ) 是一个礼阶图，且设a ( g ) 是其邻接矩阵，则称a ( g ) 的特征值p l ( g ) 化( g ) 砌( g ) 为g 的特征值；称d e t ( x l a ( g ) ) 为g 的 特征多项式，记为( g ；z ) ；称最大特征值p 1 ( g ) 为g 的谱半径，记为p ( g ) 如果g 是连通的，则a ( g ) 是不可约的，由非负矩阵的p e r r o n f r o b e n i u s 理论， 我们知道p ( g ) 的重数为，且存在唯一的正的特征向量对应于p ( g ) ，我们称这个特 征向量为g 的p e r r o n 向量 定义2 6 设g = ( ve ) 是一个n 阶图，且设a ( g ) 是其邻接矩阵，d ( g ) 是一个对角线上元为 d l ，d 2 ，d t l ，其他元都为0 的nx 礼矩阵，则称矩阵 l ( g ) = d ( g ) 一a ( g ) 是g 的拉普拉斯矩阵，它的特征值记为a 1 ( g ) 入2 ( g ) a 住( g ) ；称最大特征值a l ( g ) 为g 的拉普拉斯谱半径 定义2 7 设g = ( ve ) 是一个n 阶图，且设a ( a ) 是其邻接矩阵，则称矩阵 q ( a ) = d ( e ) + a ( g ) 是g 的无符号拉普拉斯矩阵；称d e t ( z i q ( g ) ) 为g 的无 符号拉普拉斯特征多项式，记为矽( g ，z ) ；称最大特征值为g 的无符号拉普拉斯谱 半径，记为p ( g ) 一 5 硕士学位论文 m a s f e r st h e s i s 如果g 是连通的，则q ( c ) 是不可约的，由非负矩阵的p e 册n f r o b e n i u s 理论， 我们知道p ( g ) 的重数为j ，且存在唯一的正的特征向量对应于p ( g ) ，我们称这个 特征向量为g 的p e 肿佗向量 6 硕士学住论文 m a s t e r st h e s i s 第三节极大外平面图、具有完美匹配的外平面图、极大 外平面图中z a g r e b 指标的上下界 在这一节中，我们将总结n 阶极大外平面图中，z a g r e b 指标的上下界，并相应 地确定了z a g r e b 指标达到上下界的极图；并在此基础之上，继续研究了具有完美 匹配的外平面图、极大外平面图中z a g r e b 指标的上下界及相应极图 如果平面图g 的所有顶点都位于同一个面的边界上，则称g 为外平面图如 果外平面图g 的一条边满足：它连接g 的外边界的两点，但它本身不是外边界上 的边，则称该边为g 的一条弦称本身是外平面图，但在不相邻的顶点间加边就 不是外平面图的图为极大外平面图由定义可知，在极大外平面图中，除了外平面 外，其他面的边界都由三条边构成；另外，任意一个n ( 3 ) 阶极大外平面图都有 2 n 一3 条边，至少两个2 度顶点当n 3 时，令魄表示满足以下条件的极大外平 面图： ( i ) 存在顶点 使得d ( v ) = 2 且n ( v ) = u ，w ) ； ( i i ) 对任意的x 坛 t | ，伽) ，都有z 至少与u 和t u 中一个顶点相邻 易见，k xvr 一1 鲰焉( 参见【1 】) 如图1 所示 图1 ：图焉( 其中n = 2 k ，2 k 一1 ) 下面给出本节需要用到的事实和引理： 事实3 1 设g 是任意的极大外平面图如果d ( v ) = 2 且n ( v ) = “，叫 ，则 u w e ( g ) 事实3 2 设g 是任意的n ( 4 ) 阶极大外平面图如果d ( u ) = 2 且n ( v ) = u ，叫) ，则i n ( u ) n ( 伽) i = 2 引理3 3 ( 4 2 ，3 7 】) 设t 是任意的礼阶树，则： 7 哦陶 七 圜 ( i ) 4 n 一6 m l ( t ) n 2 一礼，左端等式成立当且仅当t 笔r ，右端等式成立 当且仅当t 竺晶 ( i i ) 4 n 一8 ( t ) n 2 2 n + l 左端等式成立当且仅当t 笺r ，右端等式成 立当且仅当t 型& 具有完美匹配的树是具有偶数个顶点的树由引理3 3 ，经计算可得： 引理3 4 设? 是任意具有完美匹配的2 七阶树，则： ( i ) ( 【6 0 】) 8 k 一6 m 1 ( 丁) k 2 + 5 k 一4 ，左端等式成立当且仅当t 竺尼七，右 端等式成立当且仅当t 是在瓯+ 1 的某k 一1 个非中心点的顶点上分别粘一 个悬挂点后所得的树 ( i i ) ( 【4 6 】) 8 k 一8 尬( t ) 2 k 2 + k 一2 ，左端等式成立当且仅当t 垡b 七，右 端等式成立当且仅当t 是在鼠+ 1 的某k 一1 个非中心点的顶点上分别粘一 个悬挂点后所得的树 3 1引理的证明 引理3 5 设g 是任意的nm 5 ) 阶极大外平面图如果d ( v ) = 2 且n ( v ) = t ，叫 ，则7 d ( u ) + d ( 叫) n + 2 ，左端等式成立当且仅当g n ( u ) u n ( w ) 】竺礤； 右端等式成立当且仅当g 编 证明：首先证明：d ( u ) + d ( w ) 7 由于g 是极大外平面图，则g 中所有 顶点都在其外边界上从而，它的外边界构成唯一的哈密尔顿圈，记为g 由事 实3 1 可知u e ( g ) 因此，d ( u ) 3 且d ) 3 根据事实3 2 ，( 仳) ，( 叫) 有其他的公共邻点，记为z ( u ) 如果z 坛( u ) ( 或者坛( 叫) ) ( 见图2 ( n ) ) ， ( 口) ( 6 ) 图2 ：g 中，w 的公共邻点z 的两种构造 8 、- - ， 硕士学位论文 m a s t e r st h e s i s 则d ( u ) + d ( w ) 3 + 4 ，并且等式成立当且仅当c n ( u ) u ( 硼) 】垒碍如果 z 譬n o ( u ) 且zgn c ( w ) ( 见图2 ( 6 ) ) ，则d ( u ) + d ( w ) 4 + 4 = 8 引理第一部分 得证 其次，我们证明引理的第二部分由事实3 1 和3 2 可知：t 似e ( g ) ，并且 ( t ) ，( 叫) 除 外仅有一个公共邻点，记为x ( u ) 因此，i y c 钆，u ，w ，z ) i = n 一4 从而，d ( u ) + d ( w ) 取得最大值当且仅当场 扎，t ，叫，z 中任意点y 要么 与u 相邻，要么与w 相邻此时，假设1 ，缸2 ，饥这k 个顶点与u 相邻，则 牡，口，w ，z ，u l ，忱，u 七】中的顶点均与w 相邻，从而有： d ( u ) + d ( w ) ( 3 + k ) + ( 3 + 礼一4 一k ) = n + 2 其中等式成立当且仅当g 鲰引理得证 口 根据z a g r e b 指标的定义及直接计算可得下面的引理： 引理3 6 设n 4 ，则舰( k 1 vr 一1 ) = 礼2 + 7 n 一1 8 ，m ( 砰) = 1 6 n 一3 8 引理3 7 设n 6 ，则( vr 一1 ) = 3 n 2 + 竹一1 9 ，尬( 焉2 ) = 3 2 n 一1 0 0 引理3 8 设g 是任意的n ( 7 ) 阶极大外平面图如果d ( v ) = 2 且n ( v ) = u ，叫) ，则 d ( ) + d ( 屿) 1 2 u t e n o ( u )w j e n o ( 埘) 并且等式成立当且仅当g 【( o ( 乱) ) un ( n o ( w ) ) u 口】兰辟，其中 o ( 仳) = j 7 v ( u ) ，加】，n o ( 伽) = ( ) ，牡) 证明：由于o ( 缸) = ( 1 1 ) 【u ，) ，n o ( 似) = ( 叫) u ，u ) ，再由引理3 5 可得： i i ( u ) l + l n o ( 伽) i = d ( t | ) + d ( 加) 一4 3 ，( 3 1 ) 等式成立当且仅当d ( 叻+ d ( 伽) = 7 ，i e ，v g ( u ) u ( 叫) 】鲁片特别地，当( 3 1 ) 中等式成立时，i 0 ( t i ) u 0 ( 伽) l = 2 此时令：g o ( u ) ug o ( w ) = z l ，z 2 ) 显然在g 中z 1 与x 2 相邻不失一般性地，设 z l ，x 2 ) ( 乱) ，t , 2 ( t t ，) 此时，我们有： d ( u t ) +d ( 屿) d ( z 1 ) + d ( z 2 ) + d ( z 2 ) u t e n o ( u )0 ( t ，) 9 硕士学位论文 m a s t e r st h e s i s 其中等式成立当且仅当g n ( u ) u 、r ( 叫) 】竺碍因为g 是阶数至少为7 的极大外 平面图，结合事实3 2 可得：n ( x 1 ) ，( z 2 ) 公共邻点除了t l 之外只有一个又因为 d ( x 1 ) 3 及d ( x 2 ) 4 ，所以：当d ( x 1 ) = 3 时，d ( x 2 ) 5 从而， d ( u ) +d ( w j ) d o ：1 ) + d ( z 2 ) + d ( z 2 ) 1 3 1 2 u i e l v o ( u ) qe n o ( w ) 当d ( x 1 ) 4 时，d ( x 2 ) 4 从而， d ( u i ) +d ( w j ) d ( x 1 ) + d ( x 2 ) + d ( z 2 ) 1 2 啦 r 0 ( u )w j e g o ( w ) 综上可得： d ( u t ) + d ( w j ) = 1 2 t e n o ( u ) 嘶o ( ) 成立当且仅当a n ( u ) uj v ( 叫) 】兰焉及d ( x 1 ) = d ( x 2 ) = 4 ，i ea n ( n o ( u ) ) t j n ( n o ( w ) ) u 【u ) 】垒辟，引理得证 口 3 2 极大外平面图中m 指标的上下界 定理3 9 设g 是任意的n ( n 4 ) 阶极大外平面图，则： 舰( g ) 1 6 n 一3 8 ； 等号成立当且仅当g 皇焉( 见图1 ) 证明：对n 用数学归纳法：当n 4 ，5 ) 时，铭中分别只包含唯一的图砰， 即定理当佗= 4 ，5 时成立 当n = 6 时，磁= 研，弼，9 1 ) ( 见图3 ) 由直接计算可得： m ( 研) = 6 0 ，尬( 呸) = 6 0 ，m ( 磁) = 5 8 = 尬( 焉) ( 3 2 ) 因此，定理在礼= 6 时成立 现在假设此定理对所有顶点数小于佗的极大外平面图成立，并设g 是一个 n ( 之7 ) 阶极大外平面图 显然，如果g 呈p n ，2 则由引理3 6 ，即得证因此，接下来我们只需证明：如果 g 喾焉，则m ( g ) 1 6 n 一3 8 1 0 _ ： ： 硕士学位论文 m a s t e r st h e s i s 注意到g 是极大外平面图，故我们总可以在g 中找到度为2 的顶点u 使 得：n ( v ) = 牡，叫) 并且d ( u ) + d ( w ) 足够小由引理3 5 得：d ( u ) + d ( w ) 7 ，等式 成立当且仅当g n ( u ) uj 7 v ( 叫) 】兰片 令：g 7 = g u ，则g 7 是一个n 一1 阶极大外平面图由g 掌群，v 的选 法及归纳假设，得：m ( g ，) m i ( 碟2 一1 ) 另外，因为g 7 = g 一口，所以d g ，( 仳) = d ( u ) 一1 ，如，( 伽) = d ( w ) 一1 ，并且对任意的z y c 秒，u ，叫 ，都有d g , ( z ) = d ( z ) 从 而， m 1 ( g ) = m i ( g 7 ) + ( d ( 口) ) 2 十( d ( u ) ) 2 一( d g ，( u ) ) 2 + ( d ( 叫) ) 2 一( d g ，( ) ) 2 = m i ( g 7 ) + 2 2 + ( d ( u ) ) 2 一( d ( u ) 一1 ) 2 】+ 【( d ( 叫) ) 2 一( d ( w ) 一1 ) 2 】 = m i ( g ) + 2 + 2 d ( u ) + d ( 叫) 】 m i ( f 21 ) + 2 十2x7 = 1 6 ( n 一1 ) 一3 8 + 1 6 = m i ( 焉) 因此，由数学归纳法得：定理3 9 成立 定理3 1 0 设g 是任意的n ( 4 ) 阶极大外平面图，则： ( i ) 当n = 6 时，m i ( g ) 6 0 ，等号成立当且仅当g 望k 1vp 5 或彤( 见图3 ) ( i i ) 当n 6 时，m i ( g ) n 2 + 一1 8 ，等号成立当且仅当g 釜k 1vr 一1 证明：( i ) 当仡= 6 时，兹= z ，弼，琊) ( 见图3 ) 由等式( 3 2 ) ，即得证 勿&函 图3 ：图叫，弼，珥 ( i i ) 对n 用数学归纳法当礼 4 ，5 ) 时，兹= 砰) 显然，定理成立 当n = 7 时，。嬲= h i ，h 2 ，风，风 ( 见图4 ) 经直接计算可得： m i ( h 1 ) = 8 0 ，帆( h 2 ) = 7 6 ，m l ( h z ) = 7 8 ，舰( 矾) = 7 4 1 l 口 硕士学位论文 m a s t e r st h e s i s 圆圆 图4 ：图日1 ，仍，风，凰 因此，当n = 7 时，定理成立 现在假设定理对所有顶点数小于礼的极大外平面图成立设g 是任意一个礼 阶极大外平面图，令u 是g 中度为2 的点，记n ( v ) = u ，w ) 令：g ，= g u ，则g ，是一个n - 1 阶极大外平面图由归纳假设可得：舰( g ，) 舰( k 1vr 一2 ) = ( 礼一1 ) 2 + 7 ( 礼一1 ) 一1 8 = n 2 + 5 n 一2 4 ，等式成立当且仅当 g 7 兰k avr 一2 另外，因为g 7 = g - v ，所以d g ，( u ) = d ( u ) 一l ，d g ，( w ) = d ( 伽) 一1 ， 并且对任意的z v o 口，u ，叫) ，都有d g , ( z ) = d ( z ) 从而， 舰( g ) = 舰( g 7 ) + ( d ( ) ) 2 + ( d ( u ) ) 2 一( d o ，( u ) ) 2 + ( d ( 伽) ) 2 一( d g ，( 叫) ) 2 = m i ( g 7 ) + 2 2 + ( d ( 仳) ) 2 一( d ( t | ) 一1 ) 2 】+ 【( d ( ) ) 2 一( d ( w ) 一1 ) 2 】 =舰( g ) + 4 + 2 陋( t 正) + d ( ) 】一2 m 1 ( k 1vr 一2 ) + 2 十2 ( n + 2 )( 3 3 ) = n 2 + 7 n 一1 8 ( 3 3 ) 式中等号成立当且仅当g ，掣k 1vr 一2 及g ，等价于g 皇k 1vr 一1 ，即 得证 口 3 3 极大外平面图中m 2 指标的上下界 设口是g 中度为2 的点，记n ( v ) = u ，埘) 令g 7 = g 一 ，并记： o ( u ) = ( u ) ，伽) ，n o ( 叫) = ( 叫) ，u ) ， 弼( t 正) = a ( u ) t t ， ， 瞄( ) = j 7 v a ( 训) u ) 因此， o ( 乱) = 州( u ) ，n o ( ) = 粥( t t ，) 此外，对任意的z u ，牡，叫 ，都有： d 0 ，( t i ) = d ( 缸) 一1 ，d a ，( 叫) = d ( 叫) 一1 ，d g ，( z ) = d ( z ) 1 2 ( 3 4 ) ( 3 5 ) ( 3 6 ) 硕士学位论文 m a s t e r st h e s i s 定理3 1 1 设g 是任意的礼( 4 ) 阶极大外平面图，则( g ) ( 砰) ，等 式成立当且仅当g 垒焉 证明：对n 进行归纳 当他 4 ，5 ) 时，铭= p 2 ) ，定理显然成立 当礼= 6 时，缳= 研，赐，h i ) ( 见图3 ) 由直接计算可得： m 2 ( h 7 i ) = 9 5 ，( q ) = 9 6 ，( 焉) = 9 2 ( 3 7 ) 因此，当n = 6 时，定理成立 当n = 7 时，粥= h 1 ，2 ，h 3 ，风) ( 见图4 ) 由直接计算可得： m 2 ( h 1 ) = 1 3 5 ，( - 2 ) = 1 2 8 ，( 3 ) = 1 3 3 ，尬( - 4 ) = 1 2 4 ( 3 8 ) 因此，当n = 7 时，定理成立 现在假设此定理对所有顶点数小于n 的极大外平面图成立，并设g 是一个 礼( 7 ) 阶极大外平面图由于g 中至少有两个度为2 的顶点，故我们令可这样的点 并记：n ( v ) = 仳，叫) 由引理3 5 得：当凡5 时，d ( u ) + d ( w ) 7 ，等式成立当且 仅当g n ( u ) i j ( ) 】竺瑶 令：g ，= g 一口，则g 7 是一个7 1 , 一1 阶极大外平面图由g 喾砰， 的选法及 归纳假设，得： ( g 7 ) m 2 ( ：礞一1 ) = 3 2 ( n 一1 ) + 1 0 0 等式成立当且仅当g 7 垒p 一21 由等式( 3 4 ) 及引理3 8 可得： d ( u t ) + d ( ) 1 2 , a e g q ( , 0 w j e n o ( w ) 等式成立当且仅当c g c ( n o ( u ) ) u g ( n o ( 叫) ) u u 】兰砰再由( 3 4 ) 一( 3 6 ) - - i 得： 尬( g )= ( g 7 ) + d ( u ) d ( u ) + d ( u ) d ( 伽) + d ( u )：d ( u i ) 缸i r o ( u ) - d c , ( u ) d g ，( u t ) + d ( 伽) d ( w j ) 一d g ，( 伽) d c ，( 嘶) u 6 ( 缸)w j e n o ( w )嘶心( 删) + d ( u ) d ( 叫) 一d e ，( u ) d c ，( 伽) = ( g ) + 2 m ) + d ( ) 】+ d ( 乱) d ( u ) 一( d ( u ) 一1 ) d ( 钆t ) 1 3 + d ( 叫) d ( w j ) 一( d ( w ) 一1 )d ( w j ) + d ( t | ) d ( w ) w j e n o ( w )嘶 r 0 ) 一 d ( 仳) 一1 】【d ( 伽) 一1 】 = ( g ，) + 2 d ( u ) + d ( 叫) 】+ d ( ) + d c w j ) u , e g o c u ) w j e n o ( w ) 十【d ( u ) + d ( 伽) 】一1 = ( g ) + 3 【d ( ) + d ( t ，) 】+ d ( ) + d ( w j ) 一1 m e n o ( u ) w j e u o c w ) ( 只2 - 1 ) + 3 7 + 1 2 1( 3 9 ) = 3 2 ( n 一1 ) 一1 0 0 + 2 1 + 1 1 = ( 砰) 、 ( 3 9 ) 式中等式成立当且仅当g ，兰谁1 、g 【( ) u ( 叫) 】岂辟及g g c ( g o ( u ) ) u g d g o ( u ) ) u u 】笔砰，等价于g 垡焉 由数学归纳法可得，定理成立 口 定理3 1 2 设g 是任意的n ( 4 ) 阶极大外平面图，则： ( i ) 当竹= 6 时，( g ) 9 6 ，等号成立当且仅当g 竺曷( 见图3 ) ( i i ) 当竹6 时，( g ) 3 n 2 + n 一1 9 ，等号成立当且仅当g 竺k 1vr 一1 证明：( i ) 当7 l = 6 时，磁= 研，弼，弼) ( 见图3 ) 由( 3 7 ) 式可得结论 ( i i ) 当n 4 ，5 ) 时，兹= 焉) ，定理显然成立 当n = 7 时，粥= 风，- 2 ，风，凰) ( 见图4 ) 由( 3 8 ) 式可知，定理成立 现在假设此定理对所有顶点数小于佗8 ) 的极大外平面图成立，并设g 是 一个n 阶极大外平面图显然，如果g 竺k 1vr 一1 ，则由引理3 7 ，即得证因此， 我们只需证明：如果g 喾k 1vr 一1 ，则( g ) 3 n 2 + 1 7 , 一1 9 设口v ( g ) 且 ( u ) = u ，叫) 由引理3 5 可得：d ( “) + d ( 叫) s 礼+ 2 ，等号成- 守r 当r 仅当g 令g 7 = g t ，则g 7 是一个1 7 , 一1 阶极大外平面图由归纳假设及引理3 7 可 得： ( ) ( k lvr 一2 ) = 3 ( n 一1 ) 2 + ( 扎一1 ) 一1 9 ， 等式成立当且仅当g ，竺k 1vr - 2 由式( 3 4 ) 一( 3 6 ) 司得： m 2 ( g ) = m 2 c g ) + d ( u ) d ( 乱) + d c ) d ( 伽) + d ( u ) d ( 毗) 一如( u ) d c 如i ) t , t e n o ( u ) t t 5 ( u ) + d c w ) d ( 屿) 一d a ，( t u ) d g , ( w a + d c u ) d c w ) 一d a 和) 如和) w j e n o c w )哟心m ) = ( g 7 ) + 2 ( d ( 牡) + d c w ) ) + d ( t ) d ( u ) 一( d c u ) 一1 ) d ( u 1 ) u e l v o c t , ) , j t e n o c u ) + d c w ) d ( w j ) 一( d ( 伽) 一1 ) d c w j ) + 酬d ( ) 嘶 o ( )w j n o c w ) 一( d ( t 正) 一1 ) ( d ( w ) 一1 ) = 尬( g ，) + 2 ( d ( 让) + d c w ) ) + d ( u t ) + d ( w j ) e n o ( u ) w j e n o o r ) + ( d ( u ) + d ( 叫) ) 一1