应用超图理论实现有向基本割集矩阵
REALIZATION OF DIRECTED FUNDAMENTAL CUTSET MATRIX BY HYPERGRAPH THEORY
-
摘要: 本文应用超图理论提出了从有向基本割集矩阵Qf的树路子阵Qfp逐层判断其可实现性和综合出其对应有向图(G)的算法RFCMHGT。它的原理直观,计算复杂度为O(nl2),n和l为Qfp的行和列数。例2表明,Tutte条件不是Qf可实现的充分条件。
-
关键词:
- 网络拓扑综合; 超图; 有向图
Abstract: By applying hypergraph theory, algorithm RFCMHGT is presented fordetermining the realizability of a given directed fundamental cutset matrix Qf and synthesizing its corresponding directed graph G layer by layer from its tree path submatrix Qfp. Its principle is intuitive and its computational complexity is O(nl2). where n and l are the numbers of rows and columns of Qfp. Example 2 shows that Tutte s condition is not the sufficient condition for Qf to be realizable. -
R.E Bixby, W.H. Cunningham, Mathematics oj Operations Rcscarch, 5(1980)3,321-356.[2]S.Fujishige, Journal of Computer and System Sciences, 21(1980)1,63-86.[3]W.Mayeda, IRE Trans, on CT, CT-10(1963)1,133-134.[4]В.Ф.Ротко,Эффективные Алгритмы Синтеза Графов с Заданным Множеством Фундамента-льных Разрезов или Циклов，Кибернет, (1986)1,39-45.[5]黄汝激,超网络的有向k超树分析法，电子科学学刊,9(1987)3,244-255.[6]A. V. Aho, et al., The Design and Analysis of Compurer Algorithms, Addison-Wesley. Publishing Company. (1976).[7]陈树柏,左垲,张良震,网络图论及其应用,第九章,科学出版社,北京,1982年. -
计量
- 文章访问数: 2193
- HTML全文浏览量: 110
- PDF下载量: 535
- 被引次数: 0
下载:
