几类亚随意匹配图

David P.Sumner 在[1]中首次引进了随意匹配图的概念,并且证明了,随意匹配图有且仅有 k_(m,n)和 k_(2n)(n≥1);尔后,孟吉翔同志在[2]中引入了亚随意匹配图的概念。在文[2]、[3]中提出了几类亚随意匹配图。本文在此基础上又得到了几类更广泛的亚随意匹配图。从而,文[2]、[3]的几个主要定理都成为本文的特殊情形。本文中所论及的图都是指有限简单连通图,未说明的术语或记号均与[4]同。     

几类亚随意匹配图

本文在文献[2]至[5]的基础上构造了几类更广泛的亚随意匹配图.文中未说明的术语见[1].定义1 设 G 是在 n+1(n≥0)阶星图中的每个悬挂点 u_i 上构造一个 G_i 所得到的图,其中G_i 是由有唯一公共点 u_i 的 s_i 个偶数     

几类图簇匹配多项式的因式分解定理及其应用

通过研究几类图簇的匹配多项式的因式分解,给出了证明图的非匹配唯一性的一种新方法,并得到了这几类图簇的匹配等价图的结构性质.     

亚直既约环及其决定的上根

本文讨论几类亚直既约环的性质,定理1、2分别讨论SzA'sz在[1]中提出的公开问题42.44。定理3、4讨论幂零心的亚直既约环及其决定的上根的性质。I△R表示,是环R的理想,I△·R表示I是R的本质理想,关于本质理想、环类的本质复盖和本质闭的概念     

几类非匹配型分配格

给出了具有完美匹配的平面二部图的交不可约内环的概念及其等价刻画,利用这一概念和Kuratowski定理,证明了几类特殊有限偏序集的滤子格是非匹配型的.     

关于方程(/(t)-r)~LU=□U+f(z,t)Cauchy问题的解析解

近年来陈银通等在[1]、[2]中引入所谓无穷阶方阵B∞×∞的概念,利用幂级数法得出了几类高阶偏微分方程Cauchy问题解析解的表达式。但所用方法较烦杂,且[2]中结果也不太简洁。     

几类图完美匹配的数目

图的完美匹配的计数问题是匹配理论研究中的一个重要课题,此问题与统计晶体物理中的dimmer问题有关.一般图的完美匹配计数问题是NP-难的.本文给出了几类图的完美匹配数的显式表达式.作为应用,计算出了一些图的Hamilton圈的数目.     

连通图中水晶覆盖数的一些结果

通过对简单图中水晶覆盖数的研究，给出了几类图的水晶覆盖数，部分解决了文献[2]中提出的一个开放问题，得到了连通图的水晶覆盖数的紧的界。     

树图的最大匹配的一个简易算法

0 前言 目前一般简单图的最大匹配的算法主要是1965年Edmonds提出的逐次调整的方法[1]。对于较特殊的双图,其最大匹配的算法主要是匈牙利方法[2]和网络最大流算法[3]。Edmonds算法和匈牙利方法的本质是一致的,都是对图中未饱和点生长一个M—交错树,逐步扩大匹配,最终达到求出最大匹配的目的;而双图的最大匹配的网络最大流算法也具有类似的性质,即逐步调整流量来达到求最大匹配的目的。这些方法均不可避免地要对已经计算过的点(或线)在不同程度上重新进行计算,即便当图是树图时也是如此。这样当图的点数相当大时,其计算量是很大的。本文根据[4]提出的理论和结论,给出了树图的最大匹配的一种简易算法。该算法设有重复计算,从而在计算量上比上述诸方法大大降低。由该算法还能同时给出树图邻接矩阵的秩和行列式的值。     

具有完美匹配图的一个新特征

0 引言 [1]中指出,一个图G什么时候有一个完美匹配?这个比较困难的问题在1947年为加拿大著名图论学者托特(Tutte)所解决。托特所给出的具有完美匹配的图的特征是用G的奇支来描述的。G的一个奇支,是指图G的一个支中有奇数个点。G中奇支的数目记作oc(G)。于是,一个图G有一个完美匹配当且仅当对任何S(G),有oc(G-S)≤|S|。本文利用文[2]提出的“等秩变换”,     

结合图的导出匹配可扩性

