单圈图的Steiner k-general Wiener指数

对于连通图G,当3≤k≤n-2时,图G的Steiner k-general Wiener指数定义为SW_(k)^(m)(G)=∑S■V(G)|S|=kd^(m)(S),(m≥1),其中d(S)表示点集S的Steiner距离,即图G中包含点集S的最小连通子树的边数.给出了单圈图的SW_(k)^(m)(G)下界,并得到对应的极图.

奖励-收集Steiner树问题的精确算法

奖励-收集Steiner树问题是图的Steiner最小树问题的衍生,同时也是组合优化中的NP-hard问题。首先,提出该问题的数学性质并给出证明,利用数学性质能降低该问题的规模;其次,基于该问题的数学性质设计出上下界子算法、降阶子算法和回溯子算法,通过上下界子算法和降阶子算法可以降低该问题解空间的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间;最后,应用案例分析、算例分析以及算法分析与对比表明,所设计的算法不仅可以求出该问题的最优解,而且比没有考虑该问题数学性质的一般回溯算法的时间复杂度更低。

Steiner树优化问题的算法研究综述

最优Steiner树问题(Steiner tree problem,STP)是一个经典的组合优化问题,许多工程问题都可以归结为最优Steiner树问题。STP被广泛应用于通信网络、电路设计、VLSI设计等领域。然而,STP是典型的NP难问题,还没有多项式时间的精确算法求解该问题。目前,求解该问题的算法主要集中在基于启发式的近似算法、智能优化算法、信息传播算法等,并取得了很好的效果。在不同规模的网络中,基于传统遗传算法给出一种叶交叉机制(leaf crossover,LC),使用该机制的算法性能表现更好。通过对这些算法的原理、性能、精度等方面进行梳理,归纳出算法的优缺点,并指出STP的研究方向和算法设计路径,对于相关问题的研究有指导意义。

基于动态粒子群优化的X结构Steiner最小树算法

Steiner最小树(SMT)是总体布线的最佳连接模型,其构造是1个NP-难问题。粒子群优化(PSO)算法在解决NP-难问题中具有良好的表现,而PSO算法中种群的拓扑结构及搜索信息的传递机制对其性能有着很大的影响。1个适用于具体问题的种群拓扑结构对算法性能的提升极为显著。因此,利用PSO求解总体布线问题需要根据具体布线问题的特性来选择合适的粒子拓扑结构策略,以提升PSO的性能。提出基于动态PSO的X结构Steiner最小树(XSMT)算法以解决总体布线问题。首先,设计动态子群与信息交换策略,对种群进行子群划分,引入信息交换的概念,让子群在保持独立性的同时与其他子群进行信息交换,增加子群多样性;其次,设计粒子学习与变异策略,通过设置子群中粒子的学习对象使子群趋向于全局最优,并选择每个子群中适应度值最好的粒子进行变异,使粒子更易于跳出局部最优;最后,设计从多群局部学习过渡到单群全局学习策略,使算法在迭代次数到达阈值之后从局部学习过渡到全局学习,使得粒子在较优拓扑结构的基础上内部连接以获得更好的线长优化率。实验结果表明,与现有的2种R结构SMT(RSMT)算法相比,所提算法在优化线长方面分别优化了10.25%、8.24%;与现有的3种XSMT算法相比,该算法在优化线长方面分别优化了2.44%、1.46%、0.48%,验证了算法的有效性。

区传递Steiner t-设计与散在单群

研究具有某种高度对称性的t-设计及其自同构群的分类问题是代数组合学的重要课题之一。目前关于旗传递Steiner t-设计的分类问题已被Huber解决。然而当设计的自同构群的旗传递性减弱为区传递时,研究结果更加丰富,工作也更加困难。利用有限单群分类定理及2-传递置换群的分类结果,解决了自同构群为散在单群的区传递Steiner t-设计的分类问题,并证明了:设D=(P,E)为非平凡Steiner t-设计且G≤Aut(D)为点本原群,若G的基柱Soc(G)为散在单群,则G区传递作用在D上当且仅当G旗传递作用在D上,且D为已知的5种旗传递Steiner t-设计之一。

圈C_(n)的Steiner 3-Wiener指标

