例1，利用凯莱递推法求下图生成树的棵数。 共8棵生成树
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 例1，利用凯莱递推法求下图生成树的棵数。 共8棵生成树
凯莱公式的缺点之一是计算量很大，其次是不能具 体指出每棵生成树。 2、关联矩阵计数法 定义3：n×m矩阵的一个阶数为mim{n,m}的子方阵， 称为它的一个主子阵；主子阵的行列式称为主子行列式。 显然，当n<m时，nXm矩阵 个主子阵。 定理3设Am是连通图G的基本关联矩阵的主子阵，则 Am非奇异的充分必要条件是相应于Am的列的那些边构 成G的一棵生成树。 证明：略
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 凯莱公式的缺点之一是计算量很大，其次是不能具 体指出每棵生成树。 2、关联矩阵计数法 定义3 ：n×m矩阵的一个阶数为min｛n, m｝的子方阵， 称为它的一个主子阵；主子阵的行列式称为主子行列式。 显然，当n<m时，n×m矩阵 个主子阵。 n C m 定理3 设Am是连通图G的基本关联矩阵的主子阵，则 Am非奇异的充分必要条件是相应于Am的列的那些边构 成G的一棵生成树。 证明：略
该定理给出了求连通图G的所有生成树的方法： (1)写出G的关联矩阵，进一步写出基本关联矩阵， 记住参考点； (2)找出基本关联矩阵的非奇异主子阵，对每个这样 的主子阵，画出相应的生成树
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 该定理给出了求连通图G的所有生成树的方法： (1) 写出G的关联矩阵，进一步写出基本关联矩阵， 记住参考点； (2) 找出基本关联矩阵的非奇异主子阵，对每个这样 的主子阵，画出相应的生成树
(2)找出基本关联矩阵的非奇异主子阵，对每个这样 的主子阵，画出相应的生成树。 例2，画出下图G的所有不同的生成树。 G 解：取4为参考点，G的基本关联矩阵为： d 0 10
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 (2) 找出基本关联矩阵的非奇异主子阵，对每个这样 的主子阵，画出相应的生成树。 例2，画出下图G的所有不同的生成树。 1 2 3 4 a b c d e G 解：取4为参考点，G的基本关联矩阵为： 11000 01110 00011 Af abcde 1 2 3