生成树

摘要： 设G是连通图,G中任意两点之间的电阻距离定义为将G中的每条边用电阻(通常用单位电阻)代替后所得到的电网络中这两个节点之间的等效电阻。综述了电阻距离领域的研究进展和重要研究成果,包括电阻距离的计算公式、电阻距离的性质、电阻距离的和法则、电阻距离的递推公式以及若干重要图类的电阻距离解析计算公式。最后,给出了电阻距离研究领域的一个公开问题和两个猜想。

摘要： 证明了一类广义双锥图的生成树数目可以转化为一个二阶行列式的计算,以此得到了特殊图类的生成树数目的显式表达式,并推广已有的结果.

摘要： 网络闪断现象会造成医院所有应用中断,严重影响了正常医疗业务的开展。本文介绍了查找网络闪断故障的过程,着重分析了故障的原因,为什么在网络数据链路层上触发根桥选举会造成网络波动以及闪断。然后说明了生成树协议和触发根桥选举的过程,并探讨了多种避免触发根桥选举的做法和建议。

摘要： 记Knm(n≥2,m≥1)是n个顶点的完全多重图,即任意两个顶点间有且仅有m条边相连。Knm+G (或Knm-G)为在Knm基础上再添加(或从中删除)子图的对应边得到的图。Nikolopoulos和Papadopoulos利用Kirchhoff矩阵–树定理给出了Knm+G生成树数目τ(Knm±G)=m(mn)n-p-2det[mnIp±L(G)]。本文利用线性代数技巧(一个有关矩阵和的行列式计算公式),对该定理给出了一种新的简洁证法。并给出当G为完全图、圈、路、二部图时Knm±G生成数目的计算公式。

摘要： 针对部分重复码的有效修复问题,本文基于Harary图生成树构造出了一种新型的部分重复(Fractional Repetition based on Spanning trees of Harary graph,FRSH)码.实验结果表明,相较于现有的里所(Read-Solomon,RS)码和简单再生码(Simple Regeneration Codes,SRC),FRSH码在修复带宽开销、修复局部性等方面得到了更低的开销,且改善了修复效率,并将故障节点的修复时间缩短.

摘要： 本文使用最小生成树算法对城市道路问题进行建模,利用最小堆优化最小生成树的求解过程,最后对最小生成树的推广和应用进行总结.

摘要： 为扩展织物组织的设计思路,提供更多富于变化、风格独特的织物组织,受到瓷砖铺砌的启发,文章运用瓷砖铺砌的思路提出一种新的铺砌织物组织设计方法.该方法运用循环数不同的2种基本组织按周期铺砌规则生成织物组织.首先采用图数据结构表示瓷砖铺砌结构;然后由小铺砌块为根节点层次遍历图结构构造一棵生成树形成铺砌结构,并根据组织的四方连续性要求裁剪铺砌结构;最后按遍历顺序依次将基本组织填充至树的节点.运用C++编程语言实现了该方法并进行了多种不同变化形式的仿真设计实验.结果表明:该织物组织设计方法灵活便捷且变化形式多样,所生成的织物组织结构多变,且具有周期对称、错落有致等传统组织所不具有的特点.

摘要： 通过研究线性交叉四角链Xn和交叉四角柱状链Gn的结构特点,利用合成图的拉普拉斯特征值计算出了Xn与Gn的拉普拉斯谱,并且导出了Xn与Gn的基尔霍夫指标,度-基尔霍夫指标和生成树的数目的解析式.且得到当n趋于无穷大时,交叉四角柱状链Gn的基尔霍夫指标是线性交叉四角链Xn的基尔霍夫指标的二分之一.

摘要： 本文研究带有切换拓扑和随机故障影响的Cucker-Smale模型的集群演化特点,在切换时间间隔和故障概率满足一定约束条件下,给出系统几乎必然发生集群演化的充分条件.鉴于随机故障和拓扑切换的综合影响,Cucker-Smale模型产生了复杂的集群演化行为,其中集群收敛速度随着故障概率的增加会显著减慢.同时,我们在切换过程中并不要求每时每刻的交互图都具生成树.只需保证在有限时间段内联合图具有生成树.进一步,数值仿真结果显示,当切换时间间隔增加或故障概率较大时,系统的集群演化行为将会遭到破坏.

