k连通图在边点割原子与点割上的可去边

图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割断片的性质给出某些k连通图中在特定子图上可去边的分布情况,得到了最小度至少为(3(k-1)/2)或围长至少为4的k连通图(k≥4)中由边点割原子与点割所导出的子图的每一条边都是可去边.

基于平滑移动模型的k连通网络拓扑控制算法研究

为了使移动无线Mesh网络能够进行可靠的数据传输,保证移动网络的连通性,针对移动无线Mesh网络骨干网路由节点的移动特性,对基于平滑移动模型的k连通网络拓扑控制算法进行了研究。该算法采用节点的接收信号强度指示,实现节点在移动过程中邻居列表的动态更新。实验结果表明,该算法能够有效保证移动无线Mesh网络的连通性,提升网络的数据吞吐量,并延长了网络的生命周期。

基于多簇头K连通的抗毁拓扑构建方法

针对无线传感器网络复杂应用环境中簇头节点失效问题,提出一种改进的多簇头K连通抗毁拓扑结构构建方法。通过节点连通可靠度选举多个簇头,当簇头节点失效时,临时簇头集合中权值最大的节点自动升级成为簇头,同时利用K连通检测算法检测出关键节点并调整其发射功率实现K连通拓扑构建。该方法节约了簇头节点失效后网络重新进行簇头选举所耗费的时间及能量,并且增加了关键节点与周围节点之间的信息交互边。仿真结果表明:相比基于K-Means算法的普通分簇拓扑构建方法,该方法可使网络丢包率降低15.63%,端到端时延降低20.1%,提高了网络的抗毁性。

基于k连通的拓扑算法GKETA

主要研究了无线传感器网络的k连通拓扑控制问题。提出了一种新的基于k连通控制的拓扑算法GKETA,首先通过二元二次非线形回归法找到网络节点个数N,节点发射半径R,和连通度k之间的关系,通过最大发射功率构建初始k连通图。通过对算法的分析及大量比较实验,验证了GKETA算法在拓扑控制的冗余度和连通度上由于其k连通算法,节约了节点能量,具有更强的网络容错能力。

一种基于K连通的AMC无线监测系统

针对目前半导体装备生产环境中的悬浮分子级污染物无线监测系统网络可靠性差、部署成本高,设计了一种基于K连通的AMC无线监测系统。基于ZigBee网络,路由层应用了链路优化的K连通算法,构建了一拖多式的终端数据采集节点、低功耗路由节点和数据汇总分析平台。实验结果表明:该系统可以对AMC数据进行有效采集、存储和分析,优化的K连通网络,降低了网络丢包率和路由延迟,有助于提高网络的可靠性。该系统符合半导体装备生产环境中AMC的监测需求,网络节点的设计有助于降低系统部署成本,网络性能较优。

WSN中基于流网络的K连通算法

无线传感器网络(WSN)的连通性是保证网络容错性的重要途径。常规的多路由算法往往存在共同路径,这些共同路径会因为节点损坏、通信链路中断等故障导致整个WSN的连通性过早失效。针对共同路径问题提出了一种解决方案,通过节点分裂的方式在共同路径上生成多条路径,以支持WSN的容错,保证每个传感器节点都有K条长度有界的、到汇聚节点的不相交最短路径。仿真结果验证了本算法能提供更好的容错性,保证网络的连通性。

k 连通非正则图的 A_(α) 谱半径

设G为n个顶点m条边的k连通非正则图,图G的A_(α)矩阵[1]定义为A_(α)(G)=αD(G)+(1-α)A(G),0≤α≤1.其中D(G)和A(G)分别为图G的度对角矩阵和邻接矩阵,利用图的最大度Δ和最小度δ得到了图G的A_(α)谱半径ρ_(α)的一个上界。此外,还确定了k连通Δ正则图的子图的A_(α)谱半径的上界。

大规模网络中k点连通分量的分布式计算

近年来,k点连通分量(k-VCC)由于其结构内聚性而成为图分析中的一个关键点。k-VCC是指在删除k-1个顶点后剩余的图仍然连通的子图。现有算法对k-VCC问题的研究主要集中在单机环境下,为此,本文设计了一个分布式计算框架,挖掘给定图中的所有k-VCC,将挖掘大图的问题划分为多个更小的子图以并发执行挖掘任务。通过实验证明了所提出的分布式方法的有效性和高效性。

临界k连通图中的点度数

如果在一个k连通图G中删掉任意一个顶点后得到的图都不再是k连通,则称G为临界k连通.Chartrand,Kaugars和Lick证明了每一个临界k连通图(k≥2)都含有一个度数小于(3k-1)/2的顶点.Hamidoune进一步证明了每一个临界k连通图都至少含有两个这样的顶点,并且这一下界是最优的.在本文中,我们证明如果一个临界k连通图恰好含有两个度数小于(3k-1)/2的顶点,则这两个顶点的度数一定是k.

无线传感器网络k点连通可靠性的研究