简单图G和H的结合图G[H]的顶点集为V(G)×V(H),其中(u,v)和(u′,v′)相邻的充分必要条件是:或者uu′∈E(G)或者u＝u′并且vv′∈E(H).研究了结合图G[H]的导出匹配可扩性,证明了若G和H是非平凡图,G是连通图,且G和H满足下列条件之一,则G[H]是导出匹配可扩的:(1) G和H中有一个是导出匹配可扩的;(2) G和H都有完美匹配;(3) G和H中一个有完美匹配,另一个有几乎完美匹配.     

关于非线性对偶规划的存在性定理

§1 Rockafellar在[1]中应用共轭函数、摄动函数等概念,建立了数学规划对偶理论中更新、更一般的结果。但这些结果主要表述了原规划与对偶规划最优解之间的联系。近年来有些文献,如[2]进一步研究了对偶规划之间可行解的联系,由这条线索,本文引入了无穷下降方向、y不减函数等概念,得到了与[2]不同的对偶规划可行解之间的另外一些关系。然后由此推出了几类重要的对偶规划的最优解存在性定理。本文仅简述结果,详文将另文发表。下面给出本文用到的符号和定义。设非线性规划问题(P):     

Cn×P2的2-偶匹配可扩性

称图G的匹配M是偶匹配,如果M中的边关联的点集在G中的导出子图是偶图,即G[V（M）]是偶图称图G是偶匹配可扩的,如果G的每一个偶匹配M都包含在G的一个完美匹配中为了进一步地研究图的偶匹配可扩性,我们考虑图G的偶匹配数,即图G中最大偶匹配所含的边数,记为BM（G）,我们证明了Cn×P2是2-偶匹配可扩的。     

关于一类图的自同态谱的研究

对一个图而言,有各种不同的自同态。德国数学家Knauer于1990年在文献[1]中首次提出了自同态谱和自同态型的概念,目的是通过图的各种不同的自同态来研究图的代数结构。文献[2]运用自同态型对树进行了刻画,而文献[3]对直径为3围长为6的2-部图作了讨论,并得到了这类图的自同态型。本文将给出奇圈及其补图的自同态谱和自同态型。     

专家系统中的近似匹配和近似推理

专家系统中的知识的不确定性推动了近似推理的研究。而实施近似推理的前提是完成近似匹配。由此,本文首先讨论专家系统中有关不确定性的问题,继而通过引入λ—匹配和ε—匹配的概念探完了专家系统中的近似匹配及基于近似匹配的近似推理的策略和方法。从而修改和完善了文献[1,3,4]的部分结果。     

模的平坦根

本文引进模的干坦根概念，讨论了其性质，并对几类特殊环上模的亚干坦性进行研究．     

关于亚直不可约环为体的一个条件

G·Birkhoff 对交换的亚直不可约环得出了“无非零幂零元的亚直不可约环为域”的重要结论[1].傅昶林把[1]、[2]的一些结果推广到某些非交换环上[3],郭元春在[4]中又发展了[3]的一个结果,得到了“设 R 为无非零幂零元的亚直不可约环,其心为 H,若 R 的含于 H 的左理想具降链条件,则 R 为一体”.的结论.本文研究了具左π-正则性质的亚直不可约环,得到的结果是:定理.设 R 为亚直不可约环,若 R 的心 H 不含非零幂零元,且 H 中每一元素是左π—正则的,则 R 为体.     

一种三边Switch-box的布线问题及其图论算法

本文将一种VLSI中的三边Swithc-box的布线转化为图论中的求偶图的最大非交叉匹配问题,并在文献[1]思想的基础上提出了一个求偶图的最大非交叉匹配的有效算法。该算法已在IBM PC/XT上用FORTRAN77实现。最后给了算法用于三边Switch-box布线的实例。     

k连通［s,t］图的Hamiltion连通性

若图G的任意个s顶点的导出子图至少有t条边,则称图G为[s,t]图．[s,t]图的概念可视为图的独立数概念的推广．本文证明：若图G是k连通[k＋1,2]（k≥2）图,则G或者是Hamilton连通的或者同构于Kk∨Gk．由此可以推出,若图G的阶是n（n≥3）,α（G）≤κ（G）－1,则G是Hamilton连通的．     

几类特殊图完美匹配数目的递推求法

匹配计数理论是图论的核心内容之一,此理论有很强的物理学和化学背景.但是,一般图的完美匹配计数问题却是NP-难问题.用划分、求和、嵌套递推的方法给出了几类图完美匹配数目的显式表达式.