边权相同的最小生成树改进算法

针对当赋权连通图中存在权值相同的多条边时,传统的Kruskal算法不能计算出全部的最小生成树,提出了求解最小生成树的改进算法.实验结果表明,改进算法可以得到一个赋权连通图的所有最小生成树,进而为决策者提供更全面的最优决策方案.     

Kruskal算法在连线问题中的应用

利用Kruskal算法原理,在一个赋权图中,找出具有最小权的连通生成子图即最优树.     

带约束边的最优树问题

本文给出了求解一个赋权图中含有约束边的最优树的两种算法和证明。并在此基础上,给出了关于含有约束边最优树的一些推广问题的算法和证明。     

赋权连通图的最小树图的连通情况

以G的生成树为点,两点相邻的充要条件是两颗生成树只相差一条边,这个图称为G的生成树图。连通图的生成树图是连通的,本文对此进行推广,证明了赋权连通图的最优树图也是连通的。     

赋权连通图的最小树图的连通情况

以G的生成树为点,两点相邻的充要条件是两颗生成树只相差一条边,这个图称为G的生成树图。连通图的生成树图是连通的,本文对此进行推广,证明了赋权连通图的最优树图也是连通的。     

基于DPCNN的无向赋权图的最小生成树的求解

 利用脉冲耦合神经网络(PCNN,Pulse Coupled Neural Network)的脉冲波并行传播特性,在其时延脉冲耦合神经网络(DPCNN,Delay PCNN)的基础上提出了一种求解无向赋权图最小生成树的新算法.算法针对最小生成树的权值总和最小且连通的性质,结合时延脉冲耦合神经网络脉冲波的并行传播,通过求解无向赋权图的最短路径并对其连通性进行判断,采用迭代的方法,成功地求解了无向赋权图的最小生成树.最后给出了仿真实验,证明了该方法的有效性,与传统算法比较有一定的优势.     

求图上广探树的时间复杂度

本文研究如何找连通图的广探树问题,对边权相同的赋权连通图和边权不同的赋权连通图,分别进行了研究.在对图进行广度优先遍历的过程中找到了一棵广度优先树,并总结出:对于边权相同的图而言,至多在O(n)阶多项式步骤下可以找到图的一棵广探树;对于边权不同的图而言,至多在O(n)2阶多项式步骤下可以找到图的一棵广探树.     

关于K棵支撑树的2个问题

给定一个(有向)连通图G=(V，E)，寻找k棵支撑树(边可以重复)，满足树中的边在k棵树中出现的次数不超过其容量，考虑2个问题：①k棵支撑树的费用之和尽可能小；②k棵支撑树中费用最大的尽可能小,给出了问题①的一个最优算法，同时应用该算法，问题②是是近似的。     

最优树的若干问题

利用图的关联矩阵，给出了最优树的矩阵算法，并对当图的一条边的权发生改变后，如何利用原最优树求现最优树作了探讨。     

任意无向图的最小R边连通扩充

研究了以最少边集扩充一个任意无向图为R边连通图这一优化问题。给出了一个复杂度为O(|V|~5)的算法。利用该算法可最优地将所研究图形中任意两点达到所要求的边连通度。它发展了K边连通最优扩充的研究,从而使图的边连通扩充的研究在应用于网络结线的可靠性设计方面更具有实际意义。     

点赋权图上固定顶点的树划分问题

考虑了点赋权图上固定k个顶点的树划分问题.首先证明了点赋树图上固定k个顶点的最小最大树划分问题是NP-难的,然后给出了该问题的一个启发式算法,最后证明了该算法是点赋权完全图上固定k个顶点的最小最大树划分问题的一个2-1k近似算法.     

一类图的特征值

文章将树做了推广,给出了圈树的定义:把树的度数大于3的若干点用相应点度数一样长的圈替换得到的图为圈树。证明了点赋权树T(权重均为正),权和为W,则存在一个点v∈V(T),使得T-v的所有连通片的权和不大于W/2。以此为基础,证明了n阶圈树D,证明了一定存在{u,v},使D-{u,v},所有的连通片的阶都不大于[n/2],最后对圈树的一些特征值阶进行了估计。     

树扩图生成树数的界

连通图的生成树是指该图的极小连通生成子图．在Cayley公式的基础上，给出树扩图生成树数的上下界．     

矩阵方法求赋权图中最短路的算法

目的 给出一些计算赋权图中任意两个节点之间最短路的算法。方法 利用矩阵方法。结果 给出了赋权图中任意两点之间最短路的算法；任意两点之间在含有最少边数情况下的最短路算法；赋权图中的所有最短路算法，以及前N条最短路的算法。结论 所研究的算法解决了传统算法的某些不足，因基于矩阵运算，程序设计简单，实用性强。     

图中生成树数目的一个上界

图论中一个重要的极值问题是刻画具有最大生成树数目的某些图类的特征。利用图中割点数或割边数目,给出了连通图中生成树数目的上界。     

一类特殊的极大＋和支撑树在调整和权值下的逆问题

本文研究的是一类特殊的极大＋和支撑树在调整和权值下的逆问题．给定一个边赋权连通网络G=（VE,c,w）,对于每一条边e∈E,已知一个费用c（e）和一个权值叫（e）,极大＋和支撑树问题是指寻找一棵支撑树T＊,使得其是权值marxw（e）＋∑c（e）最小的一棵支撑树．而在极大＋和支撑树的逆问题中,给定一棵支撑树％,eET它不是已知网络中最优的极大＋和支撑树,要求调整网络中各边的费用c（e）,使死变成调整后网络中最优的极大＋和支撑树,目标函数是使得在l1模意义下的边权调整费用尽可能的小．本文针对已知网络中各边费用都相等这一特殊情况,给出了求解该逆问题的列生成算法,每次迭代时入基向量的选择可以转化为一个新参数下的极大＋和支撑树问题,从而可在多项式时间内确定入基向量的选择．本文最后给出了一个实例说明算法的有效性．     

关于树与完全图的笛卡尔乘积图的连通测地数

给出了两个非平凡图,确定了树与完全图的笛卡尔乘积图的连通测地数.测地数与连通测地数是图的两个重要参数.树与完全图的笛卡尔乘积图的测地数已被确定.     

基于生成树的低压电力线载波的STTDA算法

针对低压电力线载波网络拓扑发现问题,以连通图的方式表达并分析智能电表节点以及节点间的关系,利用生成树集合演绎树的变化过程来完成通信网络拓扑发现,给出了节点关系的判定规则,提出一种基于生成树的低压PLC网络拓扑发现算法(STTDA),通过实验分析了STTDA算法的关键因素及实现效率.     

一类工件带有优先约束的分批排序问题

本文对工件带有“扩充链”优先约束的分批排序问题进行了研究,其目标函数为最大完工时间．优先约束为：在一个扩充链上包含有n个工件,另外有m个孤立点工件（即工件之间无任何优先约束）．讨论了时问题的最优算法,把这一问题多项式转化成了组合优化中求解非二部图赋权匹配问题,并相应地给出了一个运算次数为的多项式算法．     

等参数图的最大与最小距离树对及其在电网络分析中的应用

本文推广了线图的树对及其距离的概念,提出了等参数图及其树对和树对之距离的概念。给出了等参数图中任一树对为一最大(或最小)距离树对的充分必要条件和相应的算法,讨论了等参数图中最大与最小距离树对在电网络分析中的应用,给出了网络图主划分算法1的对偶算法和电网络的最优调和分解算法。