共查询到20条相似文献,搜索用时 187 毫秒
1.
提出了求线图之主划分的一个改进算法;引入了图之调和分解树的概念,进而提出了求一个网络图之全部调和分解与最优调和分解的方法。这些方法将有利于分裂法的应用。 相似文献
2.
通信网络的可靠性评估 总被引:13,自引:1,他引:12
通信网络的可靠性评估是一个难题。目前人们只对环型网和树型网进行可靠性分析。本文首先定义了通信网络的可靠性,依据图论提出了网络生成树的计算方法,以及网络可靠度的估算公式。最后给出了一个栅格型网的可靠度估算示例。 相似文献
3.
4.
本文提出了计算大型有向网络可靠度的一种新方法,它是以网络流理论为基础的分解算法。把大型网络按照本文给出的规则划分为若干子网络,再利用本文提出的收缩顶点概念和分解算法,可求出大型有向网络可靠度。 相似文献
5.
传统通信网络数据可靠度计算方法存在分组丢失率、封包投递率与标准数据相差较大的问题,为此,提出了基于机器视觉的通信网络数据可靠度计算方法.根据机器视觉通信原理构建了通信网络数据可靠度数学模型,评估通信网络数据的可靠度,评估过程中构建通信网络数据可靠度评估模型,采用了蒙特卡罗技术将评估模型和可靠度数学模型相结合,计算通信网... 相似文献
6.
7.
网络系统可靠度的BDD算法 总被引:4,自引:0,他引:4
文中研究3-状态设备网络系统2-终端可靠度的计算问题。BDD是布尔函数的图形表示形式。武小悦和沙基昌提出了一个采用BDD方法求2-状态网络系统的不交化最小路集,从而直接计算网络系统可靠度的算法。通过引入简化技术,结合归约公式和BDD技术,给出了一个计算3-状态设备网络2-终端可靠度的一个新算法;算法有效地消除了冗余项,并且产生的分枝树具有结点少,可有效得到可靠度符号表达式。 相似文献
8.
本文首先概要介绍了网络图论学科中生成树数的常用计算方法。为改进和简化Num(T)=detAA~T的数树公式,笔者提出了用求网图短路导纳矩阵行列式来获得总树数的途径,并用一些实例进行了验证。文末还给出了笔者根据被一些文献称之为最巧妙的算法之一的“Grecdy Alo-gorithm”,编写的搜索全部树的BASIC程序。 相似文献
9.
10.
本文讨论用K-树拓扑法生成网络的全符号灵敏度函数。该方法只涉及网络图中若干种K-树。由于求K-树已有成熟的算法,因此,本方法易于用计算机实现。本文的另一个结果是获得了求节点导纳矩阵任意一个二阶代数余子式的拓扑公式。 相似文献
11.
黄汝激 《电子科学学刊(英文版)》1990,7(4):296-305
First,the state space tree method for finding communication network overall re-liability is presented.It directly generates one disjoint tree multilevel polynomial of a networkgraph.Its advantages are smaller computational effort(its computing time complexity is O(en_l),where e is the number of edges and n_l is the number of leaves)and shorter resulting expression.Second,based on it an exact decomposition algorithm for finding communication network overallreliability is presented by applying the hypergraph theory.If we use it to carry out the m-timedecomposition of a network graph,the communication network scale which can be analyzed by acomputer can be extended to m-fold. 相似文献
12.
Available algorithms for measures of network reliability require computation time f(n) where f is at least exponential in n, the number of failure-prone elements in the system. Modularization is a familiar method of decomposing a network reliability problem into a set of subproblems. This decomposition reduces required computation time from f(n) to a sum of f(ni), ni < n, usually a considerable saving. For a 2-terminal communication network, the decomposition tree of a network provides the identity of the modules and an easily read map of the relations among them. The decomposition tree is derived by finding the triconnected components of the underlying graph. Reducing computation time by finding and analyzing the triconnected components of a network has been proposed for the reliability problems of 2-terminal communication, all-terminal communication, and feasible transportation flow. This paper introduces the use of the decomposition tree for reliability computation purposes, presents a general algorithm based on the tree, and demonstrates its application to the problems named above, as well as to the problem of feasible shortest path. 相似文献
13.
A related paper provides an algorithm to compute the reliability of an undirected network. The algorithm exploits the decomposition tree of the network derived from decomposing the network graph into its triconnected components. This paper extends the algorithm to apply to reliability problems involving directed networks. Details are presented which specialize the algorithm to apply to the problems of 2-terminal communication, transportation flow feasibility, and path-length feasibility. 相似文献
14.
15.
Improvement of the reliability of a communication network is an optimal problem that finds some links to add to the network such that the reliability of the network reaches a given level and the total cost of these links is minimized. A decomposition method based on branch and bound is used for solving the problem. In order to speed up the solution procedure, an upper bound on system reliability in terms of node degrees is applied. Specially, when the threshold Po is large enough, a new algorithm, the cut tree algorithm, can more effectively give the optimal solution. 相似文献
16.
In a probabilistic network, source-to-multiple-terminal reliability (SMT reliability) is the probability that a specified vertex can reach every other vertex. This paper derives a new topological formula for the SMT reliability of probabilistic networks. The formula generates only non-cancelling terms. The non-cancelling terms in the reliability expression correspond one-to-one with the acyclic t-subgraphs of the network. An acyclic t-subgraph is an acyclic graph in which every link is in at least one spanning rooted tree of the graph. The sign to be associated with each term is easily computed by counting the vertices and links in the corresponding subgraph. Overall reliability is the probability that every vertex can reach every other vertex in the network. For an undirected network, it is shown the SMT reliability is equal to the overall reliability. The formula is general and applies to networks containing directed or undirected links. Furthermore link failures in the network can be s-dependent. An algorithm is presented for generating all acyclic t-subgraphs and computing the reliability of the network. The reliability expression is obtained in symbolic factored form. 相似文献
17.
基于结构分割的自适应MPEG—I视频编码系统 总被引:1,自引:1,他引:0
本文介绍一种基于结构分割的自适应编码系统。图像组(GOP)中参考帧的数目以及它们间的间隔由可补偿性分析自适应地确定。时间视觉掩盖效应已利用于合理分配不同帧的码率。实验结果表明,这种自适应调整图像组结构的编码系统,无论视觉效果还是信噪比,都明显优于固定结构的编码系统。 相似文献
18.
In order to estimate the reliability performance of multicast communication under multiple constraint conditions, the weight of service rate and the reliability index are defined, accompanying the calculation method. Firstly, according to the Quality of Service requirements, the appropriate routings between the central node and target nodes that meet the requirements are calculated using the iterative method in the weighted internet. Then, the disjoint set of network state and the coefficients of weighted service rate are calculated by decomposition and merge methods. Lastly, the formula for calculating the service rate is obtained based on the disjoint set of network state and the calculation of the reliability index will be completed. The simulation result shows that the reliability of multicast communication can be appropriately reflected by the weight of service rate and the calculation method, which can provide the theoretical basis for the reliability evaluation of multicast communication. 相似文献
19.
Global reliability of a network is defined and then evaluated using spanning trees of the network graph. An algorithm for generating spanning trees (termed, appended spanning trees) that are mutually disjoint is proposed. Each appended spanning tree represents a probability term in the final global reliability expression. The algorithm gives the global reliability of a network directly. It is illustrated with an example. The algorithm is fast, requires very little memory, is adaptable to multiprocessors, and can be terminated at an appropriate stage for an approximate value of global reliability 相似文献
20.
The terminal-pair reliabilities, between the root and a leaf, of the two-center binary tree, the X-tree, and the ring-tree are computed; the beheaded binary tree is used as a benchmark. A building block is identified in the two-center binary tree from which a decomposition method is formulated. Another building block is identified for the X-tree and ring-tree from which a truss-transformation method is obtained. Computation has been carried out using algorithms based on the analysis. Although the ring-tree is the most reliable at all practical ranges of link and mode reliabilities, the X-tree and two-center binary tree are also good candidates because link reliability over 0.95 is quite common, and node reliability can be kept very high. The X-tree in particular is quite desirable due to its lower connectivity at each node and hence a lower implementation complexity. Three computational methods are presented. The simplicity of the two-center binary-tree algorithm blends with the hierarchical structure of the network itself because the states directly show that the level of computation can be summarized by some reliability subcomponents 相似文献