應(yīng)用超圖理論實現(xiàn)有向基本割集矩陣
REALIZATION OF DIRECTED FUNDAMENTAL CUTSET MATRIX BY HYPERGRAPH THEORY
-
摘要: 本文應(yīng)用超圖理論提出了從有向基本割集矩陣Qf的樹路子陣Qfp逐層判斷其可實現(xiàn)性和綜合出其對應(yīng)有向圖(G)的算法RFCMHGT。它的原理直觀,計算復(fù)雜度為O(nl2),n和l為Qfp的行和列數(shù)。例2表明,Tutte條件不是Qf可實現(xiàn)的充分條件。
-
關(guān)鍵詞:
- 網(wǎng)絡(luò)拓撲綜合; 超圖; 有向圖
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]黃汝激,超網(wǎng)絡(luò)的有向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]陳樹柏,左塏,張良震,網(wǎng)絡(luò)圖論及其應(yīng)用,第九章,科學出版社,北京,1982年. -
計量
- 文章訪問數(shù): 2246
- HTML全文瀏覽量: 128
- PDF下載量: 538
- 被引次數(shù): 0
下載:
