基于最小支撑树模型的镇辖村级燃气管网规划布局研究——以长阳县龙舟坪镇为例

在“乡村振兴”的时代背景下,以长阳县龙舟坪镇为例,应用图论中的最小支撑树理论模型,结合卫星影像GIS测量技术,研究了镇辖村级地下燃气管网的规划布局,研究结果为当地城乡建设局与城乡规划部门提供了科学且可靠的总体实施方案,具有重要的参考价值。Under the era background of “rural revitalization”, taking Longzhouping Town of Changyang County as an example, the planning and layout of the village level underground gas pipeline network under the jurisdiction of the town was studied by using the minimum spanning tree theory model in graph theory and combining with the satellite image GIS measurement technology. The research results provide a scientific and reliable overall implementation plan for the local urban and rural construction bureau and the urban and rural planning department, which has important reference value.

经济距离、最小支撑树与信息产业链分析

识别信息产业链,对优化我国信息产业结构,提高我国信息产业的整体竞争力尤为重要。文章以平均步长表示产业间的经济距离,即产业之间距离的远近;引入图论中的最小支撑树方法,测度各产业在信息产业链中的位置;最后,利用时序投入产出表分析了信息产业链的发展变化,比较了竞争模型和非竞争模型下测度信息产业链的差别。结果表明:(1)电子产品制造业产业链中存在复杂的间接依赖关系和直接依赖关系,相关联的产业中大部分为制造业,信息服务业产业链关系相对简单,大部分关联产业属于第三产业,经济距离较近;(2)信息产业链的最小支撑树一方面显示信息制造业、信息服务业、电器器材业以及仪器仪表业的中心地位,另一方面显示信息产业依赖于金属矿资源;(3)信息产业链在一段时间跨度下较为稳定,在非竞争模型中信息产业链变短,产业之间的经济距离更近。

求最小支撑树的方法探讨

针对关系矩阵表示的复杂网络图 ,分析构成其最小支撑树的元素特点 ,提出两种求最小支撑树的方法 :直接生成法和表上作业法 .两种方法不需要作出复杂的网络图 ,而直接从关系矩阵中生成最小支撑树 ,从而能有效克服传统方法需绘网络图之不便 .经实例研究 ,两种方法在求解复杂问题的最小支撑树时有独到之处 .

最小支撑树算法在基因表达数据聚类分析中的应用

聚类分析已成为对基因表达数据进行挖掘以提取生物医学信息的主要方法。本文提出了基于图论的最小支撑树(Minimum spanning tree,MST)聚类算法,用MST表示多维基因表达数据,可将数据的聚类转换为对最小支撑树的分割,相对于传统聚类方法,最小支撑树算法具有形象直观、对一些准则函数能产生全局最优解等优点;将MST算法分别与Memetic algorithm及人工免疫算法(Artificial immune network,aiNet)相结合,则产生更优化的聚类结果。对酵母基因表达数据的实验结果表明,最小支撑树聚类算法是一种有效的基因表达数据的聚类方法。

附有条件的最小支撑树算法

传统最小生成树算法不能解决:度约束条件下的最小支撑树问题;动态网络的最小支撑树问题;边约束条件下的最小支撑树问题。遗传算法可以求解度约束条件下的最小支撑树问题,但存在效率低、编码复杂等缺陷。归纳了3类附有条件的最小支撑树数学模型,在最小支撑树传统算法基础上,提出了3类附有条件的最小支撑树算法。算法测试和比较表明:附有条件的最小支撑树算法是完全可行和有效的。

约束最小支撑树(C-MST)问题:复杂性和上下界估计

本文首先建立了约束最小支撑树问题的模型 ,利用背包问题的复杂性 ,证明了该问题是 NP-完全的 .然后利用一个广义线性规划的对偶算法 ,对目标函数的上下界作出了估计 。

最小支撑树的新算法

从树的等价定义出发,叙述并证明了一种不必考虑圈的求最小支撑树的算法.

单联聚类法与最小支撑树

讨论聚类分析中的单联算法与图的最小支撑树的联系，证明它给出的 ｍ —剖分既是分离量最大的又是

基于直觉模糊集的随机最小支撑树选取

为解决复杂环境下网络拓扑中节点选取难的问题,提出一种基于直觉模糊集的随机最小支撑树选取方法。通过剖析网络拓扑结构中信息的随机、模糊等不确定性,将随机模糊变量扩展为随机直觉模糊变量,对拓扑结构中的边权进行度量。将网络拓扑结构中的最小支撑树问题转化为随机直觉模糊支撑树问题,利用截集去模糊化和Prim算法求取最优解,以优化网络的拓扑结构。通过网络实验验证了所提方法的有效性和合理性。

