指定根的最小树形图的一个算法

文[1]给出了求有向图的最小树形图的算法,[2]中给出了求有指定根的最小树形图的算法.本文采用了[1]和[2]中的收缩回路的方法,给出了求有指定根的最小树形图的一个算法.设有向图G=(X,U),其中X={x_1,x_2,…,x_n}是顶点的集合,     

关于有向图上的最小树形图——具等双回路特性的情况

如果我们要在某些城镇之间建立联系这些城镇的线路(例如电线等),假设线路的交叉点只能在代表这些城镇的点上,如何能使设立的线路总长度最短呢?这类问题在图论上叫无向图上的最小树问题。又如渠道设计中,有一个水源,要把水引到若干个点上,要求渠道的分叉点必须是在给定的点上,希望设计的渠道路线总长度最短。它和最小树问题的区别在于两点之问水流是有方向的,称谓有向图上的最小树形图问题。这些问题在理论上和实际应用中均有一定的意义。最小树形图和一类有向截集有对偶性的联系。寻求最小树的方法要点是,对每一点,在以其为顶点的所有边中选一条最短的,然后把由此产生的部分图中的每个连通片中收缩成一点,对新图重复上述步骤。求最小树形图时,对每一点取指向这个顶点的一条长度最短的弧。收缩时,不是收缩一个连通片,而只能收缩每个连通片中的一条回路。因此前者的收敛速度要比后者快。本文对于具有从无向图到有向图过渡性质的一类有向图提供了一个算法,寻求其最小树形图时,可以收缩一个连通片。     

具次约束的最优树形图问题

给定一有向图G_0,其某一结点v_s称为特定结点,它共有p条出弧:α_1,α_2,…,α_p,分别指向结点v_1,v_2,…,v_p,这p个结点称为(v_s的)邻点。令T为G_0的一个支撑树形图,若其结点v_s有且仅有k条出弧,则T称为(k)支撑树形图。设对G_0的每一条弧α,均给以一弧长w_0(α),则弧长之和最小的支撑树形图称为最优树形图。若在一个最优树形图中,其结点v_s有且仅有k条出弧,则此最优树形图称为最优(k)树形图。而在所有(k)支撑树形图中,其弧长之和最小者称为(k)最优树形图。显然,一个最优(k)树形图必为     

非线性常微分方程边值问题的有限解析法

本文根据[1]和[2]中提出的有限解析法的基本思想,推导出求解非线性常微分方程两点边值问题的简便公式,并且从理论和实际计算证明了这个方法精度高、收敛快、稳定性好.对于用通常方法求不出合理结果的问题,用此方法可以求出很好的解.     

"求线性规划问题可行基的一种方法"的注记

文[2]通过两个反例的计算,认为文[1]所提出的求LP可行基的方法有不妥之处,并对[1]的方法中主要步骤作了修正。本文对[1]的算法中轴心项的选取作进一步说明,对[2]中所提出的反例以[1]中算法进行计算与[2]对比分析,说明[2]中的反例并不成立。     

关于有向整谱图的若干存在性问题

系统的回答了[1]在1974年提出的关于有向整谱图的两个问题：1．什么样的非对称强连通有向图是整的？是否存在这样的有向图？2．什么样的多重有向图是整的？。     

二级线性价格控制问题的满意解的求解思路及实例

本文就文献 [1]对线性二级价格控制问题 (BLP) 2 研究的结果及文献 [2 ]提出的问题进行了进一步的讨论。用反例指出文 [1]求出的极点最优解是错的 ,以及一般的 (BL P) 2 问题求出的最优解 ,可能是下层决策者根本无法接受的。因此 ,本文提出 (BLP) 2 的求下层目标最优解的边界搜索法及在此基础上用多目标的观点来求 (BLP) 2 的满意解的思路及实例     

关于一类带风向的投递员问题

E.Minieka在[1]中提出了所谓带风向的投递员问题(Windy Postman Problem),其提法是:设G=[V,E]是一个连通无向图,又设对于E的每一条以s、t为端点的边来说,从s走向t和从t走向s的距离不一定相同,要求在这种情况下,找出G的最短投递路线。当考虑到道路有上下坡以及有顺逆风时,上述模型就更接近于实际情况。上述问题也可以提成下述形式:构造一个有向图G_1=(V,A),这里顶点集合V与G中     

"求线性规划问题可行基的一种方法"的再注记

文[1]给出一个求线性规划问题可行基的方法，文[2]指出其判定条件（3）有误，然而所用的反例并不正确。本文给出三个正确的反例；此外，还给出反例表明文[1]的判定条件（2）也不正确的。     

再探一类矩形面积最大值问题的初等解法

<美国数学月刊>2004年1月问题11057[1]为: 设x,y,z为实数,矩形ABCD内部有一点P,满足PA=x,PB=y,PC=z,求矩形面积的最大值. 文[2]试图给出上述问题的解答,但解答有误.郭要红老师等在文[3]中指出了文[2]错误的原因,并给出了上述问题的一个微分解法.     

一类矩形面积最大值问题的初等解法

