沿通路送流的两个新算法

本文证明对满足一定约束条件的一类无耗网络,应用沿通路送流法,可获得一个有效的求多商品流算法,其运算复杂度仅为 O[d_(pr,max)|E(P_((?),max))|(n k-1)],并且当流网络中各边容量及各源汇对间传输要求量均为整数的情况下,可获得整数流解.本文还将上述算法推广到有耗网络中多商品流的求解问题,提出并证明了平面有耗网中多商品流存在的充分条件,据此获得一个求有耗网络多商品流的多项式时间算法.     

失效树分析的一种算法

本文介绍相干失效树的一种确定性算法:比特变换——分类去冗算法。本算法程序如稍加改动,即可用于非相干失效树的计算。     

图论算法复杂性问题(一)

本文论述了图论算法复杂性的基本理论和分析方法。由它的表示式和阶的运算,可以分析一个具体问题的算法复杂性,进而明确某一具体算法的有效性。     

求完备图的全部树——一种简易算法及应用

本文从一个完备图中的全部树与某种特定序列之间存在一一对应的关系出发,导出了一种求取完备图G_k(k为任意的节点数)中全部树的简易算法。这种算法已编成了程序,并在计算机上执行通过。文中用实例来加以说明,最后给出了一种比文献[3],[6]更简单的方法,证明了基本互补划分的总数公式。     

论基本互补划分表的简易产生法——复盖有向树群法

本文给出了改进的基本互补划分的定义,研究了两类非基本互补划分的规律,并用复盖有向树群的观点加以阐明,提出了产生基本互补划分表的规则与两种方法——直观法与有向树群矩阵法,乎算与计算机计算的结果表明,这一方法适用于k为任意值的情况。     

求任意k值的基本互补划分—通用算法及计算机实现

本文从文献[8]中所建立的混合树的概念出发,进一步提出了混合外向树、始点分裂树的新概念,阐明了一种特定的序列与始点分裂树、混合外向树与基本互补划分之间的一一对应关系,基于这些关系,导出了一种通用算法,从而可方便与有效地产生k为任意值时的全部基本互朴划分,按这一算法所编制的程序已在计算机上成功地实现。     

对Chan—Mai增益公式的修正

本文首先给出Chan—Mai增益公式不成立的反例,然后提出一个修正的Chan—Mai增益公式及其证明,最后指出原公式及其证明中的错误。     

混合树与混合有向树—论ECP的图表示

本文应用混合树的观点阐述ECP(基本互补划分)的概念,给出了直观的几何意义,得到了ECP的充要条件,并统一了有关文献中关于ECP的不同定义。本文还建立了关于ECP总数目的一个递推关系,在此基础上给出了W.K.Chen猜想的一个较简捷的证明。     

城市公共交通车线网络优化模型

本文以文献[8、14]为代表的城市公共交通车线网络优化评价方法为基础,改进了原有的不足,提出一种新的方法,建立了相应的模型,并利用我国的三个城市的实际数据进行了分析,获得较好的结果。     

关于基本互补划分(ECP)研究的一些进展

本文总结了两年来有关基本互补划分这一课题的若干研究成果,阐述了下列几个方面的问题:对陈惠开所给的ECP定义的发展与对不同的定义实行统一化;产生全部ECP的专用算法、通用算法及有关的新概念:两种ECP总数公式的改进证明方法。最后,简要地叙述了ECP的应用和可进一步研究的课题。     

无向单触点开关网络的直接综合法

本文给出了从给定网络的关联矩阵A,通过解不定矩阵方程BA~T=0获得全部回路的直接方法,同时给出了直接综合无向网络的系统方法,用这些方法可以从给定的独立回路矩阵B(包含全部B_f)或独立割集矩阵Q(包含全部Q_f、Q_f),通过解不定矩阵方程或取环和运算,得到所有满足给定B或Q的完全关联矩阵A_α。用上逆方法直接综合了一个无向单触点开关网络,得到了两个解答A_α,一个与文献[1]用矩阵变换得到的结果相同,另一个解答也满足给定的网络函数。     

有向单触点开关网络的直接综合法

本文给出了直接综合有向网络的无向综合有向化法。该法是先将有向网络当作无向网络,由在{0,1}域上解无向不定矩阵方程得到所有无向完全关联矩阵A_α,再按给定的有向条件将无向A_α化为有向A_α。它能系统地得到满足给定独立矩阵B、Q或可化为B或Q的函数的全部有向网络,且简便可行。用该法直接综合了两个有向单触点开关网络,其中一个与文献[3]用变换序列法得到的结果相同。     

网络图论在可靠性计算中的应用

本文介绍运用网络图论解决系统可靠性计算中的一些问题。给出了SAT网络可靠性的简易快速计算公式及其简要的证明,并给出了端对网络的MTS或当网络是平面图时MCS的快速算法,取得了较好的效果。     

关于赋权欧拉图的均匀初级圈覆盖

本文给出赋权欧拉图无公共边均匀初级圈覆盖,M—均匀初级圈覆盖,最小均匀覆盖的概念,并给出求它们的相应算法.此文所给出的算法同样适用于有向欧拉图.     

最优算法中的最短路问题讨论

最短路问题是网络理论中应用最广泛的问题之一,在生产实际中得到广泛的应用,通过研究最短路径的一般算法——Dijkstra算法,并对其进行改进,突破以往算法的局限性,具有广泛的应用前景。     

大型交通网络OD矩阵推算方法研究

ＯＤ矩阵是进行交通规划及管理的基础数据．本文首先研究了推算ＯＤ矩阵所需基本信息的获取方法．详细评述了现有ＯＤ矩阵推算模型，针对极大熵模型对路段交通量完全置信的不足，提出了极大熵修正模型，使模型能考虑交通调查产生的误差及交通分配引起的误差，极大提高了推算结果的精度．此外，本文把推算模型求解的立足点从路段转移到路径，提出了适用于大型网络ＯＤ矩阵推算的路径迭代算法．最后，本文采用山东省公路网实测ＯＤ矩阵及路段流量数据，对推算模型进行了检验，并证实了推算模型的可靠性及可行性．     

最小费用流在水电站中的应用

最小费用流指的是人们在生产过程或生活中为达到某个目的而选择一个“最优路径”方案或一组“得力”措施而取得“最佳”效果这样一个宏观过程。而在水电站设计或生产过程中，总是力求用最小流量（最低成本）发出最大的电量。1建立图论模型式中，F-从源点S输入的指定流量。jS－与节点S有直接支路相连的节点集ji－与节点i有直接支路相连的节点集ji－与节点r有直接支路相连的节点集。1．1目标函数的建立：费用流问题所涉及的问题是产品从生产地经过各种可能路径流向用户。故可以用一连通的有向图表示。这时每个节点用一个字母作为标记，每一…     

用分割法产生有向图中的生成子图

本文首先提出了一种产生全排列的新方法,提出了产生不含指定s条边的有向生成子图的方法,最后提出并证明了子图组装公式。由此公式求1-因子的最大项数为:■这些算法已在PC-8001机上实现。