（运筹学与控制论专业论文）给定度序列的连通图的randic指标的研究.pdf

r e s e a r c ho nt h er a n d i i n d e xo fc o n n e c t e dg r a p h s w i t hg i v e nd e g r e es e q u e n c e 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 uh a i y a n 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 嘶，h a n 。c h i n a 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集 体，均己在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承 担。 作者签名：移 签名日期：净年朋2 c c 日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家 有关部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学 校可以允许采用影印、缩印、数字化或其它复制手段保存学位论文：在不以赢 利为目的的前提下，学校可以公开学位论文的部分或全部内容。( 保密论文在 解密后遵守此规定) 作者签名： 导师签名： 鼬彭 _ 蜘 日期：砷年朔谢日 日期：年月日 r 中文摘要 摘要 r a n d i 6 指标，也称为连通性指标，与分子的物理化学性质有着极为密切的 关系研究r a n d i 6 指标的极值问题不仅在数学上有着重要的意义，而且对相关 的化学研究也有很大的作用和影响本文主要讨论给定度序列的连通图的广 义r a n d i d 指标，以及一种新型的拓扑指标广义和连通指标。 本论文共由三章组成，其中第一章，是对本论文所涉及的问题的背景、进展 以及所得结果的一个综述 在第二章中，我们研究了广义r a n d i 6 指标首先刻画了给定度序列的 连通图的( 广义) r a n d i 6 指标最大时的极图的结构特征，即若g 是所有度序 列为7 r = ( d 1 ，d 2 ，厶) 的连通图中( 广义) r a n d i 6 指标最大的图，则我们可以 认为y ( g ) 满足一种良序关系广探搜索序( b f s 序) 接着，给出了度序列 为7 r = ( d 1 ，d 2 ，厶) 的单圈图的( 广义) r a n d i 6 指标的上界，并构造了达到这些上 界时的极图 在第三章中，我们研究了一种与广义r a n d i 6 指标密切相关的新型拓扑指 标一广义和连通指标，也是对一个图边权关系总和的描述首先讨论了给定 度序列的连通图在局部扭转后广义和连通指标的变化，并得到结论：当口 l 或 q 0 时广义和连通指标最大( 小) 时的极图，正是0 o t 1 或q 1 o rq 0i sj u s t t h a tw i t ht h es m a l l e s t ( 1 a r g e s t ) g e n e r a ls u m c o n n e c t i v i t yf o r0 q 1o ro t 1 或o z 0 时广义和连通指标最大( 小) 时的极图，正是0 q 1 或q 1 或口 1 或o z 0 时最小的极图的步骤 4 第二章给定度序列的图的( 广义) r a n d i d 指标 2 1 引言 第二章给定度序列的图的( 广义) r a n d i 6 指标 化学分子图的拓扑指标理论是组合化学的一个重要研究分支计算化学 家通过大量的数据，用统计方法给出了分子的各种物理化学性质与它的指标 值之间的数量关系1 9 7 5 年，著名化学家r a n d i d 在研究分子结构时引入了分子图 的一个重要的拓扑指标，即r a n d i d 指标( 也称为连通性指标) 【2 9 1 这一重要的拓 扑指标与分子的物理化学性质( 如分子的沸点、色谱保留时间、生成焓、表面 积、水溶解度等) 有着极为密切的关系，因而得到了化学家的特别重视1 9 9 8 年， b o l l o b 缸和e r d 6 s 提出了广义r a n d i d 指标【1 1 ，即t t k ( g ) = 。以g ) ( d ( u ) d ( 秒) ) a ，其 中o t 为任意的实数这个关于r a n d i d 指标的推广可以视为研究r a n d i 6 指标数学性 质的一个重要转折点，它使r a n d i d 指标真正为数学家所熟悉越来越多的研究者 开始深入探讨各种图类的( 广义) r a n d i d 指标值，而不再仅局限于对化学图的研究 近年来，对于广义r a n d i c 指标的研究主要集中在以下问题：对于某些给定 的图类和q 值，如何求出最大或者最小的广义r a n d i c 指标值? 如何刻画这些 极值所对应的极图? 这里我们主要介绍一些给定度序列的图类的研究在文 献【6 】中d e l o r m e 等构造了给定度序列的树的广义r a n d i d 指标在q = l 时的最大值 对应的极图之后在2 0 0 7 年，王华【3 2 】讨论了给定度序列的树中r a n d i d 指标最大与 最小及其对应的极图关于( 广义) r a n d i d 指标极图的研究的更多详细结果可参看 文献【3 】一【5 】，【8 】一【1 2 ，【1 6 1 【2 5 ，【2 7 【2 8 ，【3 0 1 一【3 3 1 受到有关文献的内容与思想的启发，首先在本文第二章2 2 节中，我们定 义了广探搜索序，并且讨论了连通图局部扭转后广义r a n d i d 指标的变化接着 在2 3 节中，我们刻画了给定度序列的连通图的广义r a n d i d 指标最大时的极图的 结构特征，即若g 是所有度序列为7 r = ( d 1 ，d 2 ，如) 的连通图中广义r a n d i d 指 标最大的图，则我们可以认为y ( g ) 满足一种良序关系广探搜索序( b f s 序) 然后在2 4 节中，利用连通图的极图的结构特征，我们给出了度序列为非增 的7 r = ( d 1 ，如，厶) 的单圈图的广义r a n d i d 指标的上界，并构造了达到这些上界 时的极图：如果d 1 = 如= 2 ，则g 是唯一极图9 如果d 2 = 2 且下n + l d l 礼一1 ， 则瞬是唯一极图；如果d 2 = 2 r 3 d 1 詈，则图类碥中的任意一个图都是极图； 如果d 2 3 ，则簖是其中一个极图 给定非负整数序列7 r = ( d l ，d 2 ，如) ，其中d 1 d n ，n 3 鲧表示 5 湖北大学硕+ 学位论文 所有度序列为7 r 的连通图的集合瓦表示所有度序列为7 r 的树的集合瞬表示将 2 d 1 一n l 条悬挂边和佗一d 1 1 条长度为2 的悬挂链一起粘到g 的一个点上而 得到的单圈图碥表示将d 1 2 条长度至少为2 的悬挂链一起粘到圈q 上的一 个点而得到的所有单圈图的集合 2 2 广探搜索序 选取连通图g = ( ve ) d p 最大度的点作为根r ，把y 中任一点u 和根7 之间的距 离称为“的高度，记为九( “) 显然， p ) = 0 下面给出广探搜索序( b f s 序) 的定义 连通图g = ( ve ) 中y ( g ) 满足一种良序关系广探搜索序( b f s 一序) ，如果 对于所有的u ，u v 以下都成立： ( 1 ) 牡 虬( g ) 证明 由于局部扭转后各点的度保持不变，因而g ，鲧 叫。( g 7 ) 一u 口( g ) = ( d ( s ) a d ( 乱) n ) ( d ( 口) 。一d ( t ) a ) 0 从而得证 引理2 2 2 设g 鲧，若有三个点“， ，w v ( v ) 满足伽t e ( g ) ，u 伽岳 e ( g ) ，1 d ( v ) d ( z ) 对于任意的z ( 伽) 都成立，则 存在g 7 鲧使得u a ( g 7 ) u a ( g ) 证明 显然d ( 叫) 2 于是存在点p ( 伽) 使得p v 譬e ( g ) 且p 移因为 不然的话，w 的每一个邻点z 秒都与钉相邻，再加上u v e ( g ) ，u 伽譬e ( g ) ，则 d ( 叫) d ( ) + 1 这与已知矛盾 既然g 是连通图，存在一条从乱到w 的路r 伽= 乱8 w 我们考虑以下四种 情形： 6 第二章 给定度序列的图的( 广义) r a n d i 6 指标 情形l ：“u 隹r ”且v 8 簪e ( g ) 令g 7 = g u v w 8 + u w + 7 3 8 显然g 鲧， 由d ( u ) d ( s ) ，d ( v ) d ( 伽) ，再利用引理2 2 1 得，( g 7 ) ( g ) 情形2 ：u v 甓r 伽且1 ) 8 e ( g ) 令g 7 = g u v w p + u w + v p 显然g 鲧， 由d ( u ) d p ) ，d ( v ) d ( 加) ，再利用引理2 2 1 得，u q ( g ) u 口( g ) 情形3 ：t v r 。且) 除s 外都与秒相邻则8 v 隹e ( g ) 令g ，= g 一缸可一 w 8 + u w + v 8 由于g 中存在点q 满足q w e ( g ) 且q v e ( g ) ，因而g 7 连通 由d ( u ) d ( s ) ，d ( v ) d ( 叫) ，再利用引理2 2 1 得，( g 7 ) u a ( g ) 情n 4 ：u 口r 加且存在点p ( 枷) 使得p s 且p v 譬e ( g ) 令g 7 = g u v 一岬+ u w + v p 显然g 鲧，由d ( u ) d 0 ) ，d ( v ) d ) ，再利用引 理2 2 1 得，u 口( g 7 ) ( g ) 从而得证 2 3 极图的结构特征 在这一节中，我们将给出给定度序列的连通图中( 广义) r a n d i 6 指标最大的极 图的结构特征 引理2 3 1设g 在鲧中( 广义) r a n d i 芒指标最大，则我们可以把g 中所有点 标号成口l ，v 2 使d ( v 1 ) d ( v 2 ) d ( ) ，h ( v 1 ) d ( ) 成立这里，我们选取度为d 1 的点v l 作为图g 的根h ( v o ) = 0 h ( v x ) 当2 k n 一1 时，假设h ( v 1 ) h ( v 2 ) h ( v 3 ) h ( v k ) 成立，下面我 门证明h ( v 1 ) d ( 七+ 1 ) 的情况既然g 是连通图，设 p 是_ 1 ，2 七) 中最小的整数并且与 七+ l ) 中的某个点坼相邻显然， ( ) s 九( 讯) ，d ( ) d ( v k + 1 ) 我们考虑以下两种情形： 情形1 ： ( ) ( ) 一1 设只。+ 。是从移1 到v k + l 的最短路并且u q 是 只。+ ，上属于 u l ) 的最后一个点，从而由p 的选取得h ( v p ) h ( v 。) 既 然与 钉岛+ 1 v n ) 中的某点相邻，我们有h ( v k + 1 ) h ( v g ) + l ( 否则存在 一条路长为h ( v k + 1 ) 的长度更短的从口1 到u 知+ 1 的路，这是不可能的) 因此， h ( v k + 1 ) ( ) + 1 ( 吻) + 1 ( 讯) 7 湖北大学硕士学位论文 情形2 ： ( 邯) h ( v k ) 一1 ，则唧与魄不相邻( 否则h ( v k ) ( 邯) + 1 h ( v 七) 一 1 + 1 = h ( v k ) ，不可能) 再由d ( ) d ( v k + 1 ) d ( v k ) d ( v p ) ，则对于的任一邻 点，都有d ( v 。) d ( v p ) 这是因为，如果u 。 k + 1 ) ，则d ( 钉。) d ( v p ) 另 一方面，利用反证法假设d ( ) d ( v p ) ，如果v s 【u l 饥) ，则 沁) 危( 咋) 而 且，既然v s ? j k e ( g ) ，我们有 ( ) h ( v k ) h ( v s ) + 1 因此h ( v k ) 危( ) + l h ( v p ) + 1 九( ) 一1 + 1 = 危( 仇) ，此式矛盾所以有d ) d ( 吻) 由坳，v k 一- - _ 点满足诈e ( g ) ，讥隹e ( g ) ，d ( ) d ( v 。) ，利用引理2 2 2 可知，存在比( g ) 更大的度序列也为7 r 的 图g ，这与g 有最大的( 广义) r a n d i d 指标矛盾因此情形2 不可能，从而得证 定理2 3 2 设图g 在鲧中( 广义) r a n d i d 指标最大，则我们可以认为y ( g ) 满 足b f s 序 证明 由引理2 3 1 ，我们通过将g 中所有点标号，使其满足 口l 也 - v n d ( v 1 ) d ( v 2 ) d ( v n ) 和 h ( v 1 ) h ( v 2 ) ( ) 现在证明假设有四个点v i ，仇y ( g ) 满足v i v a e ( g ) ，仇e ( g ) ， v i v t 隹e ( g ) ，譬e ( g ) ，h ( v i ) = ( ) = 九( ) 一1 = ( 仇) 一1 并且v i d ( v j ) 令g 7 = g 一忱一吻仇+ v i v t + 吻由d ( 仇) d ( v j ) ， d ( v t ) d ( ) ，利用引理2 2 1 得，o j ( g 7 ) u 口( g ) ，这与g 有最大的广义r a n d i 芒指 标矛盾 情形2 ：d ( v i ) = d ( ) 我们可以将与v t 交换标号，使得 d 2 ，其度 序列是( d l 一1 ，d 2 ，如一1 ) ，或者当d l = 如，其度序列是( d l ，d 2 1 ，d 3 ，d n 一1 ) 设g 是从图g l 中最大度的点与新增加一点口连接一条边而得到因此7 r 是单圈图 g 的度序列 从而得证 接下来两个定理给出了度序列7 r = ( d 1 ，4 2 ，厶) 的单圈图的( 广义) r a n d i d 指标最大的极图 n 定理2 4 3 设7 r = ( d l ，d 2 ，厶) 中d 2 = 2 ，d l 厶且也= 2 n ( i ) 若d 1 = 2 ，则圈g 是度序列为7 r 的单圈图的唯一极图； ( i i ) 若下n + l d 1 n 一1 ，则瞬是度序列为7 r 的单圈图的唯一极图这里， 瞬是将2 d 1 一佗一1 条悬挂边和n d l 一1 条长度为2 的悬挂链一起粘到g 的一个 点上而得到的单圈图： ( i i i ) 若3 d l 罟，则图类u , r 中的任意一个图都是度序列为7 r 的单圈图的极 图这里，碥是将d 1 2 条长度至少为2 的悬挂链一起粘到圈q 上的一个点而得 到的所有单圈图的集合 证明若d 1 = 2 ，则由命题2 4 2 立刻得到( i ) 的结论接下来，我们只考虑 d l 3 的情况由命题2 4 2 ，存在一度序列为丌的单圈图g 既然d 2 = 2 ，对于 3 i 礼都有d i 2 ，同时d i = 2 n ，从而g 中有d 1 2 个悬挂点和扎- d l + 1 个 度为2 的点记口1 是g 中度为d 1 的点，设i g ( 砚) n 秽v ( a ) ：d a ( u ) = 1 ) i = 礼1 由于圈上至少要有两个2 度点，因此悬挂链上至多有n d 1 1 个2 度点从而 u 口( g )( d 1 一n 1 ) ( 2 d 1 ) 口+ n 1 奸+ ( d a 一2 一m ) 2 q + ( 扎一2 d l + 2 + h a ) 4 口 2 n 柙+ 1 + ( d l 一2 ) 2 q + ( n 一2 d 1 + 2 ) 4 口一扎1 ( d 一2 a ) ( 2 a 1 ) ( 1 ) 记厂( z ) 圭2 。霄+ 1 + ( d 1 2 ) z q + ( 礼一2 d 1 + 2 ) 4 q 一( d 宇一2 。) ( 2 口一1 ) x 则- 厂( z ) 在 z 0 上单调递增 若下n + l d l 竹一1 ，则n d a 一1 d l 一2 ，即n l 2 d l n 一1 0 因此， 由( 1 ) 式可知，乩( g ) f ( 2 d 1 一孔一1 ) ，等号成立当且仅当n l = 2 d l 一礼一l ，从而 1 0 第二章给定度序列的图的( 广义) r a n d i 6 指标 n 一2 d l + 2 + 几1 = 1 换言之，由( 1 ) 可知g 只有一条边相关联的两个点的度都为2 因此( g ) u 。( 瞬) ，等号成立当且仅当g 垒瞬从而( i i ) 得证 若3 d 1 等，则d 1 2 n d l 一2 注意到n l 0 ，同时由( 1 ) 式， u a ( g ) 厂( 0 ) ，等号成立当且仅当扎1 = 0 换言之，极图属于集合碥从而i ( i i i ) 得 证 n 定理2 4 4 设丌= ( d 1 ，d 2 ，d n ) 中，d 2 3 ，d x 厶且也= 2 n 则晖是度序列为丌的单圈图的一个极图 证明 由命题2 4 2 知，存在一个度序列为7 r = ( d 1 ，d 2 ，磊) 的单圈图g 假 设g 是所有度序列为7 r = ( d 1 ，奶，磊) 的单圈图中( 广义) r a n d i 6 指标最大的图 由定理2 3 1 ，我们可以将y ( g ) 中的所有点标号成u 1 ，v 2 ，使其满足 和 u 1 忱 ， d ( v 1 ) d ( 忱) d ( ) h ( v 1 ) ( 忱) 九( ) 记y ( ) = 勘v ( a ) ：h ( v ) = i ) ，这里i = 0 ，l ，九( ) = p 因此我们按照 y ( ) = v i l ，v i ，巩) 将g 的所有顶点重新标号从而对于i = 0 ，1 ，p 一1 ，1 歹8 t ，1 k s 件1 ，都有d ( v i l ) d ( v i 2 ) d ( v i ，。) 和d ( ) d ( v i + 1 ，岛) 成 立显然，8 1 = d ( v 1 ) = d 1 既然g 是单圈图，则g 中存在唯一一个阁记夕( g ) 为单圈图g 中的围 长设。是y ( ) 中高度最小的点，换言之，对于任意的 y ( ) 都满足 0 h a ( 坼。) = rsh g ( 口) 选取g 满足以下条件： ( i ) ( g ) 尽- i c i 邕地大； ( i i ) 在( i ) 的约束下，h a ( v ，。) ，g ( a ) 尽可能小，i v ( c g ) n 口1 1 ) i 尽可能大 我们先证明几个断言 断言1 对于任一乱v ( c c ) v r 口) ，都有九( 坼q ) 九( 札) 断言1 的证明若口= v 0 1 ，则对于任一乱v ( c c ) q ) ，都有0 = ( q ) d ( + 1 ，t ) ，则u 。( g 7 ) n ( g ) ，这与我 们的选取( g ) 尽可能地大矛盾于是，我们可以假设d ( 协口) = d ( v r + l , j ) 或 者d ( v r i ) = d ( + l ，t ) 从而，( g 7 ) = ( g ) 但是由于g 7 中v r q ，v r i c g ，且 九g ，v r q ) = h a ，( t ) ，利用断言l 可推导出g 7 是双圈图的矛盾所以，口= v 0 1 断言3v l i v l j e ( g ) ，这里1 i ，j s 1 断言3 的证明反证法假设对于所有的i ，j = l 8 1 及i j ，都有y l i y l ，隹 e ( g ) 所以存在两个点 1 y ( 1 ) 与y ( 2 ) 满足 1 1 e ( g b ) 且i 2 从 而d ( v 2 j ) 2 另一方面，由于d ( v 1 1 ) = d 1 3 ，因而存在一个点v 2 t y ( 2 ) 使 得v 2 t 隹y ( ) ，v l l u 2 t e ( g ) 且对于任意的钍n ( v 1 1 ) 且u 岳y ( c o ) ，都有 d ( v 2 t ) d ( u ) 既然g 是单圈图，则有v l i v 2 t 譬e ( g ) 且v 2 t v 2 j 岳e ( g ) 令g = g v l i y 2 j v 1 1 v 2 t 1 - v 1 1 v l i d r v 2 t v 2 j 则c 如( g 7 ) 一c 如( g ) = ( d ( 1 t ) a d ( v 2 t ) 。) ( d ( 1 1 ) 口一 d ( ) a 如果d ( v l i ) d ( v 2 t ) ，推知d ( v n ) d ( ) ，则( g 7 ) ( g ) ，这与我们 的选取u n ( g ) 尽可能地大矛盾于是，我们可以假设d ( v 1 ) = d ( 锄) 从而 u 。( g 7 ) = ( g ) 但是，由于g ( a 7 ) 夕( g ) ，这又与我们的极值图的选取条件不符 因此在我们选取的图中，u l i y l j e ( g ) ，这里1 i ，j 8 1 断言4v 1 1 1 j e ( g ) ，这里2 歹s 1 断言4 的证明反证法假设y 1 i v u e ( g ) ，这里，2 i d ( v l t ) 由于d ( 1 1 ) d ( v l t ) d ( v l j ) 及 d ( v n ) = d 2 3 ，因而存在一个点v 2 t y ( 2 ) 使得v l l v 2 t e ( g ) 既然g 是单圈图， 则有v l l v l i 岳e ( g ) 且v l j v 2 譬e ( g ) 令g ，= g u l i 口1 j v l l v 2 t + v l l 1 t + v l j v 2 贝0 ( g 7 ) 一u 。( g ) = ( d ( v l i ) n d ( v 2 t ) q ) ( d ( u 1 1 ) n d ( v l j ) a 如果d ( v l i ) d ( v 2 ) ，推知d ( v n ) d ( v l j ) ，则u q ( g ，) ( g ) 这与我们 的选取( g ) 尽可能地大矛盾如果d ( 口1 ) = d ( v 2 。) ，则( g 7 ) = u a ( g ) 但是 1 2 第二章给定度序列的图的( 广义) r a n d i 6 指标 口1 1 ， ) ，这又与我们的极值图的选取条件不符因此在我们选取的图中， v l l v l j e ( g ) ，这里2 j 8 1 断言5i ) 1 1 v 1 2 e ( g ) 断言5 的证明反证法假设u l l v l 2 岳e ( g ) 则由断言3 ，有v l l v l j e ( g ) 且 d ( v 1 ，) 2 ，这里，2 d ( v l j ) 由于d ( v , 2 ) d ( v u ) 2 ，因此存在一 个点v 2 t y ( 2 ) 使得v 1 2 v 2 t e ( g ) 且v l j v 2 隹e ( g ) 既然d ( v 1 2 ) d ( v l j ) ，则 d ( v 1 1 ) d ( v 1 2 ) d ( v l j ) d ( t j 2 t ) 令g ，= g v 1 1 v l j v 1 2 v 2 t + v l l v l 2 + v l j v 2 t 则 u 。( g ，) u q ( g ) ，这与我们的选取( g ) 尽可能地大矛盾因此在我们选取的图 中，u l l v l 2 e ( g ) 由断言2 和断言5 以及定理2 3 1 知，螺是度序列为丌的单圈图的( 广义) r a n d i 6 指标最大的一个极图 从而得证 1 3 湖北大学硕士学位论文 3 1 引言 第三章给定度序列的树的广义和连通指标 一种新型的拓扑指标一和连通指标是由周波等在2 0 0 9 年给出了定义刚。 即x 一吾( g ) = 训e ( g ) ( 也+ 也) - 1 2 与r a n d i 6 指标一样，和连通指标也是对一个 图边权关系总和的描述，并且这两个指标密切相关在文献【1 3 】中研究发现，对于 给定的图类和连通指标与r a n d i 6 指标具有很好的相关性，对一百三十四种树表示 的降低烷烃的研究中二者的相关因子高达0 9 9 0 8 8 此外，文献【2 6 】比较了各种苯 型烃的和连通指标与r a n d i 6 指标，也得到了二者相关性很强的结论 近年来，寻找给定图类的和连通指标值的最大与最小以及对应的极图，也开 始吸引了研究者的兴趣周波等在【3 4 】中还讨论了给定点数和悬挂点数的树的和 连通指标最大、第二大以及第三大与最小、第二小以及第- - d , ，并且分别给出了 对应的极图文献【7 】分别研究了给定点数和匹配数的树和单圈图的和连通指标 的最小值以及最小时对应的极图，还推导了佗阶单圈图m 4 ) 和连通指标的最小 与第- - d 的值类似于广义r a n d i 6 指标的提出，周波等【3 5 】给出了广义和连通指标 的定义，即x n ( g ) = 删e ( g ) ( 也+ d t ，) a ，其中q 为任意的实数 受到相关文献内容与思想的启发，在本文第三章中的3 2 节，我们首先讨论了 给定度序列的连通图在局部扭转后广义和连通指标的变化，并得到结论：当q 1 或q 0 时广义和连通指标最大( 小) 时的极图，正是0 d ( “) ( i ) 若d ( v ) d ( s ) ，则当o e 1 或q ( g ) ，当0 o t 1 时有 ( g 7 ) x q ( g ) ； ( i i ) 若d ( ) l 或q o 时有( g 7 ) x q ( g ) ，当0 q x 口( g ) 、； 证明 这里给出( i ) 的证明，( i i ) 可相似证得由由于局部扭转后各点的度保持 不变，因而g ，6 鲰 ) ( q ( g 7 ) 一x a ( g ) = ( d ( u ) + d ( t ) ) n + ( d ( s ) + d ( 乱) ) 口一( d ( u ) + d ( ) ) a 一( d ( s ) + d 0 ) ) 口 利用中值定理，可得 其中 ) ( q ( g 7 ) 一) ( n ( g ) = q ( f 一1 7 7 一1 ) ( d ( u ) d ( s ) ) ， d ( s ) + d ( t ) 1 d ( u ) + d ( t ) ， d ( s ) + d ( u ) 1 或q ( g ) ，当0 a 1 时有x q ( g ，) ( g ) ； 另一方面， x q ( g 7 ) 一x n ( g ) = 口( 等一1 一谚一1 ) ( d ( f ) 一d ( “) ) ， 1 5 湖北大学硕士学位论文 其中 d ( u ) 4 - d ( v ) 已 d ( v ) + d ( t ) ， d ( s ) + d ( u ) 啦，从而当q 1 或口 ( g ) ，当0 q 1 时有x 口( g 7 ) 1 或口 o 时，给定度序列的树的集合中和连通指标最 大时的极图，简称为极大树也正是0 a l 或 q o 时的极小树也正是0 q l 或口 l ，d m + l = = d n = 1 ，1 m l 或o o 时，在一棵度序列为丌的极大树丁中，对于 2 k d 1 ，g y k 】都是一棵树这里，g 【k 】表示t 中度不小于尼的点集的导出子 图 证明 首先，a l g 看作t 中删除所有的悬挂点而得到，因此g 【】也是一 棵树现在只需证明对于k 3 ，g 【圪1 是一棵树由于g 【k 】丁，因而g 【k 】无 圈所以我们只需证明g f k l 是连通图 ： 反证法，假设存在一个不连通的g 嘲，3 k d 1 ，从而存在两个点 u ，u y k 使得删ge ( r ) 令v o v l 是t 中一条极大路，且v i = u ，= ， 1 i j f 一1 则存在整数a ，使得2 d ( v o ) k ，i a j 选择v i 与分别 满足i 尽可能小与a i g 可能大则d ( v i 1 ) 1 或口 ) ( a ( t ) 这与丁的选取矛盾从而g 【k 】是一棵树，2 k d 1 证明完毕 引理3 3 3当o l 1 或q 1 或o t ( t ) 这与t 的选取矛盾 从而得证 引理3 3 4 当口 1 或o l l 或 o t ( t ) 这与丁的选取矛盾所以d ( v 1 ) d ( v 8 一 ) 下面证明d ( 。一) a ( v k ) 假设存在点仇，使得d ( v 8 一i ) d ( v k ) ，这里 i + 1 后s i 一1 并由归纳假设可得d ( 一1 ) d ( v s + 1 一) 利用引理3 2 2 知， 存在p = t 一讯一1 u i 口一v a 一 0 8 + 1 一 + 饥一l 仇一i + + 1 一 o k ，p 兀，并且当o t 1 或 o t x a ( t ) 这与t 的选取矛盾所以我们可以认为c z ( v 。一i ) c l ( v k ) ， 这里i + 1 k s i 一1 证明完毕 由引理3 3 4 可马上得到下述推论 推论3 3 5 设t 瓦是广义和连通指标在o t l 或o t 0 时的一棵极大树， 则我们总可以认为： ( i ) 树t 的中心，的度必满足d ( 7 ) = d l ； ( i i ) 树t 中所有悬挂点与r 的距离之差至多为l ； ( i i i ) 如果有两点s ，t 满足出( r ，s ) l 或q 1 或q o 时和连通指标最大的树记v ( r ) = u 1 ，) 使得对 于i 歹有d ( v i ) a ( v j ) 令y ( ) = 扣：d r ( v ，御1 ) = i ) ，这里i = 0 ，p + 1 且 y ( t ) = u 喾y ( 扪记8 i = i y ( ) i ，i = l ，p + 1 1 r 第三章给定度序列的树的广义和连通指标 我们用递归法对y ( t ) 的点重新标号对于y ( o ) 中的点v l ，将u 1 标号成v 0 1 并将此点作为t 的根对于v ( 1 ) 中的点，也即v 1 的所有邻点，将其重新标号成 钉1 1 ，v l ，。，使得对于1 i j 8 1 ，d ( v u ) d ( v l j ) 成立从而8 1 = d ( v 0 1 ) 一般而言，假设y ( ) 中的所有点已被重新标号成v m ，仇a ，这里i = 1 ，t 现在我们来标号y ( 蚪1 ) 中的点既然丁是树，则8 t + 1 = l y t + 1 i = d ( v 1 ) + + d ( v t m ) 一8 t 因此，对于1 r 8 t ，我们把y ( 蚪1 ) 中的所有邻点重新标号成 v t + l ，d ( 仇1 ) + + d ( 仇，一1 ) 一( r 一1 ) + 1 ，v t + 1 ，d ( 仇1 + + d ( 饥，) 一r ，使得d ( v t + 1 ， ) d ( v t + 1 j ) ，这 里d ( v t l ) + + d ( v t , r _ 1 ) 一( r 一1 ) + 1 i j v t l + + d ( v ) 一r 这样我们就把v ( t ) = 皑y ( ) 中的所有点重新标号完从而，我们将 y ( r ) 的点定义了如下顺序： 仇七一 li f0 i j p + 1 o ri = ja n d1 k 1 或a 1 ，d m + 1 = = 如= 1 ，1 仇 1 或q d ( v k ) 对某个k 尉2 立，这里3 k s 一3 令t 2 = 于一v k - 1 v 七一y s - 1 一2 + 仇一l v s 一2 + v k v s 一1 ，n x q ( t 2 ) x a ( t ) 因此我们可以认为d h 一2 ) d ( ) ，这里 3 s 一3 假设定理对小于i 的整数成立如果i 3 是奇数，假设d ( 饥) 1 或q 1 ， 如+ 1 = = 厶= 1 ，1 m l 或口 1 或q 1 或q 1 或q o 时的 四种不同构的极大树 所以极图唯一的充分必要条件还有待进一步探索 2 3 湖北大学硕士学位论文 因此我们提出以下问题： 问题1 找到给定度序列的单圈图的( 广义) r a n d i 指标最大时的极图唯一的充 分必要条件 问题2 找到给定度序列的树的广义和连通指标最大与最小分别对应的极图 唯一的充分必要条件 问题3 找到给定度序列的单圈图( 广义) r a n d i d 指标最小的极图 图4 四种度序列为丌0 的不同构的极大树 2 4 参考文献 参考文献 【1 】b o l l o b f i sb a n de r d 6 se g r a p h so fe x t r e m a lw e i g h t s j a r sc o m b i n ，1 9 9 8 ，5 0 ： 2 2 5 2 3 3 【2 】b o n d yj a a n dm u r t yu s r g r a p ht h e o r yw i t ha p p l i c a t i o n s