关于无穷—临界图1-因子的一个定理

Francois Bry 在[1]中提出如下问题:一个局部有限的无穷二临界图似乎有无穷多个1-因子.他还指出若能证明这条性质将是很有用的.本文给出关于无穷一临界图1-因子的一个定理.作为定理的推论,我们给出 FrancoisBry 问题的肯定回答.     

关于4—正则图的Berge猜想

我们用G=(V,E)表示简单4—正则图,v(G),ε(G)分别表示G的顶点数及棱数,即λ_(G)表示G的圈棱连通度(Cyclic edge Connectivity),λ_(G)=Min{|E′||E′E,G—E′仅由两个均含有回的连通分支构成}。若满足上述条件的E′不存在,则规定λ_(G)=ε(G)。本文中未加说明的其他记号及术语均见[1]。     

关于无向图最小树算法与最小树唯一性的若干注记

若对无向图G=(V,E)的每一条边e,赋以一个非负实数l(e),称为e的权。G连同它边上的权称为非负赋权图。T称为非负赋权图G的最小树,若T是G的支撑树而且各边权之和为最小。本文研究的均是无向、简单、连通、非负赋权图。没有特别指明的术语见[5]。最小树在交通、水利、聚类分析、计算机科学的许多实际问题中都有应用,已发展了若干行之有效的求法,如Kruskal算法、破圈法、Prim算法等。文[4]讨论了最小树唯一性问题。木文首先给出管梅谷的破圈法的一个新的简短证明并考虑如下问题:是否可以在求最小树的过程中判断出一个圈最小树是否唯一。对有些算法,问题的回答是可能的,有的算法则可部分地回答上面的问题。首先我们给出下述算法:     

两个算法的推广

人员分配问题是指n个工作人员可用来从事n项工作,每个人能胜任这些工作中的一种或多种,每种工作只需要一个人去做即可完成,能不能每人分给一种他所胜任的工作而每项工作都有人去做?这个问题已圆满解决,并有各种形式的推广和变化.实际当中一般往往是n个工作人员y_1,y_2,…,y_n从事m项工作x_1,x_2,…x_m,每个人能胜     

关于n-连通图的完美匹配与最大匹配

ξ1.引言本文所考虑的图均指无自环、无重边、无向有限的连通图,没有特别指明的术语见[1].以V(G)、E(G)分别表示图C的顶点集与边集. 设M是图G的一个支撑子图.若M的每个顶点的度是0或者1,则称M是G的一个匹配,若M是G的匹配中边数最多的一个,则称M是G的一个最大匹配;若M是G的匹配,且M中无0度顶点,则称M是G的一个完美匹配. 图G称为n连通的,若对G的任意两个不同的顶点x,y,G中存在n条以x,y为端点     

Prim算法与图的最小树唯一性

本文通过Prim算法给出弱异长图有唯一最小树的一个充分条件。关于图的最小树唯一性的研究见[1,2]。本文考虑的图均为无向、有限、连通、边非负赋权图。边赋权函数记为W。没特别指明的术语见[1,2]。 T是图G的一棵支撑树,如果T是G的所有支撑树中权最小的一棵树,则称T是G的最小树。     

局部有限无穷n-连通图1-因子的下界

Bry[1]证明;一个局部有限、有1-因子的无穷n-连通图至少有(n-1)1个1-因子。并且指出当n=2,此下界是严格的。本文证明;当n≥3时,任意一个局部有限的、有1-因子的、无穷n-连通图至少有n!个1-因子,而且这个下界是最好的。     

求一切完美匹配的一个算法

本文设计了一个求一切完美匹配的算法,它由下面的四个子算法组成:算法1 利用Edmonds.J算法,求一个完美匹配M(略)。算法2 利用类似深度搜索法的技术,求含M的某条边的一切M-交错回。算法3 求一切M-交错回。算法4 求一切完美匹配。     

关于海森堡和三对角矩阵的逆的两个定理

本文给出两个定理。首先我们给出一类海森堡矩阵的求逆公式,然后给出一个短阵的逆矩阵是三对角矩阵的充分必要条件。后者是W.Barrett的定理的推广。定义1 nxn矩阵R=(R_(ij))如果有R_(ij)=0.当2≤i+1相似文献