最小支撑树聚类分析在县级医院信息资源共享分类中的应用

目的介绍最小支撑树聚类分析及其在县级医院信息资源共享分类中的应用。方法采用最小支撑树聚类分析法分析县级医院信息资源共享的数据。结果利用最小支撑树聚类分析法可以将15所医院按信息系统当前状态分为5类。结论客观事物性质变化没有明显标志时,最小支撑树聚类分析法可以构造最小支撑树,确定长边进行分类,与其他聚类分析方法相比,其具有分类结果直观形象、结果容易理解的特点。

基于最小支撑树的光纤布线——以福建师范大学福清分校为例

信息技术的迅猛发展,人们对数据的通信要求的质量也越来越高,为了全校师生员工的科研、教学和信息检索提供了更好的网络服务.文章使用最小支撑树来解决校园网光纤布线,在提高学校网络服务效率的同时减少费用的支出,达到效率和成本兼顾.

多参数最小支撑树问题的复杂性和算法

建立了多参数最小支撑树问题 (RMST)的模型 ,并证明该问题是 NP-完全的。利用经典 Greedy算法 ,给出了该问题的一个近似算法 ,并分析了该近似算法的性能比 ,证明了所给出的界是紧的。

求解运筹学最小支撑树模型的一种新算法

为了简化对运筹学中最小支撑树模型编写简单计算机程序来实现求解,设计了一种新的简便算法----"节点列表判定法"。该算法是用节点来表述网络图的边,并从节点列表中找到了构成圈的特征结构,以此作为判定条件来确定网络图是否有圈存在。在最小支撑树模型的求解过程中,选择网络图中权数最小的边为支撑树的边。每选择一条边就判定一次,若判定有圈存在则放弃最后选择的边,反复选择边并判断,直到所有已选择的边都不构成圈且总边数等于点数-1,那么新确定的支撑树就是一个最小支撑树。这种新的算法已经Excel-BVA编制求解程序验证了其正确性、实用性和快捷性。

一种基于Split—findmin和Set—maxima的最小支撑树灵敏度分析方法

本文首先根据最小支撑树的截性质和圈性质给出了灵敏度分析的基本公式,然后基于现代图论算法中经典的Split—findmian数据结构介绍了树上边的灵敏度分析算法,最后将非树边的灵敏度分析转化为已有成熟的算法的Set—maxima问题进行处理.

最小支撑树的一种删除大权边算法及应用

最小支撑树的一种删除大权边算法是在Kruskal算法、Prim算法和破圈法的基础上,提出的另一种算法。介绍了删除大权边算法的基本概念和性质,列举了删除大权边算法的计算实例,叙述了删除大权边算法的及其应用。

最小支撑树在区域电网优化中的应用

合理地进行电网规划可以获得巨大的社会效益和经济效益。因此针对电网规划的特点,论文利用最小支撑树对电网进行优化,在优化基础上考虑N-1可靠性约束条件,对优化结果进行了修正和经济分析。修正的结果满足电网建设的可靠性要求,并符合经济性原则,因此该方法科学、可行。

约束最小支撑树问题

主要研究两类约束最小支撑树问题,即点约束和边约束最小支撑树问题.点约束最小支撑树问题主要研究了点v不是叶子和点v是叶子两个具体约束问题,边约束最小支撑树问题的约束条件分别为包含给定边e0和不包含给定边e0,对上述问题分别给出了一些基本定理和算法.

最小支撑树混合贪婪算法求解车辆路径问题

优化车辆路径可降低物资配送的服务成本,提高服务效率.建立了车辆路径问题的数学模型.针对一定规模客户的情形,先用最小支撑树算法将客户分区;然后对每个区域中路线用的贪婪算法进行优化;最后通过实例验证,该方法比四叉树混合蚁群算法的计算结果更优、计算速度更快.

基于LINGO的最小支撑树问题的模型与解法

研究了图与网络领域中的一类经典问题——最小支撑树问题,分析其现有算法的不足,通过引入0-1变量和辅助变量,根据最小支撑树的本质属性,从两个角度建立了最小支撑树问题的整数规划模型,编写了与模型相对应的LINGO程序。实证分析验证了模型的正确性,比较了两种建模模式的优劣。

单位无穷范数下边权有界的最小支撑树逆最优值问题

研究了单位l范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络G=(V,E,w),支撑树T^(0),下界向量l,上界向量u及数值K,寻求一个新的边权向量w满足上下界约束l≤w≤u,且T^(0)是在向量w下权值为K的一个最小支撑树,目标是在单位l范数下使得修改成本‖w-w‖最小。本文给出了该问题的数学模型,分析了其最优性条件,设计了求解该问题的时间复杂度为O(|V||E|)的强多项式时间算法。