A congruence theorem for trees.
A congruence theorem for trees.
复制标题
DOI：
10.2140/pjm.1957.7.961
复制
发表时间：
1957-03
影响因子：
0.6
通讯作者：
P. Kelly
中科院分区：
文献类型：
--
作者：
P. Kelly
设A和JB分别为顶点集au α2，， an和bi， b2，••••，bn的两棵树。如果它们的顶点之间存在一对一的对应关系，从而保持顶点对之间的连接关系，那么这些树是同构的，或者是“相同类型”的（a ζ^B）。设c（at）表示A^的（n- 1）点子图，该子图是通过从A中删除at和at的所有连接（弧，段）得到的。这里的目的是为了证明n-阶子图之间在类型和类型频率上是否存在一一对应lmA和J5，也就是说，如果存在一个标记使得φ ^)^c φi), i = l, 2，•••，n，那么a ~ B。因此，自始至终假设，存在一个标记使得c(α4)^c(δ4), i = l, 2，•••，n9，其中n^Z。首先建立了主要定理的一些引理。设T表示某一类j阶图，其中2<Lj <^n，在a中作为子图出现a次，在b中作为子图出现β次，如果at是顶点为at的T型子图的个数，则：
Let A and JB be two trees with vertex sets au α2, , an and bi, b2, • ••, bn respectively. The trees are congurent, are isomorphic, or "are the same type", (Aζ^B), if there exists a one-to-one correspondence between their vertices which preserves the join-relationship between pairs of vertices. Let c(at) denote the (n-l)-point subgraph of A^obtained by deleting at and all joins (arcs, segments) at at from A. It is the purpose here to show that if there is a one-to-one correspondence in type, and frequency of type, between the sub-graphs of order n — lmA and J5, that is, if there exists a labeling such that φ ^ ) ^ cφi), i = l , 2, •••, n, then A ~ B. It is assumed throughout, therefore, that there is a labeling of the two trees A and B such that c(α4)^c(δ4), i = l , 2, •••, n9 where n^Z. Some lemmas to the main theorem are established first. Let T denote a certain type of graph of order j , where 2<Lj <^n, which occurs as a subgraph a times in A and β times in B. If at is the number of T-type subgraphs which have at as a vertex, then,