关于最小可行图的一个结果

给出了关于（Ｘ１，Ｘ２，Ｘ３，Ｘ４）的可行图Ｇ＝ＵＧｉ是最小可行图的充分必要条件：Ｇ是连通单圈图；或Ｊ∈（１，２，３，４），当∩Ｘｉ≠时，∩Ｇｉ是树，对任意整数ｎ给出了关于（Ｘ１，Ｘ２，…Ｘｎ）的最小可行图的若干性质，推广了已有的结果。     

修改一类G着色图的一个算法

给出了修改一类G着色图的一算法，并证明了通过第n次循环获得的G－V0的第n 1个着色图一定不同于前n个G－V0的着色图中的任何一个，和具有两个同一分支的连续循环过程不可能无休止地进行下去。     

一个大规模网络撕裂的有效算法

该文对大规模网络分析的撕裂技术提出一种拓扑算法，该算法从求最小割集的角度，对网络进行最优撕裂，其算法理论比较简单，保证在多项式时间内获得撕裂支路数最少的撕裂结果。以图论中邻接矩阵为基础，给出了该算法的理论证明，通过实例应用可以看出该算法效果简捷有效。     

具有唯一定长路的有向图的一个注记

Ｌａｍ和ｖａｎ Ｌｉｎｔ构造了一类具有唯一定长路的有向图Ｄ（ｃ，ｋ），其阶为ｎ＝ｃ＾ｋ＋１，并证明Ｄ（ｃ，ｋ）的自同群包含一个２（ｃ＋１）阶二面体群，其中ｃ为大于１的整数，ｋ为大于１的奇数。本文利用（０，１）矩阵方程的性质证明，对任意的整数ｃ＞１和奇数ｋ＞１，存在ψ（ｋ）（ψ为Ｅｕｌｅｒ函数）个ｎ＝Ｃ＾ｋ＋１阶具有唯一定长路的有路的有向图；它们互不同构且其中每一个图的全自同构群都是２（Ｃ＋１）阶二     

用神经网络新方法求解图的最大独立集问题

在Ｈｏｐｆｉｅｌｄ神经网络优化方法的基础上,根据模拟退炎算法逃离局部最优解的原理,提出了一种神经网络计算的新方法,并用这种方法求解图的最大独立集问题。结果表明,该方法获得最优解比Ｈｏｐｆｉｅｌｄ神经网络优化算法获得的解要好,且所需时间比模拟退火算法少得多。     

最小费用/容量比生成树的一个算法

本文对最小生成树问题作进一步扩展、同时考虑费用和容量,这里费用和容量可根据不同情况赋予不同的含义。要求容量尽可能地大,而费用尽可能地小,并就此问题提出了一个有效的多项式算法。     

直线簇上区间图的最小全控制集和最小配对控制集

研究了广义区间图的最小全控制集和最小配对控制集的计算问题.对有一个公共交点的直线簇上的区间图,给出了计算其最小全控制集的O(n)时间算法和其最小配对控制集的O(n+m)时间算法.     

求二分图所有最小复盖的交的好算法以及由此求所有最小复盖的算法

本文给出了一个求二分图G所有最小复盖的交的好算法,其时间复杂性为O(max{|V(G))|~(1/2)。|E(G)|,|V(G)|~2})。并且在上述基础上再给出求所有最小复盖的算法,其时间复杂性为O(max{|V(G)|~(1/2)·|E(G)|,|V(G)|~2,|C|·|V(G)|})。其中V(G),E(G)分别是G的顶点集,边集,C是G的最小复盖组成的集     

求二分图所有最小复盖的交的好算法以及由此求所有最小复盖的算法

本文给出了一个求二分图G所有最小复盖的交的好算法,其时间复杂性为O(max{|V(G)|~(1/2)。|E(G)|,|V(G)|~2})。并且在上述基础上再给出求所有最小复盖的算法,其时间复杂性为O(max{|V(G)|~(1/2)·|E(G)|,|V(G)|~2,|C|·|V(G)|})。其中V(G),E(G)分别是G的顶点集,边集,C是G的最小复盖组成的集     

一个求图的最大圈的启发式算法

本文给出了无向图、有向图存在哈密顿圈或存在包含顶点数为N_1的最大圈的充分条件,在此基础上给出了求最大圈的找通路一扩大回路算法,这个算法是启发式的,但是有效的。利用此算法可以求出任意图的最大圈,也可以用来搜索图的最佳哈密顿圈。     

判定偶图的一个有效算法

偶图理论及其算法在VLSI设计和其它工程中均有重要的应用。本文从邻接矩阵的理论出发,提出一种有效的算法,将集合的划分,简化为该矩阵的行列交换运算,取得了较好的结果。     

统筹图中求关键路线的一个算法

给出了１个求统筹图中关键路线的多项式算法，证明了该算法的理论依据，分析了它的复杂性为Ｏ（ｎ＾３）。     

关于求Follow集合的一种算法

在构造计算机的编译程序中,常常需要找出句型中每一个非终极符后继符集合,这里用Follow表示这个集合。文中给出一种用布尔矩阵计算Follow集合的算法。     

关于PRIM算法与图的最小树唯一性的讨论

本文通过对Prim算法的修改。给出了赋权无向图有唯一最小树的一个充分必要条件。     

K连通图的k分割多项式算法

图G的K分割问题可描述为:输入(Ⅰ)G=(V,E),G为简单无向图,其中|V|=n,|E|= m;(Ⅱ)a_1,a_2,…,a_k k个G中不同的顶点;(Ⅲ)n_1,n_2,…,n_k k个正整数满足 n_1+n_2+…,+n_k= n.输出(V_1,V_2,…,V_k),对1≤i≤k,满足(Ⅰ)a_i∈V_i;(Ⅱ)G[V_i]是连通图;(Ⅲ)|V_i|=n_i.本文给出时间复杂性为O(knm)通用K连通图的k分割多项式算法.     

由基本割集矩阵求其对应图G的一种算法

本文给出判定含全“1”元素列和不会全“1”元素列两种基本割集矩阵是否有其对应图的充要条件。当满足此条件时,怎样由矩阵得到图,文中给出了一种依据此条件而构造的算法,并给出两个例子来说明这种算法的应用。     

一套有效的指纹图象预处理算法*

主要探讨在开发指纹识别系统中所实现的一套预处理算法,首先讨论了指纹图象的特点。然后,详细介绍了基于这些特点预处理算法,最后对一个处理示例,给出了算法在各个步骤中得到的处理结果。     

最小T－2倍树的构造算法

本文提出了对任意一棵树的顶点赋权使其满足一定约束条件的最小Ｔ－２倍树的定义，并给出了一个时间复杂度为Ｏ（ｎ２）的构造算法     

求图符号控制数的拟人退火算法

为确定图符号控制数的问题提出了几个拟人的求解策略,并基于模拟退火算法和拟人策略,为该问题得出了一个拟人退火算法PA-SDN．实验结果表明,算法PA-SDN能快速收敛到问题的高质量解．