关于Win猜想的部分结果

<正> 本文假定G=(V,E)是2n个点的简单图,我们用C[U]表示点集U的导出子图,用d(x)表示G中点x的次,d_H(x)表示G的子图H中点x的次.其余符号见[3]. 给定非负整数k,若图G中每一对不相邻的顶点u和ν,都有d(u)+d(ν)≥2n+k,则称G为Ore k-型图.S.Win给出下述猜想: 若G是Ore k-型图,则G有k+2个1-因子.其中k≤2n-4.     

Bondy定理的改进

设G是一个n阶k连通图(k     

ON CONNECTED FACTORS IN K_(1,3)-FREE GRAPHS

1.IntroductionWeconsiderfinitesimplegraphs,andfollowBondyandMurtyl'lforgeneralterminologyandnotation.LetG=(V(G),E(G))beagraphwithavertexsetV(G)andanedgesetE(G).ForavertexvEV(G),N(v,G)denotesthesetofneighborsofvinG,anddG(v)=IN(v,G)l.Foravertexsubset(resp.subgraph)HofG,G--HdenotesthesubgraphofGobtainedfromGbydeletingthevenicesinHtogetherwiththeedgesincidelltwiththem.IfAisanedgesubsetofGandHasubgraphofG,thenH AdenotesthesubgraphofGobtainedfromHbyaddingtheedgesinAtogetherwiththeven…     

关于Steiner最小树问题

在本刊第二卷第二期上,我们曾发表了黄光明的《最短网络》一文,对Steiner最小树问题在当时的发展情况作了一些介绍。最近由于他与堵丁柱共同解决了Gilbert和Pallak在1968年所提出的一个猜想,不少读者对于这一问题产生了兴趣。为此,我们组写了这篇文章,目的在于使读者对这一问题的历史和连带产生的问题以及目前的发展状况有一较确切的和较全面的了解。     

组合最优化问题的近似算法

<正> 1980年第1期《Mathematics of Operations Research》上,刊登了一篇美国数学家 V.Klee 的文章,题目是“Combinatorial Optimization:What is the state of the art.在这篇文章中,V.Klee 指出,组合最优化今后研究的重要方向之一,是研究它们的近似算法.这样一种看法的依据是什么呢?这要从计算复杂性的理论谈起.一、计算复杂性的基本概念虽然高速度计算机的出现和广泛使电,使过去许多无法计算的问题得到了解决,但是