关于离散形式结点域定理证明的几点注记

本文指出了文[1]的主要定理(定理4与定理6)证明中的错误,并对其进行了修正,给出了正确的证明.     

图的最小填充的分解定理

在计算数学领域,稀疏矩阵的最小填充排序问题由于其重要的实际意义而受到重视。本文从图论的观点提出一种处理方法,即运用分解定理来处理一些特殊结构,从而导出一些特殊图的最小填充数。     

度约束最小生成树的快速算法

本文对带有顶点度约束的最小生成树问题，给出了一种快速近似算法，并在微机上予以实现，经大量试算，效果良好。     

最小度生成树的一种近似算法

最小度生成树问题是一个NP难问题.本文给出了求最小度生成树的一种近似算法,这种算法得到的生成树的度数比最优解至多大1.     

轮图和多轮图的生成树的计数

本文应用计算生成树个数的有向图方法、分块矩阵的行列式计算法以及常系数线性递归方程的解法 ,计算得到轮图和多轮图的生成树个数的表达式 (显式或递推式 )     

具有最小反对称分割指数的化学树

设图$G$,其中边集为$E(G)$,顶点集$V(G)$.反对称分割指数被定义为$ISDD(G)=\sum_{uv \in E(G)}\dfrac{d_ud_v}{d_u^2+d_v^2}$,其中$d_u$, $d_v$分别为顶点$u,v$的度.化学树就是顶点的度不超过4的树.在本文中,我们刻画出具有最小反对称分割指数的$n$阶化学树.     

最小最大后悔准则下新增设施选址策略研究

基于新增设施选址问题,考虑网络节点权重不确定性,以设施中最大负荷量最小为目标,提出最小最大后悔准则下的新增设施选址问题。在网络节点权重确定时,通过证明将网络图中无穷多个备选点离散为有限个设施候选点,设计了时间复杂度为O(mn²)的多项式算法;在节点权重为区间值时,通过分析最大后悔值对应的最坏情境权重结构,进而确定最大后悔值最小的选址,提出时间复杂度为O(2ⁿm²n³)的求解算法;最后给出数值算例。     

二部图生成树的新的计数公式(英文)

设G =(V ,U ,E)是一个连通的二部图 ,其中｜V｜=m ,｜U｜=n .令M (G)表示G的关联矩阵 ,Jk×s 表示元素全为 1的k ×s矩阵 ,R =M (G)M (G)′ , Jm n =Jm -Jm×n-Jn×m Jn,t(G)表示G中生成树的个数 .在本文中我们不用对G的边定向而获得了下面的主要结论 :t(G) =(m n) -2 det( Jm n R) .     

最小成本生成树对策上Shapley值的新刻画及其应用

2002年,Kar利用有效性、无交叉补贴性、群独立性和等处理性四个公理对最小成本生成树对策上的Shapley值进行了刻画。本文提出了“群有效性”这一公理,利用这一公理和“等处理性”两个公理,给出了最小成本生成树对策上Shapley值的一种新的公理化刻画。最后,运用最小成本生成树对策的Shapley值,对网络服务的费用分摊问题进行了分析。     

|x|在调整的第三类Chebyshev结点的有理逼近问题研究CSCD

1引言非光滑函数|x|在逼近论中起着非常重要的作用.Bernstein[1]在1913年,最先用n次代数多项式逼近|x|,得到确切的逼近阶为E(|x|)=O(1/n).Newman[2]在1964年发现R(|x|)远远优于其多项式的最佳逼近E(|x|).     

THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE

ＴＨＥＤＥＳＩＧＮＡＮＤＡＮＡＬＹＳＩＳＯＦＡＬＧＯＲＩＴＨＭＯＦＭＩＮＩＭＵＭＣＯＳＴＳＰＡＮＮＩＮＧＴＲＥＥ￥（徐绪松，刘大成，吴丽华）ＸｕＸｕｓｏｎｇ；ＬｉｕＤａｃｈｅｎｇ；ＷｕＬｉｈｕａ（ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔ，ＷｕｈａｎＵｎｉ...     

Minimum Global Height支撑树及相关问题

本文研究了两个组合优化问题:minimum g1obal height支撑树和minimum aveageheight支撑树问题.利用3SAT问题的时间复杂性,本文证明了这两个问题都是NP-hard的,并分别给出了一个算法,即（mgh）-算法和（mah）-算法.在非负网络中,这两个算法的时间复杂性都为O（n3）.利用第一个问题的复杂性,本文证明了minimum height支撑树问题也是NP-hard的,从而纠正了有关文献中的一个错误结论.     

有向网络中具有一个枢纽点的最小支撑树的计算方法

对有向网络中具有一个枢纽点的支撑树的问题和性质进行了研究,给出了在有向网络图中寻找以某一定点为枢纽点的最小支撑树的计算方法,并对算法的复杂性进行了讨论,最后将该算法应用于实际算例的计算．     

THE MINIMUM SPANNING TREE PROBLEM: Jarník's solution in historical and present context

This article discusses mutual relationships between solutions to some known problems. Firstly, the history of the well-known Minimum Spanning Tree Problem, including Jarník's approach to it, is briefly revisited. Secondly, the basic differences between the three classical solutions to the MST problem are discussed. Finally, algorithms solving several other graph problems, based of Jarník's approach to the solution of the MST problem, are discussed in conjunction with the properties of the Breadth-First-Search Tree and Depth-First-Search Tree.     

带区间数据的最小风险斯坦纳树问题

考虑了在带区间数据的不确定网络中, 最小风险和模型以及最小最大风险模型下的斯坦纳树问题. 它们推广了相应模型下的最短路问题和最小支撑树问题, 在网络设计中具有更加广泛的应用.我们分别给出了这两个模型下斯坦纳树问题的近似算法, 并对算法性能做了理论分析和证明. 结果显示我们的算法具有优良的常数逼近的性质, 能在多项式时间内算出令人满意的解.     

离散时间跳-扩散过程的期权定价

本文运用 Cox、Ross和 Rubinstein的方法 ,建立了股票价格离散时间的跳 -扩散模型 ,通过无套利理论推导出离散时间的欧式期权和美式期权定价公式     

刘金旺刘晓奇周飞跃

1 引言 本文中R是指一个UFD,κ是R的商域,R[x]是以x为未定元的R上的多项式环.R上的半无限线性递归序列(lrs)与无限线性递归序列(Lrs)统记为LRS.LRS在代数编码、密码学、信号处理中是重要的研究对象,序列的综合问题主要是求出序列α的次数最小的特征多项式.     

有向循环图的支撑树数

设k≥2,1≤a_1相似文献