生成所有不同构的根树和树

本文用顶点的路长序列表示一个根树和树,并根据具有n-1个顶点的树(或根树)的路长序列与具有n个顶点的树(或根树)的路长序列之间的简单关系,得到生成所有不同构的树(或根树)的路长序列的算法,从而生成所有不同构的树(或根树).

GENERATING ALL NONISOMORPHIC ROOTED TREES AND ALL NONISOMORPHIC TREES

In the present paper, the representative sequence of path lengths of a rooted tree and that of a tree is defined. It is found that between the treeg (resp. rooted trees) of order n-1 and that of order n, there exist simple relations between their sequences of path lengths. Making use of the relations, we obtain algorithms which generate the sequences of path lengths of all nonisomorphio rooted trees and all nonisomorphio trees. The storage required is less than that of the algorithm in1], and the computer time required is less than that of the algorithm in2].