摘要： 若图G的一个生成子图T是一棵树,则称T为G的一棵生成树;若T为森林,则称它为G的一个生成森林.生成树是表征网络结构性质的一个重要物理量,网络中生成树越多,则网络越健壮.提出了一个k-正则图构成的小世界网络模型,介绍了其概念及演化过程,计算了k-正则图的相关拓扑特性,例如直径、聚类系数等,给出了此类k-正则图的生成树数目计算方法,得出生成树数目公式及熵.

摘要： 认知无线电技术可有效解决频谱资源的动态管理和利用问题,但随着通信网络规模的不断扩大以及频谱管理动态性、实时性要求的不断提高,现有的基于生成树的通信链路重要度评价方法已不再适用。本文提出了基于局部生成树的距离递进算法,通过网络局部的拓扑信息评价链路在全局网络中的重要度,并给出了距离递进算法的理论证明和性能分析。仿真结果表明该算法可以有效地减少计算复杂度,利用网络局部的拓扑信息获得较为精确的基于全局网络拓扑信息的链路重要度。

摘要： 文章解决了组合星图生成树的构造问题.首先给出了组合星图的定义及其重要的拓扑性质,然后采用构造方法获得了组合星图的一棵高度为D(Sn,k)的生成树,并给出了相应的算法,其中D(Sn,k)为组合星图的直径.该生成树具有最优的高度,且是一棵贪婪树.

摘要： 该文针对文献在最小费用网络过程瓶颈分析方面存在的缺陷，提出了基于最优生成树结构的瓶颈定义和分类，并重新定义了瓶颈裕度和瓶颈迁移。

摘要： 基于生成树理论,本文提出一种基于虚拟槽节点的无线传感器网络划分算法。算法选取网络中一组无环连通点集抽象为虚拟槽节点,形成传感器虚拟槽节点。当传感器节点进行数据汇报时,源节点通过按需路由策略通过虚拟槽节点与槽节点实现通信。本文通过理论计算确定最优虚拟槽节点选取方式,保证网络内任意节点两跳可达虚拟槽节点的概率为97﹪,并通过仿真论证算法的有效性。

摘要： 不同于以前求取割集的方法，本文在改造Prim算法的基础上，提出了一种新的求取生成树及其割集的算法。该算法原理简单，编程容易实现，适合于计算大规模拓扑图。通过一个6节点和一个30节点的拓扑图编程计算表明了该算法的正确实用性。

摘要： 节点删除法是根据删除节点后所得网络拓扑图的生成树数量大小来判断通信网中最重要节点的一种方法。本文在分析节点删除法的基础上指出其只适用于连通网络的局限性,并针对这种局限性,基于连通节点对数量和生成树数量提出一种新的评价方法。新的方法适用范围更广而且新方法保持了和节点删除法的一致性。实验结果证明了该方法的有效性。

摘要： 为了解决P2P网络计算聚集查询问题,引入了3种算法,并给出了算法形式化描述,为实现P2P网络聚集查询提供了方法.这三种算法都是基于图的连通性,采用生成树和信息广播等方法以适应于P2P网络应用环境,基本上能够保证聚集计算的有效性、准确性.

摘要： VLAN技术将物理网络划分成多个逻辑子网,有效的防止了广播风暴.IEEE 802.1Q定义了局域网/城域网中的VLAN技术标准.我们的智能交换机系统实现了符合IEEE 802.1Q标准的VLAN.本文首先简要的介绍IEEE 802.1Q标准,包括基本操作,过滤数据库和VLAN的实现方式,然后介绍我们的智能交换机软/硬件系统,重点说明支持动态VLAN实现的GVRP协议,以及相关的生成树协议和GARP协议.

摘要： 本文从哈密顿路(Hamiltonian Path)讨论了最少分叉树(Minimal Branch Tree)问题,并且给出最少分叉树(MBT)的定义和一个定理,进而讨论了它的求解算法.

摘要： 本文从哈密顿路(Hamiltonian Path)讨论了最少分叉树(Minimal Branch Tree)问题,并且给出最少分叉树(MBT)的定义和一个定理,进而讨论了它的求解算法.

摘要： 本发明涉及通信领域中通过交换芯片的设置实现通信协议的方法。一种在单生成树交换芯片上实现多生成树协议的方法，适用于支持IEEE802.1q的虚拟局域网及IEEE802.1d生成树协议的交换芯片，其特征在于：通过建立交换芯片中端口和多虚拟局域网VLAN关系表之间的对应关系，设置设备使能或禁止多生成树协议MSTP，将虚拟局域网绑定到指定的生成树实例上，设置端口在生成树实例上的状态，读取端口的MSTP状态，实现多生成树协议。采用本发明的技术方案，可在传统的支持单生成树的交换芯片上运行MSTP协议，利用芯片的VLAN和端口特性，完成MSTP各种功能，并大大降低现有网络设备的软件升级的成本。

