Cayley 定理的证明方法.doc

Cayley 定理的证明方法摘要：本文对Cayley 定理： 的生成树共有棵，即。的几种证明方法简单归纳。关键词：Cayley公式 标号树枝 生成树第一种证明方法通过确定标号树枝的个数来求生成树的个数，设生成树的数目为x个，因为每个生成树的每一个点都能作为一个根，所以标号树枝的个数为个，现在就是确定标号树枝的个数，这样一来就能确定。下面我们就来证明标号树枝的个数为。通过一步一步建立标号树枝，先拿出个点的无边土，此时这个图有个树枝森林，现在往上加边，加第一条边后，树枝森林数减少一个，当树枝数目为时，加下一条边新边的选择为，任意一个点都能当作，而必须连接不含的树枝的根，用这种方法构造标号树枝的数目应该为，因为每个标号树枝含有条边，有种顺序，也就是说每个标号树枝被构造了次，所以标号树枝的个数为。 证毕。第二种证明方法设， 是正整数，并且，则在顶点集上具有顶点度序列为的树的个数是多项式展开如下：特别地，令每一个，得到为了计算顶点集上的树的数目，必须将是正整数并且其和等于的具有顶点度序列的所有树的数目全部加在一起. 从前面的事实有顶点集上的树的数目(顶点集上的具有给定的度序列树的数目)于是Cayley公式得到证明.第三种证明方法构建概率模型在公理化体系,一般用三元总体表示一概率空间，为了证明Cayley定理,令=的生成树全体,=顶点的度为k的生成树全体,k=1,2,n-1.显然=（），且；记，令,k=1,2, ,n-1.其中表示集合中的元素个数.易知,上述定义下的成为一概率空间.若Cayley定理及Clarke定理成立, 则在上面定义的概率空间中, 分别成立下列等式: , , k=1,2, n-1.为求，建立如下概率模型.假设n 阶完全图的生成树按下述要求生成:向n阶完全图的n个顶点里随机地投(n-1)个点,每次投且仅投一点,共投(n-1)次.点落在每个顶点里的可能性是相等的.每投一次(即一次试验),点就落在某一顶点中,从这里就会且只会长出一条新边,且与原来的边不重复;如果点落入其他顶点中,则长出的新边总是向没有点落进的顶点方向生长,且不成圈.按上述方法,投(n-1)个点(即做n-1次试验)后,一定可以得到一个n阶完全图的生成树.定理证明下面,将在以上建立的概率模型中,用古典模型的方法求及。取定中的一个顶点，为了控制顶点的度数,考虑下列事件:记A=一次试验中点落入,B=第一次试验事件A发生,C=后面的(n-2)次试验中事件A共发生k次,=在第一次事件A发生的条件下,以后(n-2)次试验中事件A共发生k次,有（已知在事件B发生的附加条件下，求C事件发生的概率）由概率乘法公式,有由前面的模型假设,有:(1)在完全图的n个顶点中, 事件A发生的可能性是相等的,即:,(2)这(n-1)次试验是两两互不影响, 所以,事件B与事件C是相互独立的.即P(BC)=P(B)P(C).因此,成立以下等式:,k=0,1,2,n-2.根据模型假设,试验是随机的,等可能性的,即生成什么样的生成树的概率相同,从而,上面的与模型中所设的是一一对应的.即 k=0,1,2,n-2. k=1,2,n-1.所以, k=0,1,2,n-2.又由前面所设, 可知顶点的度为(n-1)的生成树的个数为1,即因此有,k= 0,1,2,n-1.从而成立。定理1(Cayley) 的生成树共有棵. 即定理2(Clarke) 的生成树中, 的度为k的生成树的个数为: k = 0,1,2, n-1.第四种证明方法L.E.Clarke给出了Cayley公式的不同的方法主要思想如下：令是的一个任意顶点，并令表示上的顶点具有度为的支撑树的数目，于是，问题变成证明. 令是的任意一棵支撑树，满足，易见在中被计数. 从中移走一条不与关联的任意一条边之后，剩下两个子树，其中一棵包含顶点，而另一棵包含顶点或（让我们说是），则另一棵包含顶点. 如果用一条边连接顶点和，得到一棵支撑树，其满足，显然在中被计数. 如果是通过上述方法从得到的，将称一对支撑树为一个连接，连接的总数等于.另一方面，令是的任意一棵支撑树，满足，并且令是从中通过移去顶点以及与关联的所有边而得到的子树；通过从中移去这些边（，其中属于）中的一条，并且连接顶点与任意一棵其他的子树的任意一个顶点，而得到一棵支撑树，其满足.于是，已证明，迭代这一结果，并且利用显而易见的事实，直接推导得到对所有可能的值求和，于是由以下导出的支撑树的数目为第五种证明方法1.完全关联矩阵：设图有顶点条边，令，则称由元素构成的一个矩阵称为图的完全关联矩阵。（）2.关联矩阵：在阶连通图的完全关联矩阵中，划去一行后，所得到的矩阵，称为图的关联矩阵。划去的行所对应的顶点称为参考点。（）3大行列式：矩阵的一个阶数为的方阵，称为矩阵的一个大子阵，大子阵定义的行列式称为大行列式。（）引理1毕内-柯西（Binet-Cauchy）定理 若P，Q分别是和矩阵，则乘积PQ的行列式是P和Q的所有对应的大行列式乘积之和，即 （1）这里的P和Q对应大行列式分别是由P的第和Q的行组成，即若取P的大行列式的列为，则Q的对应大行列式的行为行。举例设，P和Q对应的大行列式分别是，由毕内-柯西定理，有引理2连通图G的关联矩阵的一个大子阵是非奇异的充要条件为与这个大子阵的列相应的边组成的一棵生成树。（）引理3 连通图D的全部生成树的数目是，其中A是D的关联矩阵2。证明 显然关联矩阵A满足毕内-柯西定理的条件，故由毕内-柯西定理，有 （2）因为当且仅当A的大子阵的列对应D的一棵生成树时，此大子阵才是非奇异的，且由于A是单位模矩阵，因此（2）可代成。定理 的生成树共有棵.证明，设是阶完全图的关联矩阵，乘积的元素当时， ，或者-1,视弧是否与顶点关联而定，所以等于与顶点关联的弧的数目，由于在完全图中，每一顶点上有条弧，因而当时，这时因为时，且只有一条弧与任意两个顶点关联，上此可以得到现在来求，设另外一个阶数为的方阵T，其元素定义如下 不难证明。矩阵乘积为，由此得到 ，且由于和，故得到 第六种证明方法根据等式 ，其中是小于的正整数.令是具有个编号顶点和条边的连通的简单图，是其中的不具有端点的图的数目. 根据定义，一个端点即是恰与一个其他的顶点邻接的顶点并且该其他的顶点不再是端点，如果该图是连通的并且具有至少两个顶点，根据筛选法发现 如果通过假定将上式限定在树上. 此时，因为每个非平凡的树至少有两个端点，所以，如果. 一般结果. 可以通过把中的用代替再用归纳法直接得证.第七种证明方法矩阵数定理 设是个价标定图是的邻接矩阵，是的度对角阵，记，则的支撑树的数目等于行列式的任一个阶主了式的值。引理 设是图的一条边（不考虑自环），以-和分别表示去掉和收缩所得到的图，则有下面给出矩阵树定理的证明。设图的顶点集为，不防设，对的边数用数学归纳法。若，显然，则结论成立。归纳假设时结论成立，设的边数,任给，这里，中第元的代数余子式记为，以下证明，若顶点是孤立点，因的每行元素之和为0，则。若顶点