cayley定理

例](Cayley定理)n个有标号的顶点的树的数目等于nn+2.生长点不是叶子,每个生长点是[1,n]中的任一元.有n种选择。两个顶点的树是唯一的。[例]给定一棵有标号的树,边上的标号表示摘去叶的顺序。(摘去一个叶子相应去掉一条边)逐个摘去标号最小的叶子，叶子的相邻顶点(不是叶子,是内点)形成一个序列，序列的长度为n-2,第一次摘掉②，③为②相邻的顶点，得到序列的第一个数3,以此类推，得到序列31551,长度为7－2=5,这是由树形成序列的过程。由序列形成树的过程：由序列31551得到一个新序列111233455567,生成的过程是首先将31551排序得到11355，因为序列31551的长度为5，得到按升序排序的序列1234567，序列的长度为5+2(即n+2)，然后将11355按照大小插入到序列1234567中，得到111233455567,然后将两个序列排在一起上述算法描述：给定序列b=(b1b2…bn-2),设a=(123…n-1n),将b的各位插入a,得a',对做操作。a'是2n-2个元的可重非减序列。操作是从a'中去掉最小无重元，设为a1,再从b和a'中各去掉一个b中的第一个元素，设为b1，则无序对(a1,b1)是一条边。重复这一操作，得n-2条边，最后a'中还剩一条边，共n-1条边，正好构成一个树。b中每去掉一个元，a'中去掉2个元。由算法知由树T得b=(b1b2…bn-2)，反之，由b可得T。即f:T→b是一一对应。由序列确定的长边过程是不会形成回路的。因任意长出的边(u,v)若属于某回路，此回路中必有一条最早生成的边，不妨就设为(u,v),必须使u,v都在长出的边中重复出现，但照算法u,v之一从下行消失，不妨设为u，从而不可能再生成与u有关的边了，故由得到的边必构成一个n个顶点的树。[证]由一棵n个顶点的树可得到一个长度为n－2的序列，且不同的树对应的序列不同*，因此|T|≤nn-2。*:对n用归纳法可证.反之，由一个长度为n－2的序列(每个元素为1~n的一个整数)，可得到一棵树，且不同的序列对应的树是不同的，因此nn-2≤|T|,|T|=nn-2