摘要： 最短路径树和生成树结合的路由方法属于网络拓扑中的技术领域，其特征在于,在标准链路状态路由协议的基础上,网络中路由器节点所连接的每条链路增加休眠状态，在给定的网络拓扑上选定一棵共享的生成树，其上的链路始终处于工作状态以确保网络连通，其他不在生成树上的链路若没有流量经过则进入休眠状态，每个路由器保存全网路径的最短路径路由表和对应生成树的路由表，对于一个数据包，入口路由器根据当前链路负载决定数据包采用其中一种路径，并增加标签标识，非入口路由器根据标签选择相应路由表进行转发。

摘要： 本发明实施例涉及一种多生成树域内交换机优先级生成方法，该方法包括：域内各交换机获取本域内所有交换机的相关信息，生成本交换机的交换机信息表，并填入相关信息；对本交换机的交换机信息表的记录排序，并为域内各交换机分配交换机序号；域内各交换机获取本交换机的实例相关信息，生成本交换机的实例信息表，并填入相关信息；对本交换机的实例信息表的记录排序，并根据排序结果分配实例序号；按照优先级生成算法，各交换机为实例分配优先级。本发明通过构建优先级分配算法，能够实现多生成树域内交换机优先级自动配置，避免了手工配置繁杂和容易出错的问题。

摘要： 本发明提供一种网络系统、生成树构成方法、生成树构成节点和生成树构成程序。在连接多个节点的网络上构成生成树的节点，原封不动地运用变更前的树，用另外的VLAN生成成本变更后的树，在新树稳定后切换用于传送的树。

摘要： 在连接多个节点的网络上构成生成树的节点，原封不动地运用变更前的树，用另外的VLAN生成成本变更后的树，在新树稳定后切换用于传送的树。

摘要： 在连接多个节点的网络上构成生成树的节点，原封不动地运用变更前的树，用另外的VLAN生成成本变更后的树，在新树稳定后切换用于传送的树。

摘要： 在连接多个节点的网络中工作的生成树系统的节点中，具备：根据输入的帧的接收方MAC地址决定传送目的地端口的2个传送器；按照生成树协议作成生成树的2个树管理器；和连接树管理器与传送器的假想端口。

摘要： 本发明涉及通信领域中通过交换芯片的设置实现通信协议的方法。一种在单生成树交换芯片上实现多生成树协议的方法，适用于支持IEEE802.1q的虚拟局域网及IEEE802.1d生成树协议的交换芯片，其特征在于：通过建立交换芯片中端口和VLAN关系表之间的对应关系，将虚拟局域网绑定到生成树实例上，按照生成树实例设置端口状态，实现多生成树协议。采用本发明的技术方案，可在传统的支持单生成树的交换芯片上运行MSTP协议，利用芯片的VLAN和端口特性，完成MSTP各种功能，并大大降低现有网络设备的软件升级的成本。

摘要： 最短路径树和生成树结合的路由方法属于网络拓扑中的技术领域，其特征在于,在标准链路状态路由协议的基础上，网络中路由器节点所连接的每条链路增加休眠状态，在给定的网络拓扑上选定一棵共享的生成树，其上的链路始终处于工作状态以确保网络连通，其他不在生成树上的链路若没有流量经过则进入休眠状态，每个路由器保存全网路径的最短路径路由表和对应生成树的路由表，对于一个数据包，入口路由器根据当前链路负载决定数据包采用其中一种路径，并增加标签标识，非入口路由器根据标签选择相应路由表进行转发。

摘要： 本发明实施例涉及一种多生成树域内交换机优先级生成方法，该方法包括：域内各交换机获取本域内所有交换机的相关信息，生成本交换机的交换机信息表，并填入相关信息；对本交换机的交换机信息表的记录排序，并为域内各交换机分配交换机序号；域内各交换机获取本交换机的实例相关信息，生成本交换机的实例信息表，并填入相关信息；对本交换机的实例信息表的记录排序，并根据排序结果分配实例序号；按照优先级生成算法，各交换机为实例分配优先级。本发明通过构建优先级分配算法，能够实现多生成树域内交换机优先级自动配置，避免了手工配置繁杂和容易出错的问题。