支撑树端点数最大值的界

Schuster,蔡茂诚和林诒勋等研究了无向图支撑树端点数的内插性质。张福基和郭晓峰对有向图也得出了相应的结果。本文目的则是研究支撑树端点数最大值的上下界,显然,我们总可以假定研究的图和有向图无自环,无重边(弧),而且是连通的。以实际背景来看,在建立某个地区的通讯网络时,该系统的支撑树端点数最大的那棵树将给出一个中继点最少     

最小度限制下图的分解

一、背景和记号 本文所说的图均指有限,无向,无环和无多重边的简单图。 Gyy等人提出这样一个问题:对于给定的自然数对s,t,是否存在(最小的)自然数f(s,t),使得每个连通度至少是f(s,t)的图,其顶点集可以划分为两个集,这两个集的导出子图的连通度分别至少是s,t。为了解决这个问题,Thomassen提出一个相类比的问题:对于给定的自然数对s,t;是否存在(最小的)自然数g(s,t),使得每个最小度至少是g(s,t)的图,其顶点集可以划分为两个集,这两个集的导出子图的最小度分别至少是s和t。     

2连通正则无爪图中的Hamilton圈

本文讨论的图都是无向的简单图。图G称为无爪的,如果G没有同构于K_(1,3)的顶点导出子图。 关于2连通正则图的Hamilton性,1980年B.Jackson证明了:若G是2连通、k正则图,且G的顶点数不大于3k,则G是     

关于2树的1因子定理

Bineke等人研究了2树的特征。本文给出了一个2树有1因子的充分必要条件。有3个顶点的2树是一个三角形。当n≥3时,有n 1个顶点的2树T是从有n个顶点的2树T′增加一个新的顶点和一个含这个顶点的三角形     

线性目标函数下的greedy结构

1971年Edmonds在文献[1]中给出了在独立系统上greedy算法能使任何线性目标函数达到最优的充分必要条件:系统满足steinitz交换公理。众所周知,这样的系统称为拟阵。     

关于Benhocine、Clark等人的一个猜想

所讨论的图均指无向、有限的简单图。图G的生成闭迹或S-闭迹(S-circuit)是指一个闭迹使得它含有图G的所有的顶点。如果G中存在一条闭迹T使得G的每条边至少有一个顶点在T上,则称T是D-闭迹(Dominating circuit)。连通图G称为几乎无桥的如果它们的每一个桥至少关联一个次数为1     

粘贴DNA计算机模型(Ⅱ): 应用

经典的粘贴DNA计算模型采用单、双链混合型DNA分子编码, 其生物操作具有无需DNA链的延伸、无需生物酶以及DNA链可重复使用等优点, 已经受到不同学科学者的关注. 在经典模型的基础上, 进行一定的扩展与完善, 必对DNA计算机的研究有良好的贡献. 基于此, 对粘贴DNA计算机模型进行了较为深入的研究: (1) 提出了基于粘贴模型的矩阵表达模型; (2) 对经典粘贴模型应用于图与组合优化等方面的研究成果给予综述, 诸如集合覆盖问题、图的顶点覆盖问题、图的Hamilton路与圈问题、图的团与独立集问题、图的生成树与Steiner树问题等; (3) 给出了基于粘贴模型的图的同构问题的算法.     

Riemann流形上Hardy-Littlewood极大算子的有界性

在本文中,D表示有向强连通图,D(n,s)表示连通有向循环图。 设C是V(D)的真子集,若D-C不为强连通的或者为单一顶点,则称C为D的点截集。用B(D)记D中点截集的全体。     

Welsh猜想对简单的二元拟阵成立

§1。引言 Wclsh猜想按平均计算一个拟阵的圈的数目少于基的数目,而他还没有发现证明这个猜想的方法。至今关于这方面的结果很少。Quirk和Seymour证明了:若M是简单图的圈拟阵,则b(M)≥c(M),其中b(M),c(M)分别表示M的基与圈的数目。本文证明:若     

判断强连通自动机同构的一个多项式时间算法

