（运筹学与控制论专业论文）图的wiener指数及其逆问题.pdf

，、 o nt h ew i e n e ri n d e xo fg r a p h sa n di n v e r s ew i e n e r i n d e xp r o b l e m at h e s i ss u b m i t t e df o rt h ed e g r e eo fm a s t e r c a n d i d a t e ：w ux i a o y i n g s u p e r v i s o r ：p r o f l i uh u i q i n g h u b e iu n i v e r s i t y f 他h a n c h i n a 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个 人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承 担。 作者签名：量q 美 签名日期：o 年t 月1 日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本：学校有权保存并向国家 有关部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务：学 校可以允许采用影印、缩印、数字化或其它复制手段保存学位论文；在不以赢 利为目的的前提下，学校可以公开学位论文的部分或全部内容。( 保密论文在 解密后遵守此规定) 作者签名：昊、1 茛日期：) o f o 针月) g 日 导师签名： 翊蚴 日期：年月日 中文摘要 摘要 图的w i e n e r 指数是一个基于距离的分子图的拓扑不变量，用以反映化合物的 分子结构与其化学和物理特性之间的关系图的w i e n e r 指数逆问题在生物医学中 具有重要的研究意义，特别对有目的地合成药物有重要的理论指导意义本文中 主要研究了几类特殊图的w i e n e r 指数及其逆问题，共由三章组成，其中第一章，是 对本论文所涉及的问题的背景、进展以及所得结果的一个综述 在第二章中，我们首先考虑一类特殊的单圈图的w i e n e r 指数，根据其点数、 围长和悬挂点个数的关系，分别刻画了三种情形下的给定围长g 和悬挂点个 数k 的n 阶单圈图中具有最d x w i e n e r 指数的极值图的结构特征，并推广了一些已 有的结果接着，考虑一类给定团数的连通图的w i e n e r 指数，讨论和刻画了团数 为f 的佗阶连通图的w i e n e r 指数的上界和下界，以及达到这些上界和下界时的极值 图 在第三章中，我们首先讨论了一类特殊的给定割边数目的n 阶连通图 的w i e n e r 指数，刻画了所有含有n - k 个点的团和七条割边的n 阶连通图的w i e n e r 指 数第一小到第六小的六个极值图，进而得到了给定割边数目的n 阶连通图 的w i e n e r 指数的下界哟和达到下界时的极值图，并且对于任意不小于r 0 的任意正 整数n 均能构造一个有k 条割边的n 阶连通图，使得它的w i e n e r 指数为r ，此结果已 发表在_ a c t aa p p l i c a n d a em a t h e m a t i c a e2 0 1 0 ，1 1 0 ( 2 ) ：5 3 5 5 4 4 其次，讨论和刻画了 直径为d 的礼阶连通图中具有最d x w i e n e r 指数7 1 的图，并且对于不小于r 1 的任意正 整数r ，能构造一个直径为d 的n 阶连通图，使得它的w i e n e r 指数为7 最后，对于不 小于咆的任意正整数7 ，我们能构造一个团数为f 的佗阶连通图使得它的w i e n e r 指 数为r ，其中r 2 为团数为z 的n 阶连通图的最d x w i e n e r 指数 最后，我们对本文所作的工作进行了总结，并且提出几个有待进一步研究的 问题 关键词：图；w i e n e r 指数；逆问题；割边；团数；悬挂点；直径；围长 湖北大学硕士学位论文 a bs t r a c t t h ew i e n e ri n d e xo fag r a p hi sad i s t a n c e b a s e dt o p o l o g i c a li n v a r i a n to fm o l e c - u l a rg r a p h s ，w h i c hd e m o n s t r a t e sc o r r e l a t i o n sb e t w e e np h y s i c o c h e m i c a lp r o p e r t i e so f o r g a n i cc o m p o u n d sa n dt h et o p o l o g i c a ls t r u c t u r eo ft h e i rm o l e c u l a rg r a p h s t h er e s e a r c ho ft h ei n v e r s ew i e n e ri n d e xp r o b l e mi st h em o s ti m p o r t a n ti nb i o m e d i c a lf i e l d e s p e c i a l l yi nt h es y n t h e t i cd r u g s ，n l i st h e s i sc o n s i s t so ft h r e ec h a p t e r s a n dt h eg o a l o fw h i c hi st os t u d yt h ew i e n e ri n d e xa n dt h ei n v e r s ew i e n e ri n d e xp r o b l e mo fs o m e c l a s s e so fg r a p h s t h ef i r s tc h a p t e ri sa ni n t r o d u c t i o nt ot h eb a c k g r o u n do ft h er e s e a r c h a n dr e s u l t sp r e s e n t e di nt h i sp a p e r i nt h es e c o n dc h a p t e lw ef o c u so nw i e n e ri n d e xf o rc e r t a i nf a m i l i e so fg r a p h s f i r s tw ec o n s i d e rac l a s so fu n i c y c l i cg r a p h s ，a n dc h a r a c t e r i z et h eu n i c y c l i cg r a p hw i t h m i n i m u mw i e n e ri n d e xa m o n ga l lu n i c y c l i cg r a p h so fo r d e rna n dg i r t h 夕w i t hkp e n - d a n tv e r t i c e s ，r e s p e c t i v e l y , a c c o r d i n gt ot h er e l a t i o no f 佗，夕，k ，f r o mw h i c h ，w ec a n o b t a i ns o m ek n o w nr e s u l t s n e x t ，w eo b t a i ns h a r pl o w e ra n du p p e rb o u n d so nw i e n e r i n d e xf o rc o n n e c t e dg r a p h so fo r d e rnw i t hc l i q u en u m b e rf a n dc h a r a c t e r i z et h ee x t r e m a lg r a p h s i nt h et h i r dc h a p t e r w ef o c u so nt h ei n v e r s ew i e n e ri n d e xp r o b l e mo fs o m ec l a s s e s o fg r a p h s f i r s tw ep r e s e n tt h es i xg r a p h sw i t ht h ef i r s tt ot h es i x t hs m a l l e s tw i e n e r i n d e xa m o n ga l lg r a p h sw i t hnv e r t i c e sa n d 七c u te d g e sa n dc o n t a i n i n ga c o m p l e t e s u b g r a p ho fo r d e r 佗一k a n do b t a i nl o w e rb o u n dr 0o nw i e n e ri n d e xa m o n ga l lg r a p h s w i t hnv e r t i c e sa n d 七c u te d g e sa n dc h a r a c t e r i z et h ee x t r e m a lg r a p h a n dt h e nc o n s t r u c t ag r a p hw i t hi t sw i e n e ri n d e xn ol e s st h a nt h ei n t e g e rr 0a m o n ga l lg r a p h sw i t h 竹 v e r t i c e sa n dkc u te d g e s ，w h i c hi sp u b l i s h e di na c t aa p p l i c a n d a em a t h e m a t i c a e2 01 0 ， 1 10 ( 2 ) ：5 3 5 - 5 4 4 n e x tw ec h a r a c t e r i z et h eg r a p hw i t ht h es m a l l e s tw i e n e ri n d e xr l a m o n g a l lg r a p h sw i t h 礼v e r t i c e sa n dd i a m e t e rd ：a n dt h e nw ec o n s t r u c tag r a p hw i t hi t s w i e n e ri n d e xn ol e s st h a nt h ei n t e g e rr la m o n ga l lg r a p h sw i t hnv e r t i c e sa n dd i a m e t e r d a tl a s t ，w ec o n t r u c tag r a p hw i t hf i x e dc l i q u en u m b e rfs u c ht h a ti t sw i e n e ri n d e x i sn ol e s st h a nr 2 ，w h e r er 2i st h em i n i m u nw i e n e ri n d e xa m o n ga l lg r a p h so fo r d e rn w i t hf i x e dc l i q u en u m b e rf f i n a l l y , c o n c l u s i o n sa n d s o m ep r o b l e m st ob es t u d i e df u r t h e ra r ep r o p o s e di nt h e t h e s i s k e yw o r d s ： g r a p h ；w i e n e ri n d e x ；i n v e r s ep r o b l e m ；c u t - e d g e ；c l i q u en u m b e r ；p e n d a n tv e r t e x ；d i a m e t e r ；g i r t h 一 目录 目录 第一章绪论1 1 1 基本概念和符号 1 1 2 图的w i e n e r 指数2 1 3 图的w i e n e r 指数逆问题3 第二章图的w i e n e r 指数5 2 1 引言5 2 2 单圈图的w i e n e r 指数6 2 2 1 预备引理6 2 2 2 主要结论及其证明7 2 3 给定团数的图的w i e n e r 指数1 0 2 3 1 移接变形1 0 2 3 2 主要结论及其证明1 3 第三章图的w i e n e r 指数的逆问题1 7 3 1 引言1 7 3 2 给定割边数的图的w i e n e r 指数1 8 3 2 1 定义及引理1 8 3 2 2w i e n e r 指数极小的图2 l 3 2 3 主要结论的证明2 4 3 3 给定直径的图的w i e n e r 指数逆问题2 6 3 3 1 相关的记号和引理2 6 3 3 2 主要结论2 9 3 4 给定团数的图的w i e n e r 指数逆问题3 1 结束语3 4 结论3 4 展望3 5 参考文献3 6 附录4 1 n l 1 第一章绪论 第一章绪论 本文主要考虑图的w i e n e r 指数及其逆问题在本章中，我们将对与本文有关 的一些问题给出一个简单的综述综述由两部分组成在给出我们的综述之前，首 先引入一些符号和概念这些符号和概念将贯穿全文本节中没有给出的符号和 概念，我们将在适当的地方给出对于那些没有定义的符号和概念，可以在【l 】中 找到 1 1 基本概念和符号 设g 是一个图，我们将采用下列符号 y ( g ) ： 图g 的顶点集 e ( g ) ： 图g 的边集 始( u ) ： 点v 在图g 中的度 g ( ) ： 点v 在图g 中的邻域 u ( g ) ：图g 的团数，即图g 中最大团的阶数 召： 图g 的补图 t k n ：扎阶完全k 部图( 也称t u f a n 图) d g ( z ，可) ：图g 中两点z ，y 2 _ 间的距离，即g 中连接z 和y 的最短路的长度，其中， 一条路的长度是指其含边的个数 d i a m ( g ) ：图g 的直径，即图g 中两个顶点之间的最大距离 g z ： 删除图g 中的点z 及与z 关联的边得到的图 g x y ：删除图g 的边z 秒得到的图 g + x y ：添加一条连接图g 中不相邻的两点z ，的边得到的图 g e 7 ： 删除图g 的边子集e 中所有边得到的图 g v 7 ：删除图g 的顶点子集y 7 中顶点以及与之关联的边得到的图 ( g ) ：图g 的w i e n e r 指数( w i e n e ri n d e x ) ，定义为：掣y ( g ) d c ( u ，u ) 在不引起混淆的情形下，我们常用d ( 口) ，( u ) ，d ( u ，u ) ，g f ，g v 7 分别代 替如( u ) ，g ( u ) ，如( u ，口) ，g 一，g 一 下面是本文中所涉及的几个最基本的概念 定义1 1 2 设g 是有限图如果对v 仳，u y ( g ) ，在g 中都存在( 仳，u ) 路，则称g 为 连通图 定义1 1 3 设g 是简单连通图如果g 的顶点数等于边数，则称g 为单圈图 定义1 1 4 设g 是无向图g 中与z y ( g ) 关联的边的数目称为顶点z 的度其中 度为1 的顶点称为悬挂点，悬挂边是与悬挂点关联的边 定义1 1 5 设g 是有限图，e e ( g ) 如果g e 的连通分支数大于g 的连通分支 数，则称边e 为g 的割边 定义1 1 6 设g 是简单连通图，g 中最短圈的长称为g 的围长；若g 中没有圈则定 义g 的围长为无穷大 本论文中出现的图都是指无向简单连通图 1 2 图的w i e n e r 旨数 在化学图论和数学化学领域，拓扑指数也被称为连接性指数它是为了把 分子的拓扑性质与分子的各种可测量的性质联系起来，根据化合物的分子图 中所获得的信息得到各种数值不变量这些指数从不同方面反映分子化学结 构的生物活性，物理性质及其它分子特性例如分子图的r a n d i d 指数与烷烃的 沸点、色谱保留时间、生成焓、表面积、水溶解度等物理化学特性有很好的 相关性；分子图的w i e n e r 指数和分子的大小，表面积及稳定性等有着密切的关 系现在，分子拓扑指数已达上百种之多常见的分子拓扑指数包括w i e n e r 指 数、m e r r i f i e l d s i m m o n s 指数、h o s o y a 指数、r a n d i d 指数等 最古老的一个分子拓扑指数是h w i e n e r 在研究烷烃( 即石蜡) 分子沸点的 过程中，对烷烃分子中键空间相互作用与物理性质的关系进行了研究的基础上 在1 9 4 7 年提出的w i e n e r 指数【2 1 它是指一个图中所有点对之间的距离之和，用来 描述有机化合物的物理化学性质与它们的分子图的拓扑结构之间关系的一种数 值不变量1 9 8 1 年m o t o c 和b a l a b a n 在【3 】中已经证明了w i e n e r 指数值与分子的大 小密切相关，1 9 9 5 年g u t m a n 等对化学分子图的w i e n e r $ 旨数研究，发现它与范德华 分子的表面积密切相关【4 1 w i e n e r 指数自提出以后就在化学和数学等方面得到 了广泛的应用和研究，与之相关的研究也成为一个非常吸引研究者兴趣的问题 2 第一章绪论 其中分子拓扑指数的极值问题的研究，为利用计算机搜索具有给定拓扑指 数的分子图界定了顶点和边数的范闱，从而提高了计算机搜索效率早在二十 世纪7 0 年代就有关于w i e n e r t 旨数的极值图研究，最早的一个结果是e n t r i n g e r 等 在【5 】中得到的，他们证明了佗阶树中w i e n e r 指数最大、最小的图分别是路只与星 图岛最近j e l e n a 等在【6 】中讨论了给定最大度的n 阶树中w i e n e r 指数最小的图刘 慧清和陆玫等在【7 】中讨论了给定r 个圈的n 阶连通图的四类拓扑指数的极值图 有关w i e n e r 指数极值图的研究的更多详细结果可参看文献【8 】【1 7 及本文引用的 其它相关文献 受到有关树与单圈图等文献中思想的启发，在第二章，本文应用移图、增 减边、移接变形等方法对给定悬挂点的单圈图( 积七) 及给定团数的n 阶连通 图( 澎( k ，日) ) 进行了研究我们首先在2 2 节考虑一类特殊的单圈图的w i e n e r 指 数，根据其点数、围长和悬挂点个数的关系，分别刻画了三种情形下的给定围 长g 和悬挂点个数k 的礼阶单圈图中具有最d x w i e n e r 指数的极值图的结构特征，我 们得到如果围长9 【宁j + 1 ，那么巩，9 ，知是，夕，k 中w i e n e r 指数最小的图；如 果围长9 【宁j ，那么，g ，七是 g k 中w i e n e r 指数最小的图；如果n = ( k + 1 ) 夕 或夕= 【堡产j + 1 ，那么对任意g 飙k 有w ( c ) ( 巩，9 ，k ) = ( 9 知) 然后 在2 3 节虑一类给定团数的连通图的w i e n e r 指数，讨论和刻画了团数为f 的n 阶连通 图的w i e n e r t 旨数的上界和下界，以及达到这些上界和下界时的极值图，应用移接 变形等方法证明了给定团数为z 的n 阶连通图中具有最大、最d x w i e n e r 指数的图 分别为k u p 一l + l 与t u f a n 图 1 3 图的w i e n e r 指数逆问题 在药物合成过程，如果想合成具有某种性质的化合物，最基本思想就是设计 具有所期望的拓扑指数值的分子图的化合物而寻找所需分子的过程就是根据给 定的分子拓扑指数，建立对应的分子图，然后在已有分子库中进行搜索，选择符合 分子图结构要求且能够合成的结构进行合成的过程，即分子拓扑指数的逆问题 因此拓扑指数逆问题的研究对化学应用有着重要的理论指导意义 我们知道化合物即使具有相同的化学分子式，也会有不同结构( 不 同的w i e n e r 指数) ，从而有不同性质例如c o c a i n e 与s c o p o l a m i n e 有相同分子 式g 7 飓】d 1 4 但它们有完全不同的性质和不同w i e n e r 指数因此化合物分 子图的w i e n e r 指数研究是很有价值的理论研究课题基于化合物性质与它的 分子图的w i e n e r 指数密切关系，产生了一个重要w i e n e r 指数逆问题【1 8 1 ：给定 3 湖北大学硕士学位论文 一个正整数佗，是否具有w i e n e r 指数为n 的图1 9 9 8 年l e p o v i 6 与g u t m a n 在【1 9 】中 给出一个猜想：除了有限个正整数以外，存在w i e n e r 指数为任意正整数的树 2 0 0 0 年g o l d m a n 等人解决了一般图的w i e n e r 指数逆问题 2 0 1 2 0 0 6 年w a g n e r ：i ! e 【2 1 l q u 解决t l e p o v i 6 与g u t m a n 提出的猜想同年w a n g 等在【2 2 中证明除4 9 个 正整数外，具有w i e n e r 指数为其他任何正整数的树近些年，由于拓扑指数的逆问 题在生物医学中的重要意义，分子图的拓扑指数的逆问题引起越来越多研究者的 兴趣【2 3 卜【矧 在第三章中，应用增减边、移接变形等方法改变图的w i e n e r 指数，我们考 虑了几类特殊图类的w i e n e r 指数逆问题注意到树的每条边都是割边，受此激 发我们在3 2 节讨论并刻画了所有含有扎一七个点的团和k 条割边的n 阶连通图 的w i e n e r 指数第一小到第六小的六个极值图，进而得到了给定割边数目的n 阶连 通图的w i e n e r 指数的下界r o = ( n i 知) + 2 n k k 2 2 七和达到下界时的极值图，并 且对于任意不小于7 o 的任意正整数r ，均能构造一个有k 条割边的n 阶连通图，使 得它的w i e n e r 指数为r 在3 3 节中，我们考虑了给定直径为d 的仡阶连通图的w i e n e r 指数逆问题，讨论 并刻画了直径为d 的n 阶连通图中具有最d x w i e n e r 指数的图，得到了直径为d 的佗阶 连通图的w i e n e r 指数的下界 7 l 萼i = ( n 一；一1 ) + ( d 吉2 ) + ( 扎一d 一1 ) ( 【2 j 2 + ( d 一【2 j ) 2 + d + 2 ) ， 并且对于不小于r i 垦i 的任意正整数m 1 ，能构造一个直径为d 的佗阶连通图，使得它 的w i e n e r 指数为m 】 在3 4 节中，我们考虑了团数为f 的n 阶连通图的w i e n e r 指数逆问题，应用增减 边，移接变形，边交换术方法改变图的w i e n e r 指数，刻画了团数为f 的n 阶连通图 的w i e n e r 指数下界 r 2 = ( ；) + z ( o i l ) + ( 亿一z l 孚j ) 【孚j ， 对于不小于r 2 的任意正整数m 2 ，我们能构造一个团数为f 的礼阶连通图使得它 的w i e n e r 指数为l l l , 2 4 一 第一章 图的w i e n e r 指数 2 1 引言 第二章图的w i e n e r 指数 分子拓扑学是图论、拓扑学、化学、计算机科学相互交叉的一门新学科，是 个新兴的研究领域分子拓扑指数是分子拓扑学最重要的组成部分，因而关于 分子拓扑指数的研究是很有价值的理论研究课题其中分子拓扑指数的极值问题 的研究，为利用计算机搜索具有给定拓扑指数的分子图界定了顶点和边数的范 围，从而提高了计算机搜索效率基于有关方面的广泛应用，寻找具有最大或最小 拓扑指数的图的研究引起许多研究者的兴趣并取得许多结果【2 7 卜 w i e n e r 指数是最为流行的拓扑指数之一，已经被用来解释烷烃的物理和化 学性质的变化和它们的分子结构与药理性能的关系，因此确定w i e n e r 指数的极 值图对化学应用与数学理论有着极其重要的意义早在二十世纪7 0 年代就有关 于w i e n e r 指数的极值图的研究，最早的一个结果是e n t r i n g e r 等在【5 】中得到的， 他们证明了n 阶树中w i e n e r 指数最大、最小的极值图分别是路r 与星图& 目 前已经有许多关于w i e n e r 指数的数学与化学文献，尤其是关于树的w i e n e r 指数 研究最近d o b r y n i n 等在【1 0 】中对有关树的w i e n e r 指数的已有重要结果与几个 猜想及公开问题给出了一个综述j e l e n a 等在【6 】中讨论了给定最大度的n 阶树 中w i e n e r 指数最小的极值图刘慧清等在【7 】中讨论了给定7 个圈的几阶连通图的 四类拓扑指数的极值图与给定直径的n 阶树的w i e n e r 指数最小的极值图1 1 5 王华 在【4 1 中讨论了给定度序列的n 阶树中w i e n e r 指数最大与最小的极值图 受至l j e n t r i n g e r 与s h i 对给定悬挂点的树的w i e n e r 指数上下界的研究 3 0 , 3 8 及刘 慧清等关于圈的w i e n e r 指数研究思想的启发，本章我们考虑了给定悬挂点的单圈 图的w i e n e r 指数的极值图与给定团数的亿阶连通图的w i e n e r 指数的极值图首先 在2 2 节中，我们根据n 阶单圈图的点数、围长和悬挂点个数的关系，分别刻画了 三种情形下的给定围长g 和悬挂点个数k 的7 7 , 阶单圈图中具有最d x w i e n e r 指数的极 值图的结构特征然后在2 3 节中，我们应用移接变形等方法证明了团数为f 的n 阶 连通图中具有w i e n e r 指数最大，最小的极值图分别为k l u p 一1 + 1 与t u f a n 图 设幽奄= g ：g 是一个围长为夕和悬挂点个数为七的孔阶单圈图，3 g 佗一1 ，1 k n 一3 ) 设巩幽七( q 1 ，q k ) 表示在n 阶单圈图的圈g 的一个 顶点上附七( 后1 ) 条长为q i 的路，其 g n = g + 警1 吼，吼1 ，i = 1 ，k 设职a 知( 卯，g l ，q k ) 表示在夕+ q o 阶单圈图u g + q o , g , 1 ( g o ) 的悬挂点上附庇( 尼2 ) 5 湖北大学硕士学位论文 条长为吼的路，其中n = g + q i ，q i 1 ，i = 0 ，1 ，k 设硒是一个f 阶 团( f 3 ) ，记澎( k ，日) = g ：g 是一个具有团数为2 的佗阶简单连通图( z 3 ) ) 设图凰，恐是两个连通图且y ( 凰) ny ( 也) = _ ( u ) g = h l v h 2 是一个连通图 且y ( g ) = y ( 风) uy ( 玩) ，y ( 日1 ) ny ( 2 ) = 口) ，e ( g ) = e ( h 1 ) ue ( h 2 ) 2 2 单圈图的w i e n e r 指数 2 2 1 预备引理 首先我们介绍几个有用的引理 引理2 2 1 【7 】设日，x ，y 是三个互不相交的连通图u ，u 是图日的两个顶点， u 7 是图x 的一个顶点，u 7 是图y 的一个顶点图g 表示由图ex ，y 通过分别使口 和v 7 ，乱和重合得到的图，图g i 表示由图日，x ，y 通过使v ，重合得到的图， g ；表示由图日，x ，y 通过使u ，v 7 ，仳重合得到的图( 见图2 1 ) 则 w ( g ：) w ( a ) 或 w ( g ；) d 日( ) 一d h ( u ) ( 2 - 2 ) 如果w ( g ) 一w ( a * x ) 0 ，i s z _ , 由( 2 一1 ) 式有d h ( u ) 一d h ( v ) w ( g ；) 一6 第二章图的w i e n e r 指数 引理2 2 2 【1 5 】设g 是一个非平凡连通图，p = y 0 1 ) 1 v 2 讥，q = ? a o z t l u 2 让m 分别是两条长为k ，m ( k m 1 ) 的路，其中仇甓y ( g ) ，0 i k ，u j 莹y ( g ) ，0 j m 假设u y ( g ) 图g ：m 表示由g ，p ，q 通过 使u ，1 ) 0 ，u o 重合得到的图那么 w ( g ；，m ) i y ( 飓) j ，那么 w ( g + ) 0 2 2 2 主要结论及其证明 图2 2 在这一节中，我们将给出在，9 ，知中w i e n e r 指数最小的图为了简化我们的 结果，我们定义下面的几个单圈图 设曲k ( q l ，q k ) 是n 阶单圈图，它是在圈q 的一个顶点上附尼( 尼1 ) 条长 为吼的路( 见图2 3 ) 其中佗= g + e l 1q i ，q i 1 ，i = l ，k 设岛七( q o ，q l ，吼) ( 见图2 - 3 ) 是扎阶单圈图，它是在9 + q o 阶单圈 7 一 湖北大学硕士学位论文 图+ 驰，9 ，1 ( q 0 ) 的悬挂点上附尼( 七2 ) 条长为仍的路( 见图2 3 ) 其中扎； g + 警。吼，q i 1 ，i = 0 ，1 ，k 七七 q kq k ( a ) ，9 ，k ( q l ，q k ) m 2 3 ( b ) ，g ，k ( q o ，q l ，q k ) 记，9 ，知= 巩，g ，k ( q l ，鲰) ，其中对任意的1 i ，j 后有i 吼一q j l 1 ，g ，磨= 舰七( q o ，q t ，饥) ，其中对任意的1 i , j 启有i 吼一劬i 1 且对任意1 i 七有吼一g q o 1 那么我们有下面的结果 命题2 2 1 ( i ) 当夕 【宁j 时，有w ( 幽k + 1 ) ( 巩，g ，七) ； ( i i ) 当夕【宁j 且n g 幻时，有w ( ，9 ，七) ( g 知一1 ) ； ( i i i ) 当佗= ( 七+ 1 ) g i r t ，有( 巩，9 ，七) = ( ，9 ，七) 证明：重复应用引理2 2 2 有( i ) 和( i i ) 成立从引理2 2 3 的证明知( i i i ) 成立 下面我们给出两个在证明主要结果时需要使用的命题在下面的两个命题中 我们总是假设g 鲰 9 ，k ，c 是g 中唯一的圈且幽长为g 命题2 2 2 假设我们选择g 使得w ( g ) 尽可能小，那么在圈c 上存在唯一的 顶点w v ( c ) 有d g ( w ) 3 证明：假设有w i y ( c ) ，i = 1 ，2 使得d g ( w 1 ) 3 记y g ( w 1 ) = x l ，u l ，仳2 ) 与g g ( z 0 2 ) = y l ，y t ，v l ，晚) ，其中u 1 ，u 2 ，口1 ，v 2 y ( c