反问题方法的一例

本文通过对求最短连线问题的Greedy算法的研究过程,试图说明数学方法论中反问题研究的一种思想方法。     

NPC问题及某些近似算法(续)

§5.近似算法的概念及其例子由于人们普遍认为NPC类里的问题不大可能有多项式的算法,因此人们试图寻找NP—完全问题的多项式近似算法。这是当前对NP—完全问题的一个重要研究方向。本节我们仅讨论一些组合最优化问题,故下面的一些概念都是对组合最优化问题提出来的。给定一个组合最优化问题D,用opl(I)表示D中例子I的最优值,如果存在一个常数k同一个多项式算法A,使得对任意I∈D,有 R_A(I)≤k则称A为解问题D的多项式近似算法,其中     

图论中的树(四)

6 最小权部分树设G=（V,E）是一个无向连通图,G中每一条线e∈E,有一个实数权w（e）,它可以表示该线的长度,费用或通过该线所需要的时间等。G的一个部分树的权,定义为该树中所有线的权之和。若部分树T的权记为W（T）     

拟阵的理论及其应用

本文介绍了拟阵的基本概念,简述了拟阵的主要性质,较详细地叙述了求拟阵最优基的greedy算法及求两个拟阵最优交的算法,并且通过一些例子说明拟阵在组合优化中的作用。     

Hamilton圈存在的一个充分条件

本文推广了范更华的一个结果(J.Coob.Theory(B),37(1984),221—227),得到如下的定理:令G=(V,E)是一个n(≥3)点的简单图,用d(u)表示点u的次。设     

NPC问题及某些近似算法

在计算机科学,运筹学,图论,电网络,数论以及其它的离散数学领域里,提出了一些很困难的问题。例如,布尔函数简化问题,排序问题,货郎问题,最小反馈问题,最小复盖问题,最长路问题以及图的色数问题等等。多年来,世界上许多科学工作者,为了得到这些问题解的有效算法,付出了巨大的努力,但收效却甚微。一直到七十年代初期,Cook和Karp提出了NP完全性理论后,对这些问题的‘攻击’才暂时告一段落,从而转向对它们的近似算法的研究。     

LONGEST CYCLES IN REGULAR 3—CONNECTED GRAPHS

It is proved that for k≥71,the circumference c(G)of a 3-connected k-regular graphG on n vertices is at least min{|G|,3k+5}.This result is essentially best possible.     

3—连通正则无爪图的Hamilton圈

证明了每一个3－连通k-正则无爪图G，当G的点数n≤5k-5时，G包含一个Hamilton圈。     

POE-g-MAH增韧改性PA6的力学性能

研究了接枝马来酸酐的乙烯-辛烯共聚物（POE-g-MAH）对增韧改性尼龙6（PA6）力学性能的影响结果表明：随着POE-g-MAH含量的增加,PA6的拉伸模量和强度及弯曲模量和强度均有所下降,但冲出强度和断裂仲长率均显著提高;增韧改性后PA6断面形貌明显成韧性断裂,且其熔体流动速率随POE-g-MAH含量增加而下降;当POE-g-MAH质量分数为25％时,增韧PA6的综合性能最佳,可用作PA柔性管材专用料。     

3—连通K—正则无爪图中的最长圈

证明了最多含5K个顶点的3-连通、K-正则的无爪图是Hamilton图。