（计算机软件与理论专业论文）组合化学中树的拓扑指数逆问题研究.pdf

山东大学硕士学位论文 摘要 组合化学理论在制药和分子合成领域起重要的指导作用，其最核心的问 题之一是寻找具有给定化学或物理性质的分子结构。分子拓扑指数可以反映 特定分子结构的化学和物理特性，因而寻找所需分子的过程就是根据给定的 分子拓扑指数，建立对应的分子图，然后在已有分子库中进行搜索，选择符 合分子图结构要求且能够合成的结构进行合成的过程，即分子拓扑指数的逆 问题。它对有目的地合成药物等组合分子有重要的理论指导意义。 本文概述了几种常用拓扑指数的基本概念，深入分析了关于w i e n e r 指数 的树s p l i t s 重构问题，改进了其算法过程，提出了运算中数掘筛选的三定 理，进行了程序验证，然后研究了关于盯指数的逆问题，给出了解决算法， 进行了程序验证。 关键词：w i e n e r 指数d 指数逆问题s p l i t s 重构 山东大学硕士学位论文 a b s t r a c t c o m b i n a t o r i a lc h e m i s t r yi sa ni m p o r t a n tg u i d a n c ei nt h ef i e l do fd r u g d i s c o v e r yo rm o l e c u l es y n t h e s i s ，w h i c ho ft h em o s tc r i t i c a lp r o b l e mi st of i n dt h e m o l e c u l ew i t hg i v e nc h e m i c a lo rp h y s i c a lp r o p e r t i e s s i n c et h et o p o l o g i c a l i n d i c e sc a nr e f l e c tt h ec h e m i c a lo rp h y s i c a lp r o p e r t i e so fm o l e c u l e s t h ep r o c e s s o fs e a r c ht h en e e d e dm o l e c u l ei st ob u i l dt h ep r o p e rm o l e c u l eg r a p h sw i t hg i v e n t o p o l o g i c a li n d e x t os e a r c hi nt h ed a t a b a s eo f m o l e c u l e sa n dc h o o s et h em o l e c u l e s t r u c t u r ec o r r e s p o n d i n gt ot h em o l e c u l eg r a p h st h a tc a nb es y n t h e s i z e d t h a ti s c a l l e dt h ei n v e r s ep r o b l e mo ft o p o l o g i c a li n d i c e s ，w h i c hp l a y si m p o r t a n tr o l ef o r d r u gd i s c o v e r y o rm o l e c u l es y n t h e s i s t h ep a p e ri n t r o d u c e st h ed e f i n i t i o n so fs e v e r a lf a m i l i a rt o p o l o g i c a li n d i c e s f i r s t l y , s e c o n d l ya n a l y z e si n t e n s i v e l yt h es p l i t sr e c o n s t r u c t i o np r o b l e ma b o u t w i e n e ri n d e x ，i m p r o v e st h ea l g o r i t h m ，b r i n gf o r w a r dt h r e et h e o r e m sa b o u tt h e d a t af i l t e ri nr u n n i n gt h ep r o g r a ma n dv e r i f i e st h e mb ye x a m p l e s t h e nr e s e a r c h e s t h ei n v e r s ep r o b l e mo f 盯i n d e xa n dp r e s e n tt h es o l u t i o na l g o r i t h ma n dv e r i t i e si t k e yw o r d s ：w i e n e ri n d e x ，oi n d e x ，t h e i n v e r s ep r o b l e m ，t h es p l j t s r e c o n s t r u c t i o n 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作毒签名：聋衄日 期：塑孟塑捆 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复e p f t = , t ：ni 乜子版，允n ：沦 文被查阅和借阅；本人授权山东大学可以将本学位论文的令部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：磅导师签名： 论文作者签名：理缓导师签名： 山东大学硕士学位论文 第一章绪论 1 1 拓扑指数的逆问题在组合化学中的应用 1 1 1 分子拓扑指数的概念 若用v 表示由n 个顶点v i , v 2 v 。所构成的集合，即v = v l 。v 2 v 。 ：用 e 表示m 条边e l , e 弘e 。的集合，即e = e l ，e 2 ，e 。 ：每条边e = ( ， ) ) 表示 顶点v ，和v ，之问的连线，则顶点集矿和边集构成了图g ( 矿，) 。i f 罔的这 个定义可以看到，在图中不计边的长度，形状和边之b j 的角度等几何性质， 其着重表达的是顶点及顶点问相互连通的关系，因此图g ( v ，) 所表达的足 图形的拓扑性质。一般的来说，图g ( v ，) 是由，r 个事物和它们之问的，j f l 联系所构成的一种系统的图表示【”i 。 分子是由若干原子组成的，任意两个原子之b j 可以形成化学键，世1 叮以 不成键，这是可以分辨的。如果用图中的每个节点来代表分子中的一个原r 。 每条边代表原子之制形成的化学键，这种图就叫分子图。分子图所表达的怂 分子的拓扑性质i j s l 。 的化合物。因为分子图可以表示虽然可以用分子图【2 9 i 来表达分- 的托扑 性质，但从本质来看，分子图是个非数值的对象，而分子的各种可以洲量 的性质，都是用数值来表示的。因此为了保证分子的拓扑性质与分子物坤的 和化学的等可测量的性质联系起来，就必须把分子图中所获得的信息转变为 一种能用数值表达的量。分子图的各种不变量就是能够起到这种作用的量， 也就是说，分子图的各种不变量不但可以定量的表达分子的结构，而且可以 用束分析相关分子的结构与性能之f b j 的关系；通常就把具有这种作用的分子 图的不变量称为分子拓扑指数。 i i 2 分子拓扑指数逆问题在组合化学中的应用 在组合化学( c o m b i n a t i o n a l c h e m i s t r y ) 领域内1 1 2 3 4 1 ，经常需要计算菜分了 图的拓扑指数值，从而估计相对应的分子的化学或者物理性质：而在这同时 也会遇到其逆问题，即需要合成具有某种特性分子的结构。分子的拓扑指数 可以统计地反应分子的物理或化学性质，因而我们可以利用图论中的相关方 山东大学硕士学位论文 法，构造出相应的分子图，使得这个分子图的拓扑指数值为某个具体的值或 者在某个值域内，这就是求某个给定分子图的拓扑指数值的逆问题 5 7 1 。 1 2 课题研究意义及国内外研究现状 组合化学是一项高效化合物筛选技术，最初应用在制药【2 1 1 和农用化学品 领域，目前又推广到基础化学品生产行业。而当今组合化学中最核心的问题 之一就是寻找具有某种特定化学或物理性质的分子，即分子拓扑指数逆问题 【6 8 9 1 为了得到所期望的分子，首先要得到这种分子的拓扑指数值，然后利 用计算机搜索，建立具有这种分子指数值的分子图的数掘库，最后在库中选 择最理想且能够合成的结构去合成它们。这一过程的关键是建立具有某拓扑 指数值的分子图的数掘库，而建立这个数掘库的日的就足耍解决某给定分r 图的拓扑指数值的逆问题。对此问题的深入研究对有目的地合成新的分f 结 构具有关键的指导作用，因此在制药1 2 7 i 等领域具有重要的娜沦价值羊膨川7 7 景。 国内外目前已经找到分子拓扑指数共计4 0 多种存医药等甜l 合化学领 域已经广泛应用。国外关于此问题研究起步较早，自1 9 4 7 年w i e n e rj 旨放提 出f m j 以后即展丌了深入研究，成果比较丰富；而国内相关研究力度干f i 对 j 5 j 可查文献资料也较少。本课题正是基于深入研究两个常用拓扑指数的逆问 题，分析其应用价值的目的而展丌的。 1 3 本论文的主要内容及研究方法 本文作者查阅了国内外大量相关研究资料，贯彻理论联系实际的原则。 以实际应用为目的，对已有的关于w i e n e r 指数和盯指数的树重构算法进行了 归纳分析，对其进行了改进，阐述了改进算法的理论基础，并进行了实例验 证，分析了其应用价值。论文主要内容编排如下： 第一章描述了课题研究背景及意义，说明了拓扑指数及其逆问题的基本 概念以及其在组合化学领域的用途。 第二章概要介绍了几个常用的拓扑指数w i e n e r 指数、盯指数、f 指数和 z a g r e b 指数的基本概念，描述了其若干性质。 第三章深入分析了关于w i e n e r 指数的树s p l i t s 重构问题，提出了改进 2 山东大学硕士学位论文 型树的s p l i t s 重构算法，阐述了其理论依据，并进行了实例验证。 第四章着重描述了关于疗指数的逆问题，分析并改进了重构具有给定盯 指数的树的搜索算法，进行了实例验证。 第五章对论文的工作做了总结，并对进一步工作提出建议。 山东大学硕士学位论文 第二章组合化学中的几个拓扑指数 在组合化学领域，拓扑指数在寻找符合某种条件的化学结构式过程i ，受 到广泛应用。拓扑指数可以反映出组合化学分子结构的某些化学和物理特 性，利用拓扑指数，将化学中分子的结构映射为特定结构的图，从而可以利 用图的相关理论对分子结构的特征进行研究。 本章中概要介绍常用的w i e n e r 指数1 0 1 、盯指数i 、c 指数【j2 1 8 1z u g m h 指数【1 3 1 的基本概念，说明其基本性质。 2 1w i e n e r 指数 w i e n e r 指数是目i j 化学界公认的第一个分子拓扑指数，它足化学家 h 晰e 打e r 于1 9 4 7 年提出束的。0 1 。w i e n e r 指数是建立在分子图上j j 扑距离的 不变性的基础上的。w i e n e r 拓扑指数提出后得到了广泛的研究2 3 _ 1 霸l 应川。 在目前已有的4 0 多利，指数中，w i e n e r 拓扑指数仍是其中最重要的一种。 2 1 1 w i e n e r 指数的定义 设图g = ( v ，) ，其中v 是其节点集，e 是其所有边f i 勺集合，| i l i j j e1 4 t e n e t 指数定义为所有点到点之间的路径长度和i ，表示为： w ( g ) = t j c v d “( ，) ( 2 1 ) 组合化学中，常将多个图g f g 2 g t 按线性方式排列，连接其旗 点构成一个新的图g ，以此来表示特定的化学分子结构。定义幽序列g t g 2 ，g k 中的某个图的基点为根节点v ，则图g 是以v 为根的一棵树。按 照图的w i e n e r 指数定义，则树弘( 矿，e ) 的w i e n e r 指数表示为： w ( r ) = t , 2 c v d 如，) ( 2 2 ) 2 1 2w i e n e r 指数的性质 图和树的w i e n e r 指数具备以下基本性质： 引理2 1 2 1 1 i 对于任意一个直径为2 的图g = ( 矿，) ，其w i e n e r 指效 山东大学硕士学位论文 为w ，添加边e 芒e 到图g 中，得到图g = o ，u k ) 的w i e n e r 指数为w = w ，一l 。 证明：令p = n ，) ，f 厶口仨e ，则有矾j ( 一，0 ) = 1 成立，又因为图g 的直径为2 ，所以有比( v ，v ，) = 2 ，在添加边的过程中，其余节点之i n 的距离 没有变化，所以w = w l 成立，命题得证。 引理2 1 2 2 1 1 4 i 对于任意正整数w 2 , 5 ，存在图g ，其w i e n e r 指数 w ( g ) = w 证明：令g o = s 是节点数为n 的星，则g d 的直径为2 并且其w i e n e r 指 数为： w ( g 口) = ( ，一1 ) + 2 ( 仃- 2 ) + 2 ( ，一3 ) + + 2 【疗一( 行一1 ) 】= 2 【( ”一1 ) + ( 行2 ) + + l 】( 打一1 ) = ( ，一1 ) 。 向图g 0 中添加一条边得到图g i ，则g l 的直径为2 或抒g ，足究伞罔局。 由引理2 1 2 1 可得。 w ( g o = w ( g o ) - l 若图g l 不是完全图托，则可以重复上述过程直到图g i 是完全阉，j e w i e n e r 指数为： w ( 如) = n ( n 1 ) 2 因为在任意一步均保证w ( g ) = w ( g k i ) 一l 成立，所以对丁k 个 5 点的i j 纠 g t ，其w i e n e r 指数的取值区日j 为厶= 【月( 行一1 ) 2 ，( 盯一i ) 2 】。当n = 1 2 ，3 和4 时，厶分别为0 、l 、【3 ，4 】和【6 ，9 1 。当庀4 时，对于w ，存在w ( g ) = w ： 而对于w = l 、3 和4 ，存在路p 2 ，完全图肠和路p 3 的w i e n e r 指数与之对应。 对于具有1 1 个节点的图g 而言，显然完全图心的w i e n e r 指数最小而路p 。 的w i e n e r 指数最大，而w ( p 2 ) = l ，w ( k 3 ) = 3 。 综上所述，不存在w i e n e r 指数w = 2 或5 的图，而对于任意萨整数w 2 5 ， 存在图g ，其w i e n e r 指数w ( g ) = w 成立，命题得证。 引理2 1 2 3 ie = ( v i ，”2 ) 是树弘( 矿，d 的一条边，去掉e 得到树乃= ( n ， ，) 和树乃= ( v 2 ，e j ) 。设树r 和n 均以v ，节点为根，树乃以1 2 节点为根，n 表示树的节点数目，表示树中的所有节点到根节点的路径长度和，w 表示树 山东大学硕士学位论文 的w i e n e r 指数，则： w ( r ) = w ( 互) + w ( 疋) + ，( 互) 疗( 疋) + ，( 疋) ”( 五) + ( 正) ( 瓦) 【2 3 ) 证明：因为丁，和乃由r 分解所得，根掘w i e n e r 指数的定义何： w ( r ) = d ( u ，v ) = d ( “，v ) + d ( “，v ) + d ( “，v ) = w ( 瓦) 十w ( 疋) + 【d ( “，v 1 ) + 1 + d ( v ，v 2 ) 】 _ f 无v e t = w ( 五) + w ( 瓦) + ，( 王) h ( 疋) + ，( 疋) ，( 正) + h ( 正) ”( 瓦) 命题得证。 引理2 1 2 4 t 1 4 1 对于k 叉树r = ( n ) ，假设l = ( n ，e ，) 是t 从根生长出 柬的k 个子树，盯表示树的节点数目，表示树中所有节点到根节点的路径k 度和，w 表示树的w i e n e r 指数，则： w ( 7 ) = ( w ( r ) + 旧) + ”( r ) ) + ，( f ) ( 1 ) + 2 疗( r ) ”( 1 ) ( 2 4 ) ， ，i i i 证明：对于k 叉树丁= ( 矿，e ) ，设其根节点，从l ， 分解成k 个了树l 则根据w i e n e r 指数定义可以得到： ”，( 7 ) = ( _ ，v ，) = j ( 一，v 。) + d ( ”+ k ) + ，( ，j v ，) q ，t ， ，e ，v , e l ，q ，e 1 ，- ， = ( ”r ) + ，( z ) + ( r ) ) + ，( z ) 盯( ) + 2 胛( 一) 押( 1 ) ， ，- ji 0 个节点的完全图g = k o 一，根据盯指数的定义， 显然其盯指数等于节点数目加空集个数1 ，即等于以而盯( ) = 1 ，妒为空集。 因而命题得证。 引理2 2 2 3 j 把在所有具有圩个节点的图中，完全图匕是唯一的口指数 最小的图，而星k i , n - i 是唯一的盯指数最大的图。 证明：按照盯指数的定义，显然对于行个节点的图来说，其仃指数值爷 少为n + l ，因为其所有节点的独立集至少有w 个节点集和个空集。而完全 山东大学硕士学位论文 图的盯指数盯( k 。) = 刀+ l ，并且任意去掉其一条边，会出现一对不相关的 节点，则其1 7 指数值至少为n + 2 。所以完全图乜是唯一仃指数最小的图。下 面我们证明星k i ，i 是唯一的仃指数最大的图。 假设具有疗1 个节点的星在具有 1 个节点的图中唯一具有最人口指数 成立，另设具有r 个节点的图g ，其仃指数为所有r 个节点的图中最大的一 个因为图的盯指数必小于等于其生成树的o - 指数。所以图g 是一棵树。从 树g 上摘下一个叶子节点，而v 是“的唯一一个邻接点，则出引理2 2 2 1 、可得： 盯( g ) = 盯( g 一) + 盯( g 一“一v ) 图g 有，1 个节点。g ”v 有月2 个节点。根据假设，玎( g ) 耍达到最大值， 当且仅当g ，为星而g ，v 是月一2 个孤立点；则满足此条件的g 必然足星。 从而星局卜i 是唯一的盯指数最大的图成立。 引理2 2 2 4 1 1 2 1 在所有具有，f 个节点的树中，星k i j 卜l 是唯一的仃指数最 大的树，路p 。是唯一的盯指数最小的树。 证明：根据引理2 2 2 3 ，星k i ，i 是唯一的盯指数最人的图成立，则丝 k i 。i 是唯一的盯指数最大的树办成立。 假设具有n - 1 个节点的路p 剃在具有卅1 个节点的树中唯一具有最小盯 指数成立，设 个节点的树r ，摘下一个叶子节点玑而v 是“的唯一的邻 接点，则由引理2 2 2 1 可得： 仃仃) = a ( t 一”) + 盯p 一一v ) 仃仃) 要达到最小值，a ( t 一”) 和盯仃一“一v ) 必须同时达到最小值。根掘假设， 则正“和t - u v 同时为路，则此时7 为路。从而证明了路p 。足唯一的仃指数 最小的树。 作为盯指数的补的c 指数，其基本性质与仃指数类似。 引理2 2 2 5 1 2 对于任意自然数c 3 ，5 ，7 ，存在图g ，其c 指数f ( g ) = c 。 证明：根据c 指数的定义，易求得c ( ) = l 、c ( 只) = 2 、c ( b ) = 4 和c ( 只) = 6 ； 而对于c = 2 t ( t 4 ) ，存在k 个节点的星，c 仅一。) = c ：对于c = 2 k + 1 以4 ) 山东大学硕士学位论文 存在c ( g ) = c 下面证明不存在c 指数为3 、5 和7 的图。 根掘c 指数的定义，图的c 指数是随图的边和节点数的增加而增加的。 存在c 乜) = 8 和c ( 只) = 8 ；从图c 3 中去掉一条边，得到的图的c 指数为6 ； 而从j p 。中去掉一个节点得到的图的c 指数值也为6 ；按照这种方法，可以证 明无法构造c 指数为3 、5 和7 的图。 综上则命题得证。 引理2 2 2 6 1 1 2 i 在所有具有珂个节点的图中，完全图是唯一c 指数最 大的图，而只有树a 可能具有最小c 指数。 证明：根掘c 指数定义，节点数疗确定的情况下，显然f 指数的大小随 边e 的数目增加而增加。对于节点数r l 的图，完全图厩，存最多的边，所以完 全图是唯一c 指数最大的图成立；而边p 最小的图必然为树，所有只有 树j 可能具有最小c 指数成立。命题得证。 2 3z a g r e b 指数 2 3 1z a g r e b 指数的定义 z a g r e b 拓扑指数定义为z i ( g ) = 吐2 或者是乃倒= d ，d ，j l l l l 以 t d )：”ej ，“j j 为顶点聊的度数，z a g r e b 指数与分子的能量【3 i 以及与分子罔的匹眦多项- i = | ，| q 系数有关。 2 3 2z a g r e b 指数的性质 引理2 3 2 1 1 u i ：对于任意的简单连通图g ，z i ( g ) 是偶数。 证明：因为在图g 中，度数为奇数的点的个数为偶数，所以在矾2 。 以2 ，磊2 中有偶数个奇数，显然z i ( g ) = 砰为偶数。 t t i h 一 引理2 3 2 2 1 2 l ；除4 和8 外，对于任意偶数z 都存在简单连通图g ， 使得z l ( g ) = z 。 推论：除4 和8 外，对于任意偶数z 都存在树n 使得z l ( 乃= z 。 证明：对于任意树r l ，乃，满足z i ( t o = 4 k + 2 ，z i ( 乃) = 4 。在n ，乃的 基础上增加一个节点，并于叶子节点相邻。我们就可以得到树7 ，满足 z l ( 7 ) = 4 k + 2 或z i ( 乃= 4 k 。 山东大学硕士学位论文 引理2 3 2 3 1 3 0j ：设g 是一个有月个顶点的简单连通图，则 ( 1 ) z ( g ) 4 n 一6 ，疗2 ，当且仅当g 是n 个项点的路时等号成立。 ( 2 ) z ，( g ) n ( n 1 ) 2 ，当且仅当g 是n 个顶点的完全图时成立。 2 4 小结 在组合化学领域，拓扑指数对于寻找符合某种条件的化学结构式有重要 意义，可以反映出组合化学分子结构的某些化学和物理特性。而算法领域， 利用拓扑指数可以标明树图的某些结构特点，从而与特定的化学结构，建口 沟通关系。本章着重介绍了常用的w i e n e r 指数、仃指数、c 指数和z a g r e b 指 数的基本概念，并相应阐述了其若干性质。 0 山东大学硕士学位论文 第三章关于w i e n e r 指数的树s p l i t s 重构问题 树的卵，峦重构问题是w i e n e r 拓扑指数逆问题的一个子问题。第二章 中已经介绍了w i e n e r 指数的基本概念和性质，本章将详细介绍树的s p l i t s 重构问题，深入分析并改进了其解决算法，并用实例验证算法的有效性。 3 1 树的s p l i t s 重构问题的提出 定义3 1 ：设树及v ，e ) 有n 个定点，对于树r 的任意一条边ee e 把7 分为两棵子树乃和n ，用s 俐来表示边e 的片( s p l i t s ) ，s ( f ) 的值为子树n 乃中节点数较少的那一棵子树的节点数。用，( p ) 表示边e 的负载( l o a d s ) t 其 数学表达式为“p ) = j ( 口) x ( 行s ( p ) ) ，即，似为树t 中包含边e 的所行路的数| 。 由此我们可以重新定义树的w i e n e r 指数为： w ( t ) = 。，( e ) 由此，树的w i e n e r 拓扑指数的逆问题就转化为构造树的n i 条路。儿使 它们的和等于给定的w i e n e r 指数值。 文献【1 4 】已经证明，用给定的一组s p l i t s 值来重构一棵树，即树的卵，蕊 重构问题，是n p c 问题【。9 1 。 3 2 树的s p l i t s 重构算法 3 2 1 穷举算法 树的s p l i t s 重构穷举算法是在文献【1 4 】中提出的，其描述如下： 算法3 1 ：设给定的一组s p l i t s 值为j l 之s 2 兰芝s n i ： 首先构造一棵树，它有唯一的一个节点i t 0 ，且这个节点的权值w e l ( v o ) 5 疗，每次在这个树上插入一个叶子节点，直到这棵树有n 个节点，且每个节 点的权值为l 。 在第k 步： 在已构建的树上找到一个节点，使其满足w e i ( v ，) 之以。在节点卜加 入一个新的叶子节点v 女，使得w e l ( v k ) = s k ，且w e i ( v ，) = w e l ( v i ) s k 。 山东大学硕士学位论文 根据算法3 1 描述，其执行流程如图3 - 1 所示，我们编制了运算程序， 见附录l 。算法执行过程中我们发现，对于任意一个实例，回溯都是发生侄 连续插入具有相同权值的节点的时候，即对于给定序列s i 之印之 以2 轧， 兰芝卸+ 靴+ ，之s n - l ，其中以；“+ ，= = 乩+ n ，j ，当我们连续插入，个 权值等于而的节点的时候，力有可能发生回溯。 幽3 - i 树的s p l i t s 重构穷举算法流种幽 打j l 贫恫 3 2 2 最小值插入法 通过对大量实例的反复研究，我们发现穷举算法3 1 在执行过程中，插 山东大学硕士学位论文 入节点时如果选择满足条件且具有最小权值的节点作为插入点，可以有效减 少回溯。因而我们可以得出改进型算法如下： 算法3 2 ：设给定的一组s p l i t s 值为j l 三如兰之s n - l ： 首先构造一棵树，它有唯一的一个节点，且这个节点的权值w e i ( v o ) = ， 每次在这个树上插3 - - 个叶子节点，直到这棵树有玎个节点，且每个节点的 权值为1 。 在第k 步： ( 1 ) 在树上找到一个节点v ，使其满足w e i ( v i ) 之s k ，且对于任意一个节 点 ：，( w e l ( v j ) 之s k ) ，都有w e i ( v j ) 芝w e i ( v ，) ( 2 ) 在节点v ，上加入一个新的叶子节点v t ，使得w e i ( v j ) = “，f lw e i o ，) = w e l ( v i l - s k 。 执行流程图如图3 2 所示。 i ，望雪所彳节点舒已抽入 各节点枉值为i 址齿c 发牛 n o ，i u j 溯 所自心溯 l y 嚣，则为尚定实例 l y 髂则为青定实例 豳3 - 2 树的s p l i t s 重构最小值插入算法流群幽 山东大学硕士学位论文 1 问题：如果s l 芝s 2 芝2s 川是s p l i t s 问题的一个回答为y e s 的实例， 那么如何证明算法3 2 可以有效的减少回溯呢? 分析：已知整数序列s i 芝s 2 芝2s 是s p l i t s 问题的一个回答为y e s 的实例，则一定存在一个有效的构建树的过程q ，且在这个构建过程中没有 任何的回溯发生，另设办，。表示最小值插入法构建树的过程。 ( 1 ) 当k = l 时，过程q 和q 。是相同的。h 首先建立一棵树它仃惟 的节点v o ，且w e “v o ) = 疗。然后在v d 上插入一个叶子节点v ，使得w e i ( v ，) = s i ， w e i ( v o ) = ，f - j l 。过程q 和q 胁所建成的树是完全一致的。 ( 2 ) 假设算法执行完第k - z ( k 兰2 ) 步时，过程q 和“，。所建成的树足完 全相同的，且设已建成的树中的节点按权值由人到小的排列顺j 手为，o ，v ，一 v 。，v ，- ，接下来执行第k 步，即需要在已建成的这女个节点上 加入一个新的叶子节点v i ，且使w e i ( v ) zs t 。 因为s i 之s 2 2s 州是s p l i t s 问题的一个回答为y e s 的实例，所以l j ， 设f 饱以v ，) s t 兰陟z ，( + i ) ，则过程q 。在插入1 ，点1 ， j 7 , 所形成的 ，j i i f 卜，u 为： v 毛m =v o v i ，v m ，v ，t h ，h ； 其中删( v j ) = w e l ( v ，) 以。 对于过程q 我们可设v 插入到节点v 。h ，成为、，。的一个叶予节点， 设这个过程所形成的节点序列为： v o ，v ， v * ，v ，v t ，v k ； 兵中w e i ( vm ) 2 形e “) 轧，且w e i ( v 。) 三w e i ( v ，) 。 设序列v 。和v ：中具有不同权值的书点集合分别为v 。，和v ：i ，! i | l j 在第k 步结束后，v 。和v ：中最多有两个节点的权值可能会不同即： v ：m ：v 。，v ： v ：v l ，v t ； 显然有m a x v ve v 兰。 三m a x v v v ：) 。 下面我们进一步讨论第k + 1 个节点的插入过程，即在树中插入权值为以， 叶子节点。根掘上面的讨论，因为过程a 可以继续，所以过平口q 。一定可以 山东大学硕士学位论文 继续，且在第t + l 步不会发生回溯。 算法执行第k + l 步，插入节点v 川，其权值w e l ( v k + ，) = “+ 1 茎w e i ( v _ ) t 节点v 川只能插入到权值大于s 川的节点上。 对于过程q ，设节点v 川插入到节点上，成为的一个叶子节点 插入完成后，记v p 为v ：。 对于过程q ，设节点h + i 插入到节点v q 上，成为v q 的一个叶子节点插 入完成后，记v g 为v9 。 则过程q 和过程q 。所形成的节点序列中权值可能会不同的节点集合 为： v 掣：v 。，v ，v j ，； v f ：v ，v - ，印，v ；： 根掘节点v p 和v q 取值不同，我们分三种情况进行讨论。 ( a ) 若节点v p 与节点不是同一个节点，而节点为满足条件的任意一 个节点，显然有： m a x v v v ：? ) 之m a x v v v ：“” ： 由此可以保证只要过程q 可以执行，过程q 。必定可执行。 ( b ) 若节点印即是节点v 。，而节点为除v m 外的满足条件的任意一个 节点，则过程q 和过程幽，。中具有不同权值的节点集合可以表示为： v = ：v j ，v ? ，v 。： v ：v _ ，v ，v ； 其中眦“v ：) = w e i ( v 。) - s k + l ； w e l ( v ，) = w e i ( v ，) s k ； 眦“v 。) = w e i ( v 。) 轧； w e z ( v q ) = w e l ( v q ) 以+ i ： ：。s t + is5 t ，w e ( v m ) w e i ( v ，) ，w e i ( v q ) 兰w e i ( v m ) ； m a x v v - - 。o “, ) 芝删 饥e v ：“” 显然成立，可以保证只要过程q 可以执行，过程q 必定可执行。 山东大学硕士学位论文 ( c ) 若节点即是节点，而节点”g 为节点v 。，则过程q 和过程q 。 中具有不同权值的节点集合可以表示为： v 掣：v ，v j ； v ，v j ； 其中删( vp ) = 眦“v m ) 一s 川： w e i ( v ，) = w e i ( v ，) 一s k ； w e i ( v4 ) = 形趴) - “s k + i ： 算法执行第胁2 步时： ? 乳+ 2 ss i 且w e i ( vp ) = w e g v 。) s i s k + 2 ； 权值为“+ 2 的节点一定可以插入到树中，但是不能保证m a x v a v ，o - ( 疗一k ) 2 ： 则由已知s t + ，s 乳，有： ( 珂k ) 2 ( k ) 2 不成立；当i = k + l 时，不等式“+ l 三 ( n + 1 ( k + 1 ) ) 2 = ( 行一k ) 2 成立。 综上所述，若s i 兰s 2 2 j 川是树的s p l i t s 重构问题的一个回答为y e s 的实例，则对任意一个s j ，均满足岛s ( n + l 一0 2 ，命题得证。 应用定理3 3 1 ，我们发现可以迅速判断给定的s p l i t s 整数序列是否具箭 可以重构一棵树的基本条件，从而大大提高了重构算法的执行效率，节省了 运行时间。经过实例程序检验。其效果显著。 定理3 3 2 设s l 芝占2 之芝妇兰s “i 之2s k + ( ，i 】 “+ i 之s n i 是树的 s p l i t s 重构问题的一个实例，其中“= s 川= - - - - $ k + i ) ，( i 之2 ) 。即虬t 山东大学硕士学位论文 s 川，s k + h - i ) 是序列中连续f 个相等的整数。若行t s k + ，之j 。小算法执行j ：l j 讹 t 步的时候，设已经成功构建了树死，它有k 个节点v o ，v ，小接卜 来我们讨论是否能在树死中连续插入i 个权值相等的叶子节点 ， ， 小， v h 1 且它们的权值均等于乳。 若不能插入，则对于这个实例的回答为n o 。 假设插入成功，则设构建得到的树为死+ ，它有k + i 个节点：，o ，v i ， 巩1 ，v k + i ，v k + 1 1 ： t + t - i 且w e i ( v ，) = 月： j - o 又因为w e i ( v , ) = w e i ( v k + i ) = = w e i ( v k + 卜1 ) = 3 k ，所以有： k - ! w e i ( v ，) + 帆= h ： = o ( 3 3 ) 而对任意函。满足w e l ( s ，) 三l ； 因而一定有盯i “2k 成立。 综上所述，若，k i s t ，则一定不能插入这k 个节点，即这个实例的 答一定是加，命题得证。 定理3 3 3 若s l 兰s 2 芝芝s n i 是树的s p l i t s 重构问题的一个回答为y e s 的实例，则这疗，1 个整数中任意一个值不为l 的整数出现的次数一定不大j 二 整数l 出现的次数。 证明：设根据实例给定整数序列j l 之s 2 兰2s 川成功构建了树n 其根 节点为v o ，设序列s l ，s 2 ，j 中有m 个数的数值为l 。由构建树的基 本过程知，这m 1 个整数l 对应树r 中全部的肘1 个叶子节点。 因为树中任意两个节点之间的路是唯一的，所以m 1 个叶子节点到根节 山东大学硕士学位论文 点之例构成了m 条路，设这肘l 条路为三i ，l 2 ， 九。而树7 即可以理 解为是由这m l 条路构成的。 由树的构建过程知，若s k = 以+ l 。则由它们所构建的树的两个节点、， ， v k + 不可能位于同一条路厶上。 设序列j i 三s 2 兰三s n 1 中整数乳出现了肘次，则这m 个以对应r 树r 中的肘个节点，而且这肘个节点一定位于m 条不同的路，上：即一定 有m 曼m i ，命题得证。 定理3 3 3 同样在树构建之i i i f 可以剔除大量不符合条件的s p i t s 整数序 列，提高算法执行效率，其效果经过实例程序验证。 3 , 4 小结 w i e n e r 拓扑指数是最重要的分子拓扑指数之一，奉章着藕分析了j 逆 题的一个子问题一一卵，播重构问题。文献【1 4 i l j 卵，冰呕构址 ，( 。n d 题，本章在其基础上对此做了深入研究，对其提出的穷举算法进行了改进， 提出了可以有效减少回溯的最小值插入算法，并对其进行了分析然后又n ： 证明了关于数掘筛选的三个定理，经过实例程序验证，火i j 垃小值插入 泄： 和数掘筛选三定理均行之有效，能够火幅度提高算法的执j j 效；社，竹竹f l i ： 运行时问。 山东大学硕士学位论文 第四章关于。指数的树重构问题 盯指数也是组合化学中常用的拓扑指数之一，已经证明它与化学物质的 沸点有密切的关系。在第二章中已经介绍了盯指数的基本概念和性质，本章 中将说明树的盯指数计算算法，并着重分析和改进了关于仃指数的树重构算 法。 4 1 树的盯指数计算 引理4 1 1 1 1 2 i 给定树t - - ( v ，) ，节点v v ，v i ，v 2 ，叱是v 的予节点， 设r 是树r 以v 为根节点的子树，是树r 的盯指数，巩= 仃- 盯k 仃：楚r 中不含节点v 的独立节点集的个数。则有： 1 ) 仃。= 盯，+ 仃，仃：仃 ( 4 1 ) 2 ) 仃= 仃盯o 仃1 ( 4 2 证明：巩表示r 中不含节点v 的独立节点集的个数，盯。( i = 1 2 女) 表 示以e 为根节点的r 的子树中独立节点集的个数，则盯盯k 仃。= o - i 辊然成 立。 盯盯。盯。表示不含节点v i ，v ：，吨的独立节点集的个数，必为 v 1 ，v 2 ，叱是v 的子节点，即v i ，”2 ，v 与v 是相关联的，所以0 1 1 盯q 仃。表 示了r 中含节点v 的独立节点集的个数。 ，是树r 的仃指数，综上则有盯”= 盯，+ 盯1 盯，盯成立，命题得雕 根掘引理4 1 1 ，可以设计算法如下计算树的仃指数： 算法4 1 ： ( 1 ) 初始化树l 根节点为，： ( 2 ) 按照式( 4 一1 ) 和( 4 2 ) ，自叶子节点丌始，由底向上计算节点v 的盯和 山东大学硕士学位论文 巩，直到根节点，为止，则树的盯指数“d = ，。 文献【1 2 】已经证明，该算法运行时i a j 为0 ( ) 。图4 - l 表示了一棵树的盯 指数计算过程，其中叶子节点的矿值为2 ，仉值为l ，按照算法4 1 依次汁卯： 得到了这棵树的盯指数为2 0 6 。 2 l 笙i4 i 树的口指数计算过榉 4 2 树的仃指数逆问题 4 2 1 判定逆问题 7 设任意一棵树7 对应一个三元组( ”，以，) ，其中r 为树r 的根缸点，矿 是树，的仃指数，西是r 中不含根节点，的独立节点集的个数。 文献【1 2 中对树的盯拓扑指数进行了分析，证明了以下定理： 引理4 2 1 ：设树乃，乃的根节点分别为和v ，且树乃，乃分别对应三 元组( ”l ，o u ，矿) 和( 2 ，西，一) 。如果树r 是由在树7 1 ，乃的根节点，v l ： 添加一条边而构成的新树。则对于树r 有： ( i ) i 收乃f = h i + 2 ： ( 2 ) 仃，( 7 3 = 西o - ，“( d = 乳，； ( 3 ) 矿( 乃= 巩矿+ ( 矿- t r y ) “，g u ( 乃= 巩，+ ( 矿一t t u ) t t v 根据引理4 2 1 ，可以得到树的。拓扑指数逆问题的一个算法。下1 月j 汀 先来分析下面的两个问题。 问题一：对于任意三元组m ，西，) ，是否存在一棵以r 为根节点n 勺树n 树的节点数为行，盯指数为d ，且树中不包含根节点的独立集合数为o r ? 分析：经研究发现，对于一个节点的树而言，其盯指数在树的形状为星 山东大学硕士学位论文 形时达到最大值2 , , - t + l ；而在树的形状为一条路时达到最小值o ( p 。) ，而a ( p 。) 取值满足费波纳切数列，其中a ( p o ) = l ，a ( p i ) ；2 。所以可以得到疗，o r ， 之日j 的如下关系： ( 4 4 ) 根据引理4 2 1 的( 1 ) 、( 2 ) 和( 3 ) 式，我们可以将一组给定的( ”，西，) 值 拆分成( 疗l ，几，) 和( 疗2 ，巩，) ：而由式( 4 3 ) 、( 4 - 4 ) 可知