應用超圖理論實現(xiàn)有向基本割集矩陣
REALIZATION OF DIRECTED FUNDAMENTAL CUTSET MATRIX BY HYPERGRAPH THEORY
-
摘要: 本文應用超圖理論提出了從有向基本割集矩陣Qf的樹路子陣Qfp逐層判斷其可實現(xiàn)性和綜合出其對應有向圖(G)的算法RFCMHGT。它的原理直觀,計算復雜度為O(nl2),n和l為Qfp的行和列數(shù)。例2表明,Tutte條件不是Qf可實現(xiàn)的充分條件。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)絡的有向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)絡圖論及其應用,第九章,科學出版社,北京,1982年. -
計量
- 文章訪問數(shù): 2229
- HTML全文瀏覽量: 120
- PDF下載量: 535
- 被引次數(shù): 0
下載:
