COVERING TWO DIGRAPHS WITH ARBORESCENCES

Let G_1 and G_2 be finite digraphs,both with vertex set V.Suppose that each vertexv of V has nonnegative integers f(v) and g(v) with f(v)≤g(v),and each arc e of G_4 hasnonnegative integers a_i(e) and b_i(e) with a_i(e)≤b_i(e),i=1,2.In this paper we give anecessary and sufficient condition for the existence of k arborescences in G_4 covering each are(?) of G_i at least a_i(e) and at most b_i(e) times,i=1,2,and satisfying the condition that foreach v in Vf(v)≤r_1(v)=r_2(v)≤g(v)where r_4(v) denote the number of the arborescences in G_(?) rooted at v.     

网络流和拟阵理论的进展

网络流和拟阵理论是组合最优化的重要组成部分,有着十分广泛的应用,成为描述和解决许多理论和实际问题的有力工具,被誉为组合最优化的重要里程牌。近十年来,特别是最近几年里,人们继续深入地做了大量的研究工作,把网络流和拟阵结合起来考虑,建立起多种更加一般的理论模型,使许多彼此似乎孤立的精彩结果得到很好的统一。本文试图侧重于理论方面的工作做些简单综述。     

PACKING AND COVERING WITH ARBORESCENCES

The aim of this note is to exhibit some recent results on packing and covering witharborescences.     

竞赛图是K-圈图的充分条件

在[1] 、[2] 和[3] 里,研究了一个定向图是“泛圈”(pancyclic)的条件。最近朱永津等同志,讨论了一个竞赛图是强路联通的条件。本文将讨论一个竞赛图是 k-圈图的条件。一个定向图是称为 k-圈图,如果它的任何 k 个顶点{x_1,x_2,……,x_k},就有一个长度为 k 的简单回路,而这条回路恰由这 k 个顶点组成。一个无环的定向图,若它的任意两个顶点之间有一条且仅有一条孤,则称它为竞赛图,我们用 T(X,A)来表示它。     

图的路连通问题

如果图Ｇ的每对不同顶点ｕ和ｖ之间都有哈密顿路相连，则称Ｇ是哈密顿连通的；而如果对于所有满足条件以ｄ（ｕ，ｖ）≤ｑ≤ｎ－１的整数ｑ，ｕ和ｖ之间有长为ｑ路相连，则和Ｇ是泛连通的，其中以ｄ（ｕ，ｖ）是ｕ和ｖ间的距离，而ｎ是Ｇ的顶点数。本文证明了下述两个结果：（１）２ｋ＋１个顶点的ｋ正则简单图是哈密顿连通的，（２）ｋ连通国中任何两顶点之间存在ｋ－１条长度不同的路；进而如果Ｇ的顶点数小于２ｋ，则Ｇ是泛连通的。