Cayley 公式
定理 2.9:
。
证:设
的顶点集是 。注意,取自 N 可能组成的长为
的序列的个数是
。于是为了证明本定理,只须在
的生成
树集和这种序列的集之间建立一一对应就行了。
对于
的每棵生成树 T,使它与唯一的序列
相联系:
把 N 看作是一个有序集,设
是 T 中第一个 1 度顶点;把与
相邻的
那个顶点取作
。现在从 T 中删去
,用
记
中第一个 1 度顶
点,并把与
相邻的那个顶点作为
。重复这个手续,直至
被确
定,留下来的恰好是有两个顶点的一棵树。(见图 2.8)
图 2.8 (4, 3, 5, 3, 4, 5)
逆过程同样易懂。首先注意 T 的任一顶点 v 在
中出
现
次。于是 T 中 1 度顶点恰好是在该序列中未出现的那些顶
点。为了从
中重新构作 T,可按下法进行。设
是
不在
中的 N 的第一个顶点;连接
与
。其 次 ,设
是
不在
中的
的第一个顶点,并且连接
与
。如此继
续下去,直到确定了 条边
。现在添加这样
的一条边,它连接
中剩下的两个顶点,即可得到 T。
容易验证,不同的序列产生
的不同生成树。这样就建立了所要的一
一对应。
注意:
不是
的非同构生成树的棵数,而是
的所有不同生成
树的棵数。
恰有六棵非同构的生成树(见图 2.1), 而
的不同生成树
评论0