众所周知,自动机的同构、图的同构等问题是多项式时间等价的(Booth,SIAM J.Comput,7(1978),3)。因此,讨论自动机的同构及其子问题是十分有意义的。最近,李慧陵给出了计算强连通自动机的自同构群的一个多项式时间算法。本文借助于此结果,在固定字母表的情况下,给出了判断两个强连通自动机是否同构的一个多项式时间算法。     

图的生成环及线图的Hamilton性

所讨论的图都是无向的、有限的简单图。图G的一个生成环(S-circuit)指的是一条通过图G所有顶点的闭迹。一个连通图称为几乎无桥图,如果G的任一桥至少关联一个度为1的顶点。1977年,F.T.Boesch、C.Suffel和R.Tindell提出了有生成环图的     

字典序地生成根树和树

文献[1]中给出了有序根树的一种序列表示方法,从而字典序地生成所有具有n个顶点的不同构的有序根树。现在我们在此基础上再进一步给出根树和树的序列表示方法,从而字典序地生成所有具有n个顶点的不同构的根树和树。     

比较偶图能量的两个定理

以一定方式给某些图一个偏序是人们常常研究的课题。文献[1]研究了某些图依支撑树数排序,文献[2]研究了依匹配多少排序,文献[3]研究了树依能量排序。此类问题不仅在理论上且在实际上有价值。如对图能量的研究在化学上可比较异构物的稳定性。     

具有根式不可解特征多项式的最小图

文献[1]的末尾(p。266—267)提出9个关于图谱方面的问题。其中第7个问题为求一个图G,使得其特征多项式Pc(λ)=0根式不可解。 为方便起见,我们将具有根式不可解特征多项式的(无向简单)图叫作不可解的,否则便叫作该图是可解的,Goclsil证明了几乎所有树均是不可解的,但是若用他的方法构作出不可解树则需要有1.1×10~(27)个顶点。在文献[3]中我们找出两个10顶点不可解树,它们如图1所     

关于A.Ainouche和N.Christofides的一个猜想

一、引言 Ainouche和Christofides提出一个猜想:设a,b为2-连通图G=(V,E)的两个不相邻顶点,若,有,则G是Hamilton图当且仅当G+ab是Hamilton图。     

表示直向代数的Auslander-Reiten箭图中的Hammocks

Brenner引进了Hammock的概念并用以刻划有限表示型代数的Auslander-Reiten箭图。Ringel和Vossieck给出Hammock的公理化定义,并确定了Hammock与偏序集的表示之间的关系。用组合方法来研究代数表示理论,Hammock起了很好的作用,参见文献[1～3]。本文给出一类在表示直向代数的Auslander-Reiten箭图中自然出现的Hammock,推广了Scheuer的结果。 1 主要结果 本文总约定代数A是某个代数闭域k上基的连通的带单位元的有限维代数。特别地,本文总假定A是表示直向代数。     

Ramsey数r(3,14)和r(3,15)的新下界

Ramsey数r(p,q)是满足下述条件的最小正整数r:对任意的r个顶点的图G(本文中的图均指无向简单图),则G或有P个顶点的团(即完全子图k_p)或有q个顶点的独立集。Ramsey 1930年证明了Ramsey数的存在性,Ramsey理论的研究在近六十年中也取得了许多有意义的结果(参看文献[2]     

关于最小距离下限的一般定理

在纠错编码理论中,求给定线性分组码的最小距离是非常重要和非常困难的,这个问题至今没有解决。因此,许多研究者提出求最小距离下限的方法。本文给出求最小距离下限的一般定理。这定理包括并改进关于最小距离下限的许多定理。设任意域F上的矩阵A和B为:     

q树的色性

称为q树的图是递归定义的,最小的q树是q阶完全图K_q,一个n+1阶的q树是在n阶的q树上添上一个新点,并且添上邻接这个点与n阶的q树上任意选取的q个两两相邻的点的边而得到。     

3连通图中圈上的可去边

３连通图Ｇ中的边ｅ称为可去的,若Ｇ－ｅ是一个３连通图的剖分,讨论了３连通图中圈上可去边的分布,得到这些可去边数依赖于图中极大半轮数的下界,这些下界在某种意义上是不能改进的。