导读:本文包含了连通指数论文开题报告文献综述及选题提纲参考文献，主要关键词:关键节点问题,树,动态规划算法,时间复杂度
连通指数论文文献综述
刘超[1]（2018）在《综合考虑连通指数、度和连通分支属性的关键节点问题》一文中研究指出本文主要研究的是无向图上关键节点问题:在一个无向图G中,删除某些节点,使得剩余图在某种意义下的连通性尽可能小.通过分析前人研究的优势与不足之处,提出两个新的模型,综合考虑图的连通指数、度以及连通分支属性,使得剩余图的连通性尽可能小.第一章首先介绍了关键节点问题的研究背景及研究意义,然后从社会网络分析方法以及系统科学分析方法两个角度介绍了关键节点问题的国内外研究现状,列出目前已有的一些关键节点问题模型,最后介绍了本文所需要的图以及动态规划算法的相关预备知识.第二章我们分析对比了目前已有的关键节点问题模型,发现它们在剩余图的均衡性描述方面存在不足,即可能出现在删除点之后,存在多个孤立点同时还存在一个较大的连通分支的极限情形,导致剩余图的分布极不均衡.鉴于此,我们以连通指数和及度和作为图的连通性优化目标,在约束条件中考虑了连通分支属性,主要提出了两个新模型,即在连通分支大小有界时的最小连通指数与度的和关键节点问题和在连通分支大小和分支数有界时的最小连通指数与度的和关键节点问题.第叁章和第四章在内容结构上是类似的,主要考虑的是树上单位点权情形下两个新模型的求解.我们先给出了两个新模型的动态规划解法,分析了其时间复杂度,但是,此动态规划算法的时间复杂度并不是多项式时间.因此我们对该算法的具体实现方式进行了改进,设计了一个新的数据结构——节点i的最左s-子树Ti1:s,并将其分解为最左s-1-子树Ti1:s-1与子树Tis的并集,通过综合利用这两个子树的解来计算Ti1:s上的目标函数值,以此形成一个连续的动态规划过程,将上述指数时间动态规划算法改进成多项式时间的动态规划算法.同时将算法利用MATLAB软件将其编程实现,进行了大量的数据实验,根据实验结果来看,该算法具有较好的运行效率.第五章主要对本文的相关工作进行了总结与展望.(本文来源于《东南大学》期刊2018-05-01）
秦倩楠[2]（2018）在《广义和连通指数极值问题的研究》一文中研究指出图的广义和连通指数作为新提出的一类分子拓扑指数,在QSPR/QSAR中有很大的应用价值.树图、圈图、仙人掌图的极值问题已取得很多结果,本文主要研究叁圈图及具有完美匹配的仙人掌图的极值问题.第一部分介绍了连通性指数的研究基础和国内、外的发展现状,及其一些定义、相关的一些结论以及本文的主要结论;第二部分限制-1??(27)0,对叁圈图的广义和连通指数进行了研究.通过对叁圈图的分析,构造了一种图的变换,指出在叁圈图中广义和连通指数的极小值必由其中的七种类型图取得.然后通过悬挂边的变换,最终得到叁圈图广义和连通指数的极小值并刻画了唯一的极图;第叁部分限制-0.585??(27)0,对具有完美匹配的仙人掌图的广义和连通指数进行了研究.通过分析,利用一种图的变换,将符合条件的仙人掌图缩小范围,然后通过数学归纳法进行证明,最终解决了具有完美匹配的仙人掌图的广义和连通指数的极值问题,取得极小值并刻画出对应的极图.(本文来源于《中北大学》期刊2018-04-01）
秦倩楠,邵燕灵[3]（2018）在《叁圈图的极小广义和连通指数》一文中研究指出图的广义和连通指数作为新提出的一类分子拓扑指数,在QSPR/QSAR中有很大的应用价值.树图、单圈图和双圈图的极值问题已取得很多结果,而叁圈图相关问题的研究较为复杂.限制-1≤α<0,对叁圈图的广义和连通指数进行了研究.通过对叁圈图的分析,构造了一种图的变换,指出在叁圈图中广义和连通指数的极小值必由其中的七种类型图取得.然后通过悬挂边的变换,最终得到叁圈图广义和连通指数的极小值并刻画了唯一的极图.(本文来源于《运筹学学报》期刊2018年01期）
林金广[4]（2017）在《以剩余图的连通指数与度为优化目标的关键节点问题》一文中研究指出本论文研究的是关键节点问题:在无向图G上,删去一些点的集合,使得导出子图在某种意义下的分散程度尽可能大.本文提出一个新的思路来描述图的分散程度,即综合考虑剩余图的连通指数和剩余图的度的关系,通过优化它们之间的关系来使得剩余图不连通性增加,从而使得图分散的结果更好.第一章介绍了关键节点问题的背景知识以及一些前人提出的描述图的分散程度的函数,并列出了本文研究所需要的一些预备知识.第二章研究了综合考虑剩余图的连通指数和剩余图的度的关系后树上的关键节点问题的动态规划解法.我们分析其时间复杂度为O(n3K2),并进行数值试验和结果分析.第叁章我们的目标函数综合考虑了剩余图的连通指数,剩余图的度和,剩余图的最大度这叁个因素的关系.在这一章节,我们考虑了删除点的权重wi以及删除的对应的边的权重cij.我们先从树上的问题开始考虑,然后再推广到一般图上.对于树上和一般图上,我们都针对不同的wi和cij考虑了六种情况,包括(0,1),(0,≥ 1),(1,0),(≥1,0),(1,1),(≥ 1,≥ 1),其中两个元素分别表示点权向量w和边权矩阵向量c的取值情况,对于不同的系数组合,我们都提出了对应的寻找关键点的贪婪算法.在不同的情况下,我们都进行了不同的数值实验.第四章对本文的研究工作作出总结与展望.(本文来源于《东南大学》期刊2017-01-16）
郭文涛,赵飚[5]（2016）在《和连通指数和色数的一个关系》一文中研究指出目的研究简单图的和连通指数和色数的一个关系。方法对和连通指数删除一个最小度点的作用。结果与结论设图G的和连通指数为X(G),v是G中最小度的点,G-v是G中删除点v后得到的图,可证得结论 X(G)≥X(G-v)并且得到和连通指数X(G)和色数χ(G)的一个关系χ(G)≤2 X(G)。(本文来源于《宝鸡文理学院学报(自然科学版)》期刊2016年01期）
汤自凯,侯耀平[6]（2015）在《关于第二原子键连通指数（英文）》一文中研究指出设G=(V,E)是简单连通图,第二原子键连通指数是一种的新的原子键连通指数ABC2,即ABC2=ABC2(G)=∑uv∈E(G)(nu+nv-2/nunv)1/2,其中nu(nv)表示图中到边e=uv的顶点u(v)距离比到顶点v(u)距离小的顶点数.本文刻画了具有第一小、第二小与第一大、第二大第二原子键连通指数的树及具有最小第二原子键连通指数的单圈图.(本文来源于《湖南师范大学自然科学学报》期刊2015年04期）
谢琼珠,詹欣豪[7]（2014）在《乘积形式的离心连通指数》一文中研究指出设G=(V,E)是一个图,定义ηc(G)=∏uv∈E(G)(eu+ev),eu表示u点在G中的离心率,ηc(G)表示图G的乘积形式的离心连通指数,该指数对有机分子的结构、性质具有良好的预测作用.通过计算,给出用其他图的不变量对离心连通指数建立上界和下界的方法.此外,还找出了在直径为d、顶点数为n的树(2≤d≤n-2,n>5)中,乘积形式的离心连通指数的最小值,并推断出顶点数为n的树中,倒数前3位的乘积形式的离心连通指数的3种树如下:1)Sn;2)n个顶点的双星图;3)对有5个顶点道路的中心添加(n-5)条悬挂边而成的树.(本文来源于《肇庆学院学报》期刊2014年02期）
李小新,查淑萍,范益政[8]（2014）在《连通图的Harary指数上界及其极图》一文中研究指出图的Harary指数定义为图的所有顶点对的距离的倒数之和.刻画了在给定点数和直径的图类中,Harary指数达到最大的极图,并由此确定了Harary指数关于直径的一个上界.另外,在n阶连通图中,刻画了Harary指数达到第二大和第叁大的图的结构.(本文来源于《中国科学技术大学学报》期刊2014年02期）
侯远[9]（2014）在《连通图的度距离和Wiener指数》一文中研究指出令P+(n)表示圈没有公共边的n阶连通图的集合,P+(n,m)表示P+(n)中具有m(m≥1)个极小圈的连通图集合.证明了当n≥6时,P+(n,m)中具有最小度距离的图是花F(n,m),它是m个具有一个公共顶点的叁角形并在公共顶点粘上n-1-2m条悬挂边的图;同时证明P+(n)中具有最小度距离的图是F(n,1),它是一个叁角形并在一个顶点上粘n-3条悬挂边的图.(本文来源于《福州大学学报(自然科学版)》期刊2014年01期）
许丽[10]（2013）在《叁圈图和连通指数的研究》一文中研究指出图论是数学的一个分支,图论中的图可以代表很多含义,因此图论在很多方面都有很多重要的应用。近年来图论和许多应用学科结合,形成分支学科。例如：代数图论、拓扑图论、化学图论、算法图论、随机图论等。其中分子拓扑指数是现代化学图论中最活跃的研究领域之一。自从H.Wiener在1947年提出第一个分子拓扑指数即Wiener指数以来,数百种分子拓扑指数,包括和连通指数被广泛的研究和应用。本文主要研究了化学图论中的和连通指数并找出了相应的极图,全文共分为叁章,具体组织结构如下：在第一章中,主要介绍有关和连通指数的研究背景以及本文中可能用到的有关图论基础知识,重点介绍并证明了4个重要的变换及5个引理。在第二章中,关于和连通指数的一些研究成果,重点介绍了树,单圈图,双圈图的最大和连通指数,并用上面介绍的引理重新推导出单圈图,双圈图的最大和连通指数并找出相应的极图。在第叁章中,运用引理1.2,1.3,1.4,1.5推导出只含有叁个圈的叁圈图的最大和连通指数并找出相应的极图。(本文来源于《安徽大学》期刊2013-03-01）
连通指数论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
图的广义和连通指数作为新提出的一类分子拓扑指数,在QSPR/QSAR中有很大的应用价值.树图、圈图、仙人掌图的极值问题已取得很多结果,本文主要研究叁圈图及具有完美匹配的仙人掌图的极值问题.第一部分介绍了连通性指数的研究基础和国内、外的发展现状,及其一些定义、相关的一些结论以及本文的主要结论;第二部分限制-1??(27)0,对叁圈图的广义和连通指数进行了研究.通过对叁圈图的分析,构造了一种图的变换,指出在叁圈图中广义和连通指数的极小值必由其中的七种类型图取得.然后通过悬挂边的变换,最终得到叁圈图广义和连通指数的极小值并刻画了唯一的极图;第叁部分限制-0.585??(27)0,对具有完美匹配的仙人掌图的广义和连通指数进行了研究.通过分析,利用一种图的变换,将符合条件的仙人掌图缩小范围,然后通过数学归纳法进行证明,最终解决了具有完美匹配的仙人掌图的广义和连通指数的极值问题,取得极小值并刻画出对应的极图.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
连通指数论文参考文献
[1].刘超.综合考虑连通指数、度和连通分支属性的关键节点问题[D].东南大学.2018
[2].秦倩楠.广义和连通指数极值问题的研究[D].中北大学.2018
[3].秦倩楠,邵燕灵.叁圈图的极小广义和连通指数[J].运筹学学报.2018
[4].林金广.以剩余图的连通指数与度为优化目标的关键节点问题[D].东南大学.2017
[5].郭文涛,赵飚.和连通指数和色数的一个关系[J].宝鸡文理学院学报(自然科学版).2016
[6].汤自凯,侯耀平.关于第二原子键连通指数（英文）[J].湖南师范大学自然科学学报.2015
[7].谢琼珠,詹欣豪.乘积形式的离心连通指数[J].肇庆学院学报.2014
[8].李小新,查淑萍,范益政.连通图的Harary指数上界及其极图[J].中国科学技术大学学报.2014
[9].侯远.连通图的度距离和Wiener指数[J].福州大学学报(自然科学版).2014
[10].许丽.叁圈图和连通指数的研究[D].安徽大学.2013