1. Unified theory on the generation of trees of a graph.
- Author
-
Wai-Kai Chen
- Subjects
TREE graphs ,GRAPHIC methods ,ALGEBRA - Abstract
The efficiency with which a complex electrical network may be analyzed by a digital computer using topological formulas depends largely upon the efficiency with which the trees and directed trees of the corresponding graph are generated. The problem of efficient generation of trees of a graph has been treated rather extensively in the literature. In this paper it is shown that many of the existing techniques in the literature, seemingly so different in their appearance, are actually the variants of the Wang algebra formulation. Thus, they can all be unified. The unified theory enables one to summarize many of these results systematically and to provide a simple and easy way for their derivations.
In the paper we have shown that many of the existing results described in the literature on the problem of generation of trees of a graph, seemingly so different in their appearance, are actually variants of the Wang algebra formulation. Thus, it enables one to provide a unified theory for their derivation and to summarize most of these results systematically.
The main advantage of the Wang algebra formulation lies in the fact that once a desired set of sets, which can be obtained easily by inspection, is derived from a given graph all the remaining manipulations are algebraic. It is not necessary for one to go back to the original graph to see whether a generated term forms a tree (co-tree) or not. However, the techniques are not very efficient for large graphs because duplicated terms are generated during the process. Apart from slowing down the process of generating trees, this limits the sizes of the graphs that can be analyzed since one must retain the set of all trees in computer memory and check each new tree against the list for possible duplication.
The application of the Wang algebra technique to the generation of directed trees and multi-trees has been considered by Chen (1966). A special case of which is recently given by Shinoda (1968). [ABSTRACT FROM AUTHOR]- Published
- 1969
- Full Text
- View/download PDF