GENERATION OF DIRECTED TREES, 2-TREES AND PATHS WITHOUT DUPLICATION,
Abstract
The increasing number of applications of graph theory to the solution of problems in many fields make it desirable to have available complete knowledge of the properties of these graphs. Since many problems in electrical networks, switching circuits, and communication nets can be formulated in terms of directed graphs, it is appropriate to study their properties. In this paper, procedures are developed for generating the directed trees, 2-trees and paths of a directed graph. Unlike other methods for generating these subgraphs, the procedures developed here avoid generating duplicate elements thus they eliminate the necessity of repeated search to select a complete set of elements. Proofs are given to verify that all elements of the set of directed trees, 2-trees or paths are generated and that no duplicate elements occur. Examples are given to illustrate the procedures in detail. The procedures are amenable to digital computer application. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1965
- Accession Number
- AD0610149
Entities
People
- Archie Joseph Paul Jr.
Organizations
- University of Illinois Urbana–Champaign