令图G是一个连通图,图G的点集是V(G),边集是E(G).当2≤k≤n-1时,图G的Steiner_(k)-Wiener指标定义为SW_(k)(G)=∑S■V(G),|S|=k d_(G)(S),其中d G(S)表示图G中S的Steiner距离,即连通图G中包含点集S的最小连通子图的边数.本文利用Steiner k-Hosoya多项式给出了圈C_(n)的Steiner 3-Wiener指标的表达式.

异质信息网络中最大路径连通Steiner分量查询算法

异质信息网络(HINs)是包含多种类型对象(顶点)和链接(边)的有向图,能够表达丰富复杂的语义和结构信息.HINs中的稠密子图查询问题,即给定一个查询点q,在HINs中查询包含q的稠密子图,已成为该领域的热点和重点研究问题,并在活动策划、生物分析和商品推荐等领域具有广泛应用.但现有方法主要存在以下两个问题:(1)基于模体团和关系约束查询的稠密子图具有多种类型顶点,导致其不能解决仅关注某种特定类型顶点的场景;(2)基于元路径的方法虽然可查询到某种特定类型顶点的稠密子图,但其忽略了子图中顶点之间基于元路径的连通度.为此,首先在HINs中提出了基于元路径的边不相交路径的连通度,即路径连通度;然后,基于路径连通度提出了k-路径连通分量(k-PCC)模型,该模型要求子图的路径连通度至少为k;其次,基于k-PCC模型提出了最大路径连通Steiner分量(SMPCC)概念,其为包含q的具有最大路径连通度的k-PCC;最后,提出一种高效的基于图分解的k-PCC发现算法,并在此基础上提出了优化查询SMPCC算法.大量基于真实和合成HINs数据的实验结果验证了所提出模型和算法的有效性和高效性.

单圈图的Steiner Wiener指数的极值问题

Wiener指数作为化学图论中的一个重要的化学指标,是连通图的任意两个顶点的距离之和。Steiner Wiener指数是Wiener指数的一种推广形式,定义为所有k个顶点的集合S的Steiner距离的和,其中S的Steiner距离是包含S的最小连通子图的边数。本文研究了具有最小(大)Steiner Wiener指数的单圈图结构。

乘积图和F-Sum图的Steiner K-距离

图的距离是图论中非常重要且基本的概念,是研究基于距离的图不变量的基础。Steiner距离是图论组合研究中的经典问题。本文运用Steiner树的定义证明了corona积的Steiner k-半径和cluster积的Steiner k-半径的上下界以及F-sum图的Steiner距离和Steiner k-直径的界。

广义欧几里德Steiner问题的研究与进展

广义欧几里德Steiner问题是指确定连接平面上一组给定点的满足特定连通性要求的最短网络的问题。本文主要介绍了此问题的研究与进展,在建立了求给定平面点集的最短U-连通(或边连通)生成网络的整数规划模型的基础上,证明了文献[13]中所给的一个例子是错误的,并提出了一些关于广义Steiner问题的进一步研究的问题。

KMT2A基因变异致Wiedemann-Steiner综合征3例临床及遗传学分析

目的报告3例KMT 2 A基因变异所致的Wiedemann-Steiner综合征(Wiedemann-Steiner syndrome,WDSTS)的临床和遗传特点,提高对该疾病的认识及临床诊治效率。方法回顾三个家系的3例KMT 2 A基因变异导致的WDSTS患儿的临床资料,并复习总结文献。结果3例患儿均为婴儿期诊断,最小诊断年龄2个月,就诊原因分别为生长迟缓和食欲不振。与以往文献相似的临床表现为特殊面容、营养不良(3/3),喂养困难、睡眠障碍、多毛(2/3),发育迟缓(1/3),既往无报道的临床表现为脐疝、腹股沟疝。3例均是新发移码变异,变异分别发生于热点变异区的外显子3和27以及非热点变异区的外显子11。结论对于营养不良、喂养困难及发育迟缓的患儿,结合特殊面容和特异性多毛的临床表现,应考虑Wiedemann-Steiner综合征,需要做高通量全外显子基因分析确诊,有助于患儿尽早诊断;KMT2A基因以新生移码变异常见,变异热点是外显子27和3,本研究未经报道的3个移码变异丰富了该基因的变异谱,KMT 2 A基因含CXXC区变异的患者临床表型可能更重。

