
Accession Number : AD0640542
Title : THE EXISTENCE AND GENERATION OF A HAMILTON CIRCUIT IN A TREE GRAPH.
Corporate Author : ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB
Personal Author(s) : Kamae,Takahiko
Report Date : SEP 1966
Pagination or Media Count : 45
Abstract : The existence of a Hamilton circuit in a tree graph was first proved by R. L. Cummins in his Ph. D. thesis at the University of Illinois. However, the proof involves complicated procedures, and it is hard to apply it to the generation of all the trees in a given graph. The new proof, which is straightforward and concise, is given in this paper. This proof is constructive and applicable to the generation of all the trees in a given graph. A general procedure for obtaining a Hamilton circuit in a tree graph is shown. By applying this procedure, all the trees in a graph with 5 vertices and 8 edges are generated in an example. The procedure is of recursive nature and hence suitable for computation by a digital computer. (Author)
Descriptors : (*TOPOLOGY, *CIRCUITS), ELECTRICAL NETWORKS, GRAPHICS
Subject Categories : Electrical and Electronic Equipment
Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE