导读:本文包含了强连通论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:相异,传感器,哈密尔顿,特征值,时间,复杂度,向量。
强连通论文文献综述
胡赢双,陆亿红[1]（2019）在《基于MapReduce的强连通网格聚类算法》一文中研究指出随着位置大数据的爆炸式增长,传统的串行算法已无法对其进行高效地聚类处理,因此,基于MapReduce框架的并行聚类算法研究逐渐成为热点。聚类算法并行化后的聚类质量通常难以保证,因此对并行化聚类结果进行归约的方法极为重要。首先提出基于网格的改进DBSCAN并行化聚类算法,通过该步骤得到每个数据子集的聚类结果。然后在分析网格与簇的关系,定义网格簇和网格簇的连通、强连通概念的基础上,通过计算网格簇之间的连通权值矩阵,对具有强连通关系的网格簇进行归约,构成基于MapReduce的强连通网格聚类算法。该算法可实现位置大数据集的高效聚类。实验分析表明,基于MapReduce的强连通网格聚类算法对位置大数据的处理具有较高的效率和聚类质量。(本文来源于《计算机科学》期刊2019年S2期）
廖小飞,陈意诚,张宇,金海,刘海坤[2]（2019）在《一种高效的面向动态有向图的增量强连通分量算法》一文中研究指出强连通分量(strongly connected component, SCC)算法可以将一个有向图缩略为有向无环图(directed acyclic graph, DAG),广泛应用于可达性查询等有向图分析应用.尽管现有工作已经提出多种面向静态有向图的强连通分量算法,但是它们需要高额的运行时开销来反复对整个图进行全量计算,以响应现实世界中普遍存在的动态有向图结构的频繁变化.其实,在通常情况下,动态有向图每次改变量极小(少于5%).其允许我们以增量的方式对动态有向图进行强连通分量计算,以缩短响应时间.因此,为解决此问题,本文提出了一种高效的面向动态有向图的增量强连通分量算法Incremental Strongly Connected Components Algorithm,简称Inc-SCC,通过对不必要的计算进行裁剪以减少算法的数据访问量和计算量,并利用SCC的不相交性进行并行处理以提升SCC计算效率.其次,提出了一种启发式优化方法进一步加快算法收敛速度.实验结果显示,本方法可以用于实时响应有向图持续性动态变化,并且当整个有向图的边变化比例为5%时,本方法相对于现有算法的加速比可达2.8到12倍,当整个有向图的边变化比例为0.5%时,本方法相对于现有算法的加速比可达2.9到12倍.(本文来源于《中国科学:信息科学》期刊2019年08期）
高策[3]（2018）在《强连通有向图的MSSS问题—Kneser图，区间图》一文中研究指出对于强连通有向图D(V,X)而言,D的一个强连通支撑子图H,若对于Va ∈H,子图H-a都不具有强连通性,那么称H为极小强连通支撑子图.类比于连通图中的支撑树,容易看出一个强连通有向图D包含多个极小强连通支撑子图.我们称D的所有极小强连通支撑子图中包含弧最少的为最小强连通支撑子图DM.对于寻找强连通有向图D的最小强连通支撑子图DM的问题我们称其为MSSS问题.在许多情况下解决强连通有向图D的MSSS问题是非常有用的,但是这个问题很难实现,因为若D包含哈密尔顿圈,那么我们就必须寻找D的哈密尔顿圈.在本文中,我们进一步研究了两类重要的可以找到其最小强连通支撑子图的强连通有向图.本文第一章首先介绍了最小强连通支撑子图问题的研究背景,其次介绍了本文的基本定义和符号,最后简述了本文研究的核心问题,研究进展及本文的主要结果.本文第二章主要是确定了本文的主要研究方法.在第一节给出了可删弧的定义,这也是我们研究方法和算法所涉及的核心定义,第二节利用深度优先搜索算法确定可删弧集,第叁节利用可删弧集内部的相关性定义一个由强连通有向图D(V,X)的可删弧集A(D)决定的无向图GA,并将我们寻找强连通有向图D(V,X)的最小强连通支撑子图DM问题转化为计算无向图GA的最大独立集问题.本文第叁章与第四章,我们会结合第二章给出的算法解决这两个重要图类的MSSS问题,更精确的说,当可删弧集A(D)所构造的无向图GA是Kneser图或者区间图,我们就可以利用算法在多项式时间内计算出强连通图D的最小强连通支撑子图所包含弧的数量或者找出其最小强连通支撑子图.(本文来源于《安徽大学》期刊2018-02-01）
张慧[4]（2017）在《强连通k准传递有向图的结构特征》一文中研究指出对有向图D中的任意一条长为k的路,若起点和终点相邻,则称有向图D是kc准传递有向图.当kc = 2时,称为准传递有向图.kc准传递有向图的概念是由Galeana-Sanchez等人在准传递有向图的基础上提出的.准传递有向图和危准传递有向图是有向图中非常重要的图类,近几年来,有关这类图的结构性质和其它相关内容的研究越来越受到学者们的关注,也取得了很多突出的成果.本文研究直径diam(D)k≥ + 2的强连通kc准传递有向图的性质,并刻画了它的结构.本文共分为叁章.第一章介绍了 kc准传递有向图的研究背景和现状以及一些与本文相关的基本概念.第二章研究了 kc为偶数且diam(D)≥ k + 2的强连通kc准传递有向图D的结构特征.设P是D中的一条长为kc + 2的最短路,得到以下结论:(1)D[V(P)]和D[V(D)V(P)]都是半完全有向图.(2)D有一条哈路.第叁章研究了 kc为奇数且diam(D)≥ k + 2的强连通kc准传递有向图D的结构特征.设P是D中的一条长为kc + 2的最短路,得到以下结论:(1)D[V(P)]或者是半完全二部有向图,或者是半完全有向图.(2)令 = {x ∈ V(D)V(P):(x,V(P))≠(?)且(V(P),x)≠(?)},可以得到 D[BC]或者是一个半完全二部有向图,或者是一个半完全有向图,或者是一个空图.(本文来源于《山西大学》期刊2017-06-01）
徐培培,吴振华[5]（2016）在《无线传感器网络中基于有向图的强连通支配集的构造》一文中研究指出提出一种基于有向图的分布式强连通支配集的构造方法(Ds CDS,Distributed constructing of strongly Connected Dominating Set)。该方法通过分布式的选取权值大的节点,构造性能较优的强连通支配集。实验研究显示:该算法通过构造合理的权值及每次选取最大权值的最好节点,使得最终产生一个性能较优的强连通支配集,可以较大程度的延长无线传感网络的生命周期。(本文来源于《南昌航空大学学报(自然科学版)》期刊2016年02期）
徐培培[6]（2016）在《无线传感网络中强连通支配集的构造研究》一文中研究指出无线传感器网络(Wireless Sensor Networks,WSNs)是随机的撒播于预定区域内(一般环境较差)的数量巨大的传感器节点形成的一种大规模的自组织网络系统,其中的节点通过无线通信和自组织的方式将收集到的信息进行以多跳的方式传递到基站。该网络系统被广泛应用于军事、智慧城市、智能家居等众多领域。WSNs由于在各领域的应用前景,成为了众多研究者的热门研究对象。然而,无线传感网络中传感器节点在具有体积小、处理和储存能力低及能量低等缺陷,加上WSNs部署的环境条件通常较为恶劣,这样的网络特性从而决定了设计无线传感器网络的设计的目标应该是尽可能的均衡的利用节点能量,从而有效使用片上受限资源(能量、内存和处理能力)来保持较长的网络生命周期。因此无线传感器网络的路由研究应该为其研究的重点,通过虚拟骨干网来进行路由管理效率尤其突出,而无线网络将图论中的连通支配集(Connected Dominating Set,CDS)广泛应用来构成虚拟骨干网。因此,对于连通支配集的研究也就具有了非常重要的意义。关于无线传感器网络,在其实际的网络情况中,大多数网络链路是不对称的,因此,我们不能简单地将研究无线传感网络的问题直接抽象为研究简单无向图中连通支配集问题。本文针对无线传感器网络链路不对称、节点资源有限等特性,提出一种无线传感器网络中基于有向图、分布式强连通支配集的构造方法(DsCDS,Distributed constructing of strongly Connected Dominating Set)。首先综合分析影响网络生命周期的各个因素(包括剩余能量、RSSI、节点度及邻居性能)之间的关系,通过权值公式构造一个更能代表节点质量的权值,然后依次通过贪婪策略选取权值较大的节点进行分布式地构造强连通支配集,最终获得一个综合性能较好的强连通支配集。通过算法的仿真实验及相关性能对比分析表明,DsCDS算法通过构造合理的权值及每次选取最大权值的最好节点,使得最终产生一个能量均衡、生命周期较长的强连通支配集。(本文来源于《南昌航空大学》期刊2016-06-01）
钱潮恺,黄德才[7]（2016）在《基于维度频率相异度和强连通融合的混合数据聚类算法》一文中研究指出k-Prototypes算法对初始点选取的敏感性导致聚类结果具有随机性,并且忽视样本数据点与聚类集合中已有样本的总体差异.针对此问题,文中提出基于维度频率相异度和强连通融合的混合数据聚类算法,首先通过多次预聚类产生大量子簇,然后根据子簇之间的连通关系,采用强连通融合的策略得到最终的聚类结果.在UCI数据库中3个混合属性数据集上的实验表明,相比k-Prototypes算法及已有的混合属性聚类算法,文中算法具有更好的聚类质量,从而验证文中算法的优越性.(本文来源于《模式识别与人工智能》期刊2016年01期）
杨倾泉[8]（2015）在《有关连续时间条件下强连通赋权有向图的平均一致性算法》一文中研究指出在本篇文章中提出了一种分布式算法来解决强连通赋权有向图的连续时间平均一致性问题。基于耦合平均一致性算法与拉普拉斯矩阵零特征值对应的左特征向量的估计。解决了连续时间条件下非平衡强连通有向图的平均一致收敛问题；另外一个特点是移除了对自主体出度邻居的信息的要求。论文最后以仿真例子验证了本文的结论。(本文来源于《郑州大学》期刊2015-05-01）
李艳艳[9]（2014）在《κ-强连通竞赛图外弧4泛圈点的研究》一文中研究指出2006年,Feng等人证明了每个k-强连通竞赛图至少包含k+1个外弧4泛圈点.2010年,郭巧萍等人证明了每个k-强连通竞赛图至少包含k+2个外弧5泛圈点.在这篇文章中,我们将对k-强连通竞赛图的外弧4泛圈点做进一步的研究.(本文来源于《应用数学学报》期刊2014年05期）
吴金全[10]（2014）在《有向图的强连通分量及应用》一文中研究指出有向图的强连通分量应用非常广泛,比如有向图的强连通分量数量巨大的时候,为了更加高效必须要用缩点法。深度优先遍历是求有向图的强连通分量的一个有效方法,根据实现方式的不同,总体上,求有向图的强连通分量有叁种算法,分别是Kosaraju算法,Gabow算法和Tarjan算法。叁种算法的时间复杂度均为O(n+e)(n为顶点数,e为边数)。(本文来源于《软件》期刊2014年03期）
强连通论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
强连通分量(strongly connected component, SCC)算法可以将一个有向图缩略为有向无环图(directed acyclic graph, DAG),广泛应用于可达性查询等有向图分析应用.尽管现有工作已经提出多种面向静态有向图的强连通分量算法,但是它们需要高额的运行时开销来反复对整个图进行全量计算,以响应现实世界中普遍存在的动态有向图结构的频繁变化.其实,在通常情况下,动态有向图每次改变量极小(少于5%).其允许我们以增量的方式对动态有向图进行强连通分量计算,以缩短响应时间.因此,为解决此问题,本文提出了一种高效的面向动态有向图的增量强连通分量算法Incremental Strongly Connected Components Algorithm,简称Inc-SCC,通过对不必要的计算进行裁剪以减少算法的数据访问量和计算量,并利用SCC的不相交性进行并行处理以提升SCC计算效率.其次,提出了一种启发式优化方法进一步加快算法收敛速度.实验结果显示,本方法可以用于实时响应有向图持续性动态变化,并且当整个有向图的边变化比例为5%时,本方法相对于现有算法的加速比可达2.8到12倍,当整个有向图的边变化比例为0.5%时,本方法相对于现有算法的加速比可达2.9到12倍.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
强连通论文参考文献
[1].胡赢双,陆亿红.基于MapReduce的强连通网格聚类算法[J].计算机科学.2019
[2].廖小飞,陈意诚,张宇,金海,刘海坤.一种高效的面向动态有向图的增量强连通分量算法[J].中国科学:信息科学.2019
[3].高策.强连通有向图的MSSS问题—Kneser图，区间图[D].安徽大学.2018
[4].张慧.强连通k准传递有向图的结构特征[D].山西大学.2017
[5].徐培培,吴振华.无线传感器网络中基于有向图的强连通支配集的构造[J].南昌航空大学学报(自然科学版).2016
[6].徐培培.无线传感网络中强连通支配集的构造研究[D].南昌航空大学.2016
[7].钱潮恺,黄德才.基于维度频率相异度和强连通融合的混合数据聚类算法[J].模式识别与人工智能.2016
[8].杨倾泉.有关连续时间条件下强连通赋权有向图的平均一致性算法[D].郑州大学.2015
[9].李艳艳.κ-强连通竞赛图外弧4泛圈点的研究[J].应用数学学报.2014
[10].吴金全.有向图的强连通分量及应用[J].软件.2014
论文知识图