域上Steiner扩张的代数性质(英文)

讨论了Steiner列的结构 ,得到了Steiner扩张的一些性质 ,并推出每个Steiner列 {sn}中 ,任意圆是可以尺规作出的。

Creative Activity and the Development of Consciousness:A Discussion With Piaget and Rudolf Steiner

This study aims to discuss the possibility of becoming conscious of certain aspects of one’s own existence through creative activity.The discussion involves Piagetian constructivism and Steiner’s ideas about human development and is justified by the contribution of creative activity to the development of autonomy,according to Piaget,and to the development of an ethical individuality,according to Steiner.The participation of adults in sessions of creative process,as well as the questions posed after this activity,asking for the relationships between what they created and their life,is evidence of practices favourable to increasing the grasping of consciousness of self and of the process of developing an ethical individuality.

Steiner对称化后对偶混合体积部分性质

在本文中,我们探讨对偶混合体的性质,考虑在星体的径向加法下,星体经过Steiner对称化后做加法与先加后做Steiner对称化两者之间的包含关系,继而利用包含性来得到星体经过Steiner对称化后相应的对偶混合体积性质,最后利用高斯球逼近定理构建单调序列来证明特殊星体的对偶Minkowski不等式。

圈C_n的k-Steiner Wiener指数和超k-Steiner Wiener指数

点集S的Steiner距离d(S)是指包含子集S的最小连通子图的边数即d(S)=min{|E(H)|:S■V(H),H是G的连通子图}.2016年,李学良,毛亚平和Gutman提出了k-Steiner Wiener指数SW k(G)和超k-Steiner Wiener指数SWW k(G)的概念,SW k(G)=∑S■V(G),|S|=k d(S)SWWk(G)=1/2∑S■V(G),|S|=k d(S)+1/2∑S■V(G),|S|=k d(S)2.文章利用k-Hosoya多项式给出了圈C n的k-Steiner Wiener指数和超k-Steiner Wiener指数.

已知拓扑下的4度Steiner树算法

设Ｎ为平面上２ｎ个固定点的集合，Ｍ为ｎ－２个可动点的集合，Ｅ为连接这些点的边的集合（也称作拓扑）．设Ｅ为点集Ｖ上的满４度Ｓｔｅｉｎｅｒ拓扑（满Ｓｔｅｉｎｅｒ拓扑也就是满足固定点的度为１，可动点的度为４的树的拓扑），Ｈ（Ｅ）为包含Ｅ在内的所有Ｅ的退化拓扑的集合．文中构造了计算拓扑属于Ｈ（Ｅ）的４度Ｓｔｅｉｎｅｒ树算法，并证明了算法的时间复杂性是Ｏ（ｎ２）．

基于最小生成树的Steiner最小树生成算法

提出了基于最小生成树的Steiner最小树的生成算法,分析了该算法的时间复杂性为O(nlogn)。

约束Steiner最小树问题

本文首先提出了一个约束Ｓｔｅｉｎｅｒ最小树问题，设欧氏平面上直线Ｌ的一侧有ｎ个点，记点集为Ｎ，现要在Ｌ上找一点Ｐ，使关于Ｎ∪（Ｐ）的Ｓｔｅｉｎｅｒ树长度最小，文章解决了ｎ＝２及ｎ＝３的情形。

带圆周约束的Steiner树问题

本文首先考虑了带圆周约束的Ｓｔｅｉｎｅｒ树问题．设欧氏平面上有一圆，平面上有ｎ个点，所成点集为Ｎ，该问题是要在圆周上找一点Ｐ，使Ｎ∪｛Ｐ｝这ｎ＋１个点的Ｓｔｅｉｎｅｒ树之长度达到最短．本文对于ｎ＝２的情形给出解．另一方面，鉴于问题的复杂性为ＮＰ－Ｃ，作者提出了一个近似解，并证明了近似解的性能比为３／２．

关于对偶Steiner多项式的根的注记

受凸体的Steiner多项式的启发,定义了星体的对偶Steiner多项式,并利用对偶Aleksandrov-Fenchel不等式讨论了对偶Steiner多项式的根.进而,得到了关于对偶Steiner多项式的根的一些不等式,这些不等式恰好是关于Steiner多项式的根的不等式的对偶形式.