导读:本文包含了强连通有向图论文开题报告文献综述及选题提纲参考文献，主要关键词:强连通分量,动态有向图,增量计算,收敛
强连通有向图论文文献综述
廖小飞,陈意诚,张宇,金海,刘海坤[1]（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期）
高策[2]（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）
张慧[3]（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）
徐培培,吴振华[4]（2016）在《无线传感器网络中基于有向图的强连通支配集的构造》一文中研究指出提出一种基于有向图的分布式强连通支配集的构造方法(Ds CDS,Distributed constructing of strongly Connected Dominating Set)。该方法通过分布式的选取权值大的节点,构造性能较优的强连通支配集。实验研究显示:该算法通过构造合理的权值及每次选取最大权值的最好节点,使得最终产生一个性能较优的强连通支配集,可以较大程度的延长无线传感网络的生命周期。(本文来源于《南昌航空大学学报(自然科学版)》期刊2016年02期）
杨倾泉[5]（2015）在《有关连续时间条件下强连通赋权有向图的平均一致性算法》一文中研究指出在本篇文章中提出了一种分布式算法来解决强连通赋权有向图的连续时间平均一致性问题。基于耦合平均一致性算法与拉普拉斯矩阵零特征值对应的左特征向量的估计。解决了连续时间条件下非平衡强连通有向图的平均一致收敛问题；另外一个特点是移除了对自主体出度邻居的信息的要求。论文最后以仿真例子验证了本文的结论。(本文来源于《郑州大学》期刊2015-05-01）
吴金全[6]（2014）在《有向图的强连通分量及应用》一文中研究指出有向图的强连通分量应用非常广泛,比如有向图的强连通分量数量巨大的时候,为了更加高效必须要用缩点法。深度优先遍历是求有向图的强连通分量的一个有效方法,根据实现方式的不同,总体上,求有向图的强连通分量有叁种算法,分别是Kosaraju算法,Gabow算法和Tarjan算法。叁种算法的时间复杂度均为O(n+e)(n为顶点数,e为边数)。(本文来源于《软件》期刊2014年03期）
王晓丽,王世英[7]（2014）在《非极大弧连通有向图弧连通度的下界》一文中研究指出设D是一个有向图,δ(D)是最小度,弧连通度为λ(D),则λ(D)≤δ(D)。当λ(D)<δ(D)时,称有向图D是非极大弧连通的。本文给出了非极大弧连通图的弧连通度的下界。(本文来源于《山东科学》期刊2014年01期）
张崧[8]（2013）在《强连通半传递有向图的弧连通性》一文中研究指出有向图D=(V，E)被称为是最优弧连通的,如果λ(D)=δ(D).此外,有向图D被称为是超弧连通的,如果每个最小的弧割都是其某个点的入弧集或者出弧集.以X1和X2为两部的一个有向二部图是半传递的,如果自同构群Aut(D)分别传递的作用在X1和X2上如果有向图D的任意一个点u的出度等于入度,则称D是平衡的.在这篇论文中,我们证明了强连通的半传递有向图是最优弧连通的.此外,我们还证明了除了少部分例外,强连通半传递平衡有向图是超弧连通的.本文结构如下：第一部分是前言,简要介绍了与有向图弧联通性和超弧连通性相关的一些概念,弧传递相关概念,以及半传递图的相关概念.简要回顾了有向图的弧连通性研究的现状.第二章通过我们分的析研究,解决了强连通半传递有向图的弧连通性,得到了强连通半传递有向图是最优弧连通的.第叁章我们讨论了强连通半传递平衡有向图的超弧连通性,刻画了不是超弧连通的图类.(本文来源于《新疆大学》期刊2013-06-30）
李春芳,林上为[9]（2013）在《存在至少2个非临界点的强连通有向图》一文中研究指出证明顶点数为n≥3,弧数为m≥(n/2)+2的强连通有向图D中存在两个不同的顶点u*,v*,使得D-u*和D-v*都是强连通的;并用例子说明这里所给的关于弧数的下界是紧的.(本文来源于《山西大学学报(自然科学版)》期刊2013年02期）
尹作香,邵燕灵[10]（2012）在《本原极小强连通有向图的重下scrambling指数》一文中研究指出利用图论、数论的相关知识,分析了图中每一点经过t长途径所到达的点的集合,再结合scrambling指数和重下scrambling指数的定义刻画了本原极小强连通有向图的重下scrambling指数的界.(本文来源于《河南师范大学学报(自然科学版)》期刊2012年06期）
强连通有向图论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
对于强连通有向图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的最小强连通支撑子图所包含弧的数量或者找出其最小强连通支撑子图.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
强连通有向图论文参考文献
[1].廖小飞,陈意诚,张宇,金海,刘海坤.一种高效的面向动态有向图的增量强连通分量算法[J].中国科学:信息科学.2019
[2].高策.强连通有向图的MSSS问题—Kneser图，区间图[D].安徽大学.2018
[3].张慧.强连通k准传递有向图的结构特征[D].山西大学.2017
[4].徐培培,吴振华.无线传感器网络中基于有向图的强连通支配集的构造[J].南昌航空大学学报(自然科学版).2016
[5].杨倾泉.有关连续时间条件下强连通赋权有向图的平均一致性算法[D].郑州大学.2015
[6].吴金全.有向图的强连通分量及应用[J].软件.2014
[7].王晓丽,王世英.非极大弧连通有向图弧连通度的下界[J].山东科学.2014
[8].张崧.强连通半传递有向图的弧连通性[D].新疆大学.2013
[9].李春芳,林上为.存在至少2个非临界点的强连通有向图[J].山西大学学报(自然科学版).2013
[10].尹作香,邵燕灵.本原极小强连通有向图的重下scrambling指数[J].河南师范大学学报(自然科学版).2012