Hamiltonian[k,k+1]-因子

本文考虑n/2-临界图中Hamiltonian[k,k+1]-因子的存在性。Hamiltonian[k,k+1]-因子是指包含Hamiltonian圈的[k,k+1]-因子;给定阶数为n的简单图G,若δ(G)≥n/2而δ(G\e)相似文献   

关于连贯的计数问题

大家知道,两类元素连贯的理论在质量控制中、两种处理的效果比较中都得到了广泛的应用.利用连贯的理论,还可以发现微小的系统误差.在铁路运输、多种处理的效果比较等实际问题中,还遇到了多类元素的连贯问题.如利用多类元素连贯的理论,可以很好地解决过去中外文献中尚未见到的铁路运输中“组号和平均解体钩数”关系问题.所以,多类元素连贯理论的研究有其实际的和理论的意义.     

网络流在清理三角债问题中的应用

本文把清理三角债中两种优化数学模型问题，化成求解相应网络上最小费用流的问题，从而得到（强）多项式算法，并把另外的一种优化数学模型问题。化成线性规划问题.于是解答了文[3]中提出的清理三角债的三个基本问题．     

Applications of matroid partition to tree decomposition

1.IntroductionWeshallassumefamiliaritywithmatroidtheory--foranintroduction,andforthedefinitionoftermsnotdefinedinthispaper,see[31.Edmonds'matroidpartitiontheoremisaveryimportanttheorem,whichhasmanyapplications.Twoclassicresultsof[4,5],whichconcernwithpackingandcoveringoftheedgesetofagraphwithkedge--disjointspanningtrees,canbeeasilydeducedfromit(see[3],PP.125--127).Inthepresentpaperwewillpresentamatroidapproachtotheproblemoftreedecompositionraisedrecently(see[6,7]).Ourmainaimistogivealternati…     

两个逆网络选址问题的计算复杂性

本文考虑两个我们称之为逆网络选址的改进问题,它们是修改网络上各个边的长度,分别使得网络上某个给定的顶点到网络上所有点的最大距离以及该点到其它顶点的距离之和不大于预先给定的上界,并且所做的修改总量最小.我们将证明这两个逆网络选址问题都是强NP困难的.     

具有次限制的最小树问题

F.Glover和D.Klingman在[2]中给出了予先确定的一个点x具有固定次数为k的最小树算法。 本文给出了任意m个互不关联点具有次数限制的最小树问题的算法.算法的基础是线性规划的对偶理论。     

偶图中彼此不交的对集

本短文考虑偶图中k个彼此不交的对集存在的充要条件. 先引进几个术语和记号. 给定集合S及其子集族={A_1,A_2,…,A_n}.对于S的子集R如果存在一一对应:R→{1,2,…,n),使得对于每个r∈R,r∈A_((r)),则称R为的不同代表系.类似地,定义的部分不同代表系R’,如果R’是部分子集族的不同代表系.     

SOME RESULTS ON UNIVERSAL MINIMAL TOTAL DOMINATING FUNCTION

1. IntroductionLet G = (V, E) be an undirected graph. The open neighborhood N(v) of vertex v E Vis given by N(v) = {u E V: tv E E}. A total dominating function (TDF) of G is afunction f: V - [0, 11 such that Z f(u) 2 1 for each vertex v. A TDF f is minimaladN(~)(MTDF) if no function g < f is also a TDF of G. The illteger valued TDFs are preciselythe characteristic functions of total dominating sets of G (i.e., subset X G V such that anyv is adjacellt to at leajst one x E X). T…     

关于拟阵的最小限制基问题

关于求拟阵的最小基问题,众所周知,有很简明的算法(被称为Greedy Algorithm)。本文考虑求带剖分限制的最小基问题,同样也给出了较简单的有效算法,最后举例说明,许多组合问题都可以化成拟阵的最小限制基问题而求解。     

离散事件动态系统研究中图论方法的某些应用

因为许多离散生产过程都可以用离散事件系统描述，所以离散事件动态系统有很强的实用背景，例如柔性制造系统，因此，受到国内外的广泛注意和重视，进行深入研究，已获得一些很重要的理论结果．本文试图用图论的观点和方法，对离散事件动态系统的某些重要结果予以注释和新的证明，并探讨图论在该领域研究中的进一步应用．