应用科学学报 ›› 1987, Vol. 5 ›› Issue (1): 79-84.

• 论文 • 上一篇    下一篇

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

刘家壮   

  1. 山东大学
  • 收稿日期:1984-01-25 修回日期:1985-01-26 出版日期:1987-03-31 发布日期:1987-03-31

GENERATING ALL NONISOMORPHIC ROOTED TREES AND ALL NONISOMORPHIC TREES

LLU JLAZHUANG   

  1. Shandong University
  • Received:1984-01-25 Revised:1985-01-26 Online:1987-03-31 Published:1987-03-31

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

Abstract: 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 in[1], and the computer time required is less than that of the algorithm in[2].