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

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

失效树分析的一种算法

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

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

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

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

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

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

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

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

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

平面图中的多商品流

本文讨论了源汇对间添加一条边后所得的网络图为平面网络图的情况下,如何求有可行流存在的网络中的多商品流,提出了求解多商品流的多项式时间算法,其运算复杂度函数为O{(n k-1)nlnn[|E(Q_(1e,max))|-1]}。作为此算法的应用,讨论了运输网系统如何合理安排商品的流量及流向的问题。     

沿通路送流的两个新算法

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

一种计算广播型网络可靠度的新方法

介绍了初等有向树变换的概念，并基于初等有向树变换给出了一种计算广播型网络可靠度的新方法，该方法不需进行非独立事件和的概率计算或有向树的专门不交化处理，因而所需计算量较小。     

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

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

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

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

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

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

一种计算线图端对可靠性的精确方法

本文介绍了一种计算网络任意端对可靠性的精确方法。用此方法计算网络任意两端的最小路集仅需展开一个行列式;计算全部sdp项(互不相交乘积之和)的数学表达式简洁,计算方法简洁、直观。     

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

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

对“货郎担问题”的研究

“货郎担问题”是不少学者研究的世界难题之一。本文指出“货郎担问题”的描述及经典解法与实际应用上的差距,从而给出与实际应用相符合的“货郎担问题”：的研究义及其有效的算法,从而使该问题更具有重要的实用价值。     

求网络割集的分裂方法

提出一种新的求网络割集的方法——分裂法,这种方法的特征是:先将网络划分为两个(或多个)子网络,分别求出这些较小网络的割集;然后.利用其中的一部分——关联割,再求出原网络中的其余割集.文中给出了一个详细的算例.     

互感网络对偶方程的网络实现法

互感的对偶关系和对偶电路是很受关注的一个问题,它涉及到电网络中对偶网络的定义。本文列举了几位学者对电网络对偶性的论述,从中可看出,当对偶网络的定义有所扩展时,对偶理论在电网络中的应用就有新的进展。本文重点介绍列出含互感网络的网孔电压方程的对偶方程及实现网络的方法,最后讨论了互感参数的对偶关系。     

基于社会网络分析的共享密码监督方法研究

为了对密码共享进行监督和管理,基于社会网络分析(SNA:Social Network Analysis)方法,对网络用户密码共享行为的监督技术进行了研究,提出了一种寻找密码传播路径的方法.结合图论中有向图及路径的相关理论,对简化后的密码传播最短路径算法进行描述.该方法通过扫描电子邮箱库中系统管理员邮箱与所有外部电子邮箱之间的最短路径,找出密码共享可能的传播路径,以便对用户密码的共享行为进行监督.结果表明,该方法可对当前系统的密码安全状态进行评估,对密码共享行为所造成的保密信息泄露起到一定的预防作用.     

一种基于网络图的电路状态方程列写方法

提出一种应用图论建立电路状态方程的方法，通过具体例子进一步介绍了建立图并由图得到状态方程的步骤。与其它同类方法相比，该方法更直观简捷，且无限制条件，可应用于任何电路。可看出，动态分析对于复杂电路是一种有效的方法。