导读:本文包含了最大支撑树论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:组合,算法,方程组,下界,位移,复杂性,顶点。
最大支撑树论文文献综述
杨若望[1]（2018）在《若干情形下最大支撑树部分反问题的研究》一文中研究指出组合优化反问题是指通过改变组合优化问题的权函数,使得给定的一个可行解成为最优解并最小化权函数的改变量.部分反问题是反问题的推广,是指给定组合优化问题的一个部分解(包含在某些可行解中),通过改变权函数,使得存在一个包含部分解的最优解并最小化权函数的改变量.支撑树作为一个经典的组合优化问题,其反问题和部分反问题都得到了广泛的研究.本文主要就最大支撑树的部分反问题(PIMST)进行了研究.本文分为六章.第一章介绍了PIMST的背景、基本概念和记号,并罗列了本文得到的主要结论.第二章主要研究了带容量限制的PIMST问题(CPIMST)最优解的性质,并从基本圈和基本割两方面给出了判定给定权函数是否可行的充要条件.第叁章主要研究了l_∞-范数下的CPIMST问题.利用l_∞-范数下CPIMST问题最优解的性质,找出问题最优值的可选范围,结合二分搜索法给出了求解该问题的计算复杂度为O(mnlog n)的精确算法,并将算法推广至赋权l_∞-范数下CPIMST问题.第四章主要研究了部分解只有一条边时的CPIMST问题.通过若干次固定ω′(e_0)的取值,将问题转化为若干个CPIMST~-问题并找出每个问题的最优解.进一步,在这些解中选取最优的一个作为CPIMST问题的近似解;最后,根据范数的连续性得到了近似解误差上界为(?)?(σ-ω′(e_0)),其中σ是边e_0的取值上界,λ为转化的CPIMST~-问题的个数.第五章主要研究了部分解包含k条边时的CPIMST~-问题.首先,将问题分解为若干个部分解只包含一条边的CPIMST~-子问题;然后,利用已有的算法得到每个子问题的最优解;最后,通过这些最优解得到了原问题的可行解,并证明了近似比的上界为(?).进一步,将得到的结果推广至CPIMST问题.第六章总结了本文的主要结果并展望了后续的研究工作。(本文来源于《兰州大学》期刊2018-04-01）
龚亚娟[2]（2018）在《l_1模下调整最大权值的极大加和支撑树逆问题》一文中研究指出本文研究的是一类在l1模下调整最大权值w的极大加和支撑树逆问题。极大加和支撑树问题是在一个边赋权无向连通图G=(V,E,c,w)中,找一棵最优的支撑树T*,使得目标函数max w(e)+∑c(e)最小,该问题的时间复杂度为0(mlogn),其中m:=|E|,n:=|V|。它的逆问题描述为:给定网络G的一棵非最优的支撑树T0,调整网络各边的权重w到w,使得T0成为新网络G=(V,E,c,w)的最优极大加和支撑树,其中w-l≤w+u,l≥0,u≥ 0。目标函数是使得调整边权的总费用在l1模下尽可能地小,即min ∑q(e)|w(e)-w(e)|,其中q(e)是调整1单位w(e)所需的费用。这篇文章首先建立l1模下极大加和支撑树逆问题的数学模型,并引入符号对模型进行了简化,然后分析该逆问题的可行解和最优解所具有的性质,给出了树边最大权值的上下界。接着考虑了无界单位l1模下的逆问题,针对叁种调整权值的方式进行具体分析,设计了基于基本割和关键边求树外边权值总上调量的子算法,最终给出了无界单位l1模下求解极大加和支撑树逆问题的启发式算法。本文还设计了求解该问题的基于树外边全排列顺序的算法,并通过数值实验将两种算法的运行结果及运行效率进行了对比,说明了该算法的有效性。(本文来源于《东南大学》期刊2018-03-09）
贾俊华[3]（2017）在《l_∞模下调整最大权值的极大加和支撑树逆问题》一文中研究指出本文研究的是l_∞模下调整最大权重w的极大加和支撑树逆问题.极大加和支撑树问题是在一个边赋权无向连通图G(V,E,c,w)中,找一棵最优的支撑树T*,使得目标函数max_(e∈T)w(e)+∑_(e∈T) c(e)最小,该问题的时间复杂度为O(m log n),其中m:= |E|,n:= |V|.它的逆问题描述为:给定网络G的一棵非最优的支撑树T_0,调整网络各边的权重w到(?),使得T_0成为新网络G(V,E,c,(?))下的最优极大加和支撑树,其中w-l≤(?)≤w+u,l≥0,u≥0.目标函数是使得maxe∈Eq(e)|w(e)-(?)(e)|最小,其中q(e)是调整1单位w(e)所需的费用.本文首先分析了该逆问题的可行解和最优解所具有的性质,其次得到了如何通过给定的可行目标函数值构造可行解这个重要结论.最后我们分别讨论了叁种情况.首先在无界的单位无穷模情况下,我们根据最优值的性质设计了二分法确定最优值的下界,进一步根据最优解的性质确定了最优值,并证明了该算法的迭代次数不超过O(m),算法的时间复杂度为O(m~2 log n).在赋权无穷模的情况下,我们先讨论了无界的情况,再推广到一般有界的情况.我们先将已知树上的边分成两类,根据每类边的不同性质设计了寻求最优解的算法.证明了算法最多调用O(m~2)次求解极大加和支撑树问题的算法,因此时间复杂度为O(m~3 log n).(本文来源于《东南大学》期刊2017-03-06）
毛太田,邹凯,毛静,周军[4]（2011）在《基于模糊集的Web文本最大支撑树聚类算法》一文中研究指出当今信息社会,Internet上的信息资源杂乱繁多,用户很难准确地获得所需的信息。对此,本文提出根据特征词在html网页中的title、keywords、description标签的位置来计算各Web文本内容之间的相关度,对Web文档进行模糊聚类的算法,这种基于模糊集的Web文本最大支撑树聚类算法改善了文本聚类的时间和空间的复杂度,减少了文本处理的维度,提高了聚类的速度和精度,从而提高了用户对信息资源获取的方便性。(本文来源于《现代情报》期刊2011年11期）
张春明[5]（2004）在《灰色关联聚类的最大支撑树方法》一文中研究指出This article studies the grey clustering method based on the grey correlation degree, defines the connected intensity,λ-cut graph and connected closure of a weighted graph, gets the properties of the maximum spanning tree, λ-cut graph and connected closure, presents the maximum spanning tree algorithm of grey correlation cluster, and checks the method by an example.(本文来源于《山东交通学院学报》期刊2004年02期）
李帮义,姚恩瑜[6]（2001）在《最小最大后悔支撑树问题》一文中研究指出本文建立了最小最大后悔支撑树问题的模型 .利用划分问题 ,证明了该问题是 NP- C的 .然后利用两个已有的算法 ,给出了上下界估计 .最后对一种特殊情况 ,给出了一个启发式算法 ,并证明了其性能比是紧的(本文来源于《浙江大学学报(理学版)》期刊2001年03期）
张福基,陈治柏[7]（1987）在《支撑树端点数最大值的界》一文中研究指出Schuster,蔡茂诚和林诒勋等研究了无向图支撑树端点数的内插性质。张福基和郭晓峰对有向图也得出了相应的结果。本文目的则是研究支撑树端点数最大值的上下界,显然,我们总可以假定研究的图和有向图无自环,无重边(弧),而且是连通的。以实际背景来看,在建立某个地区的通讯网络时,该系统的支撑树端点数最大的那棵树将给出一个中继点最少(本文来源于《科学通报》期刊1987年07期）
陈惟荣[8]（1982）在《最大支撑树算法在机构学中的应用》一文中研究指出本文利用图论中的最大支撑树算法,建立构件系统的位移方程组或虚位移方程组,可使其中未知量及方程式的数目显着减少。文中为系统瞬时活动度的计算提供了可靠且较简便的普遍计算方法。此外,文中证明了关于系统‘全循环’活动度的一个定理,据此可以确定具有完整、定常约束的系统的‘全循环’活动度。(本文来源于《山东矿业学院学报》期刊1982年01期）
最大支撑树论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文研究的是一类在l1模下调整最大权值w的极大加和支撑树逆问题。极大加和支撑树问题是在一个边赋权无向连通图G=(V,E,c,w)中,找一棵最优的支撑树T*,使得目标函数max w(e)+∑c(e)最小,该问题的时间复杂度为0(mlogn),其中m:=|E|,n:=|V|。它的逆问题描述为:给定网络G的一棵非最优的支撑树T0,调整网络各边的权重w到w,使得T0成为新网络G=(V,E,c,w)的最优极大加和支撑树,其中w-l≤w+u,l≥0,u≥ 0。目标函数是使得调整边权的总费用在l1模下尽可能地小,即min ∑q(e)|w(e)-w(e)|,其中q(e)是调整1单位w(e)所需的费用。这篇文章首先建立l1模下极大加和支撑树逆问题的数学模型,并引入符号对模型进行了简化,然后分析该逆问题的可行解和最优解所具有的性质,给出了树边最大权值的上下界。接着考虑了无界单位l1模下的逆问题,针对叁种调整权值的方式进行具体分析,设计了基于基本割和关键边求树外边权值总上调量的子算法,最终给出了无界单位l1模下求解极大加和支撑树逆问题的启发式算法。本文还设计了求解该问题的基于树外边全排列顺序的算法,并通过数值实验将两种算法的运行结果及运行效率进行了对比,说明了该算法的有效性。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
最大支撑树论文参考文献
[1].杨若望.若干情形下最大支撑树部分反问题的研究[D].兰州大学.2018
[2].龚亚娟.l_1模下调整最大权值的极大加和支撑树逆问题[D].东南大学.2018
[3].贾俊华.l_∞模下调整最大权值的极大加和支撑树逆问题[D].东南大学.2017
[4].毛太田,邹凯,毛静,周军.基于模糊集的Web文本最大支撑树聚类算法[J].现代情报.2011
[5].张春明.灰色关联聚类的最大支撑树方法[J].山东交通学院学报.2004
[6].李帮义,姚恩瑜.最小最大后悔支撑树问题[J].浙江大学学报(理学版).2001
[7].张福基,陈治柏.支撑树端点数最大值的界[J].科学通报.1987
[8].陈惟荣.最大支撑树算法在机构学中的应用[J].山东矿业学院学报.1982
论文知识图
