（计算机软件与理论专业论文）对树的wiener+index逆问题的研究.pdf

山东大学硕士学位论文 摘要 组合化学是近十几年逐渐发展并成熟起来的一门学科，它将化学合成、组 合理论、计算机辅助设计融于一体，在短时间内将不同构建模块经过连接形成 化合物库，再对库成分进行筛选优化，得到可能的有目标功能的化合物结构 通过计算机辅助设计可以极大提高库的组成并同时控制库的大小，因而计算机 技术正在组合化学中发挥着越来越大的作用 经过长期的研究，科学家们发现很多化合物的物理性质和化学性质与它们 的拓扑性质密切相关w i e n e ri n d e x 就是一个与化合物的物理化学性质密切相 关的拓扑系数，它的性质已经放广泛应用于组合化学领域中。树的w i e n e r i n d e x 逆问题是组合化学中的一个重要问题。g o l d m a n 于2 0 0 0 年提出的动态规划算法 虽然理论上可以解决此问题，但是算法的计算量很大，程序复杂性和运行速度 方面也不太理想。 本文首先对树的w i e n e ri n d e x 和其它一些拓扑系数的关系进行了分析，并 进一步利用这种关系对原算法进行了改进，极大地减小了原算法的搜索空间和 递归次数：在此算法基础上本文又对树的w i e n e ri n d e x 判定逆问题的算法做出 了改进，使其在计算量、程序复杂性和运行速度方面明显优于已有算法；最后 本文给出了一种新的解决树的w i e n e ri n d e x 构造逆问题的算法 关键词： 组合化学w i e n e ri n d e x 动态规划 山东大学硕士学位论文 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 sas c i e n t i f i c t e c h n o l o g yb e i n gd e v e l o p e d d r a m a t i c a l l yf o rm o r et h a nad e c a d e i tr e l a t e st r a d i t i o n a lc h e m i c a lc o m p o u n da n d c o m b i n a t i o nt h e o r yw i t l lc o m p u t e ra i d e dd e s i g ns ot h a tw ec a nc o x 、j l e c tv a r i o u s c o m p o n e o t st ob u i l dc o m p o u n dl i b r a r i e si nv e r ys h o r tt i m e t h e nw ec a l lc h o o s ea n d r e f i n ei n g r e d i e n t si nt h ec o m p o u n dl i b r a r yt oo b t a i nc o m p o u n d sw i t hd e s i r b l e f u n e t i o i l s w i t ht h eh e l po fc o m p u t e ra i d e dd e s i g n , w e 啪i n c r e a s et h eq u a l i t yo f c o m p o u n dl i b r a r i e sw h i l ec o n t r o lt h es i z eo f t h e m a sar e s u l t , c o m p u t e rs c i e n c ea r c p l a y i n ga ni m p o r t a n tr o l ei nc o m b i n a t o r i a lc h e m i s t r y a f t e rm a n yy e a r s r e s e a r c h , s c i e n t i s t sf o u n dt h a tt h e r ei sa v e r yc l o s er e l a t i o nb e c w - - nt h ep h y s i c a lc h a r a c t e r i s t i c s a n dc h e m i c a lc h a r a c t e r i s t i c so fm a n yc o m p o u n d sa n dt h et o p o l o g i c a lc h a r a c t e r i s t i c s o f t h e m w i e n e ri n d e xi ss u c h - i lt o p o l o g i c a li n d e xt h a th a sc l o s er e l a t i o nw i t ht h e p h y s i c a lc h a r a c t e r i s t i c sa n dc h e m i c a lc h a r a c t e r i s t i c so fm a n yc o m p o u n d sa n di t s c h a r a c t e r i s t i ch a sb e e na p p l i e dw i d e l yt om a n yf i e l d so fc o m b i n a t o r i a lc h e m i s t r y t h ei n v e r s ew i e n e ri n d e xp r o b l e mo fn 伪i sap r o b l e mo fg r e a ti m p o r t a n c ei n c o m b i n a t o r i a lc h e m i s t r y “ a l t h o u g ht h ed y n a m i cp r o g r a m m i n ga l g o r i t h mp r o p o s e db yg o l d m a ni n2 0 0 0 c a l ls o l v et h i sp r o b l e m , i t sp e r f o r m a n c ei ss t i l ln o tv e r ys a t i s f y i n g n o to n l yi st h e a l g o r i t h mv e r yc o m p u t a t i o n a l l ye x p e n s i v e ，b u tt h ec o m p l e x i t ya n ds p e e do fi ta r e a l s ov e r yd e m a n d i n g i nt h i sp a p e r ，i no r d e rt oi m p r o v et h ep e r f o r m a n c eo ft h i s a l g o r i t h i n ，w ef i r s ta n a l y z e dt h er e l a t i o nb c t w e e nw i e n e ri n d e xa n ds o m eo t h e r t o p o l o g i c a li n d e x e s ，b yv i r t u eo fw h i c hw em a d em a n yi m p r o v e m e n t st ot h i s a l g o r i t h m i na d d i t i o n , w er e f i n e dt h ea l g o r i t h md e s i g n e dt os o l v et h ed e c i s i o n v e r s i o no ft h ei n v e r s ew i e n e ri n d e xp r o b l e mo ft r e e s a sa r e s u l t , t h es e a r c hs p a c e a n dt h ea m o u n to fr e e u r s i o n so ft h en e wa l g o r i t h md e c l i n e de x p o n e n t i a l l y t h e r u n t i m ea n a l y s i ss h o w st h a tt h e r ei sad r a m a t i ci n c r e a s ei nt h es p e e do f t h ea l g o r i t h m w h i l et h ec o m p l e x i t yo fi td e c r e a s e sg r e a t l y f i n a l l y , w ep u tf o r w a r dan e w a l g o r i t h m 山东大学硕士学位论文 w h i c hc a l ls o l v et h ec o n s t r u c t i o nv e r s i o no ft h ei n v e r s ew i e n e ri n d e xp r o b l e mo f t r e e s k e yw o r d s ： c o m b i n a t o r i a lc h e m i s t r yw i e n e ri n d e x d y n a m i cp r o g r a m m i n g i i i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 一 ， 论文作者签名：盈氐丛生，日期：垄壁丛，日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：塑呻师签名： 牺期：辫 山东大学硕士学位论文 第一章绪论 1 1 组合化学的发展历史 组合化学是在近十几年逐渐发展并成熟起来的一个学科，其概念和技术已被 广泛地接受并用于科学研究的各个方面。( s c i c e ) 1 9 9 8 年把它列为科学研究 领域的九大突破之一在美国化学会最近组织的一次研讨会上，化学家们称之为 “2 l 世纪的化学合成” 组合化学与高通量筛选技术并驾齐驱，促成了新药开发领域的一次大的突破， 并且已经成为新药发现和优化过程中不可缺少的一项技术。近几年来，组合化学 的研究方法正逐渐用于新材料和新催化剂的研制，组合化学的概念及思维甚至被 推广到生物学研究中在绪论中我们将简要地就组合化学的起源与发展、研究方 法和其对相关学科的影响作一综述 1 1 1 组合化学的创立与发展 组合化学的创立与发展始于新药研究的需要自8 0 年代末期，随着分子生物 学研究的突破高通量筛选技术的发展，新药开发所需要的新分子实体的数 目越束越多，科学家们把注意力从寻找天然产物转入合成大数目的化合物群 一化学库。化学库是由诸多具有不同属性的有机化合物的组成的，组合化学就是 一种合成化学库的技术运用这项技术，不同系列的合成砌块一反应成分有 序地排列起来以组成大系列的多样化分子实体群。 组合化学是在固相合成多肽基础发展起来的一项快速合成新技术。从这个意 义上说，组合化学的奠基人应该是m e r d f i e l d ，因为他早在6 0 年代就发明了固相多 肽合成法并因此而得了诺贝尔奖【1 捌后来，固相合成被很有限地应用到小分子合 成上。 8 0 年代中期，g e y s c n 用九十六孔板在高分子笔上首次合成多肽成功，标志着 组合合成的丌始f 3 1 。此后，新的固相合成方法不断涌现出来，姗o u g h t e n 的茶叶袋 法“1 和f u r k a 的混合裂分合成法1 5 l 相继发表混合裂分合成法曾一度成为主流 为了确定混合物的成分，合成物密码标记和解密技术以及产物追踪技术也逐渐地 发展起来丌始时，组合化学局限于用固相方法合成多肽和多糖。后来，人们用其 山东大学硕士学位论文 合成多肽衍生物并逐渐应用到小分子合成上 到y 9 0 年代初，以合成小分子为主的平行单分子合成技术有了很大的发展。 并成为组合合成的主要技术组合化学合成从8 0 年代末开始应用在新药开发领 域。a 衔m “研究所作为第一家风险投资的组合化学公司出现在新兴的生物制药 公司中。a m m a ) c 的成功使用组合化学的风险投资进一步增加，至t j 9 0 年代前期 a r q u l e 和p h a r m a c o p e i a 成立时进入顶峰 9 0 年代后期，组合化学技术被进一步推广应用于新材料和新型催化剂的研 究日前，国外风险投资兴办的新的组合化学公司仍在兴起，以组合合成技术为主 体的制约公司和新材料研制公司仍是美国投资领域的热点之一。与工业应用相比。 组合化学在学术界的发展稍晚些尽管如此，美国各大学里都相继设立了组合化 学课程和研究课题。一些有影响的合成化学家，如斯坦福大学的p a u i w e n d e r 、 s c r i p p s 研究所的k c n i c o l a i 、哈佛大学的s t u a r ts c h r i e b c r 和加州大学伯克利分 校的p e t e rs h u r z 等先后加入组合化学研究。与此同时，美国大学里的一些年轻化 学家，如加州大学伯克利分校的j o ne l l m a n 和加州大学洛杉矶分校的r o b e r t a r m s t r o n g 等也以组合化学的研究成果而一举成名。 今天，组合化学的概念和思维已超越有机合成和药物合成的范畴并应用于科 学研究的各个领域它已不仅仅是一项工业技术，而且已发展成为一个新的学术 分支 1 1 2 组合化学的研究方法 组合化学经常被人们称为数字游戏，也就是如何排列众多的合成砌块的问 题。从理论上讲，组合合成的总反应产物数n 是由两个因素决定的，每一步的合成 砌块数目b 和合成的步骤数x 例如，对于一个三步的线性组合反应。如果每步的 反应物数目分别是b l 、b 2 和b 3 ，那么，理论上的总反应产物的数目是n = b lb 2 b 3 。组合化学研究的目标就是怎样有效地得到这一反应的所有产物n 组合合 成的另一研究目标是反应产物的结构多样化问题。实际上，这还是一个数字问题。 反应物的数目越多，反应组分越多，产物的数目越大，产物的结构也就越多样化。因 此，组合化学合成的根本问题就是怎样快速地得到更多的包罗万象的化合物。近 年来，从固相合成到快速液相平行合成。组合化学在合成方法上取得了突破性的进 展。到目| ；i 为止最常用的几种合成方法包括：1 混合裂分法；2 平行合成法； 山东大学硕士学位论文 3 多组分液相合成法；4 官能团转换法 6 t i l 1 1 3 组合化学对相关学科的影响 组合化学不仅成为新药发现与优化和新材料开发过程中的一项重要手段，而 且其概念和思维已经渗透到科学研究的其它领域。组合化学造成了合成化学家思 维上的突破，也相继带动了相关学科及技术方面的进步与更新。它对现代科学研究 的发展和技术的进步产生了深远的影响 i 化学合成思维上的突破 在经典有机合成中，最终产物是一个个地合成出来的因此，反应产物的分离 和纯度非常重要，人们寻求的是高产率、易分离的有机反应。另外，在药物化学合 成过程中，对化合物的纯度要求高。每一个化合物都要经过仔细地分离鉴定合成 化学家的大部分时日j 花在分离、提纯和鉴定上，然而。合成出来的绝大部分化合物 都是没有用的，研究效率非常低。组合化学把人们从原始合成的思路中解放出来， 着眼点已不再是每个产物的高纯度和定性，而是产物的数量和结构的多样性，这是 一个思维上的突破和生产力的极大提高 2 药物化学研究方法的革新 组合化学和快速筛选技术首先应用于新药发明组合化学技术为药物化学研 究带来了前所未有的快速合成方法组合化学用于合成供筛选用分子库。使新药 筛选不再依赖自然界提供的天然产物它被用在先导化合物的优化过程中，把科 学家们从一个一个的结构活性分析中解放出来。使多方位的结构活性研究成为可 能。因此新药开发的速度和效率获得了成倍的提高。 3 生物筛选的化合物来源 组合化学技术的建立使合成化学家第一次想到有意地设计合成供筛选用的 小分子化合物库，那种生物筛选靠天然产物和多年累积化学库的时代已成为历 史。这一技术曾一度使有些化学家达到头脑发热的程度。例如，9 0 年代初，有人曾 提出合成包罗万象的宇宙化学库的概念，试想从这一。宇宙库”中找到医治百病 的特效药。根据d o l l e 等的统计，1 9 9 2 1 9 9 7 年的文献中共列举了8 6 个合成化学 库【12 1 ，仅在1 9 9 8 年里就发表了7 4 个合成化学库【1 3 1 ，未发表的例子会更多。 4 自动化合成技术 组合化学发展的必然结果就是自动化合成仪器的研制。科学仪器的供应商们 山东大学硕士学位论文 纷纷涉足于这一市场如命多种全自动的合成仪已经问世这一商业领域的市 场大有增长的趋势，而且竞争会越来越强。 5 分离和鉴定技术的革新 组合合成的产物成千上万，甚至上亿，象经典有机合成那样一个一个的纯化分 离鉴定已不再可能这导致了分析化学技术的进步，以平行化的、小量的、甚至 微量的自动化快速分离为目标的分离鉴定技术被研制出来。新的以平行自动化操 作为基础的高压液相色谱分离技术相继问世色2 质联机、紫外与色谱联机、以 及更多种分析分离方法联用的自动化技术得到了广泛的开发应用。用于组合合成 提纯的新吸附材料也不断地被研制出来 6 计算机模拟技术和计算化学的应用 尽管组合合成追求的是数目，人们很快就发现要合成所有的化合物既不可能。 也没有必要最重要的是产品的质量和结构的多样化，也就是要设计有代表性的 产品。因此，计算化学和计算机模拟技术被应用到组合化学库的设计中。与组合合 成技术紧密结合，互相促进这一研究领域将在未来的几年中进一步地快速发展。 7 信息系统化 组合化学的发展，生物技术的突破，带动了新的信息学科的建立化学信息化 和自动化研究就是在此基础上开始的。组合合成的产物数目如此之大，要像以前 那样一个一个地画反应产物结构是不可能的。因此。以组合化学结构衍变为目标 的软件问世了人们把与组合化学有关的合成化学的反应数据、分析数据、结构 定性数掘以及有关的生物活性数据储存在一个整体化的数据库中，并且可以根据 需要随时提取所需数据。 8 新材料研制 随着研究测试手段的不断提高，组合化学的应用也从药物化学研究扩展到其 他领域。近几年来，组合化学已被用来寻找新型材料以及新的催化剂。国外的一 些化学公司纷纷投入大量的人力物力在组合化学的应用上，希望组合技术能加快 新材料开发的速度，在新材料研究方面新建的技术公司中，最有影响力的莫过于 位于美国加州的s y m y ) 【。这一公司成立于1 9 9 5 年，目前已发展到2 0 0 人的规模。 他们号称已经解决了组合化学在新材料方面应用的关键技术问题，并要在两年半 的时间里把一种新材料推向市场然而，组合化学在新材料研究方面的应用的最 大挑战不是合成，而是产品检测。与有机合成及药物化学应用相比，非常成型的检 测技术至今未见详细报道。r l 4 】 山东大学硕士学位论文 1 2 组合化学中的重要系数简介 1 2 1w i e n e ri n d e x 通过大量的实验，人们发现化合物的性质与它们的结构之间存在联系这里 所说的化合物的结构既包括对化合物分子结构的二维拓扑系数，又包括在化合物 分子结构的三维拓扑系划1 5 , 1 6 , 1 7 。想在对化合物分子结构的大量的拓扑系数中找 出与化合物性质相关的系数，难度是非常大的但是，科学家们已经发现了一些 这样的系数。这其中很著名的一个例子就是w i e n 盯i n d e x w i e n e r i n d e x 是指化合 物分子的图中所有的节点对的距离之和，即w ( t ) = u 。捆，( i ，j ) 。它与化合 物的很多物理化学性质有密切的联系，例如化合物的沸点1 1 町w i e n e ri n d e x 是 化学家h a r o z dw i e n e r 在1 9 4 7 年首先提出的【1 9 1 在此基础上，科学家们又进行了 大量的研究，发现了很多与化合物的性质有关的二维和三维拓扑系数 1 2 20 i n d e x 给定一个分子的平面图g ，g 的0 - i n d e x 就是指图g 中任意大小的独立集的总 数，其中包括空集。例如，只有一个顶点的图的。一i n d e x 为2 ，即空集和这个顶 点自己；而顶点总数为n 的星形图的。一i n d e x = n + 1 + ( c 。- 2 1 + 艮2 2 + c r 2 3 + + 1 ) + ( c m l + c 。? + + 1 ) + + l = n + 1 + ( 2 “一1 ) + ( 2 “一1 ) + + 1 = 2 ( 2 ”- 2 _ 1 ) 一( n - - 2 ) + ( n + 1 ) = 2 ”一1 没有任何顶点的空 图被视为连通图。显然，o ( 由) = 1 我们也可以把空图看作完全图( 即一个 团) ，一个独立集，或者是一棵树 0 - - i n d e x 又铍称为独立集系数，或者是m e r r i f i e l da n ds i m m o n s 系数0 - i n d e x 是组合 化学中竹常重要的一个拓扑系数。它的值与分子的一些物理性质密切相关在m e r r i f i e l d 雨l s i m m o m ；丁1 9 8 9 年发表的论文中，他们阐述了o i n d 骼和化合物的沸点之问的联系【2 0 】 1 2 3c - i n d e x 给定一个图g ，它的c i n d e xc ( g ) 是指图g 上的任意大小的团的数目可以看 山东大学硕士学位论文 出，c - i n d e x 是对o - - i n d e x 的补充显然，c ( g ) 就等于图g 的补图的a - - i n d e x 而且c ( 巾) = 1 ，c ( k - - i ) = 2 n ，c ( p 。) - - - 2 n 。另外，c ( c 3 ) = 8 且当n 4 的时候c ( c 。) = n + 1 + ( 2 + 2 + + 2 ) 2 = 2 n + 1 ，其中c 代表n 个顶点的多边形 1 3 组合化学中的逆问题 化合物的系数就是指从具体的化合物分子到具体数字的映射。我们可以把这 些具体的数字看作是反映化合物性质的域事实上，很多具有相似性质的化合物 所映射得到的数字也是接近的。甚至有大量的化合物被映射相等的或者几乎相等 的数值。所以我们很自然的可以想到，如果给定了一些具体的系数值，或者给定 了一个系数值的域，我们应该可以设计出系数值等于给定值或者处在所给的域中 的化合物。这就是我们要在组合化学中解决的逆问题。 这种逆问题的输入值是从实验室的试验得来的，解决这样的逆问题的目的就 是引导新的试验，提高发现新的、更符合要求的化合物的可能性为了达到这样 的目的，我们首先必须解决各种特定系数的逆问题，当然，我们希望每个逆问题 的多个解能够尽量的多样化，这罩所说的多样化是指化合物分子的结构应有较大 的差异。这样我们就可以创建出新的化合物库并发现新的先进的化合物 6 山东大学硕士学位论文 第二章树的w i e n e ri n d e x 逆问题算法的提出 2 1 基本定义和定理 由于组合化学的发展，各种各样的应用于化合物库的设计的图的重构问题随 之出现由给定的拓扑系数构造出相应的图或树就是其中重要的一种；另一种重 要的重构问题是从一个化合物库中选择化合物片段来构成人造蛋白质，以使其与 给定的拓扑系数相匹配。在这一章中，我们将对w i e n e ri n d e x 的逆问题进行讨论， 对以往的研究中得出的结论进行说明，并重点对g o l d m a n 等人提出的树的w i e n e r i n d e x 逆问题算法进行阐述。为了方便后面的证明，我们下面先对要用到的定义 和符号进行统一的说明 定义1 1 给定一个图g = ( v ，e ) ，也( i ，j ) 表示图上的两个顶点i ，j 2 _ 间的最短距 离( 即边数最少的路径长度) 如果g 是一棵树，则也( i ，j ) 表示的是顶点i ，j 2 _ 间 唯一的路径的长度。 同时我们用n 或者n ( g ) 来表示一个图的节点总个数，用来表示n 个节点的完 全图，用s 表示n 个节点的星形图( 即除了一个节点外都是叶节点的图) ，用p 。表 示n 个节点的路。 为了定义方便，在这篇论文中当我们用到。，时，我们所指的i ，j 是不同的 点对。 定义1 2 给定一个图g - ( v ，e ) 。它的w i e n e ri n d e xw ( 6 ) 是指图上所有点对的 最短距离之和。即w ( g ) = 。v 也( i ，j ) 山东大学硕士学位论文 定义1 3 一个化合物片段是指具有一个特殊的顶点v ( 称为a n c h o r 或者 h o o k i n gp o i n t ) 的图一个p e p t o i d 是指一个通过一条连接各个片段的特殊顶点 的路把k 个片段g ，g - 从左到右连接成一个线性的f a s h i o n 得到的图( 如 上图) 。当k = 1 时一个片段就是p e p t o i d 的一个特例。对于一个p e p t o i d d = ( v ，e ) ，l ( d ) = 。d 6 ( i ，v - ) 表示所有的点到最右边的h o o k i n gp o i n t 的距离之 和。当k = l 时，1 ( d ) 就表示一个片段上的所有的点到它的h o o k i n gp o i n t 的距离之 和。 我们可以把一棵树视为一个h o o k i n gp o i n t 就是它的根的片段，这样我们就 可以给出如下的定义。 定义1 4 给定一棵树t - ( v ，e ) ，它的根为v v ，它的所有顶点到它的根的距离 之和是1 ( t ) = 。d ( i 。v ) 对于w i e n e r i n d e x 逆问题，科学家们进行了大量的研究。得出了很多有用的 结论，为进一步的研究打好了基础 定理3 1 对于任何不等于2 或5 的w 值都存在一个图g ，使得w ( g 产w 为了证明这个定理，我们先要证明下面的引理： 引理3 1 对于任何直径为2 且w i e n e ri n d e x 为w 的图g - - ( v , e ) ，图g 刈丑u e ”，e 不属于e 的w i e n e ri n d e x 为w - i 。 证明：令e = ( v i ，v 2 ) 显然d g ( v j ，v 2 ) = 2 且d g ( v l ，v 2 ) = 1 而从图g 到图g 的变化 对其它各项点对的最短距离并没有影响，所以图g 的w i e n e ri n d e x 为w - i 。 下面来证明定理1 1 证明：令g 0 = s 。，即图g 0 为节点数为n 的星形图则有 w ( g o ) = ( n 1 卜2 ( ( n 2 ) h n - 3 卜+ 1 ) = ( n - 1 ) + ( n - 1 ) ( n 2 ) = ( n - 1 ) 2 且图g o 的直径为 2 。令g l 为在g o 上添加一条本来不包含在g o 中的边后得到的图。这样如果n 3 ， 则g l 是一个完全图k ，否则图g 1 的直径为2 由上面的引理可知。w ( g 1 ) = w ( g 0 ) - i 。 我们可以反复进行这个步骤，每次都会使图g 的w i e n e rl h d e x 值减少1 ，直到我们 得- n n 个节点的完全图k 。，容易看出，n 个节点的完全图k 。的w i e n e ri n d e x 值 w ( k n 声- n ( n 0 1 ) 2 。而在这其中的任何一步，引理都保i 芷t w ( g o - - w ( a k i ) - l 。这样 山东大学硕士学位论文 就可以知道在区问i = 【n | n 1 胆，( n 1 ) 2 】内的所有的数都是某个k 值所对应的图g k 的w i e n e ri n d e x 值。 ， 又因为当n 4 时，区白j i = 【n ( n - 1 ) 2 ，( n - 1 ) 2 】在n 取不同值时互相重叠；而n = 4 和n = 5 时区间i 正好衔接所以对于所有的w 5 都有图g 使得w ( g ) = w 而l ， 3 和4 分别是p 2 ，k 3 和p 3 的w i e n e r i n d e x 值n 个节点的图在这个图为完全图k 时有 最小的w i e n e ri n d e x 值，在图为一条路时有最大的w i e n e ri n d e x 值。而w ( p 2 ) = 1 且w ( k 3 ) = 3 ，所以证明了没有图g 使得w ( g ) = 2 。 由这个定理的证明，我们可以发现一种解决这个问题的算法，即输出一个具 有给定w i e n e r i n d e x 的图。因为一个图的w i e n e r i n d e x 是与它的节点数多项式相关 的，并且一个数字可以由它的对数大小的位数来表示，所以这个算法是伪多项式 时白j 的即这个算法对于描述问题规模的参数而言是多项式时间的，但对于这 个参数的实例输入长度而言则不是多项式时间的更具体的来说。计算的时间是 出输出所需要的图的时间决定的，即0 ( 一) 因为有n ( n - 1 ) 2 w ( n - 1 ) 2 ，所以 算法的时间复杂度也可以表示为0 ( w ) 2 2 树的w i e n e ri n d e x 逆问题 在这一节中我们要关注这样的问题：给定一个正整数w ，判定是否存在一棵 树t ，使得w ( t ) 硼，即树的w i e n e ri n d e x 的判定逆问题我们同时还会考虑找出 这样一棵树的问题，即树的w i e n e ri n d e x 的构造逆问题。显然。定理1 1 中包含 了不是树的图，所以它所得出的结论不能适用于这个更具体的集合。实际上，有 很多的整数是某个图的w i e n e ri n d e x 值，但不是任何树的w i e n e ri n d e x 值。通过 计算可以发现对于所有小于1 0 0 0 0 的w 值1 5 9 是这样的数中最大的。由此我们可以 得出如下的推论： 推论3 1 除了一个有限的集合外，所有的正整数都是某一棵树的w i e n e r i n d e x 值。 这个推论是首先在引文 2 1 j 中出现的，在那篇文章中通过完全枚举所有 w i e n e ri n d e x 值小于等于1 2 0 6 且节点数小于等于2 0 的未标记的不同形状的树，对 这个推论进行了证明。如果这个推论却是成立的话，那将会说明树的w i e n e r 9 山东大学硕士学位论文 i n d e x 逆问题的判定逆问题是微不足道的，但是即使推论成立，它对于解决树的 w i e n e ri n d e x 构造逆问题也没有什么帮助 2 3w i e n e ri n d e x 的递归联系 为了解决树的w i e n e ri n d e x 的判定逆问题和构造逆问题，必须对其进行进一 步的研究，以发现其中的规律 令t = ( v ，e ) 为一棵树，且( v i ，v d 为树的一条边令t = ( v ，e 。) 和t ；( v z ，e 。) 为树t 拿掉边( v i ，v d 后形成的两棵新的树。设树t 和t 。的根均为v 。 而树t ：的根为v z 。对于树的w ，l ，n 的值，我们可以发现如下的递归联系 定理1 2 n ( d = n 盯1 ) + n ( t 2 ) ( 1 ) l ( t ) = l 口l h ( 砣) + n f r 2 ) ( 2 ) w ( t ) = w ( t i ) + w ( t 2 ) + i ( t i ) n ( t 2 ) + i ( t 2 ) n ( t i ) + n ( t i ) n ( t 2 ) ( 3 ) 阱t 2 3 洲 ( 1 ) 是显而易见的。要证明( 2 ) 我们需要使用( 1 ) 的定义并对其形式进行简 单的修改。 l ( d = ，v d ( v l ，v ) = ，e v l d ( v i ，v ) + ，e d ( v hv ) = ，ev j d ( v ，v ) + e ，e v 2 ( d ( v 2 ，v ) + 1 ) + 1 = 1 ( t i ) + 1 ( t 2 ) + n ( t 2 ) 下面证明( 3 ) ： w ( t ) = e v d ( v ，w ) = 。e v , d ( v ，w ) + h 。e v 2 d ( v ，w ) + ，e v t , e v 2 d ( v ，w ) = w ( t i ) 竹( t z ) + ( d ( v ，v i ) + 1 + d ( v 2 ，w ) ) = w ( t 1 ) + w ( t 2 ) + 1 ( t i ) n ( t 2 ) + 1 ( t 2 ) n ( t 1 ) + n ( t i ) n ( t 2 ) 除了这个递归联系外，我们还需要对w 、l 、n 之f b j 的拓扑关系进行研究和分 析以方便提出解决这个逆问题的算法。 定理i 3 给定一棵树t ，w ( t ) = w ，l ( t ) = l n ( t ) = n 。则有 山东大学硕士学位论文 ( n - 1 ) 2 w ( n 3 - n ) 6( 4 ) n 1 l n ( n i ) 2 ( 5 ) 【2 5 2 6 】 证明： 容易看出，对于n 个节点的树而言，其w 和l 值在树的形状为星形且 根是星形的中心时达到最小值；而在树的形状为一条路且根是路的端点时达到最 大值。 当树t 的形状为展形时： | ( i ) 2 n - - l w 盯户( n i 卜2 ( ( n - 2 卜( n - 3 卜1 ) ：( n - 1 ) + ( n - 1 ) ( n - 2 ) = ( n 1 ) 2 当树t 的形状为一条路且树的根是路的端点时： 1 ( t ) = 1 + 2 + + ( n 一2 ) + ( n 1 ) = n ( n - 1 ) 2 w ( t ) = ( 1 + 2 + ( n - i ) ) + ( 1 + 2 + + ( n 一2 ) ) + ( 1 + 2 + ( n - 3 ) ) + + 3 + l = ( n - i ) n 2 + ( n - 2 ) ( n - i ) 2 + + 1 = ( n + i ) n ( n - i ) 6 = ( n 3 - n ) 6 所以定理成立。 2 4w i e n e ri n d e x 逆问题算法的提出 由这些递归联系。g o l d n m n 等人提出了一个解决树的w i e n e ri n d e x 逆问题的 动态规划算法。要想解决树的w i e n e ri n d e x 判定逆问题，即判定对于一个给定的 w 值，是否有w i e n e ri n d e x 值与其相等的树存在，必须先解决这样一个问题：对 山东大学硕士学位论文 于给定的w ，l ，n 值，是否有w i 乃、l 和n ( 1 ) 分别与其相等的树t 存在通过观察 我们可以得出如下的结论：每一棵至少具有一条边的树都可以通过上述的递归联 系进行分解，即通过移掉一条边把原来的一棵树分解为两棵树。不管被移掉的是 哪条边，我们都会得到两棵树t i ，i = 1 , 2 ，并且对于每个i ，都有w ( t i ) w f r ) ， l ( t i ) l ( d ，n 盯i ) n ( r ) 。我们定义一个三维矩阵m ，在这个矩阵中，如果存在一棵 树t 使得w ( t ) = w ，l ( r ) = l ，n ( t ) = n 则m w i n = 1 。否则m w i 。= o 。根据上一节的 递归联系，如果对于每一个w w ，l 姐，n h i 我们都知道m 。，i ，。，的值，我们 就可以研究树t 的所有分解情况，如果对树t 作的所有分解中的任意一次所形成 的两个分支的w ( t 0 、i ( t 0 、- , ( t o 值在矩阵中所对应的值都是l ，那就说明对应值 ( w ，l , n ) 至少有一棵树存在，只需把那两个分支的根连接起来就可以得到这棵 树；反之如果对树t 作的每一次分解形成的两个分支在矩阵中对应的值都不能同 时为l ，那就说明没有对应值w ，l n 的树存在。显然我们可以看出m o , o a = 1 ，而 那些w 、l 、n 值不满足我们上面所证的拓扑性质要求的m w i i i 显然取值为o 。这 样我们就可以以m o 0 1 _ 1 为起点，不断的按顺序向上进行递推，就可以计算出从 m o ，o ，l 一直到m 。1 n 的值，然后通过检验m w , i , 。的值，就可以解决树的w 、l 、n 值 逆问题。 以这个算法为基础，g o l d m a n 等人进一步提出了解决树的w i e n e r i n d 逆问 题的算法：给定w 值，我们首先根据w 和l 、n 的关系计算出l 和n 取值的上界， 这样我们就可以使用上面得出的算法了。按照上面的算法自下而上依序填充矩阵 m 一直到单元m ，如果对于所有的l l n n 都有m w 1 ，。，= o ，则说明没有树使 得w ( t 卜w 我们还可以进一步对这个算法进行扩展使它能够返回一棵w i e n e ri n d e x 值等 于给定w 值的树，从而解决树的w i e n e ri n d e x 构造逆问题。扩展的思想是这样的： 就像我们经常在动态规划中使用的那样，每当矩阵m 中有一个单元的值经计算为 1 时，我们就将使它为l 的两个分支所对应的单元记录下来，这样最后经过分析和 组合我们就可以得出整棵树的形状。 山东大学硕士学位论文 在对算法的具体实现上，g o l d m a n 使用了一项与动态规划有关的称为 m c m o i z a t i o n 的技巧因为如果自下而上的依次填充矩阵m ，在w 、l 和n 取值较 大的情况下，其计算量将是非常惊人的，很难在实际中应用使用这项技巧，首 先就是要递归的应用w 、l 和n 之间的递归联系，为了避免对矩阵m 中同一个单 元的重复计算，我们把取得的中间结果都存到矩阵m 中去这实际上可以被视为 自上而下版的动态规划值得指出的是如果不对中间结果进行存储，那么算法的 时间复杂度将呈指数级上升，这是因为需要矩阵m 中的单元进行大量不必要的重 复计算。当算法在矩阵m 并没有被完全填充就运行结束的情况下尤其有效如果 矩阵m 中的所有单元都被填充，则使用m v m o i z a t i o n 技术所需计算的单元数与自下 而上的计算方法所需计算的单元数时完全一样的，但相对于自下而上的方法仍然 会稍快一些，这主要是由于两种方法对函数的调用次数不同和对栈的管理方式不 同造成的对于我们所面临的问题而言，使用了m e m o i z a t i o n 技术的算法在处理 回答为是的实例时要比原方法快得多，这主要是因为回答为是时，矩阵m 中需要 计算的单元数一般只是总单元数的很小一部分例如，( 5 2 4 ，3 6 ，1 9 ) 是一个 回答为是的实例，硬用g o l d m a n 廖提出的算法在不到一秒钟之内就可以完成计 算；而( 5 2 5 ，3 6 ，1 9 ) 是一个回答为否的实例，使用g o l d m a n 的算法对其进行 计算就需要1 4 5 秒钟。这个例子是比较极端的，但是这样的现象是一直都存在的 为了进一步对算法进行优化，加快其运行速度，g o l d m a n 又尽可能的采用了 分而治之的策略这是因为要使用递归联系有很多可能的方式，我们首先从n * n ( d 开始应用递归联系，这样我们就能直接的从可能的最小子问题开始计算。 这种方法在最坏的情况下是无效的，因为当w - - - - ( n - - 1 ) 。l - - - - n - - 1 的情况下， 即树t 是n 个节点的星形图的情况下，不管移去哪一条边，都会形成一个星形图 和一个单独的点可是这种方法仍然提出了一种合理的递推顺序。g o l d m a n 所最 终提出的算法如下所示【2 4 1 ： t r e e ( w ，l ，n ) f n 3 - n w u l n ( n i ) 2 t h e n r e t u m0 i fm u n d e f i n e dt h e n 托l u m m w , l , n 山东大学硕士学位论文 j fn = l t h e n r e t u r n 0 f o rn l ；n 2 t o n - i d o n 2 = n - n l f o rl l - n 1 - 1 t o l n 2d o l 2 = l - l l n 2 ： f o rw 1 = l l t o w - l i n 2