无线传感器网络的出现引起了人们的广泛关注,由于无线传感器网络的节点不是预先定位而是随机撒放,那么如何保证一定区域内的传感器节点在满足连通可靠性要求的情况下连结成一张网络?而若干次随机抛撒所形成网络的连通度的平均值与网络的节点个数、节点的通讯半径之间又有何关系?通过计算机仿真模拟试验,给出了网络的k(k>0)连通度概率分布曲线;引入了连通度的数学期望概念来描述若干次抛撒所形成网络的连通度k的平均值,给出了其随网络节点个数、节点通讯半径变化的回归方程;给出了无线传感器网络k点连通概率曲线和3点连通的经验公式;分析了边界节点对网络连通度的影响。这些对无线传感器网络节点个数和节点通讯半径的选择、系统冗余设计等都具有重要的指导意义或参考价值。

k道路连通空间

本文给出k连续映射和k道路连通性的定义,讨论k连续映射等价刻画和性质,证明了k连续满映射保持k连通性和k道路连通性,进而研究k道路连通性的基本性质,证明了k道路连通性是k连通的,k道路连通性是同胚不变性和有限可积;最后讨论k道路连通分支。

有向传感器网络中基于概率感知模型的最小连通k覆盖集算法

无线传感器网络的基本问题之一是,网络节点如何利用有限的能量对人们所关注的物理世界进行满意的监测,这可抽象为最小连通k覆盖集问题。传统的最小连通k覆盖集问题是基于确定型全向感知模型的,该模型过于理想化,不能适用于复杂的应用环境,也不能应用于有向传感器网络中。针对上述局限,本文提出了有向传感器网络中基于概率感知模型的最小连通k覆盖集问题(MCKS),并指出这是NP难问题;设计了基于0-1整数规划和最小生成树的集中式近似算法(IPA)和基于覆盖效益探测的分布式近似算法(CBDA),分别证明两种算法最终得到的是MCKS问题的可行解,并分析了算法的时间复杂度、性能比和通信复杂度。通过仿真实验并与ILP算法和DGA算法进行比较的结果表明:在基于概率感知模型的条件下,IPA和CBDA能够有效实现有向传感器网络中的连通k覆盖,并且激活节点数目较少,网络寿命延长。

有向树图的最小K点连通扩充

本文解决了图论的连通性理论中的一个重要的问题———以最小边集扩充一个任意有向树图为K点连通图 ,证明了该问题在算法上属于P问题 ,提出了一个时间复杂度为O(|V|3 )的有效算法DTKA 。

任意有向图的最小K边连通扩充

本文研究了以最小边集扩充一个任意有向图为K边连通有向图这一优化问题。提出了一个复杂度o(|V|5)的有效算法。该算法为可靠网络的计算机辅助设计打下了基础。

基于图压缩的最大Steiner连通k核查询处理

研究了基于图压缩的最大Steiner连通k核查询处理,提出了一种支持最大Steiner连通k核查询的图压缩算法SC,证明了基于SC压缩算法的查询正确性.由于最大Steiner连通k核查询仅需要找到符合要求的连通区域,提出了图压缩算法TC,进一步将压缩图压缩为树.证明了基于压缩树的查询正确性,并提出了线性时间的无需解压缩的查询处理算法.真实和虚拟数据上的实验结果表明：压缩算法平均可将原始图压缩掉88%,且对于稠密的原始图,压缩算法的压缩效果更好,可将原始图压缩掉90%,与在原始图上直接进行查询处理相比,基于压缩图的查询处理算法效率更好,平均提升了1~2个数量级.

不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个k(k≥5是一个整数)连通图G中,如果δ(G)≥k+1,并且G中既不含K_5^-,也不含5K_1+P_3,则G中含有一条k可收缩边.对此进行了推广,证明了在一个k连通图G中,如果δ(G)≥k+1,并且G中既不含K_2+([k-1/2]K_1∪P_3),也不含tK_1+P_3(k,t都是整数,且t≥3),则当k≥4t-7时,G中含有一条k可收缩边.

图是超级λ_k-连通(k=4,5)的一个Ore型充分条件

图的k阶限制边连通度λk(G)对衡量网络可靠性起重要的作用.本文给出图是超级λk(k=4,5)连通的一个Ore型条件.

无向树图的k点连通最小扩充

解决了以最少边集扩充一个任意无向树图为k点连通图这一优化问题,提出了一个计算复杂度为D(|V|~4)的算法。为进一步研究可靠网络的计算机辅助设计打下基础。

无向加权图的K点连通扩充算法

本文首先研究了无权情况下的极小K点连通扩充算法;然后成功地将模拟退火方法应用于任意无向加权图的K点连通扩充问题,提出了一个O(ΩK|V|~4)的近似算法,为解决加权图的扩充问题提供了一种新途径.

任意无向加权图K点连通扩充的逐次改善算法

为了对网络的可靠性寻求较好的近似算法,研究了任意无向不加权图情况下的极小K点连通扩充算法;在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理,并加以证明。最终推出了任意无向加权图K点连通最小扩充的逐次改善算法,应用该算法作了大量例题,得到比较满意的效果。为解决任意无向加权图最小扩充问题给出了一种新途径。