《美国数学月刊》2004年1月问题11057[1]为:设x,y,z为实数,矩形ABCD内部有一点P,满足PA=x,PB=y,PC=z,求矩形面积的最大值.文[2]试图给出上述问题的解答,但解答有误.郭要红老师等在文[3]中指出了文[2]错误的原因,并给出了上述问题的一个微分解法.文[3]在最后说明:“如何使用初等     

样条最佳插值结点的非线性规划算法

§1.问题的提出 [1]研究了二阶算子样条最佳插值结点的特征.对于少数几个函数,利用特征定理精确求出了其最佳插值结点.但是,如[1]中指出,对于绝大多数函数,要精确求出其最佳插值结点,是相当困难的.因此,设计相应的数值求解方法,对于实际应用是很有必要的.     

主轴箱坐标计算的逼近法

组合机床主轴箱坐标的计算是设计工作中必要而且十分重要的一环,关系到齿轮传动质量的优劣.实际设计工作中常遇到这样的问题:已知主轴箱两轴中心的坐标O(0,0),A(x_A,y_A)以及第三轴中心(未知轴)至该两轴中心的距离分别为b和a,求第三轴中心的坐标B(x,y)(图1).这类问题的计算是主轴箱传动树形图中最主要最复杂的一种.     

关于任意边界缺口或裂纹群问题的一类解法——(Ⅲ)边界裂纹群的计算*

本文是文献[1]、[2]关于任意边界缺口或裂纹群问题的一类解法研究的继续。这里我们利用和发展了文献[1]、[2]所提出的理论和计算公式,对边界裂纹群问题进行了实际计算.数值计算实例表明:本文所给出的方法在特征参数适当的范围内是行之有效的.本文的结果扩充了“应力强度因子手册”中的工作.     

新增结点下最小生成树研究

本文研究了对于给定结点及边的图,在可新增结点的情况下求最小生成树的问题.利用文献[3]的部分结果和LINGO软件编程计算等方法,获得了费尔马点的坐标表示及n结点图的最小生成树只需至多增加n-2个结点的结果.同时寻找到四结点图的最小生成树的一般解法及理论证明,推广了费尔马点对于平面的结论到三维空间中,有利于某些可建立树图模型的优化问题的求解.     

轮迴矩阵的逆矩阵

<正> 如何求轮回矩阵的逆矩阵?由于数理统计以及其他学科,如固态物理的需要,所以这 是一个为人们所关注的问题.1955年,D.Greenspan在文[1]中总结求逆矩阵的种种方法时,特意为轮回矩阵提出了一种求逆的方法,但只有结论而无证明.1962年,T.L.Gilbert在文[2]中用Jordan标准形理论,把轮回矩阵A化为对角形,然后再求出A的逆矩阵A~(-1),从而事实上给出了文[1]提出的计算方法的一种证明.文[1]的方法是用特     

分支数≤7时S^2NS有向图的禁用子图刻划

实方阵A称为强符号非异阵（S~2NS阵）,若任一与A符号模式相同的矩阵非异且其逆的符号模式也一致。若一个有向图是某一S~2NS阵对应赋号有向图的基础有向图,称为S~2NS有向图。本文用禁用子图形式给出了分支数≤7时有向图成为S~2NS有向图的刻划,同时部分地解决了[2]和[4]中提出的问题。     

并行列扫描Gram—Schmidt正交化方法

Gram-Schmidt正交化方法在求解线性代数方程组、最小二乘问题、代数特征值问题等很多矩阵计算问题中有着广泛的应用。因而,设计一种能在并行计算机上高效运行的GS正交化方法,必将对其他若干实际计算问题带来莫大的益处。张丽君教授在文献[2]和[3]中就方阵的正交三角分解问题作了详细的讨论。但实际情况中常遇到长方阵的正交化问题(如最小二乘问题)。本文提出一种适于并行计算的GS正交化方法,该方法采用了类似于求解三角形方程组的“列扫描”处理技巧。本算法特别适用于最小二乘等问题中常见的向量序列短而向量维数高(即后文的m(?)n)的情形,程序实现也很简单,尤其在备有内积功能部件的向量机上运行效率可达O(1)。     

灰色系统模型的优化岭回归算法

文献[1]指出了目前用普通最小二乘法估计灰微分方程参数的方法由于方程组的病态问题很难求解得合理的参数;文献[2]指出了根据初值求解灰色系统模型的时间响应式的方法由于初值的误差使所求得时间响应式产生系统误差.为了克服灰色模型的上述两个缺点,本文设计了一种求解灰色系统模型的优化岭回归算法,计算一个广泛引用的算例演示了这种算法的优越性.     

二阶椭圆问题的稳定化杂交有限元分析

0　引　　言Raviart&Thomas(1977)[13]基于Babǔska-Brezzi有限元理论[1][5]发展了二阶椭圆问题的基本杂交方法.该文指出,为确定合适的自由度,一般将杂交元刻划为非协调元.然而,对三角形偶数次杂交元和四边形杂交元而言,[13]是通过扩充手段克服有限维空间“匹配”问题的.由于扩充元的复杂性及其不再能刻划为非协调元,以致于实际计算无法选取自由度.Thomas的博士论文[15]提供了一个解决办法.即利用Gauss-Legendre数值求积分公式将扩充元近似刻划成非协调元,得到数值积分意义下的杂交方法.如此处理虽然大大简化了原杂交格式的求解过程,但数…